RAIN-128算法的中間相遇攻擊

杜小妮 鄭亞楠 梁麗芳 李鍇彬

①(西北師范大學數學與統計學院 蘭州 730070)

②(西北師范大學密碼技術與數據分析重點實驗室 蘭州 730070)

③(西北師范大學計算機科學與工程學院 蘭州 730070)

1 引言

近年來，隨著射頻識別技術和無線傳感器的發展與應用，為了保障這些資源受限設備中的信息安全，功耗低和軟硬件實現面積小的輕量級分組密碼算法被廣泛應用。然而輕量級分組密碼算法追求低功耗與高效率并存，這一矛盾會使算法的安全性無法得到保證，因此對輕量級分組密碼算法進行安全性分析是非常有必要的。

1977年Diffie和Hellman[1]提出中間相遇攻擊的思想，并將其應用到DES[2]的安全性分析中，之后廣泛應用于Feistel結構的密碼算法分析中；隨后在FSE 2008上Demirci和Sel?uk[3]利用文獻[1]的思想，構造了AES[4]的4輪中間相遇區分器，首次提出了8輪AES-256的中間相遇攻擊，是目前針對SPN結構分組密碼最經典的中間相遇攻擊，一般稱之為Demirci-Sel?uk中間相遇攻擊(DS-MITM)；2010年，Dunkelman等人[5]利用差分枚舉技術、多重集技術和密鑰橋技術對文獻[3]方法進行了改進，降低了復雜度；隨后Derbez等人[6]通過搜索得到了大量減輪AES-256的高效路徑，進一步降低了復雜度。在ASIACRYPT 2018上，Shi等人[7]首次將自動化搜索模型與算法的相關約束條件結合，實現了SKINNY[8]的22輪中間相遇攻擊；2020年，Chen等人[9]利用密鑰橋技術，使得密鑰恢復攻擊的復雜度有所降低；為了進一步降低算法的復雜度，肖鈺汾等人[10]在2021年對SKINNY的中間相遇區分器進行自動化搜索時，將搜索過程中一部分狀態的猜測轉換為密鑰的猜測，同時結合密鑰橋技術，降低了密鑰的猜測量和區分器的存儲復雜度。

截斷差分分析[11]是差分分析[12]的一個變體。與經典差分分析考慮具體差分值不同，截斷差分只考慮差分的一部分性質，比如差分落在某個集合里，差分的某一位為0等。

RAIN是由曹梅春等人[13]于2021年提出的一種面向軟硬件和門限實現的輕量級分組密碼算法，并額外的調柄輸入形成可調分組密碼，增加了算法的靈活性。具有類似結構的算法還包括QARMA[14]，CRAFT[15]等。設計者從差分分析[12]、不可能差分分析[16]、積分分析[17]和不變子空間分析[18]4個方面對算法進行了安全性評估，結果顯示，算法具有較大的安全冗余，在PC, ARM平臺和FPGA平臺上都具有出色的實現性能。

本文首次對RAIN-128進行中間相遇攻擊，表1給出了8輪和10輪攻擊的復雜度對比，主要貢獻如下：

表1 RAIN算法的8/10輪中間相遇攻擊復雜度

(1) 通過分析算法的結構特性和截斷差分特征，利用差分枚舉技術找到了4輪區分器，實現了8輪中間相遇攻擊，使得預計算階段的時間復雜度為P次8輪加密，存儲復雜度為 275bit。

(2) 類似地，利用(1)中的方法找到了6輪區分器，并實現了10輪中間相遇攻擊。其中預計算階段的時間復雜度為2214次10輪加密，存儲復雜度為2219bit。

(3) 利用算法的結構特性和等價密鑰MC-1(K)，減少了在線攻擊階段狀態字節的猜測量，使得在線攻擊階段的時間復雜度為2109次8/10輪加密，數據復雜度是 272個選擇明文。

本文結構安排如下：第2節對本文用到的符號進行說明，并簡要介紹RAIN算法和DS-MITM攻擊；第3節對RAIN-128進行8輪中間相遇攻擊；第4節給出RAIN-128的10輪中間相遇攻擊；第5節總結全文。

2 預備知識

2.1 符號說明

2.2 RAIN算法介紹

RAIN[13]是一族輕量級分組密碼算法，分組長度支持64 bit和128 bit，對應的密鑰長度為64 bit和128 bit，迭代輪數為30輪和36輪，分別記為RAIN-64和RAIN-128。

算法的輪函數由列混合、 字節替換、行移位和輪可調密鑰加4種運算構成。r輪(r=30/36)算法的整體結構如圖1所示，第i輪的輪函數結構如圖2所示。將64/128 bit的明文、中間狀態、密文統稱為密碼狀態。令M=m0||m1||...||m15表示一個密碼狀態，對于1≤s ≤15，當分組長度為64 bit時，ms的長度是4 bit，即半字節；當分組長度為128 bit時，ms的長度是8 bit，即一個字節。按照行的順序，依次將密碼狀態輸入到4×4的矩陣中，其矩陣形式為

圖1 RAIN算法的整體結構

圖2 RAIN算法的輪函數結構

RAIN-128的加密流程，具體如下：

(1) 初始白化：將明文P與白化密鑰K按字節進行異或操作。

(2) 列混合：密碼狀態左乘矩陣

(3) 字節替換：對密碼狀態中的16 Byte分別進行S盒替換，采用8 bit的S盒。

(4) 行移位：采用與AES相同的行移位變換，即密碼狀態的第2～4行分別向左循環移位1 Byte,2 Byte, 3 Byte。

(5) 輪可調密鑰加：將輪可調密鑰與步驟(4)的輸出進行異或操作。

2.3 DS-MITM攻擊

在DS-MITM的分析過程中，將r輪加密算法E分解為如圖3所示的E0,E1和E2，即E=E2?E1?E0。其中E1為加密算法的第r0輪至第r0+r1輪，且為構建的區分器。E0為加密算法的第0輪至第r0-1輪，E2為加密算法的第r0+r1+1輪至第r-1輪。

圖3 DS-MITM模型

圖4 4輪RAIN-128算法的中間相遇區分器

定義1(δ-集)[3]若RAIN-128的1 Byte遍歷256個值，其它15 Byte取固定值，這樣的結構被稱為δ-集。其中，遍歷256個值的字節為活躍字節，其余為非活躍字節。

在圖3中，對于區分器E1，首先需確定δ-集活躍字節的位置和區分器輸出字節的位置；其次根據δ-集在第r0輪至第r0+r1輪的差分傳播路徑，以及輸出字節在第r0+r1輪至第r0輪的差分傳播路徑，猜測兩條路徑在每一輪輸入相交的狀態值，窮盡所有相交狀態值，在第r0+r1輪可得到不同的輸出狀態/差分集合，將集合存儲在哈希表中，構成中間相遇區分器。對于E0，需確定在第r0+r1輪形成δ-集的明文集，并猜測部分輪密鑰；然后將明文集加密r輪生成密文，猜測E2的部分輪密鑰，對密文進行解密，求得第r0+r1輪固定字節的輸出狀態/差分，判斷狀態/差分值是否在區分器的哈希表中；若存在，則判斷E0和E2中猜測的密鑰為正確密鑰，否則為錯誤密鑰，再通過窮舉搜索篩選出正確密鑰。

3 RAIN-128的8輪中間相遇攻擊

本節首先介紹RAIN-128的4輪中間相遇區分器，其次利用該區分器實現了8輪攻擊，最后分析了復雜度。

3.1 4輪中間相遇區分器

3.2 8輪RAIN-128的中間相遇攻擊

8輪RAIN-128的中間相遇攻擊由兩個階段組成：預計算階段和在線攻擊階段。攻擊過程如圖5所示。

圖5 8輪RAIN-128算法的中間相遇攻擊

在線攻擊階段：

(1) 選擇28×9=272個明文，這些明文滿足在第0, 4, 6, 8, 9, 12, 15Byte處差分為0，其余9 Byte窮盡即可；

(2) 由于列混合與密鑰加是線性操作，故可交換這兩個操作，具體操作為：

(a)用等價密鑰MC-1(K)異或密碼狀態；

(b) 對(a)中的狀態進行列混合(MC)操作。

記u[i]=MC-1(K[i])，則只需猜測u[5],u[10],u[15] 和ATK0[4, 8, 12]，篩選一對明文，使得這對明文在第2輪輸入狀態差分僅在第0 Byte非0，取其中之一記為P0；

(3) 根據δ-集的性質，以及上述猜測的輪密鑰和P0，可反解P1,P2,...,P255。對P0,P1,...,P255進行8輪加密，得到相應密文；

(5) 猜測ATK6[7, 10, 13]。

(6) 利用上述密鑰值部分解密第 (3) 步得到的密文，可得W5[0]，計算差分集。判斷差分集是否在預計算階段建立的哈希表T中。若在，則猜測的密鑰為正確密鑰，否則為錯誤密鑰。

(7) 通過窮盡搜索的方式篩選出正確密鑰。

上述攻擊步驟中，需要猜測13 Byte，得到18 Byte的密鑰：u[5],u[10],u[15] ,ATK0[4, 8,12],ATK6[7 , 10, 13], ATK7[1, 2, 3, 5, 7, 9, 10, 14, 15]。

3.3 攻擊復雜度分析

預計算階段需猜測8 Byte，計算264×28=272個差分值，因此預計算的時間復雜度為264×28×8/(8×16)=268次加密8輪RAIN-128，存儲復雜度為(28-1)×8×28×8≈275bit。

在線攻擊階段選擇明文量為 272個明文，即數據復雜度為 272個選擇明文。在線攻擊階段需猜測1 3 B y t e，因此在線攻擊的時間復雜度為2104×28×16/(8×16)=2109次加密8輪算法。

4 10輪RAIN-128的中間相遇攻擊

本節實現了RAIN-128 的10輪中間相遇攻擊，因攻擊過程與第3節類似，故僅給出結論，不再給出證明過程。

首先給出6輪中間相遇區分器的相關結論，區分器如圖6所示。

圖6 6輪RAIN-128算法的中間相遇區分器

定理3設Z0[0]為活躍字節，,...,}是經過6輪RAIN-1 2 8 加密的輸出，若存在明文對(0≤j ≤255)滿足圖6的截斷差分特征，則輸出差分由以下39 Byte確定：

定理4若參數滿足定理3的條件，且0，則差分集合可分別由以下字節確定：

10輪中間相遇攻擊過程及復雜度分析如下。

在線攻擊階段：需要猜測13 Byte。利用算法的結構特性和等價密鑰MC-1(K)可推導出18 Byte的密鑰：u[5],u[10],u[15] , ATK0[4, 8, 12] ,ATK8[7, 10, 13], ATK9[1, 2, 3, 5, 7, 9, 10, 14, 15]。利用所得密鑰值對密文進行部分解密，可得W7[0]，計算差分集。若差分集在預計算階段建立的哈希表T中，則猜測的密鑰為正確密鑰，否則為錯誤密鑰，并通過窮盡搜索的方式篩選出正確密鑰。因此10輪RAIN-128所需數據復雜度為 272個選擇明文，時間復雜度為2104×28×16/(10×16)≈2109次加密10輪算法。

5 結束語

本文將DS-MITM模型與 RAIN-128的一類截斷差分特征相結合，構造了RAIN-128的4輪和6輪區分器，并利用該算法的結構特性和差分枚舉技術，實現了8輪和10輪的中間相遇攻擊。用等價密鑰MC-1(K)和算法的結構特性減少了在線攻擊需猜測的密鑰量，降低了在線攻擊階段的時間復雜度。在攻擊的過程中如何減少狀態字節的猜測量仍需進一步研究。