基于交換等價的縮減輪AES-128的密鑰恢復(fù)攻擊

張 麗 吳文玲 張 蕾 鄭雅菲

(中國科學(xué)院軟件研究所 北京 100190) (中國科學(xué)院大學(xué) 北京 100049)

分組密碼在對稱密碼學(xué)中起著非常重要的作用，為加密提供了基礎(chǔ)的工具，因此，它們是最受信任的加密算法，經(jīng)常被用作構(gòu)造其他加密算法的基礎(chǔ)工具，這些算法的安全性證明是在假設(shè)底層分組密碼是理想的情況下進(jìn)行的.因此對分組密碼安全性研究是具有非常重要的現(xiàn)實意義.2001年美國通過3年的征集和評選，新的高級加密標(biāo)準(zhǔn)(advanced encryption standard, AES)[1]得以誕生，成為了至今為止最廣為人知和使用最廣泛的分組密碼.AES的安全性研究也一直是密碼學(xué)中最重要的熱點之一.AES已經(jīng)被證明能夠抵抗差分和線性密碼分析.在過去20年的大量研究中只有biclique攻擊[2]能比窮舉搜索更快地突破全輪的AES，所以突破全輪的AES一直是密碼研究人員努力的目標(biāo).

近些年，為了研究出更新更好的方法去實現(xiàn)對全輪AES的攻擊，研究人員更加關(guān)注對于縮減輪的AES攻擊上.對縮減輪AES的攻擊之所以重要，有3個原因:1)它們使我們能夠評估AES的安全冗余，即可以成功攻擊的輪數(shù)與全輪AES的輪數(shù)之比.2)它們使我們能夠開發(fā)新的攻擊技術(shù)，隨著進(jìn)一步的改進(jìn)，這些技術(shù)可能會變得更加有效.3)有許多建議使用縮減輪AES作為它們的組件，比如LED[3]，WEM[4]，ElmD[5]等.

當(dāng)試圖評估密碼的安全性時，密碼的非隨機特性可用來區(qū)分密碼與隨機置換.其中密碼分析最重要的工具之一無疑是差分密碼分析.差分密碼分析方法經(jīng)過多年的發(fā)展，已經(jīng)有了許多的變體，知名的變體方法有截斷差分，不可能差分，高階差分，飛來去器攻擊和差分線性攻擊.此外，近些年多面體密碼分析[6]、子空間密碼分析、yoyo game、混合密碼分析[7]、交換等價攻擊等方法的使用產(chǎn)生了許多好的分析結(jié)果.這些結(jié)果使得對AES進(jìn)行越來越多的全新的、更有效的攻擊成為可能.

對AES算法的安全性分析工作近些年已有許多優(yōu)秀的成果.在FSE 2015 Tiessen等人[8]提出了第1個基于積分分析的6輪AES-128密鑰恢復(fù)，作者研究了在保持其他信息不變的情況下，用一個秘密的8 b S盒去代替AES的S盒.隨機選取的S盒有可能高度抵抗差分和線性攻擊.結(jié)果表明對6輪AES密鑰恢復(fù)的復(fù)雜度已經(jīng)遠(yuǎn)小于窮舉搜索.在Crypto 2016上，Sun等人[9]提出了第1個AES密鑰獨立5輪區(qū)分器.密鑰獨立意味著攻擊不關(guān)心特定的輪密鑰，與相關(guān)密鑰攻擊形成對比.他們利用AES列混合矩陣的特性，將4輪積分性質(zhì)擴展到5輪.雖然他們的區(qū)分器需要整個密碼本，但它為AES產(chǎn)生了一系列新的基礎(chǔ)結(jié)果.后來，通過將4輪不可能差分性質(zhì)擴展到5輪，它被改進(jìn)為298.2選擇明文和2107次計算代價.在FSE 2017，Grassi等人[10]提出了子空間密碼分析方法，給出了5輪子空間跡和5輪不可能差分密鑰恢復(fù).在2017年的歐密會Eurocrypt上，Grassi等人[11]提出了第1個5輪選擇明文區(qū)分器，它僅需要232選擇明文，計算成本為235.6，存儲內(nèi)存大小為236B.

隨后，在2017年Grassi等人證明，通過加密明文空間的某些子空間的陪集，密文對的差分在狀態(tài)空間的特定子空間中的次數(shù)總是8的倍數(shù).亞密會Asiacrypt上，R?njom等人介紹了Rijndael型分組密碼設(shè)計的新基本特性，給出了基于Yoyo game[12]的新型3～6輪AES密鑰區(qū)分器，打破了所有以前的記錄.作者介紹了AES的新的確定性4輪屬性，即通過對角線的任意子集交換而等價的明文對集合在4輪后加密到一組密文對集合，在最終的線性層之前的完全相同列中它們的差分都為0.該結(jié)果在混合密碼分析中得到了進(jìn)一步的探討.在Asiacrypt 2019上，Bardeh和R?njom提出了一種適用于類SPN分組密碼的新技術(shù)——交換等價攻擊[13].交換等價攻擊屬于差分密碼分析，是一種選擇明文攻擊方法，它通過研究特定明文差分的交換性質(zhì)以及對應(yīng)密文的0差分模型，將分組密碼與隨機置換區(qū)分開，并在此基礎(chǔ)上進(jìn)行密鑰恢復(fù)攻擊.該文中給出了交換等價的定義，以及如何利用對明文狀態(tài)進(jìn)行交換等價及AES的性質(zhì)來得到在最終的線性層之前的完全相同列中它們的差分都為0.結(jié)果表明，當(dāng)明文從一個特定的集合(交換等價集)中選擇時，AES的5輪和6輪選擇明文區(qū)分器可以區(qū)別于隨機置換.隨后Bardeh基于交換等價的基礎(chǔ)知識提出了5輪和6輪AES自適應(yīng)選擇密文區(qū)分器[14]，它是從密文出發(fā)做交換等價，去尋找解密后明文狀態(tài)是否具有相同列差分為0，6輪自適應(yīng)密文區(qū)分器需要有283數(shù)據(jù)和時間復(fù)雜度，因此交換等價攻擊方法的提出可以看作是AES密碼分析的一個巨大飛躍.在Africacrypt 2019中，Bardeh基于子空間的知識提出了對5輪AES的有效攻擊[15].到目前為止，最好的密鑰恢復(fù)攻擊可以達(dá)到7輪AES.

本文的主要貢獻(xiàn)有3個方面：

1) 基于由交換等價攻擊提出的5輪自適應(yīng)選擇密文區(qū)分器上向前擴展一輪，提出了一個新的6輪AES-128密鑰恢復(fù)攻擊;

2) 攻擊主要利用了AES列混合矩陣系數(shù)的基本性質(zhì).列混合矩陣的每一行或每一列都有3個和為0的元素，使得在選取明文時滿足這一性質(zhì)，另外使得一輪后的狀態(tài)滿足0差分指定狀態(tài);

3) 用分組長度為64 b的小版本AES實驗驗證了我們的理論結(jié)果，并且該實驗結(jié)果支持我們的理論.

本文對6輪AES密鑰恢復(fù)攻擊的結(jié)果和已有的6輪AES密鑰恢復(fù)的結(jié)果進(jìn)行了比較，如表1所示，其中文獻(xiàn)[14]中的結(jié)果是區(qū)分器的結(jié)果，其余均表示密鑰恢復(fù)攻擊結(jié)果.在數(shù)據(jù)復(fù)雜度、時間復(fù)雜度和存儲復(fù)雜度3方面分別進(jìn)行了對比，結(jié)果表明本文的數(shù)據(jù)復(fù)雜度、時間復(fù)雜度的結(jié)果是最優(yōu)的.數(shù)據(jù)復(fù)雜度以選擇明文(chosen plaintext, CP)數(shù)量/自適應(yīng)選擇密文(adaptive chosen ciphertext, ACC)數(shù)量表示，時間復(fù)雜度以加密(encryption, E)等價形式來表示，空間復(fù)雜度以128 b塊大小為單位表示.我們假定一輪加密約等于20次查表[8].因其他文獻(xiàn)中復(fù)雜度單位不一致，為了方便對比，在這里我們統(tǒng)一換算單位.

Table 1 Key-recovery Attacks on Round-reduced AES-128表1 6輪AES-128密鑰恢復(fù)攻擊

1 AES加密算法介紹

AES分組密碼算法是美國于2001年頒布的高級加密標(biāo)準(zhǔn)，分組長度為128 b，128 b明文將內(nèi)部狀態(tài)初始化為一個4×4字節(jié)矩陣，即所有的運算均在有限域F28上進(jìn)行.密鑰長度分別為128 b，192 b和256 b，根據(jù)AES密鑰長度的不同，迭代輪數(shù)和密鑰長度關(guān)系為：AES-128的輪數(shù)為10輪；AES-192的輪數(shù)為12輪；AES-256的輪數(shù)為14輪.AES加密算法的輪函數(shù)由4種不同變換組成：

1) 字節(jié)代替變換(Subbytes,SB).S盒的變換就是字節(jié)代替變換的本質(zhì)，它是一個作用于狀態(tài)字節(jié)的非線性變換，在狀態(tài)中，其每一個字節(jié)都會經(jīng)過同一個8×8的S盒變換為另一個字節(jié)，簡記為SB.

2) 行移位變換(Shiftrows,SR).AES加密算法中線性運算包括行移位變換，而且它的移位方案僅僅與狀態(tài)有關(guān)，對一個狀態(tài)的每一行循環(huán)左移不同的位移量，第0行不移位保持不變，第1行循環(huán)左移1 B，第2行循環(huán)左移2 B，第3行循環(huán)左移3 B，簡記為SR.

列混合變換有2個基本性質(zhì)：

性質(zhì)1.列混合系數(shù)矩陣的每一行或每一列都有2個和為0的元素.

性質(zhì)2.列混合系數(shù)矩陣的每一行或每一列都有3個和為0的元素.

4) 子密鑰加變換(Addroundkey,ARK).輪子密鑰長度是128 b，一個字為32 b.將一個輪子密鑰按位異或到一個狀態(tài)上.輪子密鑰按順序取自擴展密鑰，簡記為ARK.

此外，AES在第1輪加密之前，有一個白化密鑰層，且最后一輪沒有列混合變換.

我們用R(*)=MC°SR°SB°ARK(*)表示一輪加密AES.在本文中，為了方便描述，我們考慮保留最后一輪的MC作為全輪AES.此外，S盒被一個秘密的S盒取代，其他結(jié)構(gòu)和組件與原AES加密算法相同.

2 交換等價攻擊方法

本節(jié)我們主要介紹交換等價的概念和相關(guān)的定理.以及在自適應(yīng)選擇下5輪自適應(yīng)密文區(qū)分器的原理.我們先給出一些基本的定義及定理.

2.1 基本定義及定理

一對狀態(tài)定義了一個有2w tc(α⊕β)可能的列交換差分的集合，其中wtc(x)表示x的非零列的數(shù)量.現(xiàn)在可以定義3個相關(guān)的運算符，在一對AES狀態(tài)之間交換對角、列和混合值.

其中L=MC°SR.

概率為

P(|I|,|J|,|K|)=(2-8)4(|I|+|J|)-|K||J|-2|I||J|.

成立的概率為

我們注意到定理2的結(jié)果在解密方向上同樣適用，通過應(yīng)用適當(dāng)?shù)慕粨Q操作來考慮相應(yīng)的線性層.

2.2 5輪自適應(yīng)選擇密文區(qū)分器

本節(jié)我們介紹基于交換等價的5輪自適應(yīng)選擇密文區(qū)分器.

成立的概率為

由于密文是隨機的，在定理3中只考慮|K|=0的情況.Bardeh根據(jù)定理3的結(jié)果建立一個5輪的區(qū)分器.其主要思想是自適應(yīng)地生成一個新的明文對為

其中α″⊕β″表示α′⊕β′經(jīng)過5輪解密得到的新的明文狀態(tài)對.Bardeh在文章中給出了一個例子，例如選取明文狀態(tài)僅在第1，2對角活躍，另外2個對角取常數(shù)值，即d=2.且在混合操作時僅交換一列，即|I|=1.則根據(jù)定理3可得：該5輪自適應(yīng)選擇密文區(qū)分器概率為p5(|I|,0)=2-46，而隨機置換的概率為prand=2-32×(4-d)=2-64.

如圖1所示，上層圖表示5輪自然加密狀態(tài)，下層圖表示應(yīng)用了定理3得到的新的加密狀態(tài).其中灰色格表示差分活躍的字節(jié)，白格表示差分為0的字節(jié)，斜條格表示應(yīng)用了混合交換操作后被交換的字節(jié).

Fig. 1 5-round exchange trail圖1 5輪交換跡示意圖

3 對6輪AES-128的密鑰恢復(fù)攻擊

本節(jié)介紹是本文的主要內(nèi)容，基于5輪自適應(yīng)選擇密文區(qū)分器，我們可以向前擴展一輪得到一個新的6輪AES-128密鑰恢復(fù)攻擊.

3.1 選擇合適的明文集合

首先，我們期望所選擇的明文經(jīng)過一輪加密后滿足5輪自適應(yīng)選擇密文區(qū)分器的輸入狀態(tài)，即R(p0)⊕R(p1)在2個對角保持活躍狀態(tài)，剩余對角差分為0. 4個對角狀態(tài)表示如圖2所示：

Fig. 2 Diagonal state圖2 對角狀態(tài)示意圖

基于AES列混合變換的基本性質(zhì)2：列混合系數(shù)矩陣的每一行或每一列都有3個和為0的元素.如果在列混合變換的4個輸入字節(jié)中有3個字節(jié)非0且有相同的值，剩余一個字節(jié)值為0，那么4個輸出字節(jié)中將有2個0字節(jié)，該事件發(fā)生的概率為1.不失一般性，我們假設(shè)輸入差分狀態(tài)為[a,a,a,0]T，其中a∈F28且非0.那么可以得到輸出差分狀態(tài)中的前2個字節(jié)為0.

(1)

為了得到[a,a,a,0]T的輸入差分狀態(tài)，我們定義明文集合Aα,δ的形式，

(2)

其中,α,δ0,δ1∈F28,α是非0隨機數(shù)，c是常數(shù)，那么對于每一個δ0,δ1，每一個明文集合包含216明文對.

3.2 尋找候選值δ0,δ1

從該集合中選取2個不同的明文狀態(tài)p0∈Aα,δ0,δ1,p1∈Aα,δ0,δ1，滿足僅第1對角有活躍狀態(tài)，其余對角均取常數(shù)值.明文狀態(tài)為

(3)

然后我們定義異或明文狀態(tài)的密鑰為k，且分為4個對角密鑰為k=(k0,k1,k2,k3).第1對角的密鑰為k0=(k0,0,k1,1,k2,2,k3,3)，2個明文狀態(tài)經(jīng)過1輪加密后得到中間狀態(tài)x0,x1及差分x0⊕x1，中間狀態(tài)差分x0⊕x1形式為

(4)

我們期望1輪加密后的中間狀態(tài)差分x0⊕x1符合5輪自適應(yīng)選擇密文區(qū)分器的輸入形式，即有2個對角保持差分活躍狀態(tài).此時如3.1節(jié)所述，如果中間狀態(tài)差分x0⊕x1的第1列中有2 B為0，那么就滿足區(qū)分器輸入狀態(tài)，即式(1).

令f=SR°SB°ARK表示MC之前的操作，則f(p0)和f(p1)的第1列差分記為

(5)

其中S為SB的簡記，我們令式(5)的前3個字節(jié)簡記為

β0=S(k0,0⊕α)⊕S(k0,0),β1=S(k1,1⊕α⊕δ0)⊕S(k1,1⊕δ0),β2=S(k2,2⊕α⊕δ1)⊕S(k2,2⊕δ1).

為了滿足式(1)，需要滿足β0=β1=β2,即β0=β1=β2時，中間狀態(tài)第1列為0,0,z2,z3，這樣就可以滿足5輪區(qū)分器的輸入要求，即在第2，3對角差分活躍.如圖3所示:

Fig. 3 One round of encryption operation圖3 1輪加密操作

如果我們令δ0,δ1遍歷有限域F28×F28所有值可以得到至少4個值能夠保證z0=z1=0，即，

(δ0,δ1)=(k0,0⊕k1,1,k0,0⊕k2,2), (δ0,δ1)=(k0,0⊕k1,1,α⊕k0,0⊕k2,2), (δ0,δ1)=(α⊕k0,0⊕k1,1,k0,0⊕k2,2), (δ0,δ1)=(α⊕k0,0⊕k1,1,α⊕k0,0⊕k2,2)

.

這樣我們就可以找到候選值δ0,δ1，即找到正確密鑰信息k0,0⊕k1,1和k0,0⊕k2,2.

3.3 猜測正確密鑰

vd(R(p′0⊕k)⊕R(p′0⊕k))=vd(0,1,1,0).

(6)

那么就可以篩選出正確密鑰，通過對7個新的明文對測試每個對角剩余的216個候選密鑰來檢測式(6)是否成立，如果成立，那么就可能過濾所有錯誤密鑰.為了減少復(fù)雜度，我們對明文的4個對角狀態(tài)獨立進(jìn)行檢測，即對于每一個新的明文對，首先猜測新明文對(p′0,p′1)第1對角剩余的216密鑰，經(jīng)過一輪加密后，滿足式(6)的密鑰篩選概率為2-16；然后再依次猜測第2，3和4對角密鑰，經(jīng)過一輪加密后，分別滿足式(6)的密鑰篩選概率均為2-16；最后就可以和隨機置換區(qū)分開.

3.4 算法的主要攻擊過程

主要攻擊過程由6個步驟構(gòu)成：

1) 選擇滿足式(3)的明文狀態(tài)(p0,p1)；

2) 對所選的明文狀態(tài)進(jìn)行6輪加密操作得到對應(yīng)的密文對(c0,c1)；

4) 取其中5對新的密文對進(jìn)行6輪解密操作得到對應(yīng)的新的明文對(p′0,p′1)；

5) 檢查新的明文對(p′0,p′1)經(jīng)過一輪加密后的狀態(tài)差分是否滿足式(6)；

6) 滿足式(6)的密鑰則為正確密鑰，不滿足的則為錯誤密鑰.

攻擊過程如算法1所示：

算法1.6輪AES密鑰恢復(fù)攻擊算法.

輸入：251.5個不同的明文；

輸出：密鑰k0

① forδ0from 0 to 28-1 do

② forδ1from 0 to 28-1 do

④c0←enck(p0,6),c1←enck(p1,6)；/*明文加密6輪得到密文*/

⑤ formfrom 0 to 5 do

/*取5對新密文對*/

|I|=1；

/*新密文對解密6輪得到新明文對*/

⑧P←P∪{(p′0,p′1)}

⑨ for all (p′0,p′1)∈Pdo

⑩ ifwt(vd(enck(p′0⊕k,1)⊕

enck(p′1⊕k,1)))≠2 then

/*檢查是否滿足判定條件(6)*/

3.5 復(fù)雜度計算

1) 數(shù)據(jù)復(fù)雜度

首先，該5輪自適應(yīng)選擇密文區(qū)分器的概率為2-46，可以構(gòu)造223.5選擇明文和247自適應(yīng)密文.文獻(xiàn)[14]為了減少數(shù)據(jù)復(fù)雜度，對區(qū)分器進(jìn)行了優(yōu)化，令3輪加密后的第2個對角差分為0，則密文狀態(tài)僅有3列活躍，最終構(gòu)造了235.5選擇明文和239自適應(yīng)密文.

2) 時間復(fù)雜度

對于每一個對角，猜測密鑰的集合應(yīng)該是216而不是2×216.因為δ0,δ1將遍歷所有216個可能的值.足以測試k1,1=k0,0⊕δ0，k2,2=k0,0⊕δ1，并沒有必要測試k1,1=k0,0⊕δ0⊕α和k2,2=k0,0⊕δ1⊕α.并且當(dāng)我們知道k1,1⊕k0,0和k2,2⊕k0,0的值時，我們就可以得到第3個密鑰信息k2,2⊕k1,1.

步驟5中復(fù)雜度的計算：對于每一個新明文對(p′0,p′1)的每一個對角的密鑰我們要檢查是否滿足式(6)，那么每一次需要2×4次S盒查表，共需要216次和5×239×216新的明文，所以這一步所需的時間復(fù)雜度為

2×4×(5×239×216)×216≈276.32.

另外，在對新明文檢查時，我們對新明文的4個對角狀態(tài)同時且獨立得去檢查，過濾掉不滿足式(6)的密鑰，該步所需時間復(fù)雜度為276.32×4≈278.32.

所以總時間復(fù)雜度為278.32，一輪加密約等于20次查表或16次S盒查表[9]，所以總時間復(fù)雜度約為272次6輪加密.

3) 空間復(fù)雜度

我們需要存儲239×5×216新明文，因此需要一個順序表大小為257.42.另外去檢查滿足條件的狀態(tài)對時，需要把明文經(jīng)過一輪后的狀態(tài)分別放到大小為232的存儲表中去尋找碰撞.所以最終需要空間復(fù)雜度為257.42+232×4≈258個AES-128塊.

4 小版本AES實驗驗證

小版本[18]AES(small-scale AES)分組長度為64 b，64 b明文將內(nèi)部狀態(tài)初始化為一個4×4半字節(jié)矩陣，在矩陣中每一個字是4 b.密鑰長度為64 b.輪函數(shù)和AES一致，其中字節(jié)代替變換使用的是4 b S盒.行移位變換和列混合變換保持不變.

采用和第3節(jié)相同的攻擊方法，我們可以得到復(fù)雜度分析：

數(shù)據(jù)復(fù)雜度.區(qū)分器在小版本AES的規(guī)模下成立的概率應(yīng)為2-23，因為AES的字節(jié)是屬于有限域F28，小版本AES的半字節(jié)屬于有限域F24，所以經(jīng)過優(yōu)化后最后區(qū)分器概率為2-35，我們構(gòu)造了218選擇明文和220對自適應(yīng)密文.我們考慮了5對新的密文對，去檢查是否符合式(6).因為這5對新的密文對滿足式(4)的概率為2-8×5=2-40，因此錯誤密鑰通過的概率為220×5×28×2-40≈2-11.68?1.所以用5對就可以過濾掉錯誤密鑰.因此，要找到2個半字節(jié)的密鑰，我們需要218×28=226選擇明文和220×28×5≈230.32自適應(yīng)選擇密文.

時間復(fù)雜度.對于總計算復(fù)雜度，測試猜測密鑰的集合應(yīng)該是28.考慮δ0,δ1將遍歷所有28個可能的值.因此，步驟5：對于5對中的每一對新明文對(p′0,p′1)的每一個密鑰我們要檢查是否滿足式(6)，那么每一次需要2×4次S盒查表，共需要28次和5×220×28新的明文，所以這一步所需的時間復(fù)雜度為

2×4×(5×220×28)×28≈241.32.

另外，在對新明文檢查時，我們可以對新明文的4個對角狀態(tài)同時且獨立得去檢查，過濾掉不滿足式(6)的密鑰，該步所需時間復(fù)雜度為241.32×4≈243.32.

所以總時間復(fù)雜度為243.32，一輪加密約等于20次查表或16次S盒查表，所以總時間復(fù)雜度約為236次6輪加密.

空間復(fù)雜度.我們需要存儲5×220×28新明文，因此需要一個順序表大小為230.32.另外去檢查滿足條件的狀態(tài)對時，需要把新明文一輪加密后的狀態(tài)分別放到大小為216的存儲表中去尋找碰撞.所以最終需要空間復(fù)雜度為230.32+216×4≈230.32個AES-64塊.

通過在C/C++語言中實現(xiàn)了小版本AES，如算法1所示，總共進(jìn)行了10次測試.所使用的計算機參數(shù)為lntel?CoreTMi7-9700 CPU @ 3.00 GHz，內(nèi)存為16 GB.實驗驗證了所提出的密鑰恢復(fù)攻擊的有效性，所以實驗結(jié)果支持理論結(jié)果.

5 總 結(jié)

在本文中，我們提出了一種對于6輪AES新的密鑰恢復(fù)攻擊結(jié)果.該攻擊過程利用了基于交換等價提出的5輪自適應(yīng)選擇密文的區(qū)分器和AES列混合操作系數(shù)矩陣的基本性質(zhì)，通過在5輪自適應(yīng)選擇密文區(qū)分器前擴展一輪，利用列混合操作系數(shù)矩陣的基本性質(zhì)和0差分性質(zhì)恢復(fù)第1輪所需的密鑰.結(jié)果表明，本文提出的密鑰恢復(fù)攻擊結(jié)果在秘密S盒下是最優(yōu)的結(jié)果.另外，我們用一個小版本的AES去測試來支撐理論結(jié)果的正確性.