譚 林， 閆雪萍， 戚文峰

戰(zhàn)略支援部隊信息工程大學， 鄭州 450001

1 引言

高級加密標準AES[1]是目前使用最多、研究最多的分組密碼算法. 許多密碼算法、Hash 函數(shù)和偽隨機數(shù)發(fā)生器采用類似AES 的結(jié)構(gòu)來設(shè)計， 甚至直接采用減輪AES 作為核心部件. 從AES 提出至今二十多年來， 學者們進行了大量密碼分析研究. 雖然未對AES 產(chǎn)生實際的威脅， 但學術(shù)界持續(xù)的研究促進了人們對AES 密碼結(jié)構(gòu)性質(zhì)的認識和AES 型密碼分析技術(shù)的發(fā)展. 對AES 主要的密碼分析技術(shù)有: 積分[1，2]、不可能差分[3-6]、零相關(guān)線性[7-10]、子空間路徑[11]、混合差分[12-16]、yoyo[17]、交換攻擊[18]、飛鏢[19]、中間相遇攻擊[20]等. 2016 年以前， 針對AES 的區(qū)分攻擊最多只到4 輪， 包括經(jīng)典的積分、不可能差分和零相關(guān)線性等. 利用AES 列混合矩陣的特點， 文獻[9，10，21] 給出了密鑰相關(guān)的5 輪區(qū)分器.在2017 年歐密會上， Grassi 等人[16]發(fā)現(xiàn)了5 輪AES 具有“8 的倍數(shù)” 結(jié)構(gòu)性差分特征， 首次給出了5輪AES 與密鑰獨立的區(qū)分器. 文獻[22] 給出了“8 的倍數(shù)” 結(jié)構(gòu)性差分特征的一般化證明. 該特征揭示了5 輪AES 具有結(jié)構(gòu)性的不隨機性， 基于此， 文獻[12] 提出了針對AES 的混合差分分析. 在2017 年亞密會上， R?njom 等人[17]將yoyo 技術(shù)應(yīng)用于SPN 型密碼分析， 給出了首個與密鑰獨立的6 輪AES區(qū)分器. Yoyo 技術(shù)與混合差分具有很強的關(guān)聯(lián)性， 文獻[23] 指出了AES 的4 輪yoyo 區(qū)分器等價于廣義混合差分區(qū)分器. 文獻[14，15] 利用混合差分技術(shù)給出了減輪AES 的具有實際數(shù)據(jù)和存儲復(fù)雜度的攻擊方案. 其中， 5 輪AES-128 的混合差分攻擊的復(fù)雜度為224， 這是目前選擇明文模式下5 輪AES 密鑰恢復(fù)攻擊的最好結(jié)果. 在2019 年亞密會上， Bardeh 等人[18]將混合差分、yoyo 等技術(shù)與概率分析方法相結(jié)合， 給出了首個選擇明文模式下的6 輪AES 區(qū)分器， 這是目前為止對AES 區(qū)分分析的最好結(jié)果. 在2020 年歐密會上， Dunkelman 等人[19]基于混合差分技術(shù)提出“折回鏢” 攻擊， 給出了適應(yīng)性選擇明密文模式下5 輪AES 密鑰恢復(fù)攻擊的最好結(jié)果. 本文在文獻[14，15] 的基礎(chǔ)上， 適當?shù)靥嵘龜?shù)據(jù)和存儲復(fù)雜度， 改進了6 輪AES 混合差分攻擊的時間復(fù)雜度， 使得總復(fù)雜度為262.62. 在本文中， 總復(fù)雜度是指數(shù)據(jù)復(fù)雜度、時間復(fù)雜度和存儲復(fù)雜度的最大值. 表1 給出了目前5 輪以上AES-128 密鑰恢復(fù)攻擊的主要結(jié)果， 數(shù)據(jù)復(fù)雜度中ACC 表示適應(yīng)性選擇明密文， 其余是選擇明文.

表1 5 輪以上AES-128 密鑰恢復(fù)攻擊主要結(jié)果Table 1 Key recovery attacks on 5 and more rounds of AES-128

PRINCE[24]是Borghoff等在2012 年亞密會上提出的一種AES-like 低時延輕量級分組算法， 適用于物聯(lián)網(wǎng)環(huán)境下的加密. 它基于FX 結(jié)構(gòu)設(shè)計， 采用α反射技術(shù)， 加解密具有對稱性， 在硬件實現(xiàn)上具有優(yōu)勢. 2014 年P(guān)RINCE 的設(shè)計者發(fā)起了針對該算法實際攻擊的公開挑戰(zhàn)， 使其成為研究的熱點.對PRINCE 主要的密碼分析技術(shù)有: 積分[25-27]、差分[28，29]、截斷差分[26，30]、多重差分[23，31]、高階差分[25]、中間相遇[28，32]等. 目前， PRINCE 的密鑰恢復(fù)攻擊最長的是10 輪多重差分攻擊[31]和10 輪中間相遇攻擊[28，32]. 由于PRINCE 具有AES-like 結(jié)構(gòu)， 針對AES 的許多分析技術(shù)可以直接應(yīng)用于PRINCE 和PRINCEcore的分析. 文獻[23] 將混合差分攻擊技術(shù)應(yīng)用于PRINCE， 給出了5 輪PRINCEcore的混合差分密鑰恢復(fù)攻擊. 本文將改進的6 輪AES 混合差分攻擊應(yīng)用到6 輪的PRINCE和PRINCEcore， 給出了總復(fù)雜度分別為230.66和222的密鑰恢復(fù)攻擊， 其中6 輪PRINCEcore的攻擊結(jié)果優(yōu)于積分攻擊和差分攻擊. 表2 給出了目前6 輪以上PRINCE 和PRINCEcore的密鑰恢復(fù)攻擊的主要結(jié)果.

表2 6 輪以上PRINCE 和PRINCEcore 密鑰恢復(fù)攻擊主要結(jié)果Table 2 Key recovery attacks on 6 and more rounds of PRINCE and PRINCEcore

2 準備工作

在AES 和PRINCE 算法中， 通常將明文、密文、輪密鑰以及中間狀態(tài)用4×4 的矩陣來描述， 元素順序如圖1 所示. 記col(i) 表示矩陣的第i列， SR(col(i)) 表示矩陣的第i條反對角線， SR-1(col(i))表示矩陣的第i條對角線，i= 0，1，2，3. 對矩陣X， 記X{i1，i2，···，in}表示X的第i1，i2，···，in個元素，Xcol(i1，i2，···，in)表示X的第i1，i2，···，in列.X的對角線和反對角線采用相似的方式表示.

圖1 狀態(tài)矩陣元素順序Figure 1 Order of elements in state matrix

文獻[12] 提出了明文混合結(jié)構(gòu)的概念并應(yīng)用于減輪AES 的混合差分分析， 文獻[15] 給出了混合結(jié)構(gòu)和混合四元組更一般的定義.

定義 1[15]設(shè)X1，X2，X3，X4是四個4×4 的矩陣， 它們僅在第j列的值不同， 0≤ j ≤3.

3 AES 的6 輪混合差分攻擊

3.1 AES 簡介與4 輪混合差分區(qū)分器

AES 算法的分組長度為128 比特， 密鑰長度支持128、192 和256 比特， 相應(yīng)的迭代輪數(shù)分別為10、12 和14， 分別用AES-128、AES-192 和AES-256 來表示. 輪變換包括以下4 個操作:

- 字節(jié)替換(SB): 狀態(tài)矩陣的每個字節(jié)查詢同一個8 比特的S 盒.

- 行移位(SR): 將狀態(tài)矩陣的第i行循環(huán)左移i個字節(jié)， 其中i=0，1，2，3.

- 列混合(MC): 用F28上一個MDS 矩陣乘以狀態(tài)矩陣的每一列.

- 輪密鑰加(AK): 將狀態(tài)與輪密鑰逐比特異或.

AES 算法中明文先與主密鑰異或，再進行相應(yīng)的輪變換，最后一輪沒有MC.關(guān)于AES 詳細的介紹參見文獻[1]. 記Kr表示第r輪輪密鑰，它由主密鑰K0通過密鑰擴展算法產(chǎn)生. 記R=AK°MC°SR°SB表示AES 的輪函數(shù)， 和絕大多數(shù)文獻一樣， 用Rn表示n輪AES， 最后一輪沒有MC. 本文的研究對象是6 輪AES-128.

在文獻[12] 中， Grassi 發(fā)現(xiàn)了明文混合結(jié)構(gòu)經(jīng)過4 輪AES 后保持差分的某種關(guān)聯(lián)性， 由此構(gòu)造了4輪混合差分區(qū)分器.

定理1[12]設(shè)(X1，X2，X3，X4)是AES 算法中一個混合四元組，則(R4(X1)+R4(X2))SR(col(i))=0當且僅當(R4(X3)+R4(X4))SR(col(i))=0，i ∈{0，1，2，3}.

在4 輪AES 混合差分區(qū)分器的基礎(chǔ)上往前增加一輪， 文獻[16] 給出了首個與密鑰獨立的5 輪AES區(qū)分器“8 的倍數(shù)”. 選擇第0 條對角線遍歷、其余12 字節(jié)取任意固定值的232個明文， 經(jīng)過1 輪后狀態(tài)僅在第一列活躍. 對任意的狀態(tài)對(X1，X2)， 存在8n-1 個對(X3，X4) 與其構(gòu)成混合四元組， 所以密文差分在任意反對角線為0 的密文對個數(shù)是8 的倍數(shù). 文獻[12] 基于4 輪AES 的混合差分區(qū)分器給出了5 輪密鑰恢復(fù)攻擊， 其猜測K0的某條對角線， 在第一輪MC 后構(gòu)造混合四元組， 利用定理1 來判斷猜測密鑰的正確性， 恢復(fù)全部密鑰的復(fù)雜度為234. Bar-On 等人[14，15]利用更少的混合結(jié)構(gòu)和預(yù)處理表等技術(shù)進一步改進了5 輪AES 的混合差分攻擊， 總復(fù)雜度為224. 在5 輪混合差分攻擊的基礎(chǔ)上往后增加一輪， Bar-On 等也給出了具有實際數(shù)據(jù)和存儲復(fù)雜度的6 輪混合差分攻擊， 數(shù)據(jù)、存儲復(fù)雜度均為230.5，時間復(fù)雜度為273. 本節(jié)在文獻[14，15] 的基礎(chǔ)上， 適當?shù)靥嵘龜?shù)據(jù)和存儲復(fù)雜度， 改進了6 輪AES 混合差分攻擊的時間復(fù)雜度， 使得總復(fù)雜度為262.62.

3.2 改進6 輪AES 混合差分攻擊的時間復(fù)雜度

交換第5 輪的AK 和MC， 用等效的輪密鑰加AK′來表示， 6 輪AES 加密過程如圖2 所示. 記第1輪MC 后的狀態(tài)為X， 第5 輪MC 后的狀態(tài)為W，Z=MC-1(W). 我們選擇第0 條對角線遍歷、其余12 字節(jié)取任意固定值的明文結(jié)構(gòu)， 每個結(jié)構(gòu)約有263個明文對. 猜測K0的第0 條對角線K0，SR-1(col(0))，在狀態(tài)X處構(gòu)造混合四元組(X1，X2，X3，X4). 由于AK 操作不改變混合結(jié)構(gòu)關(guān)系， 由定理1， 如果存在某個i ∈{0，1，2，3}使得(Z1+Z2)SR(col(i))= 0， 則(Z3+Z4)SR(col(i))= 0. 猜測第6 輪部分輪密鑰， 解密至狀態(tài)Z， 利用4 輪區(qū)分器對猜測密鑰進行篩選. 文獻[15] 稱滿足存在i ∈{0，1，2，3}使得(Z1+Z2)SR(col(i))=0 的明文對(P1，P2) 為Good Pair. 篩選密鑰需要至少有一對Good Pair， 平均意義下找到一個Good Pair 的概率為4×2-32=2-30， 所以每次密鑰猜測需要對至少230個明文對進行部分加密和解密. 我們對密文對施加限制條件來提高找到Good Pair 的概率. 選擇密文差分有兩條反對角線為0 的密文對(C1，C2)， 例如(C1+C2)SR(col(2，3))=0， 則(Z1+Z2)col(2，3)=0， 從而Good Pair 存在的概率為2-16×4 = 2-14. 這樣， 對每次密鑰猜測所要進行操作的數(shù)據(jù)對從230降低到214， 改進了篩選密鑰的計算復(fù)雜度， 付出的代價是為了找到滿足密文差分條件的密文對需要增加數(shù)據(jù)復(fù)雜度. 為獲得滿足條件的214個數(shù)據(jù)對， 需要215個明文結(jié)構(gòu). 下面詳細介紹我們6 輪AES 混合差分攻擊的流程.

圖2 6 輪AES 算法Figure 2 6 rounds of AES

對L中每個明文對和K0，SR-1(col(0))的每次猜測， 構(gòu)造表L1，i和L2，i的復(fù)雜度為2×216×6×2≈220.58次S 盒計算， 表匹配找碰撞的復(fù)雜度為2×216×4 = 219次查表， 相當于219次一輪加密， 驗證碰撞確定的K6，SR(col(0))的計算復(fù)雜度為210×10×4≈215.32次S 盒計算. 所以使用中間相遇技術(shù)改進后步驟(2)(a) 的總復(fù)雜度為(214×232×(220.58/20+219+215.32/20))/6≈262.62次6 輪AES 加密. 步驟(2)(b) 的計算復(fù)雜度為(214×4×232×16×4)/(20×6)≈247.09， 步驟(3) 和步驟(4) 的計算量相比之下可以忽略. 改進的6 輪AES 混合差分攻擊算法1 的數(shù)據(jù)復(fù)雜度為215×232= 247， 時間復(fù)雜度為262.62.篩選滿足密文差分條件的明文對時構(gòu)建Hash 表的大小為232， 表L1，i和L2，i的大小均為216， 表T的大小約為28， 所以算法的主要存儲復(fù)雜度為明密文數(shù)據(jù)存儲. 算法成功的概率等于L中214個明文對存在Good Pair 的概率1-(1-2-14)214≈1-e-1≈63%. 如果將密文篩選條件(C1+C2)SR(col(2，3))=0 改為任意兩條反對角線差分為0， 算法1 仍然有效. 我們?nèi)栽?14個對中尋找Good Pair， 數(shù)據(jù)和存儲復(fù)雜度可降為247/6≈244.42， 時間復(fù)雜度和成功率不變.

算法1 AES 的6 輪混合差分攻擊選擇215 個明文結(jié)構(gòu)， 每個明文結(jié)構(gòu)第0 條對角線遍歷、其余字節(jié)取隨機固定值. 詢問加密機獲取它們的密文.對每個明文結(jié)構(gòu)， 以密文的第2、3 條反對角線的值構(gòu)建Hash 表， 將滿足密文差分(C1 +C2)SR(col(2，3)) = 0 的明文對(P1，P2) 存入表L 中.for L 中每個明文對(P1，P2) do for 猜測K0，SR-1(col(0)) do部分加密1 輪到(X1，X2)， 由X1，col(0) 和X2，col(0) 構(gòu)造7 個混合結(jié)構(gòu)(Xj3，Xj4)， 1 ≤j ≤7.對Xj3，Xj4 部分解密1 輪得到其明文Pj3，Pj4， 查詢獲得相應(yīng)的密文Cj3，Cj4， 1 ≤j ≤7.for 猜測K6，{0，13} do分別對(C1，C2)， (C13，C14)， (C23，C24) 部分解密計算ΔZi 關(guān)于ΔW{0，1} 的部分和， 并將它們級聯(lián)以K6，{0，13} 為索引存入表L1，i 中， i = 0，1，2，3;end for 猜測K6，{7，10} do分別對(C1，C2)， (C13，C14)， (C23，C24) 部分解密計算ΔZi 關(guān)于ΔW{2，3} 的部分和， 并將它們級聯(lián)以K6，{7，10} 為索引存入表L2，i 中， i = 0，1，2，3;end for 0 ≤i ≤3 do對表L1，i 和L2，i 進行匹配找碰撞， 將碰撞對應(yīng)的索引K6，{0，7，10，13} 存儲到表T 中;for T 中K6，SR(col(0)) 的每個候選值do部分解密(Cj3，Cj4)， 如果存在(Zj3 +Zj4)i /= 0， 3 ≤j ≤7， 則將該候選值從表T 中刪除;end if T 不是空集then利用(Z1 +Z2)SR(col(i)) = (Zj3 +Zj4)SR(col(i)) = 0， 1 ≤j ≤7 分別篩選K6 的另外三條反對角線.end end end end對候選的K6 進行加密驗證.

4 PRINCE 和PRINCEcore 的6 輪混合差分攻擊

4.1 PRINCE 算法簡介

PRINCE 算法的分組長度為64 比特， 密鑰長度為128 比特， 迭代輪數(shù)為12 輪， 算法結(jié)構(gòu)如圖3 所示.64 比特狀態(tài)用4×4 的矩陣來描述時， 矩陣中每個元素是一個4 比特塊. 128 比特的密鑰被分為2 個64比特的子密鑰k0和k1， 其中k1應(yīng)用于算法的核心部件PRINCEcore，k0和k′0用于算法輸入、輸出兩端的白化， 這里k′0=(k0?1)+(k0?63). PRINCEcore采用對稱結(jié)構(gòu)， 中間2 輪是對合的， 前后5 輪除輪常數(shù)不同外互為逆變換. 輪常數(shù)滿足RCi+RC11-i=α， 0≤i ≤11， 這里α是固定常數(shù). PRINCE算法的解密可以通過加密操作來實現(xiàn)， 即D(k0‖k′0‖k1)(·) =E(k′0‖k0‖k1+α)(·). 本文使用Rn表示n輪的PRINCE 變換， 輪變換包括以下5 個操作:

圖3 PRINCE 算法Figure 3 PRINCE cipher

-S層: 狀態(tài)矩陣的16 個塊同時查詢一個4 比特的S 盒.

- 擴散層(M′): 使用F2上的一個64×64 的矩陣乘以64 比特狀態(tài)，M′-1=M′.

- 行移位(SR): 將狀態(tài)矩陣的第i行循環(huán)左移i個塊， 其中i=0，1，2，3.

- 輪常數(shù)加(ARC): 將狀態(tài)與一個64 比特輪常數(shù)RCi異或， 0≤i ≤11.

- 密鑰加(AK): 將狀態(tài)比特異或64 比特密鑰k1.

4.2 6 輪PRINCE 的混合差分攻擊

由于PRINCE 與AES 具有相似的結(jié)構(gòu)， 所以我們能夠得到如下4 輪PRINCE 的混合差分性質(zhì).

定理2 設(shè)(X1，X2，X3，X4)是PRINCE 的一個混合四元組，則(R4°SR(X1)+R4°SR(X2))col(i)=0當且僅當(R4°SR(X3)+R4°SR(X4))col(i)=0，i ∈{0，1，2，3}.

證明: 忽略不影響差分的AK 和ARC，

交換SR 與S的順序，

與4 輪AES 相比最后少一個SR. 4 輪混合差分性質(zhì)與S 盒和列混合矩陣的細節(jié)無關(guān)， 故結(jié)論成立.

圖4 6 輪PRINCE 算法Figure 4 6 rounds of PRINCE

4.3 6 輪PRINCEcore 的混合差分攻擊

6 輪PRINCEcore如圖5 所示. 對6 輪PRINCEcore的混合差分攻擊與PRINCE 相似， 選取的明文結(jié)構(gòu)和混合差分區(qū)分器均相同. 不同之處在于PRINCEcore沒有白化密鑰， 輪密鑰都是k1， 我們只猜測k1的某一列即可進行明文的部分加密和密文的部分解密， 故計算復(fù)雜度與PRINCE 相比有較大減少. 下面介紹6 輪PRINCEcore的混合差分攻擊流程.

圖5 6 輪PRINCEcore 算法Figure 5 6 rounds of PRINCEcore

算法2 PRINCEcore 的6 輪混合差分攻擊選擇一個明文結(jié)構(gòu)， 在第0 列取所有可能值， 其他字節(jié)取任意固定值. 詢問加密機獲取它們的密文.將216 個密文按照第3 列的值構(gòu)建Hash 表， 構(gòu)造滿足(C1 +C2)col(3) = 0 的明文對(P1，P2)， 任選其中210個對存儲到表格L 中.for L 中每個明文對(P1，P2) do for 猜測k1，{0，1} do對(C1，C2) 部分解密計算ΔZi 關(guān)于ΔW{0，1} 的部分和， 以k1，{0，1} 為索引存入表L1，i 中，i = 0，1，2，3;end for 猜測k1，{2，3} do對(C1，C2) 部分解密計算ΔZi 關(guān)于ΔW{2，3} 的部分和， 以k1，{2，3} 為索引存儲到L2，i 中，i = 0，1，2，3;end for 0 ≤i ≤3 do對表L1，i 和L2，i 進行匹配找碰撞， 將碰撞對應(yīng)的索引k1，col(0) 存儲到表T 中;for T 中k1，col(0) 的每個候選值do對(P1，P2) 進行一輪部分加密得到(X1，col(0)，X2，col(0));for 1 ≤j ≤7 do由X1，col(0) 和X2，col(0) 構(gòu)造(Xj3，Xj4);對(Xj3， Xj4) 部分解密一輪得到明文(Pj3，Pj4)， 查詢獲得密文(Cj3，Cj4);部分解密(Cj3，Cj4)， 如果ΔZi /= 0， 將該候選值從T 中刪除;end end if T 不是空集then利用(Z1 +Z2)SR-1(col(-i mod 4)) = (Zj3 +Zj4)SR-1(col(-i mod 4)) = 0， 1 ≤j ≤7 分別篩選K0 的另外三列.end end end對候選的k1 進行加密驗證.

5 結(jié)論

文獻[14] 和[15] 表明混合差分攻擊可以將數(shù)據(jù)和存儲復(fù)雜度限制到較小的程度， 而不追求時間復(fù)雜度的最優(yōu). 本文在文獻[14，15] 中的6 輪AES-128 混合差分攻擊的基礎(chǔ)上， 通過對密文差分增設(shè)條件限制來提高Good Pair 出現(xiàn)的概率， 減少了每次密鑰猜測需要驗證的數(shù)據(jù)對數(shù)， 將6 輪AES-128 混合差分攻擊的時間復(fù)雜度由273改進到262.62， 數(shù)據(jù)和存儲復(fù)雜度提高到244.42. 在所有6 輪AES-128 的密鑰恢復(fù)攻擊中， 本文攻擊方案的總復(fù)雜度優(yōu)于除了積分攻擊以外的其他所有攻擊. 將改進的6 輪混合差分攻擊應(yīng)用于PRINCE 和PRINCEcore， 我們給出了總復(fù)雜度分別為230.66和222的密鑰恢復(fù)攻擊， 其中6輪PRINCEcore的攻擊結(jié)果優(yōu)于積分攻擊和差分攻擊. 如何以追求時間復(fù)雜度、總復(fù)雜度最優(yōu)為目標改進AES 和PRINCE 的混合差分攻擊是值得后續(xù)深入研究的問題.