QQ登录协议安全性分析和改进

作者：没有姓名的鬼，tpu01yzx@163.com

摘要：QQ作为国内用户最大的即时聊天工具，其安全性关系着广大网民的个人隐私和诸多基于QQ应用的信息系统的安全。本文通过对QQ2010登录协议进行形式化分析，首先指出了该协议存在离线字典攻击和伪随机数攻击，然后给出了具体实施攻击的方法和实验数据，并且提出了相应的改进方法。

关键字：QQ2010，登录协议，TEA，伪随机数

1引言

2010年3月5日19时52分58秒，QQ同时在线会员达到1亿[1]。作为国内最大的即时聊天工具，QQ的安全性在整个互联网的信息安全里占据着极其重要的地位。本文采用传统的黑箱测试的方法，结合现有公开的成果[2][3]，对QQ2010正式版SP1(1760) （SHA1摘要为：D52B248539C9B5F7B2CC8E5D772A23AC5DF6CFCA）的登录协议进行了研究分析。注意到，由于QQ协议本身是不公开的，因此验证协议安全性的唯一办法就是通过黑箱测试，然后试验模拟攻击。在本文的试验中，均采用被动截包的方法，避免了对正常QQ通讯协议的破坏。通过理论分析和试验，我们发现QQ登录协议存在离线字典攻击和伪随机数攻击。

本文第一部分介绍了一些协议安全及QQ登录协议有关的概念；第二部分分析了QQ登录协议的安全性；第三部分指出其存在若干安全漏洞；第四部分给出了相关攻击的实验数据，并做了简要的分析，然后给出了改进方法；最后是对本文研究内容的总结。

2 QQ协议

2.1基本概念

协议方面的概念：

身边标识（ID）：标识协议参与者的身份。

口令：用户容易记忆的一串可见字符。

密钥交换协议：使得通讯双方建立一个公共的密钥的协议。

会话密钥：密钥交换协议中双方建立的公共密钥。

基于身份口令的密钥交换协议：通讯双方通过事先共享的一个口令，并以此建立一个公共密钥的协议。

加密工具方面的概念：

对称加密：加密和解密使用相同的密钥。

哈希函数：单向的不可逆的映射变换。

 

另外，关于密钥交换协议的安全性，一般定义为通过该协议建立的会话密钥的安全性（不可预测性）。

 

2.2QQ登录协议

根据截包分析和参考资料得知，QQ登录协议分为一下几个步骤：（为了简化，去掉了一些无关的内容）

其中用到的对称加密算法为反馈随机交织填充的TEA变形加密算法，记作QQTEA；用到哈希函数为MD5。其他的符号说明如下：

QQNumber：QQ号码，即身份标识；

QQPassword：QQ密码，即口令；

SessionKey：会话密钥。

MD5：一种哈希函数。

M2P：Md5(Md5(QQPassword))。

RandomKey：随机生成的16字节长度的密钥。

Ki：16字节长度的密钥。(i=0,1,2,3,4)

E(K,P)：表示使用密钥K对明文P加密，这里是指QQTEA加密。

D(K,C)：表示使用密钥K对密文C解密，这里指QQTEA解密。

DATAi：表示未知具体意义的数据。

图2.1 QQ登录协议

3安全性分析

如上一章提到的那样，QQ使用到的是TEA加密的一种变形。关于TEA的加密过程，请参考文献[4]，这里仅介绍其中的填充和反馈部分。

3.1TEA加密的变形

填充算法：首先为了适用TEA算法，需要使得明文的字节数是8的倍数。同时在明文和最后填充了7个字节的0x00，在开头增加一个字节，其中低三位表示后面填充的字节数。最后填充完的结果为：

 

图3.1 填充结果

其中，填充长度=8-（（明文长度+2）%8）

这表明，对于已知明文的长度，我们只需要使用测试密钥来解密前一组密文，通过对比填充长度来判断该测试密钥是否正确。通过试验表明，大约有87.5%密钥可以通过这一步判断为错误的密钥。

 

反馈加密：TEA是分组加密算法，因此需要将明文分块。plain[i]表示明文的第i个分组，crypted[i]表示密文的第i个分组，所有分组加密使用的密钥是相同的，设为key。其具体的反馈加密过程为：

图3.1 反馈加密模式

即：

i=1时，crypted[i] = E(key, plain[i])；

i>1时，crypted[i] = plain[i-1] xor E(key, plain[i] xor crypted[i-1])。

在文献[3]中，作者指出要验证一个密钥是否正确，只需要取明文和密文的最后16个字节（即两个分组）即可。可是根据上式，我们知道，对于第一个分组，并没有进行反馈处理，因此，只需要对前8个字节（即一个分组）出来解密，通过比较也能判断出测试密钥的正确性。通过试验表明，大约有12.5%密钥可以通过这一步判断为错误的密钥。

关于TEA算法最新的攻击方法在文献[5][6][7]。

3.2MD5哈希函数的不稳固性

注意到QQ协议使用到了MD5[8]作为消息一致性检验的哈希函数。根据参考文献[9][10]，MD5似乎不再具备这样的功能，当然在我们提出的QQ协议的安全漏洞中并没有利用到MD5的不稳固性，但是我们相信如果得到了口令的哈希值，可以在接受的时间内计算得到口令。关于计算MD5的原像，还可以采用彩虹表的方法，具体可以参考文献[11]。

3.3伪随机数生成器

伪随机数生成器(PRNG)是一个产生不可预测的序列的函数。由于计算机的确定性，因此研究伪随机数的安全性，往往是指在多项式时间内不可预测。在很多加密算法和安全协议中，都涉及到随机数的生成，因此一个安全的随机数生成器对于密码学来说是十分重要的。在QQ2010客户端程序中使用的伪随机数生成器是一种线性同余发生器(LCG)[12]。一般的LCG的形式为：

QQ2010客户端使用的LCG也许来自Microsoft Visual/Quick C/C++的rand()函数。其中的rand()函数实现如下[12]：

int __cdecl rand (void) {

        return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);

}

这样的一个LCG是存在安全问题，具体地可以参考，其他人的研究成果[13][14][15]。而我们注意到如果使用该LCG来生成随机密钥，那么有两种方法：要么每次产生两个字节，要么每次产生一个字节。作为一个通用的函数例程，我们有理由认为其使用的是后一种方法，其函数例程如下：

int fillrandom (char *buffer, const int size) {

       int i;

    for(i = 0; i < size; i++) buffer[i] = rand() & 0xff;

}

[15]里指出，对于一般的LCG，选取适当的常数a和c，产生的序列周期可以达到m，对于32位程序来说，这样的周期还是安全的。可是，若按上述例程来产生密钥，那么由于只使用到了8-15的比特位（最低位为第0位），那么其周期是大大缩短了。我们产生了这样完整的一个周期，其长度为2^24。在可以接受的时间内搜索完这个序列是可能的，这就为下面的攻击提供了机会。

4协议的安全漏洞与改进

4.1离线字典攻击

在文献[3]中，作者已经提出了一种针对QQ(2008)的离线字典攻击的方法，同样的方法对QQ(2010)也是有效的。根据我们前面对TEA变形的分析，可以看出，要验证一个口令是否正确，除了选取最后16个字节进行检验之外，还可以先对头8个字节进行解密检验。这是第一个分组是没有反馈的，并且第一个字节的低三位包含了已知的信息（随机填充的字节数）。事实上，明文中任何连续两个分组如果是已知的，都可以用来做解密的检验。本文不再对这个攻击做进一步的分析。具体的攻击方式可以仿照[2]，其中的测试密钥验证程序可以改进为：

图4.1 检验测试密钥正确性程序流程

注1：第一个判断流程是由于对于正确的身份验证来说，服务器返回的数据包大小总是为285个字节明文，按照填充规则，填充的头一个字节的低8位应该等于（8-（285+2）%8）=1。

注2：第二个判断流程同样是对于正确的身份验证来说，服务器返回的前四个字节内容是固定的。

注3：第三个判断流程是依据[2]的方法增设的，虽然根据我们的试验，只需要前两个判断流程就可以判断测试密钥的正确性。这一个判断流程只是出于严谨的角度增设的。

4.2 伪随机数生成器攻击

前面我们已经介绍了QQ2010客户端使用的伪随机数生成器的安全漏洞，这使得我们可以对其产生的随机密钥进行有效的预测。根据第二节对QQ登录协议的描述，很明显地，知道K0，就可以知道{K1,K2}；知道K2，就可以知道{K3,K4}；知道K3，就知道SessionKey。因此，对于K0的攻击，就是对SessionKey的攻击。如果我们可以预测K0，那么就可以预测SessionKey。以此为依据，我们直接给出对QQ登录协议中关键的SessionKey密钥的攻击：

图4.2 破解SessionKey流程图

注1：dport表示UDP数据包的目的端口；sport表示UDP数据包的源端口。Rand.bin是使用上一节提到的方法生成的随机数的完整一个周期的数据文件。

注2：关于“寻找RandomKey对应的偏移量”，使用暴力的方法也是可以接受的，之前我们已经讨论过了，Rand.bin大小只有16MByte。如果这个周期比较大，通过合理的组织数据结构和预先的计算，可以在更快的时间内找到其对应的偏移量。这里暂不做深入的讨论。

注3：关于“从offset开始测试每一个可能的密钥”，事实上，通过多次的试验，我们发现K0一般在offset-16的偏移量位置。复杂的客户端登录操作可能会改变这个偏移量，所以我们采用了搜索的方式，而offset-16这个偏移量位置对于大部分情况下都是正确的。

注4：关于流程中的“包含”，根据[2]对QQ协议的描述，我们只需要根据UDP数据包的第4个和第5个字节来判断。[2]中有详细的说明，这里不再累赘。

注5：同时我们还注意到这种攻击方式并非所有情况下都适用，至少在“登录保护”[16]下是无效的。我们认为在“登录保护”下的K0应该是至少与登录IP有关的一个MD5校验值。

4.3协议的改进

针对上述提及的两种攻击方法，本文提出如下的改进方式：

1.       抵御离线字典攻击的方法。如果我们假设攻击者采用字典攻击，那么在攻击者和合法用户之间并没有更多信息上的差异。而如果要采取安全的密钥交换协议，目前来说至少是基于DiffieHellman密钥交换协议[17]，而这一类协议需要一定的存储量和计算量，并不太适合一些QQ终端。因此只有想办法增加字典攻击的复杂度。

a)         具体来说可以增加TEA变换的轮次

b)        修改明文尾部附加的7个字节的填充内容

2.       抵御伪随机数攻击的方法。应对这种攻击的方法是显而易见的，就是修改随机数生成密钥的方式，方法有：

a)         更换其他周期更长的随机数生成器。事实上根据[15]的结论，可以很容易构造出周期更长的随机数。

b)        K0的生成除了有随机数的参数，还可以与MD5({QQNumber,QQPassword,Time})做一次异或操作，使得攻击者无法通过简单的随机数预测来获得K0的信息。

5结论

       通过实际的试验攻击，我们发现了QQ登录协议存在两个安全漏洞：离线字典攻击和伪随机数攻击。同时，我们还有针对性地给出了改进意见。

 

Security Analysis and Improvement of QQ Login Protocol

 

Abstract: As the most popular instant message software in domestic, the security of QQ has much to do with personal privacy and a lot of information systems based on it. On the foundation of the formal analysis of QQ2010 login protocol, we first point out the existence of offline dictionary attack and pseudo-random number attack against the protocol, and then give specific attack methods and experimental data. At last, we make improvement corresponding to the attack methods.

Keywords: QQ2010, login protocol, TEA, pseudo-random number

参考文献

[1] QQ同时在线用户数突破1亿，Tencent，2011.4.15，

http://tech.qq.com/zt/2010/qq100000000/

[2] QQ2010Protocol，V.E.O@TOM.COM，2011.4.15，

http://code.google.com/p/libqq-pidgin/wiki/QQ2010Protocol

[3] 俞凯，QQ登录协议安全性研究与分析，信息网络安全，2008, (11)

[4] David J. Wheeler and Roger M. Needham, TEA, a tiny encryption algorithm, Lecture Notes in Computer Science, 1995, Volume 1008, Fast Software Encryption, Pages 363-366

[5] Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang and Wonil Lee, et al.， Differential Cryptanalysis of TEA and XTEA, Lecture Notes in Computer Science, 2004, Volume 2971, Information Security and Cryptology - ICISC 2003, Pages 402-417

[6] Juliio César Hernández Castro and Pedro Isasi Vi?uela, New results on the genetic cryptanalysis of TEA and reduced-round versions of XTEA, New Generation Computing, 2005, Volume 23, Number 3, Pages 233-243

[7] John Kelsey, Bruce Schneier and David Wagner, Related-key cryptanalysis of 3-WAY, Biham-DES,CAST, DES-X, NewDES, RC2, and TEA, Lecture Notes in Computer Science, 1997, Volume 1334, Information and Communications Security, Pages 233-246

[8] The MD5 Message-Digest Algorithm, R. Rivest, 2011.4.21, http://tools.ietf.org/html/rfc1321

[9]Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, EUROCRYPT 2005, LNCS 3494, pp.19-35, 2005

[10] Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen Lenstra and David Molnar, et al., Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate, Lecture Notes in Computer Science, 2009, Volume 5677, Advances in Cryptology - CRYPTO 2009, Pages 55-69

[11] Philippe Oechslin, Making a Faster Cryptanalytic Time-Memory Trade-Off, Lecture Notes in Computer Science, 2003, Volume 2729, Advances in Cryptology - CRYPTO 2003, Pages 617-630

[12] Linear congruential generator, 2011.4.22, http://en.wikipedia.org/wiki/Linear_congruential_generator

[13] Christiane Lemieux, Pseudorandom Number Generators, Springer Series in Statistics, 2009, Monte Carlo and Quasi-Monte Carlo Sampling, Pages 1-30

[14] Joan B. Plumstead, Inferring a sequence generated by a linear congruence

, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, Pages 153 - 159

[15] Manfred Schroeder, Random Number Generators, 2009, Number Theory in Science and Communication, Part IX, Pages 347-353

[16] Diffie–Hellman key exchange，2011.4.22，http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange