第2章 QQ登录协议的安全性
2.1 TEA简介
TEA算法是由剑桥大学计算机实验室的 David Wheeler和 Roger Needham 于1994年发明。 TEA是Tiny Encryption Algorithm的缩写。特点是加密速度极快，高速高效，但是抗差分攻击能力差。TEA加密算法是一种分组密码算法，其明文密文块64比特（8字节），密钥长度128比特(16字节)。TEA加密算法的迭代次数可以改变，建议的迭代次数为32轮，两个TEA Feistel周期算为一轮。 TEA算法被广泛应用于QQ的数据加密中，QQ采用16轮的TEA算法加密，在这时采取16轮加密而不采取标准的32轮加密为了减少验证服务器的压力。QQ在数据加密前采用了密码学中的常用的填充及交织技术，减少加密数据的相关性，增加破译者的破解难度。 TEA算法代码如下：
void qq_encipher(unsigned long *const plain, const unsigned long *const key, unsigned long *const crypt)
//参数为8字节的明文输入和16字节的密钥，输出8字节密文 {unsigned long left = plain[0],right = plain[1], a = key[0], b = key[1], c = key[2], d = key[3], n = 32, sum = 0, delta = 0x9E3779b9;
// 明文输入被分为左右两部分，密钥分为四部分存入寄存器，n表示加密轮数推荐32。delta是一个常数。 while (n-- > 0) { sum += delta;
left += ((right << 4) + a) ^ (right + sum) ^ ((right >> 5) + b); right += ((left << 4) + c) ^ (left + sum) ^ ((left >> 5) + d);} crypt[0] = left ; crypt[1] = right ; }
void decrypt(unsigned long *v, unsigned long *k) { //解密过程 unsigned long y=v[0], z=v[1], sum=0xC6EF3720, i; unsigned long delta=0x9e3779b9;
//delta黄金分割率。它的作用是使得每轮的加密不同。初始化为0x9e3779b9 unsigned long a=k[0], b=k[1], c=k[2], d=k[3]; for(i=0; i<32; i++){ //循环入口
z -= ((y<<4) + c) ^ (y + sum) ^ ((y>>5) + d); y -= ((z<<4) + a) ^ (z + sum) ^ ((z>>5) + b); sum -= delta; /*结束循环*/ } v[0]=y; v[1]=z;}
2.2 QQTEA算法
5
在本文第一章中提到，协议用到的对称加密算法为反馈随机交织填充的TEA（Tiny Encryption Algorithm，一种分组加密算法）变形加密算法，记作QQTEA。那么这里将主要介绍填充、交织和反馈这三点，如果大家对TEA算法的加密过程感兴趣，可参考相关文献[1]。 （1）填充算法
为了适用TEA算法，需要使得明文的字节数是8的倍数。如果明文本身的长度不是8的倍数，那么还要进行填充以使其成为8的倍数。以字节为单位，令N=原始字符串+10+填充字节数n，则N应该是8的倍数。
具体的填充方法：第一个字节为：(random()&0xf8)|n，随后填充(n+2)个字节random()&0xff ,后面接原始数据，最后填充7 个字节0x00 。因为使用了不同的随机数，所以填充的结果使得即使对于相同的明文，密文的结果也会不同。 如图：
1Byte
填充长度（n）+2 明文长度
明文
7Byte 0x00
随机数 填充长度 随机数 random()&0xf8 n random()&0xf8
3Byte 填充长度（n）=8-（（明文长度+2）%8） （2）交织算法
消息被分为多个加密单元，每一个加密单元都是8字节，使用TEA进行加密，加密结果与下一个加密单元做异或运算后再作为待加密的明文。 （3）反馈加密
因为TEA是分组加密算法，所以需要将明文分块。plain[i]表示明文的第i个分组，crypted[i]表示密文的第i个分组，所有分组加密使用的密钥是相同的，设为key。具体的反馈加密过程如下图所示：
plain[i]
crypted[i-1]
key TEA plain[i-1]
crypted[i]
当i=1时，crypted[i] = E(key, plain[i])；
6
当i>1时，crypted[i] = plain[i-1] xor E(key, plain[i] xor crypted[i-1])。
在参考文献[1]中提到要验证一个密钥是否是正确的，那么只需要取明文和密文的最后16Byte（也就是两个分组）就行了。可是根据上面给出的式子，我们就会发现，对于第一个分组，其实并没有进行反馈处理，因此，只需要对前8Byte（即一个分组）出来解密，通过比较也能判断出测试密钥的正确性。
2.3 伪随机数生成器
在QQ2012客户端程序中使用了伪随机数生成器（PRNC），下面简单介绍伪随机数及其安全性。 （1）伪随机数
真正意义上的随机数（或者随机事件）在某次产生过程中是按照实验过程中表现的分布概率随机产生的，其结果是不可预测的，是不可见的。而计算机中的随机函数是按照一定算法模拟产生的，其结果是确定的，是可见的。所以用计算机随机函数所产生的“随机数”并不随机，是伪随机数。
（2）伪随机数生成器
伪随机数字生成器(PRNG)是一种生成伪随机数的方法。在很多的加密算法以及诸多安全协议中都涉及到了随机数的生成，由此可以看出，一个安全的伪随机数生成器对于密码学来说是至关重要的。因此研究伪随机数的安全性是尤为必要的，但是由于计算机的确定性，那么研究伪随机数的安全性往往是指在多项式时间内不可预测。需要指出的是，QQ2012客户端程序中使用的伪随机数生成器是一种线性同余发生器LCG（Linear congruential generator）。QQ2012 客户端使用的 LCG 来自Microsoft Visual/Quick C/C++ 的rand() 函数。具体的计算方法如下：Xn = (Xn-1 * A + B ) mod M
其中Xn 是序列的第n个数，Xn-1 是序列的第n-1个数，A,B,M都是常数（一般会取质数）。当B=0时，叫做乘同余法。引出一个概念叫seed，它会被作为X0被代入上式中，然后每次调用rand()函数都会用上一次产生的随机值来生成新的随机值。可以看出实际上用rand()函数生成的是一个递推的序列，一切值都来源于最初的 seed。所以当初始的seed取一样的时候，得到的序列都相同。 rand()函数原型：
int __cdecl rand (void){
return(((holdrand=holdrand*214013L+2531011L)>>16)&0x7fff); }
若是要使用该线性同余发生器LCG来产生随机密钥，那么有两种方法：第一种是每次产生两个字节，另一种是每次产生一个字节。作为一个通用的函数例程，其使用的应该是是第二种方法，具体函数例程如下： int fillrandom (char *buffer, const int size) { int i;
7
for(i=0;i { buffer[i]=rand()&0xff; }} 通过上文可以了解到，当选取恰当的A和B时，产生的序列周期是可以达到M的。对于32位的程序来说，这样的周期还是安全的。但是，如果按照上述例程来产生密钥，由于只使用到了8-15的比特位（最低位是第0位），其周期是大大缩短了。这样产生的一个完整周期，它的长度为2^24。在允许的时间范围内检索完这个序列是绝对有可能的，这样一来便为离线字典攻击提供了机会。 第3章 QQ登录协议的漏洞及改进 3.1漏洞1-伪随机数生成器攻击 上文中已经对伪随机数及QQ2012客户端程序中使用的伪随机数生成器进行了简要介绍，并分析了安全性。由此可知，因为伪随机数生成器的安全漏洞，才让我们能够对其生成的随机密钥进行有效预测。从本文第1章对QQ登录协议的介绍可以了解到，一旦我们预测到了Key0,就可以获得{Key1，Key2}；获得了Key2，进而就知道了{Key3，Key4}；通过Key3就能最终获得SessionKey(会话密钥)。所以，我们可以这样理解：对Key0的攻击，实际上就是对于SessionKey。因此，直接研究对QQ登录协议中极为重要的SessionKey会话秘钥的攻击就可以了。下面重点讲解对SessionKey的攻击(相关数据可参照第1章QQ登录协议流程图)： a. 开始捕捉pcap_loop(UDP数据包) b. 判断数据包是否捕捉成功，是则进行c,否则重新捕捉 8
相关推荐：
loading