|
靈鑰科技
前言
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算法做加密時，采用了交織及隨機填充隨機數的技術，增加了密碼分析者分析難度，從一定程度上保護了信息的安全。
|