|
靈鑰科技
前言
TEA算法被廣泛地應(yīng)用于計(jì)算機(jī)數(shù)據(jù)加密領(lǐng)域，OICQ的數(shù)據(jù)安全采用了TEA算法。本文討論了TEA的算法的原理及實(shí)現(xiàn)，并揭示了QQ中該算法的應(yīng)用，本文是靈鑰科技公司(www.panakes.com)在即時(shí)通信密碼研究公開的第一篇論文，今后我們將陸續(xù)發(fā)表相關(guān)的論文及相應(yīng)的產(chǎn)品。
TEA算法簡介
TEA算法是由劍橋大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室的 David Wheeler和 Roger Needham 于1994年發(fā)明. TEA是Tiny Encryption Algorithm的縮寫。特點(diǎn)是加密速度極快，高速高效，但是抗差分攻擊能力差。
TEA加密算法是一種分組密碼算法，其明文密文塊64比特（8字節(jié)），密鑰長度128比特(16字節(jié))。TEA加密算法的迭代次數(shù)可以改變，建議的迭代次數(shù)為32輪，盡管算法的發(fā)明人強(qiáng)調(diào)加密16輪就很充分了。兩個(gè)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)值作為變化， ，就是黃金分割率。它的作用是使得每輪的加密是不同。 的準(zhǔn)確值可能不太重要。但是在這里，它被初始化為
=0x9e3779b????
QQ是如何利用TEA進(jìn)行加密的?
TEA算法被廣泛應(yīng)用于QQ的數(shù)據(jù)加密中，QQ采用16輪的TEA算法加密，在這時(shí)采取16輪加密時(shí)而不采取標(biāo)準(zhǔn)的32輪加密時(shí)為了減少驗(yàn)證服務(wù)器的壓力。QQ在數(shù)據(jù)加密前采用了密碼學(xué)中的常用的填充及交織技術(shù)，減少加密數(shù)據(jù)的相關(guān)性，增加破譯者的破解難度。??
下表列出了QQ 應(yīng)用TEA算法幾個(gè)方面
??
序號
應(yīng)用
相關(guān)文件
1
通訊報(bào)文的加密/解密
???
2
消息記錄的加密/解密
MsgEx.db
3
本地消息密碼、首次登錄時(shí)間、提示內(nèi)容驗(yàn)證密碼
Matrix.db
4
消息備份文件
*.bak
QQ的TEA算法源程序分析
QQ在進(jìn)行TEA加密前采用ntohl函數(shù)對原文數(shù)據(jù)和加密密鑰進(jìn)行了變換，從網(wǎng)絡(luò)字節(jié)順序轉(zhuǎn)換位主機(jī)字節(jié)順序進(jìn)行加密后，再通過htonl函數(shù)將數(shù)據(jù)轉(zhuǎn)換為網(wǎng)絡(luò)字節(jié)順序的數(shù)據(jù)。
為什么要這樣做呢？因?yàn)椴煌挠?jì)算機(jī)使用不同的字節(jié)順序存儲(chǔ)數(shù)據(jù)。因此任何從Winsock函數(shù)對IP地址和端口號的引用和傳給Winsock函數(shù)的IP地址和端口號均時(shí)按照網(wǎng)絡(luò)順序組織的。
?? 為防止分析者分析出QQ是采用TEA加密算法的，程序的設(shè)計(jì)者采用了sub????? eax, 61C88647h 指令，而不采用Add eax 9e3779b9h指令。因?yàn)榉治稣咧恍枰袛?e3779b9h（即是我們前面提的黃金分割率的值）就知道采用了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]進(jìn)行ntohl變化,
mov [esi], eax
add esi, 4
dec [ebp+arg_0]
jnz short loc_409A79
push 10h??????????????????????????????????? ;做十六輪TEA運(yùn)算
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???????????????????????? ;加密結(jié)果
call htonl
mov [esi+4], eax???????????????????? ;加密結(jié)果
pop edi
pop esi
pop ebx
leave
retn
sub_409A43 endp
?? 結(jié)論
作為一種分組加密算法，TEA加密算法在其發(fā)展的過程中，目前出現(xiàn)了幾種針對TEA算法設(shè)計(jì)的缺陷攻擊方法，使得原有的TEA加密算法變得不安全，在過去的十幾年中，TEA算法進(jìn)行了若干次的改進(jìn)，歷經(jīng)XTEA, Block TEA, XXTEA幾個(gè)版本。目前最新的算法是XXTEA。
QQ采用了最初的TEA算法做其核心的加密算法，QQ在采用TEA算法時(shí)采用了16輪的加密，其加密復(fù)雜度比32輪減了許多。利用TEA算法的設(shè)計(jì)缺陷，使得快速破解QQ密碼成為可能。
值得一提的QQ在利用TEA算法做加密時(shí)，采用了交織及隨機(jī)填充隨機(jī)數(shù)的技術(shù)，增加了密碼分析者分析難度，從一定程度上保護(hù)了信息的安全。
|