WEP安全性能研究及其攻击

关键词：有线等效加密 密钥调度算法 伪随机数发生器

随着８０２．１１标准的制定以及相关软硬件技术的逐渐成熟，８０２．１１无线局域网产品的使用愈来愈广泛。其通信范围广、数据传输速率高的特点使８０２．１１同蓝牙等协议一起成为无线局域网组网的可选协议之一，广泛应用于办公、会议等场合。这些场合中所使用的ＰＣ卡绝大多数提供了一种称为ＷＥＰ（Ｗｉｒｅｄ Ｅｑｕｉｖａｌｅｎｔ Ｐｒｉｖａｃｙ）的加密协议。

ＷＥＰ便于管理，每块８０２．１１卡具有一个加密密钥（ｋｅｙ）。在实际使用中，大多数设备均使用同一个加密密钥，包括接入点ＡＰ（Ａｃｃｅｓｓ Ｐｏｉｎｔ）。８０２．１１通过ＷＥＰ来防止对局域网的非法访问，为用户提供与传统有线局域网保密程度相当的通信环境。

ＷＥＰ中采用的ＲＣ４算法是一种对称流加密算法。由于ＲＣ４算法的加密或解密速度均非常快，又提供了相当的强度，所以得到了广泛应用。其最重要的应用就是ＳＳＬ（Ｓｅｃｕｒｉｔｙ Ｓｏｃｋｅｔ Ｌａｙｅｒ）加密套接字协议层和ＷＥＰ。

针对ＲＣ４算法及其弱点，人们进行了许多研究，其中大多数为理论研究，并不具有实际意义。直到最近，Ｂｏｒｉｓｏｖ、Ｇｏｌｄｂｅｒｇ ａｎｄ Ｗａｇｎｅｒ指出?１?：在ＷＥＰ中，由于没有明确规定ＩＶ（Ｉｎｉｔｉａｌｉｚａｔｉｏｎ Ｖｅｃｔｏｒｓ）的使用方法，有些厂商简单地在每次初始化时将ＩＶ置零，然后加一。这种不当使用导致密钥重用的概率大增，可用于简单的密码分析攻击。另外，作者还指出，由于ＩＶ的可用空间太小，将不可避免地导致相同的密钥重用问题。

Ｆｌｕｈｒｅｒ、Ｍａｎｔｉｎ ａｎｄ Ｓｈａｍｉｒ 描述了一种针对ＷＥＰ采用的ＲＣ４算法的被动密文攻击方法?２?。作者针对ＲＣ４的状态初始化，提出了一种ＫＳＡ攻击方法。揭示了ＷＥＰ存在的严重漏洞。

本文在文献?２?提出的ＫＳＡ攻击方法的基础上，提出了一种更为高效的攻击方法。并在实际环境中，成功地实施了针对ＷＥＰ的攻击。实验结果表明，与文献?２?中提出的ＫＳＡ攻击相比，本文提出的方法具有效率高、所需数据量更小的优点。

１ ＲＣ４算法

１．１ ＲＣ４概述

ＲＣ４算法属于二进制异或同步流密码算法，其密钥长度可变，在ＷＥＰ中，密钥长度可选择１２８ｂｉｔ或６４ｂｉｔ。

ＲＣ４算法由伪随机数产生算法ＰＲＧＡ（Ｐｓｅｕｄｏ Ｒａｎｄｏｍ Ｇｅｎｅｒａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ）和密钥调度算法ＫＳＡ?Ｋｅｙ Ｓｃｈｅｄｕｌｅ Ａｌｇｏｒｉｔｈｍ?两部分构成。其中ＰＲＧＡ为ＲＣ４算法的核心，用于产生与明文相异或的伪随机数序列；ＫＳＡ算法的功能是将密钥映射为伪随机数发生器的初始化状态，完成ＲＣ４算法的初始化。

ＲＣ４算法实际上是一类以加密块大小为参数的算法。这里的参数ｎ为ＲＣ４算法的字长。在ＷＥＰ中，ｎ＝８。

ＲＣ４算法的内部状态包括２ｎ个字的状态表和两个大小为一个字的计数器。状态表，也称为状态盒（Ｓ－ｂｏｘ，以下用Ｓ表示），用来保存２ｎ个值的转置状态。两个计数器分别用ｉ和ｊ表示。

ＫＳＡ算法和ＰＲＧＡ算法可表示如下：

ＫＳＡ： ＰＲＧＡ：

Ｉｎｉｔｉａｌｉｚａｔｉｏｎ： Ｉｎｉｔｉａｌｉｚａｔｉｏｎ：

Ｆｏｒ ｉ＝０ ｔｏ ２ｎ－１ ｉ＝０，ｊ＝０

Ｓ[ｉ]＝ｉ Ｇｅｎｅｒａｔｉｏｎ Ｌｏｏｐ：

ｊ＝０ ｉ＝ｉ＋１

Ｓｃｒａｍｂｌｉｎｇ： ｊ＝ｊ＋Ｓ[ｉ]

Ｆｏｒ ｉ＝０ ｔｏ ２ｎ－１ Ｓｗａｐ（Ｓ[ｉ]，Ｓ[ｊ]）

ｊ＝ｊ＋Ｓ[ｉ]＋Ｋ[ｉ ｍｏｄ ｌ] Ｏｕｔｐｕｔ ｚ＝Ｓ[Ｓ[ｉ]＋Ｓ[ｊ]]

Ｓｗａｐ（Ｓ[ｉ]，Ｓ[ｊ]）

其中，ｌ为密钥的长度。

１．２ ＲＣ４算法安全性能分析

仔细研究ＲＣ４的算法流程，不难发现：

状态盒Ｓ从一个统一的２ｎ个字的转置开始，对其进行的唯一操作是交换。Ｓ始终保存２ｎ个字的某个转置状态，而且转置随着时间而更新。这也是ＲＣ４算法的强度所在。算法的内部状态存储在Ｍ＝ｎ２ｎ＋２ｎ比特中，由于Ｓ为一个转置，此状态大约保存了ｌｏｇ２（２ｎ！）＋２ｎ≈１７００ｂｉｔ的信息。

状态盒的初始化状态仅仅依赖于加密密钥Ｋ，因此，若已知加密密钥就可完全破解ＲＣ４。加密密钥完全且唯一确定了伪随机数序列，相同的密钥总是产生相同的序列。另外，ＲＣ４算法本身并不提供数据完整性校验功能，此功能的实现必须由其他方法实现（例如ＷＥＰ中的数据完整性校验向量，即ＩＣＶ）。

下面考虑一些特殊的攻击模型，这些模型均与要讨论的ＲＣ４的安全问题密切相关。

ＲＣ４算法属于同步流密码算法中的一种，由于其伪随机数发生器ＰＲＮＧ（Ｐｓｅｕｄｏ Ｒａｎｄｏｍ Ｎｕｍｂｅｒ Ｇｅｒｎｅｒａｔｏｒ）的输出完全由加密密钥确定，所以对于一个设计良好的流密码算法必须满足两个条件：输出的每个比特应该依赖于所有加密密钥的所有比特；而且，任意一个比特或者某些比特同加密密钥之间的关系应该极其复杂。

上述第一个条件意味着输出的每个比特依赖于加密密钥所有比特的值。密钥中任意比特值的改变均有１／２的几率影响到输出的每一个比特。如果满足此条件，那么，破解此加密需要尝试所有可能的密钥值，输出值同加密密钥之间几乎不存在任何联系。

如果上面的条件得不到满足，那么就可被利用来对其进行攻击。举例来说，假设输出的某８个比特仅仅依赖于加密密钥的某８个比特，那么就可以简单地进行对此８比特密钥的所有可能值进行尝试，并与实际输出相比较获取此８比特密钥的值，这样就大大降低了穷举攻击所需的计算量。

因此，如果输出以比较高的概率由密钥的某些比特所确定，那么此信息就可被利用来对此流密码进行攻击。

第二个条件意味着即使已知两个加密密钥之间的联系，也无法得出ＰＲＮＧ输出之间的联系。此信息也可用来降低穷举攻击的搜索空间，从而导致加密强度的降低。

ＲＣ４算法属于二进制异或流密码，相同的密钥总是产生相同的ＰＲＮＧ输出。为解决密钥重用的问题，ＷＥＰ中引入了初始化向量ＩＶ（Ｉｎｉｔｉａｌｉｚａｔｉｏｎ Ｖｅｃｔｏｒ）。初始化向量为一随机数，每次加密时随机产生。初始化向量以某种形式与原密钥相组合，作为此次加密的加密密钥。由于ＩＶ并不属于密钥的一部分，所以无须保密，多以明文传输。虽然初始化向量的使用很好地解决了密钥重用的问题，然而，Ｆｌｕｈｒｅｒ? Ｓ等人在文献?２?中指出：初始化向量的使用将导致严重的安全隐患。

下面详细地讨论本文所提出的ＫＳＡ攻击方法。

２ ＫＳＡ攻击

本文着重讨论ＷＥＰ中所采用的ＲＣ４算法，即前附加初始化向量ＩＶ的ＲＣ４算法。

２．１ ＫＳＡ

考虑ＫＳＡ，注意到唯一影响状态表的是交换操作。因此,状态表的每个元素至少交换一次(尽管有可能同它自己交换)。假设ｊ是一个均匀分布的随机数,那么,考虑状态表中某一个特殊元素,在所有初始化期间ｊ都不指向此元素的概率为:

Ｐ＝(２５５／２５６)∧２５５≈３７％

(指数为２５５是因为当ｉｎｄｅｘ２和ｃｏｕｎｔｅｒ相等时可以忽略)

这意味着有３７％的概率某一特定元素在初始化期间仅交换一次。

由此可看出:

给定一密钥长度Ｋ(ｂｙｔｅｓ),如果Ｅ＜Ｋ,那么元素Ｅ有３７％的概率仅在ｉ指向它时被交换。

那么由ＲＣ４的ＫＳＡ 算法可看出仅Ｋ[０]．．．．Ｋ[Ｅ－１],和Ｋ[Ｅ]影响它。这只是近似估算,因为ｉｎｄｅｘ２不可能是均匀分布。

为利用上述结果,需要确定状态表最可能的值。因为每个元素至少交换一次(当ｃｏｕｎｔｅｒ指向它时),所以有必要对交换可能带来的影响加以考虑。交换是令人讨厌的非线性操作,难于分析。然而当处理状态表前几个元素时,某个具体元素有很高的概率没有参与它前面的几次交换,因此还保留初始值(Ｓ[Ｘ]＝Ｘ)。

相似地，仅处理状态表中前几个元素时，即ｉ比较小时，Ｓ[ｊ]有很高的概率等于ｊ。因此，可以得到：

状态表中元素Ｓ[Ｅ]（Ｅ比较小时）最可能的值为：

注意，本文中两个元素操作均为模２５６操作。

基于以上分析，可以计算出状态表中各个元素满足Ｂ的概率。为统计状态表中元素满足上式的概率，采用８比特ＲＣ４算法进行实验。下面为１０００００次实验中Ｓ[Ｅ]中前４８个元素满足上式的概率：

Ｐｒｏｂａｂｉｌｉｔｙ ?％?

０～７ ３７．０ ３６．８ ３６．２ ３５．８ ３４．９ ３４．０ ３３．０ ３２．２

８～１５ ３０．９ ２９．８ ２８．５ ２７．５ ２６．０ ２４．５ ２２．９ ２１．６

１６～２３ ２０．３ １８．９ １７．３ １６．１ １４．７ １３．５ １２．４ １１．２

２４～３１ １０．１ ９．０ ８．２ ７．４ ６．４ ５．７ ５．１ ４．４

３２～３９ ３．９ ３．５ ３．０ ２．６ ２．３ ２．０ １．７ １．４

４０～４７ １．３ １．２ １．０ ０．９ ０．８ ０．７ ０．６ ０．６

结果表明，经过ＫＳＡ后，状态表中前面的一些元素实际值与用Ｂ所预测出的值强相关。

２．２ 弱密钥

首先定义ｉｔ，ｊｔ分别为ＫＳＡ算法经过ｔ步后相应的两个计数器的值，Ｓｔ为ＫＳＡ经ｔ步后状态盒的状态。从其流程可以看出，ＰＲＮＧ首字节输出仅仅依赖于状态盒Ｓ中的三个值：Ｓ[１]、Ｓ[Ｓ[１]]和Ｓ[Ｓ[１]＋Ｓ[Ｓ[１]]]。如果此三个值为已知，那么就可以完全确定ＰＲＮＧ的首字节输出。

ＫＳＡ经过ｉ步操作后(ｉ＞１),设Ｓｉ[１]＝Ｘ，Ｓ[Ｘ]＝Ｙ，假设ｊ为均匀分布的随机数，那么Ｓ[１]，Ｓ[Ｘ]，Ｓ[Ｘ＋Ｙ]均不参与剩余交换的概率约为ｅ－３≈０．０５，此时ＲＣ４的首字节输出为Ｓ[Ｘ＋Ｙ]。

假设ＩＶ的长度为Ｉ个字节，ＩＶ附加在密钥Ｋｅｙ前面组成加密密钥Ｋ，即Ｋ＝ＩＶ｜Ｋｅｙ，且我们已知Ｋ中前Ｂ个字节的值（初始化时Ｂ＝０）。如果ＫＳＡ经过Ｉ＋Ｂ－１次迭代后满足：

ＳＩ＋Ｂ－１[１]＜Ｉ

ＳＩ＋Ｂ－１[１]＋ＳＩ＋Ｂ－１ [ＳＩ＋Ｂ－１[１]]＝Ｉ＋Ｂ

考虑第Ｉ＋Ｂ次迭代：

ｉＩ＋Ｂ＝Ｉ＋Ｂ

ｊＩ＋Ｂ＝ｊＩ＋Ｂ－１＋Ｓ[Ｉ＋Ｂ]＋Ｋ[（Ｉ＋Ｂ） ｍｏｄ Ｌ]

交换ＳＩ＋Ｂ－１[ｉＩ＋Ｂ]，ＳＩ＋Ｂ－１ [ｊＩ＋Ｂ]：

ＳＩ＋Ｂ [ｉＩ＋Ｂ]＝ＳＩ＋Ｂ－１ [ｊＩ＋Ｂ] ，

ＳＩ＋Ｂ [ｊＩ＋Ｂ]＝ＳＩ＋Ｂ－１ [ｉＩ＋Ｂ]

在满足上述条件的情况下，Ｓ[１]，Ｓ[Ｓ[１]]和Ｓ[Ｓ[１]＋Ｓ[Ｓ[１]]]这三个元素以很高的概率（大于５％）均不参与ＫＳＡ剩余的交换操作，也即首字节输出以很高的概率满足：

Ｏｕｔ＝ＳＩ＋Ｂ－１[ｊＩ＋Ｂ]＝ＳＩ＋Ｂ－１[ｊＩ＋Ｂ－１＋Ｋ[Ｂ]＋ＳＩ＋Ｂ－１[Ｉ＋Ｂ]]

这种情况下，通过重建ＫＳＡ，能够成功地从首字节输出中获取加密密钥中某个特定字节Ｋ[Ｉ＋Ｂ]的信息：

Ｋ[Ｂ]＝Ｓ[Ｏｕｔ]－ｊＩ＋Ｂ－１－ＳＩ＋Ｂ－１[Ｉ＋Ｂ]]

Ｓ[Ｏｕｔ]表示元素Ｏｕｔ在状态表中的位置。

从前面分析可以看出，在满足ＳＩ[１]＜Ｉ＋Ｂ?且ＳＩ[１]＋ＳＩ[ＳＩ[１]]＝Ｉ＋Ｂ条件的情况下，可以准确重建Ｋ[Ｂ]的概率大于５％，远远大于１／２５６。这样通过收集足够数量的满足上述条件的数据包，就可以成功地重建密钥Ｋ[Ｂ]。同理，在成功重建Ｋ[Ｂ]的基础上，就可以用类似的方法重建所有密钥。

具体算法如下：

ＲｅｃｏｖｅｒＷｅｐＫｅｙ(ＣｕｒｒｅｎｔＫｅｙＧｕｅｓｓ,ＫｅｙＢｙｔｅ)

Ｃｏｕｎｔｓ[０．．．２５５]＝０

Ｆｏｒ ｅａｃｈ ｐａｃｋｅｔ－＞Ｐ

Ｉｆ Ｒｅｓｏｌｖｅｄt(Ｐ．ＩＶ）

Ｃｏｕｎｔｓ[ＳｉｍｕｌａｔｅＲｅｓｏｌｖｅｄ(Ｐ,ＣｕｒｒｅｎｔＫｅｙＧｕｅｓｓ)]＋＝１

Ｆｏｒ ｅａｃｈ ＳｅｌｅｃｔＭａｘｉｍａｌＩｎｄｅｘｅｓＷｉｔｈＢｉａｓ(Ｃｏｕｎｔｓ)－＞ＢｙｔｅＧｕｅｓｓ

ＣｕｒｒｅｎｔＫｅｙＧｕｅｓｓ[ＫｅｙＢｙｔｅ]＝ＢｙｔｅＧｕｅｓｓ

Ｉｆ Ｅｑｕａｌt(ＫｅｙＢｙｔｅ,ＫｅｙＬｅｎｇｔｈ)

Ｉｆ ＣｈｅｃｋＣｈｅｃｋｓｕｍｓ(ＣｕｒｒｅｎｔＫｅｙＧｕｅｓｓ)

Ｒｅｔｕｒｎ ＣｕｒｒｅｎｔＫｅｙＧｕｅｓｓ

Ｅｌｓｅ

Ｋｅｙ＝ＲｅｃｏｖｅｒＷＥＰＫｅｙ(ＣｕｒｒｅｎｔＫｅｙＧｕｅｓｓ,ＫｅｙＢｙｔｅ＋１)

Ｉｆ ｎｏｔＥｑｕａｌt(Ｋｅｙ,Ｆａｉｌｕｒｅ)

Ｒｅｔｕｒｎ Ｋｅｙ

Ｒｅｔｕｒｎ Ｆａｉｌｕｒｅ

２．３ 算法改进

可以看出，以上的攻击方法中，所有关于Ｋ[Ｉ＋Ｂ]的预测均是基于其前面所有密钥（Ｋ[０]，．．．，Ｋ[Ｉ＋Ｂ－１]）已知的基础上。换言之，前面的预测错误将直接导致Ｋ[Ｉ＋Ｂ]的错误预测。那么能否从Ｋ[Ｉ＋Ｂ]中推测出Ｋ[０]，．．．，Ｋ[Ｉ＋Ｂ－１]的信息？

考虑ＫＳＡ，如果经过Ｉ次迭代后，满足：

Ｉ＜ＳＩ[１]＋ＳＩ[ＳＩ[１]]＝Ｉ＋Ｂ≤Ｌ

ＳＩ[１]≤Ｉ

则ＳＩ[１]和ＳＩ[ＳＩ[１]]以很大的概率（（２５４／２５６）Ｌ－Ｉ≈１）不参与第Ｉ步与第Ｌ步之间的迭代。同时，ｊ以很大的概率不指向ＳＩ[Ｉ]，．．．，ＳＩ[Ｉ＋Ｂ]这几个元素。

即：

ＳＩ[１]＝ＳＩ＋Ｂ－１[１] ｉＬ－１＝Ｌ－１

ｊＩ＋Ｂ－１＝ｊＩ＋ＳＩ[Ｉ]＋．．．＋ＳＩ[Ｉ＋Ｂ－１]＋Ｋ[Ｉ]＋．．．＋Ｋ[Ｉ＋Ｂ－１]

考虑第Ｌ步：

ｉＩ＋Ｂ＝Ｉ＋Ｂ ｊＩ＋Ｂ＝ｊＩ＋Ｂ－１＋ＳＩ[Ｉ＋Ｂ]＋Ｋ[Ｉ＋Ｂ]

交换Ｓ[ｉ]，Ｓ[ｊ]，则ＳＩ＋Ｂ[Ｉ＋Ｂ]＝ＳＩ＋Ｂ－１[ｊＩ＋Ｂ]。

如果ＳＩ＋Ｂ－１[ｊＩ＋Ｂ]，ＳＩ＋Ｂ－１[１]和ＳＩ＋Ｂ－１[ＳＩ＋Ｂ－１[１]]不参与剩余的交换操作，那么输出为：

Ｏｕｔ＝ＳＩ＋Ｂ－１[ｊＩ＋Ｂ]

而由前面的分析可以看出，ＳＩ＋Ｂ－１[ｊＩ＋Ｂ]以很高的概率（约为１）没有参与前面的交换操作，也即ＳＩ＋Ｂ－１[ｊＩ＋Ｂ]＝ｊＩ＋Ｂ。由此可知

Ｏｕｔ＝ｊＩ＋ＳＩ[Ｉ]＋．．．＋ＳＩ[Ｉ＋Ｂ－１]＋Ｋ[Ｉ]＋．．．＋Ｋ[Ｉ＋Ｂ－１]＋ＳＩ[Ｉ＋Ｂ]＋Ｋ[Ｉ＋Ｂ]

利用上述关系可以成功地推出不同Ｋ字节之间的关系，从而加速攻击。

另外，由于密钥管理时密钥需要手工输入，所以绝大多数情况下，密钥只是ＡＳＩＩＣ字符。这样大大减小了密钥的搜索空间，提高了攻击效率。

３ 实验结果与结论

为对上述算法进行验证，进行了实验。实验中所采用的硬件为朗讯的ＯＲｉＮＯＣＯ无线网卡，操作系统为Ｒｅｄｈａｔ７．１。实验结果表明，本文所提出的算法平均在收集１００万到２００万加密数据包的情况下，成功地恢复出了原加密密钥。与Ｆｌｕｈｒｅｒ?Ｓ．、Ｍａｎｔｉｎ?Ｉ．、 Ｓｈａｍｉｒ? Ａ．所提出的ＫＳＡ攻击需要４００万到６００万数据包相比，攻击效率有了很大提高。

基于以上分析，不难看出：现有ＷＥＰ加密中存在重大的安全漏洞，这种情况并不因加密密钥长度的增加而得到改善，所以在ＷＥＰ２中同样存在。为此，建议现有的８０２．１１用户：

．假设８０２．１１链路层并不提供安全措施；

．为保障网络通信的安全，使用ＩＰＳＥＣ或者ＳＳＨ等高层加密手段；

．把所有通过８０２．１１接入的用户置于防火墙之外。

．经常更换密钥，同时针对密钥应尽量采用某种ＨＡＳＨ算法，避免采用全为ＡＳＩＩＣ字符的加密密钥。