|
灵钥科技
前言
TEA算法被广泛地应用于计算机数据加密领域，OICQ的数据安全采用了TEA算法。本文讨论了TEA的算法的原理及实现，并揭示了QQ中该算法的应用，本文是灵钥科技公司(www.panakes.com)在即时通信密码研究公开的第一篇论文，今后我们将陆续发表相关的论文及相应的产品。
TEA算法简介
TEA算法是由剑桥大学计算机实验室的 David Wheeler和 Roger Needham 于1994年发明. TEA是Tiny Encryption Algorithm的缩写。特点是加密速度极快，高速高效，但是抗差分攻击能力差。
TEA加密算法是一种分组密码算法，其明文密文块64比特（8字节），密钥长度128比特(16字节)。TEA加密算法的迭代次数可以改变，建议的迭代次数为32轮，尽管算法的发明人强调加密16轮就很充分了。两个TEA Feistel周期算为一轮。图1示例了TEA一轮的加密流程。
以下示例了TEA的C语言加密算法，TEA的解密算法与加密算法类似。
#define TEA_ROUNDS 0x20
#define TEA_DELTA 0x9E3779B9
#define TEA_SUM 0xE3779B90
void tiny_encrypt(unsigned long *const v, unsigned long *const w,
const unsigned long *const k)
{
register unsigned long
y = v[0],
z = v[1],
a = k[0],
b = k[1],
c = k[2],
d = k[3],
n = TEA_ROUNDS,
sum = 0,
delta = TEA_DELTA;
while (n-- > 0) {
sum += delta;
y += (z << 4) + a ^ z + sum ^ (z >> 5) + b;
z += (y << 4) + c ^ y + sum ^ (y >> 5) + d;
}
w[0] = y;
w[1] = z;
}
TEA 算法利用的不断增加的 (即源程序中的delta)值作为变化， ，就是黄金分割率。它的作用是使得每轮的加密是不同。 的准确值可能不太重要。但是在这里，它被初始化为
=0x9e3779b
QQ是如何利用TEA进行加密的?
TEA算法被广泛应用于QQ的数据加密中，QQ采用16轮的TEA算法加密，在这时采取16轮加密时而不采取标准的32轮加密时为了减少验证服务器的压力。QQ在数据加密前采用了密码学中的常用的填充及交织技术，减少加密数据的相关性，增加破译者的破解难度。
下表列出了QQ 应用TEA算法几个方面
序号
应用
相关文件
1
通讯报文的加密/解密
2
消息记录的加密/解密
MsgEx.db
3
本地消息密码、首次登录时间、提示内容验证密码
Matrix.db
4
消息备份文件
*.bak
QQ的TEA算法源程序分析
QQ在进行TEA加密前采用ntohl函数对原文数据和加密密钥进行了变换，从网络字节顺序转换位主机字节顺序进行加密后，再通过htonl函数将数据转换为网络字节顺序的数据。
为什么要这样做呢？因为不同的计算机使用不同的字节顺序存储数据。因此任何从Winsock函数对IP地址和端口号的引用和传给Winsock函数的IP地址和端口号均时按照网络顺序组织的。
为防止分析者分析出QQ是采用TEA加密算法的，程序的设计者采用了sub eax, 61C88647h 指令，而不采用Add eax 9e3779b9h指令。因为分析者只需要判断9e3779b9h（即是我们前面提的黄金分割率的值）就知道采用了TEA加密算法。
sub_409A43 proc near ; CODE XREF: sub_409B8C+AEp
; sub_409B8C+109p ...
var_10 = dword ptr -10h
var_C = dword ptr -0Ch
var_8 = dword ptr -8
var_4 = dword ptr -4
arg_0 = dword ptr 8
arg_4 = dword ptr 0Ch
arg_8 = dword ptr 10h
push ebp
mov ebp, esp
sub esp, 10h
push ebx
push esi
mov esi, [ebp+arg_0]
push edi
push dword ptr [esi] ; netlong
call ntohl
push dword ptr [esi+4] ; netlong
mov edi, eax ;y
call ntohl
mov ebx, eax ;z
mov eax, [ebp+arg_4]
lea ecx, [ebp+var_10]
lea esi, [ebp+var_10]
sub eax, ecx
mov [ebp+arg_0], 4
mov [ebp+arg_4], eax
jmp short loc_409A7C
; 哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪?
.text:00409A79
loc_409A79: ; CODE XREF: sub_409A43+49 j
mov eax, [ebp+arg_4]
loc_409A7C: ; CODE XREF: sub_409A43+34 j
push dword ptr [eax+esi] ; netlong
call ntohl ;对k[0],k[1],k[2],k[3]进行ntohl变化,
mov [esi], eax
add esi, 4
dec [ebp+arg_0]
jnz short loc_409A79
push 10h ;做十六轮TEA运算
xor eax, eax
pop ecx
loc_409A93: ; CODE XREF: sub_409A43+88 j
mov edx, ebx
mov esi, ebx
shr edx, 5 ;z>>5
add edx, [ebp+var_C] ;z>>5+k[1]
sub eax, 61C88647h ;sum=sum+delta delta:0x9e3779b9
shl esi, 4 ;z<<4
add esi, [ebp+var_10] ;z<<4+k[0]
xor edx, esi ;(z>>5+k[1]) ^ (z<<4+k[0])
lea esi, [eax+ebx] ;sum+z
xor edx, esi ;(z<<4+k[0]) ^ (sum+z)^(z>>5+k[1])
add edi, edx ;y+=(z<<4+k[0]) ^ (sum+z)^(z>>5+k[1])
mov edx, edi
mov esi, edi
shr edx, 5 ;y>>5
add edx, [ebp+var_4] ;y>>5+k[3]
shl esi, 4 ;y<<4
add esi, [ebp+var_8] ;y<<4+k[2]
xor edx, esi ;(y>>5+k[3])^(y<<4+k[2])
lea esi, [eax+edi] ;(sum+y)
xor edx, esi ;(y<<4+k[2])^(sum+y)^(y>>5+k[3])
add ebx, edx ;z+=(y<<4+k[2])^(sum+y)^(y>>5+k[3])
dec ecx
jnz short loc_409A93
push edi ; hostlong
call htonl
mov esi, [ebp+arg_8]
push ebx ; hostlong
mov [esi], eax ;加密结果
call htonl
mov [esi+4], eax ;加密结果
pop edi
pop esi
pop ebx
leave
retn
sub_409A43 endp
结论
作为一种分组加密算法，TEA加密算法在其发展的过程中，目前出现了几种针对TEA算法设计的缺陷攻击方法，使得原有的TEA加密算法变得不安全，在过去的十几年中，TEA算法进行了若干次的改进，历经XTEA, Block TEA, XXTEA几个版本。目前最新的算法是XXTEA。
QQ采用了最初的TEA算法做其核心的加密算法，QQ在采用TEA算法时采用了16轮的加密，其加密复杂度比32轮减了许多。利用TEA算法的设计缺陷，使得快速破解QQ密码成为可能。
值得一提的QQ在利用TEA算法做加密时，采用了交织及随机填充随机数的技术，增加了密码分析者分析难度，从一定程度上保护了信息的安全。
|