摘  要: 以Fluhrer， S.， Mantin， I.， Shamir， A.提出的KSA(Key Schedule Algorithm)攻击为基础,提出了一种改进的KSA攻击方法。与Fluhrer等提出的KSA攻击相比,新方法具有更高攻击效率。利用这种方法,成功地实现了针对802.11网络链路层" title="链路层">链路层安全协议——WEP的攻击,成功地恢复出了原加密密钥。本文详细地描述了这种攻击,同时针对802.11网络存在的安全问题,提出了一些安全建议。

　　关键词: 有线等效加密  密钥调度算法  伪随机数" title="随机数">随机数发生器

　　随着802.11标准的制定以及相关软硬件技术的逐渐成熟,802.11无线局域网产品的使用愈来愈广泛。其通信范围广、数据传输速率高的特点使802.11同蓝牙等协议一起成为无线局域网组网的可选协议之一,广泛应用于办公、会议等场合。这些场合中所使用的PC卡绝大多数提供了一种称为WEP(Wired Equivalent Privacy)的加密协议。

　　WEP便于管理,每块802.11卡具有一个加密密钥(key)。在实际使用中,大多数设备均使用同一个加密密钥,包括接入点AP(Access Point)。802.11通过WEP来防止对局域网的非法访问,为用户提供与传统有线局域网保密程度相当的通信环境。

WEP中采用的RC4算法是一种对称流加密算法。由于RC4算法的加密或解密速度均非常快,又提供了相当的强度,所以得到了广泛应用。其最重要的应用就是SSL(Security Socket Layer)加密套接字协议层和WEP。

　　针对RC4算法及其弱点,人们进行了许多研究,其中大多数为理论研究,并不具有实际意义。直到最近,Borisov、Goldberg and Wagner指出^[1]:在WEP中,由于没有明确规定IV(Initialization Vectors)的使用方法,有些厂商简单地在每次初始化时将IV置零,然后加一。这种不当使用导致密钥重用的概率大增,可用于简单的密码分析攻击。另外,作者还指出,由于IV的可用空间太小,将不可避免地导致相同的密钥重用问题。

　　Fluhrer、Mantin and Shamir 描述了一种针对WEP采用的RC4算法的被动密文攻击方法^[2]。作者针对RC4的状态初始化,提出了一种KSA攻击方法。揭示了WEP存在的严重漏洞。

　　本文在文献[2]提出的KSA攻击方法的基础上,提出了一种更为高效的攻击方法。并在实际环境中,成功地实施了针对WEP的攻击。实验结果表明,与文献[2]中提出的KSA攻击相比,本文提出的方法具有效率高、所需数据量更小的优点。

1 RC4算法

1.1 RC4概述

　　RC4算法属于二进制异或同步流密码算法" title="密码算法">密码算法,其密钥长度可变,在WEP中,密钥长度可选择128bit或64bit。

　　RC4算法由伪随机数产生算法PRGA(Pseudo Random Generation Algorithm)和密钥调度算法KSA(Key Schedule Algorithm)两部分构成。其中PRGA为RC4算法的核心,用于产生与明文相异或的伪随机数序列；KSA算法的功能是将密钥映射为伪随机数发生器的初始化状态,完成RC4算法的初始化。

　　RC4算法实际上是一类以加密块大小为参数的算法。这里的参数n为RC4算法的字长。在WEP中,n=8。

RC4算法的内部状态包括2ⁿ个字的状态表和两个大小为一个字的计数器。状态表,也称为状态盒(S-box,以下用S表示),用来保存2ⁿ个值的转置状态。两个计数器分别用i和j表示。

　　KSA算法和PRGA算法可表示如下:

　　KSA:                                  PRGA:

       Initialization:                    　Initialization:

              For i=0 to 2n-1               　　i=0,j=0

                 S[i]=i          　　　　 　Generation Loop:

              j=0                           　  i=i+1

　　Scrambling:                               　j=j+S[i]

              For  i=0 to 2n-1            　　　Swap(S[i],S[j])

              j=j+S[i]+K[i mod l]   　　　　　　Output z=S[S[i]+S[j]]

              Swap(S[i],S[j])

　　其中,l为密钥的长度。

1.2 RC4算法安全性能分析

　　仔细研究RC4的算法流程,不难发现:

　　状态盒S从一个统一的2ⁿ个字的转置开始,对其进行的唯一操作是交换。S始终保存2ⁿ个字的某个转置状态,而且转置随着时间而更新。这也是RC4算法的强度所在。算法的内部状态存储在M=n2ⁿ+2ⁿ比特中,由于S为一个转置,此状态大约保存了log₂(2ⁿ!)+2n≈1700bit的信息。

　　状态盒的初始化状态仅仅依赖于加密密钥K,因此,若已知加密密钥就可完全破解RC4。加密密钥完全且唯一确定了伪随机数序列,相同的密钥总是产生相同的序列。另外,RC4算法本身并不提供数据完整性校验功能,此功能的实现必须由其他方法实现(例如WEP中的数据完整性校验向量,即ICV)。

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

　　RC4算法属于同步流密码算法中的一种,由于其伪随机数发生器PRNG(Pseudo Random Number Gernerator)的输出完全由加密密钥确定,所以对于一个设计良好的流密码算法必须满足两个条件:输出的每个比特应该依赖于所有加密密钥的所有比特；而且,任意一个比特或者某些比特同加密密钥之间的关系应该极其复杂。

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

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

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

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

　　RC4算法属于二进制异或流密码,相同的密钥总是产生相同的PRNG输出。为解决密钥重用的问题,WEP中引入了初始化向量IV(Initialization Vector)。初始化向量为一随机数,每次加密时随机产生。初始化向量以某种形式与原密钥相组合,作为此次加密的加密密钥。由于IV并不属于密钥的一部分,所以无须保密,多以明文传输。虽然初始化向量的使用很好地解决了密钥重用的问题,然而,Fluhrer， S等人在文献[2]中指出:初始化向量的使用将导致严重的安全隐患。

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

2 KSA攻击

　　本文着重讨论WEP中所采用的RC4算法,即前附加初始化向量IV的RC4算法。

2.1 KSA

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

　　P=(255/256)∧255≈37%

　　(指数为255是因为当index2和counter相等时可以忽略)

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

　　由此可看出：

　　给定一密钥长度K(bytes)，如果E

　　那么由RC4的KSA 算法可看出仅K[0]....K[E-1]，和K[E]影响它。这只是近似估算，因为index2不可能是均匀分布。

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

相似地,仅处理状态表中前几个元素时,即i比较小时,S[j]有很高的概率等于j。因此,可以得到:

　　状态表中元素S[E](E比较小时)最可能的值为:

　　注意,本文中两个元素操作均为模256操作。

　　基于以上分析,可以计算出状态表中各个元素满足B的概率。为统计状态表中元素满足上式的概率,采用8比特RC4算法进行实验。下面为100000次实验中S[E]中前48个元素满足上式的概率:

    结果表明,经过KSA后,状态表中前面的一些元素实际值与用B所预测出的值强相关。

2.2 弱密钥

　　首先定义i_t,j_t分别为KSA算法经过t步后相应的两个计数器的值,S_t为KSA经t步后状态盒的状态。从其流程可以看出,PRNG首字节输出仅仅依赖于状态盒S中的三个值:S[1]、S[S[1]]和S[S[1]+S[S[1]]]。如果此三个值为已知,那么就可以完全确定PRNG的首字节输出。

　　KSA经过i步操作后(i>1)，设S_i[1]=X,S[X]=Y,假设j为均匀分布的随机数,那么S[1],S[X],S[X+Y]均不参与剩余交换的概率约为e-3≈0.05,此时RC4的首字节输出为S[X+Y]。　

　　假设IV的长度为I个字节,IV附加在密钥Key前面组成加密密钥K,即K=IV|Key,且我们已知K中前B个字节的值(初始化时B=0)。如果KSA经过I+B-1次迭代后满足:

　　S_I+B-1[1]

　　S_I+B-1[1]+S_I+B-1 [S_I+B-1[1]]=I+B

　　考虑第I+B次迭代:

       i_I+B=I+B

       j_I+B=j_I+B-1+S[I+B]+K[(I+B) mod L]

       交换SI+B-1[iI+B],SI+B-1 [jI+B]:

　　S_I+B [i_I+B]=S_I+B-1 [j_I+B] ,

　　S_I+B [j_I+B]=S_I+B-1 [i_I+B]

　　S_I+B [i_I+B]=S_I+B-1 [j_I+B] ,

　　S_I+B [j_I+B]=S_I+B-1 [i_I+B]

　　在满足上述条件的情况下,S[1],S[S[1]]和S[S[1]+S[S[1]]]这三个元素以很高的概率(大于5%)均不参与KSA剩余的交换操作,也即首字节输出以很高的概率满足:

　　这种情况下,通过重建KSA,能够成功地从首字节输出中获取加密密钥中某个特定字节K[I+B]的信息:

　　表示元素Out在状态表中的位置。

　　从前面分析可以看出,在满足S_I[1]I[1]+S_I[S_I[1]]=I+B条件的情况下,可以准确重建K[B]的概率大于5%,远远大于1/256。这样通过收集足够数量的满足上述条件的数据包,就可以成功地重建密钥K[B]。同理,在成功重建K[B]的基础上,就可以用类似的方法重建所有密钥。

　　具体算法如下:

2.3 算法改进

　　可以看出,以上的攻击方法中,所有关于K[I+B]的预测均是基于其前面所有密钥(K[0],...,K[I+B-1])已知的基础上。换言之,前面的预测错误将直接导致K[I+B]的错误预测。那么能否从K[I+B]中推测出K[0],...,K[I+B-1]的信息?

考虑KSA,如果经过I次迭代后,满足:

       II[1]+S_I[S_I[1]]=I+B≤L

       S_I[1]≤I

　　则S_I[1]和S_I[S_I[1]]以很大的概率((254/256)L-I≈1)不参与第I步与第L步之间的迭代。同时,j以很大的概率不指向S_I[I],...,S_I[I+B]这几个元素。

　　即:

　　S_I[1]=S_I+B-1[1]                  i_L-1=L-1       

　　j_I+B-1=j_I+S_I[I]+...+S_I[I+B-1]+K[I]+...+K[I+B-1]

　　考虑第L步:

　　i_I+B=I+B        j_I+B=j_I+B-1+S_I[I+B]+K[I+B]

　　交换S[i],S[j],则SI+B[I+B]=SI+B-1[jI+B]。

　　如果S_I+B-1[j_I+B],S_I+B-1[1]和S_I+B-1[S_I+B-1[1]]不参与剩余的交换操作,那么输出为:

　　Out=S_I+B-1[j_I+B]

　　而由前面的分析可以看出,S_I+B-1[j_I+B]以很高的概率(约为1)没有参与前面的交换操作,也即S_I+B-1[j_I+B]=j_I+B。由此可知

　　Out=j_I+S_I[I]+...+S_I[I+B-1]+K[I]+...+K[I+B-1]+S_I[I+B]+K[I+B]

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

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

3 实验结果与结论

　　为对上述算法进行验证,进行了实验。实验中所采用的硬件为朗讯的ORiNOCO无线网卡,操作系统为Redhat7.1。实验结果表明,本文所提出的算法平均在收集100万到200万加密数据包的情况下,成功地恢复出了原加密密钥。与Fluhrer，S.、Mantin，I.、 Shamir， A.所提出的KSA攻击需要400万到600万数据包相比,攻击效率有了很大提高。

　　基于以上分析,不难看出:现有WEP加密中存在重大的安全漏洞,这种情况并不因加密密钥长度的增加而得到改善,所以在WEP2中同样存在。为此,建议现有的802.11用户:

　　.假设802.11链路层并不提供安全措施；

　　.为保障网络通信的安全,使用IPSEC或者SSH等高层加密手段；

　　.把所有通过802.11接入的用户置于防火墙之外。

　　.经常更换密钥,同时针对密钥应尽量采用某种HASH算法,避免采用全为ASIIC字符的加密密钥。

参考文献

1 BORISOV， N.， GOLDBERG， I.， and WAGNER， D. Intercepting mobile communications：The insecurity of 802.11.

MOBICOM, 2001 (2001)

2 FLUHRER， S.， MANTIN， I.， and SHAMIR， A. Weaknesses in the key scheduling algorithm of RC4. Eighth

Annual Workshop on Selected Areas in Cryptography， August 2001

3 LAN/MAN Standard Comitee. Wireless LAN medium access

control (MAC) and KSA physical layer (PHY) specification 1999 edition. IEEE standard 802.11， IEEE or Computer Society， 1999

4 SCHNEIER， B. Applied Cryptography-Protocols， Algorithms.and Source Code in C. John Wiley & Sons，Inc.，1994

5 Scott R. Fluhrer and David A. McGrew， Statistical analysis of the alleged RC4  keystream generator， FSE：Fast Software Encryption， FSE＇2000， Springer-Verlag，nalytic 2000:19～30

6 Jovan Dj. Golic. Linear statistical weakness of alleged RC4 key-stream generator， EUROCRYPT： Advances in

Cryptology-EUROCRYPT ＇97， International And Conference on the Theory and Application of Cryptographic Techniques，EUROCRYPT＇97 (Konstanz， Germany)， LNCS， vol. 1233， Springer-Verlag， May 1997， eloved:226～238