深入WEP密码破解原理

首先看看WEP加密,解密的流程图

     WEP加密算法实际上是利用RC4流密码算法作为伪随机数产生器,将由初始矢量IV和WEP密钥组合而成的种子生成WEP密钥流(图中的KSA和PRGA部分),再由该密钥流与WEP帧数据负载进行异或运算来完成加密运算.
    RC4流密码是面向字节的,在算法过程中只是用了置换的方法,按照图中分成的两个部分,其C代码如下
    KSA部分:
[cpp] view plaincopy
int i,j = 0;
for (i = 0; i < 256; i++)
{
    s[i] = i;
}
for (i = 0; i < 256; i++)
{
    k[i] = key[i % 8];//针对64bit的WEP加密,128bit的为[i % 16]
}
for (i = 0; i < 256; i++)
{
    j = (j + s[i] + k[i]) % 256;
        Swap(s[i], s[j]);//进行置换
}


其中s[256]为状态列,k[256]为密钥列,key[8]为64位的密钥,状态列初始化为{0,1,2,3, , ,255},密钥列按照提供的密钥8字节重复填充至256字节满,通过置换,生成了一个状态列用以生成密钥流.
PRGA部分(只生成256个字节的密钥流):
[cpp] view plaincopy
for (i = 0, j = 0, LengthofKeyStream = 0; LengthofKeyStream < 256; LengthofKeyStream++)
    {
        i = (i + 1) % 256;
        j = (j + s[i]) % 256;
        Swap(s[i], s[j]);
        keystream[LengthofKeyStream] = s[(s[i] + s[j]) % 256];
    }


至此,我们就有了一个可以进行异或加密的密钥流keystream[256].在WEP加密当中应该是根据数据data的长度来调整需要得到的密钥流的长度,这里做了简单的处理.
在对使用WEP加密的无线网络抓包的时候,由于ARP包和IP包明文的第一字节是802.2头标(0xAA),这样我们就有了数据第一字节的明文(0xAA),同时我们也有了密文的第一字节,当将这两个字节进行异或的时候,我们可以得到keystream[0],也就是伪随机生成序列的第一字节,现在通过对这第一个字节进行分析,看看能否逆推出某个密钥字节.
根据PRGA部分代码,执行第一次循环时生成keystream[0],初始条件i=0,j=0,按流程走下来,最后可知keystream[0]=s[s[1]+s[s[1]]],假设s[1]的值为X,s[s[1]](即s[X])的值为Y, s[s[1]+s[s[1]]](即s[X+Y])的值为Z,则如图

由此可以看出,keystream[0]的值受3个值的影响,分别是X,Y,和Z.这3个值是在KSA算法当中通过置换形成的.
[cpp] view plaincopy
for (i = 0; i < 256; i++)
{
    j = (j + s[i] + k[i]) % 256;
        Swap(s[i], s[j]);//进行置换
}

    注意到,当生成供给PRGA使用的状态列的时候,进行的KSA循环是256次,根据大量的数据统计表明[1],在经过i(i>=1)次KSA循环之后,X,Y,Z三者不参与接下来置换的概率大概是0.05大一点,也就是100次里面大概有5次,X,Y,Z再之后的循环当中是保持不变的,一直保持在这个位置没有被置换,这样最后利用这个状态列生成的keystream[0]的值就是Z,这种状态称为断然状态(Resolved Condition),如果用一个处于断然状态的密钥流进行异或加密,我们就能够从中得到与密钥相关的一些信息,利用已知的密钥流第一个字节keystream[0]推算出密钥当中的一个字节.
举例来说,现在现实的情况是这样的.我们知道的初始向量IV为3个字节,即密钥的结构为key[8]={IV[0], IV[1], IV[2], USER[0], USER[1], USER[2], USER[3], USER[4]},USER[]表示用户自己定义的5个字节密钥.加上IV的3个字节就是8个字节64bit,回过头看KSA算法中的置换循环:
[cpp] view plaincopy
for (i = 0; i < 256; i++)
{
    j = (j + s[i] + k[i]) % 256;
        Swap(s[i], s[j]);//进行置换
}


    由于i从0开始,j的值与s[i]的值和k[i]的值相关,s[i]的初始值我们知道,s[i]=i,那么现在知道了key[0],key[1],key[2]这3个值,我们就可以计算得到3个状态列(即经过3次循环时s[]的值),我们用s_n[](如s_1[])表示i=n时进行置换后的状态列,用j_n(如j_1)表示i=n时j的值,也就是说,我们可以根据已知的条件推算出s_0[],s_1[],s_2[],j_0,j_1,j_2,假设在i=3时,状态列进入断然状态,那么根据前面的分析,此时有keystream[0]=s_3[s_3[1]+s_3[s_3[1]]],若此IV满足下面两个条件:1.s_3[1]<3;2.s_3[1]+s_3[s_3[1]]=3.此时就有keystream[0]=s_3[3],由于s_3[3]是由s_2[j_3]置换而来的(Swap(s[i], s[j]);)[2],j_3=j_2+s_2[3]+k[3],k[3]也就是key[3],则k[3]=j_3-j_2-s_2[3],根据等式,j_3通过在s_2[]中查找keystream[0]的值得到其索引即是j_3,j_2可以通过计算得到,s_2[3]已知,这样就可以计算出k[3]的值,有一定的概率是正确的,对于k[4]的取得方式也是以此类推,建立在计算出的k[3]值的基础上.
考虑现在具有特殊形式的的IV={3, 255, N},N表示任意数,用一个表格表示s状态列在i各个值时候的情况:
初始状态i=0,j=0
S初始
0
1
2
3
…
5+N
…
255
i=0,j_0=3
s_0
3
1
2
0
…
5+N
…
255
i=1,j_1=3
s_1
3
0
2
1
…
5+N
…
255
i=2,j_2=5+N
s_2
3
0
5+N
1
…
2
…
255
i=3,j_3=6+N+k[3]
s_3
3
0
5+N
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…

由上表可以得知,s_3[3]=s_2[6+N+k[3]]=s_2[5+N+1+K[3]]=s_2[j_2+s_2[3]+k[3]],由此可以求出k[3]的值.特殊形式IV只要满足那两个条件即可,不一定是给出的{3, 255, N}的形式.
求出了k[3]之后可以进一步的求的k[4],以此类推直到求得k[7],由于状态列进入断然状态存在一定概率,因此通过大量的数据包进行推算,然后根据得到的推算密钥字节进行统计,选取出现概率高的推算密钥字节进行组合,之后再进行验证即可得到WEP的密钥.


参考文献:
[1] A L Grosul,D S Wallach.A related-key cryptanalysis of RC4.2000-06
[2]夏新军,俞能海,陆铭.针对RC4算法的无线局域网攻击.2004

//                   作者:GaA.Ra(zhoufan#yahoo.cn)
//                   随意转载,但请保留此部分信息,谢谢

补充：综合编程 , 安全编程 ,