基于代數結構視角對輕量分組密碼WARP 的積分分析

邢朝輝 張文英 曹梅春

1 （山東師范大學信息科學與工程學院 濟南 250358）

2 （山東交通學院理學院 濟南 250357）

3 （山東管理學院信息工程學院 濟南 250357）

（3613452@qq.com）

無線傳感網絡（wireless sensor network, WSN）與射頻識別技術（radio frequency identification, RFID）在工業互聯網中有著廣泛應用，工業互聯網的底層集成和使用了大量資源受限的終端設備，例如傳感器、智能儀表、可編程控制器等，所生產的海量數據的安全傳輸是保障工業互聯網安全運行的關鍵，于是，專門為WSN 及RFID 設計的輕量級加密算法應運而生.輕量級密碼算法的早期典型代表是PRESENT[1]和LBlock[2-3]，近幾年新提出的算法有GIFT[4]，WARP[5].

WARP 算法是由Banik 等人[5]在SAC 2020 會議上提出來的輕量級分組密碼，它具有硬件面積小、能耗低的特點，在大多數典型硬件配置下，是目前128b分組密碼中硬件面積最小的. 另外，它在軟件實現上也有非常好的表現：在8b 微處理器上進行軟件實現，在可接受的執行時間內，具有非常有競爭力的短代碼長度和極低的RAM 能耗；在高端處理器上使用SIMD 進行軟件實現時，實現效率非常高，適用于計算能力弱、存儲空間小等資源受限的物聯網加密環境. 多方安全性評估是新密碼算法在投入市場之前必有的檢驗. 設計者[5]給出了一個21 輪不可能差分區分器和一個20 輪積分區分器；文獻[6]給出了一條19 輪差分路徑和21 輪密鑰恢復攻擊；文獻[7]基于21 輪區分器進行了24 輪矩形攻擊，還給出了一個全輪的相關密鑰差分攻擊. 相關密鑰攻擊假設攻擊者可以反轉密碼機里密鑰的某些比特位，但在實際應用中攻擊者不具有這個權限，該攻擊對密碼算法安全性不形成實際威脅. 設計者在算法描述文檔中曾聲明不考慮相關密鑰攻擊的威脅. 本文用積分分析的方法對WARP 進行了單密鑰情境下的有效攻擊.

積分攻擊是針對分組密碼算法最有效的攻擊方法之一，它是由Daemen 等人[8]在評估分組密碼SQUARE 時首次提出. 在2002 年FSE 會議上，Knudsen等人[9]對此類攻擊技術進行了理論上的統一，稱之為積分攻擊. 積分攻擊的關鍵是尋找一個覆蓋輪數盡可能多的積分區分器. 傳統的積分區分器構造方法主要有2 種：一是通過評估積分性質的傳播進行構造的方法；二是代數次數估計方法. 在2015 年歐密會上，Todo[10]提出了可分性的概念，它是積分性質的推廣，它的提出為積分區分器的構造帶來突破性的進展. 可分性在構造積分區分器時考慮了更多加密原語的代數信息，更準確地描述了積分性質，從而改進了許多加密算法的積分攻擊結果[11-14]. 此外，可分性還可以與多種自動化搜索工具相結合，實現對可分性的自動化搜索[15-18]. 但是當密碼算法的分組規模較大時，對可分性的搜索會受限于計算復雜度和存儲復雜度. 目前，一些研究從代數結構層面進行宏觀分析和可證安全性探索[19-20]，在某些算法的分析上取得了優于可分性的積分分析結果，例如，在文獻[20]中，作 者將SPN（substitution permutation network）密碼算法多輪的加密變換表示成上的多變量多項式，其中b為S 盒的輸入比特數，研究多變量多項式中出現次數較少的輸入字可能帶來的密碼學性質得到了SKINNY 的10 輪積分區分器，時間復雜度低于使用可分性得到的積分區分器.

本文中總體框架采用Feistel 結構，且F 函數采用SP（substitution permutation）結構的分組密碼稱為Feistel-SP 類分組密碼[21]. 本文的研究動機來源于Zhang 等人[20]的工作以及WARP 算法的問世. 借鑒文獻[20]方法的核心思想，本文也把輸出字寫成輸入字的多變量多項式，基于多變量多項式中輸入字的出現次數討論分組密碼基于代數結構的積分性質. 在研究過程中，發現了某種代數結構的密碼算法具有積分性質，并通過分組密碼S 盒差分分布表（difference distribution table, DDT）的特性：|{x| x∈為偶數，證明了這一性質.利用該性質，可以找到某些覆蓋輪數更多的積分區分器，從而改進利用代數結構進行積分分析的方法.另外，通過對幾個Feistel-SP 結構分組密碼的結構進行分析，發現此分析方法可從分析SPN 分組密碼擴展到分析Feistel-SP 分組密碼上，并將改進的積分分析方法應用到Feistel-SP 分組密碼WARP 算法上，構造了2 個數據復雜度為2116的22 輪積分區分器，基于該區分器給出26 輪積分攻擊，而WARP 設計者只給出1 個數據復雜度為2124的20 輪積分區分器，且認為最多可進行21 輪攻擊. 為了驗證所給方法和理論的正確性，對用此方法所構造的18 輪積分區分器做了實際實現，其復雜度為232，耗時7.1 h. 將本文的結果與之前所有單密鑰情境下的攻擊結果進行了對比，如表1 所示. 結果表明，本文的積分攻擊是目前對WARP 可驗證的最好的密鑰恢復攻擊結果.

Table 1 Key-Recovery Attacks on WARP in the Single-Key Scenario表1 單密鑰情境下對WARP 的密鑰恢復攻擊

1 預備知識

本節簡要介紹積分分析方法、文中用到的基本符號和定義，以及WARP 算法描述.

1.1 積分分析

積分分析的主要思想是選擇特定的明文集合，一般是對明文的某些比特位進行遍歷（稱為活躍比特），其余的明文比特位固定（稱為常量比特），對選定的明文集合進行加密，對得到的所有密文值逐比特位異或求和（稱為積分），若積分中的某些比特位恒為0（與密鑰和常量比特無關），則稱這些比特位是平衡的，即H:而對于均勻分布的隨機變量而言，積分的每一比特位等于0 的概率為1/2，攻擊者通過積分值的非隨機性將目標算法與隨機置換區分，并恢復某些密鑰比特位.

1.2 二元關系

定義1[22]. 由2 個元素x和y（x，y可屬于不同集合）按一定順序排列成的二元組稱作一個有序對，記作〈x,y〉,其中x是第1 元素，y是第2 元素.

定義2[22]. 如果一個集合滿足條件之一：1） 集合非空，且它的元素都是有序對；2） 集合是空集. 則稱該集合為一個二元關系.

定義3[22]. 設U，G為二元關系，U和G的復合記作U°G，其中U°G={〈x,y〉|?t使得〈x,t〉∈U∧〈t,y〉∈G}.

1.3 WARP 算法描述

因為在本文中S 盒細節以及輪常數取值不影響對算法的分析，所以忽略S 盒細節及輪常數描述. 解密過程與加密過程類似，只是將置換π換成π?1，輪常數逆序使用. 具體加密過程為：

首先，將128 b 明文X加載到128 b 的初始 狀態Q0中，然后迭代運行41 輪. 當輪數r=1, 2, …, 40 時，輪函數包含4 個步驟.

解密過程略. 關于WARP 算法的詳細描述，請參見文獻[5].

2 利用代數結構構造積分區分器的框架

首先簡要回顧文獻[20]中利用代數結構構造SPN 分組密碼積分區分器的主要思想：把明文字（密文字）用中間狀態字的多變量多項式表示出來，通過統計中間狀態字在多變量多項式中出現的次數來構造積分區分器. 給定的分組密碼的代數結構通過多變量多項式體現出來，用以評估抵抗攻擊的安全性.我們發現該思想同樣適用于Feistel-SP 結構分組密碼，并且攻擊效果更佳. 該文獻指出可用S 盒的置換性質構造積分區分器，定理1 描述了該性質.

Fig.1 The round function of WARP圖1 WARP 算法的輪函數

Table 2 Shuffle π and π?1 of WARP on 32 Nibbles表2 WARP 算法中面向32 個半字節的置換π 和π?1

本文將用$（x）表示置換Sn?1（…S1（S0（x⊕c0）⊕c1）…⊕cn?1）. 定理1 表明，若中間狀態字在密文字的表達式里只出現1 次，則當中間狀態字遍歷時，密文字是平衡的. 在研究過程中，發現了某種代數結構的密碼算法具有積分性質，可以用中間狀態字的多變量多項式進行判別，并將某些積分區分器擴展至更多輪數，見定理2.

定理2 表明，雖然中間狀態字在密文字里出現2 次，但是若以S（S（x）⊕S（x⊕u）⊕v）的形式出現，則當中間狀態字遍歷時，密文字也是平衡的. 借鑒文獻[20]給出的構造積分區分器的思想，輔助運用定理1 和定理2，給出了一個構造SPN 結構和Feistel-SP 結構分組密碼積分區分器的通用框架. 在介紹通用框架之前，本節先給出構造過程中用到的一些概念.

本步驟關注從中間狀態Q開始，經過r輪加密得到Y的加密過程. 把每個密文字yi用中間狀態字q0,q1, …,qn?1表示出來，然 后統計每個中間 狀態字qj在每個密文字yi表達式中出現的次數. 當加密輪數超過某個數值re時，每個中間狀態字qj在每個密文字yi表達式中至少出現1 次，小于數值re時，有些中間狀態字在某些密文字表達式中出現次數為0，re即加密方向全擴散的輪數. 假設qa在加密re輪后的密文字yb的表達式中只出現1 次，根據定理1，當qa活躍，其他中間狀態字固定為常數時，加密re輪后，密文字yb是平衡的，這樣可以得到一個

3 對WARP 算法的積分分析

設計者利用MILP 和可分性，給出了一個需要2124個選擇明文（令31 個明文字活躍）的20 輪積分區分器，設計者認為利用該積分區分器最多只能實現21 輪密鑰恢復攻擊. 本節中利用多變量多項式的代數結構分析方法給出了2 個只需要2116個選擇明文（令29 個明文字活躍）的22 輪積分區分器，并且利用該積分區分器，至少可以實現26 輪密鑰恢復攻擊. 為方便實驗驗證，本文特地給出了一個時間復雜度為232的18 輪可實現積分區分器.

3.1 構造20 輪積分區分器

根據第2 節給出的框架，分3 步來構造WARP的積分區分器.

步驟1. 構造Te.

假設從中間狀態Q=（q0,q1, …,q31）加密r輪后得到密文Y=（y0,y1, …,y31），將每個密文字yi用q0,q1, …,q31表示出來，然后統計中間狀態字qj在yi中出現的次數. 具體做法如下所示.

當r=1 時，用中間狀態字q0,q1, …,q31把1 輪加密后的密文字y0,y1, …,y31表示出來，請見附錄A 中式（A1）.

迭代1 輪加密的表達式，得到r=2, 3, …, 10 輪后每個密文字yi的多變量多項式表達式. 由1 輪加密表達式可以看出，中間狀態字qj在r輪密文字yi中出現次數等于qj在某些r?1 輪密文字中出現次數之和，編程迭代計算可以得到每個中間狀態字在每個r輪密文字中出現的次數. 我們發現10 輪時達到了全擴散，即每個qj在每個yi的表達式中至少出現1 次，如圖2所示. 圖2 中的（i,j）元素表示第j個中間狀態字在第i個密文字中出現的次數. 假設qu在yv的表達式中恰好出現1 次，則令qu活躍，其他中間狀態字固定為常數，加密10 輪之后的密文字yv是平衡的.

接下來，本文借助于實驗尋找加密更多輪后積分為0 的密文字. 依次令單個中間狀態字qj活躍，其余的31 個中間狀態字固定，觀察加密多于10 輪后是否仍存在積分為0 的密文字. 實驗發現加密11 輪和12 輪后依然存在積分為0 的密文字，但這些密文字是否真正平衡需要根據定理1 和定理2 對該密文字表達式的代數結構進行判斷. 例如，令q3活躍，其他中間狀態字固定，加密12 輪之后的密文字y15的積分為0.q3在y15表達式中出現4 次，寫出y15的代數表達式（詳見附錄B），發現該表達式結構為：y15=S（S（x⊕α）⊕S（x）⊕β）⊕$（q3）⊕$′（q3）⊕γ，其 中α，β，γ是不包含q3的項，$（q3）和$′（q3）是定理1 中所示S 盒的復合，q3在其中各出現1 次. 當q3活躍，其他中間狀態字為常數時，根據定理1 和定理2，y15平衡. 從而可以得到一個同樣的方法，可以得到另一個另外還有若干個11 輪的Traile.

Fig.2 The number of times qj appears in yi after 10-round encryption圖2 加密10 輪后qj 在yi 的表達式中出現的次數

步驟2. 構造Td.

假設從中間狀態Q開始解密r輪得到明文X=（x0,x1, …,x31），用q0,q1, …,q31把每個明文字xi表示出來，并統計qj在每個xi的表達式中出現的次數.

當r=1 時，用中間狀態字q0,q1, …,q31把一輪解密后的明文字x0,x1, …,x31表示出來，請見附錄A 中式（A2）.

迭代一輪解密的表達式，得到r=2, 3, …, 10 輪解密后的每個明文字xi的表達式，并統計每個中間狀態字qj在其中出現的次數，發現與加密相同，解密10 輪時達到了全擴散. 解密9 輪時，存在qj在某些xi的表達式中出現次數為0，例如，q0在x16，x26，x28的表達式中出現次數為0，從而可以得到一個本文中 令A={x0,x1, …,x31}，xi∈{0,1}4. 通過解密9 輪后qj在xi的表達式中出現的次數，如圖3所示，可以找到所有從而得到二元關系圖3 中的（i,j）元素表示第j個中間狀態字在第i個明文字中出現的次數.

Fig.3 The number of times qj appears in xi after 9-round decryption圖3 解密9 輪后qj 在xi 的表達式中出現的次數

20 輪積分區分器Ⅰ: 令集合{xi|i∈{0, 1, …, 31}{8, 14, 18}}中的每 個明文字活躍，x8，x14，x18為常數，經過20 輪加密后，y15是平衡的.

20 輪積分區分器Ⅱ：令集合{xi|i∈{0, 1, …, 31}{2, 24, 30}}中的每 個明文字活躍，x2，x24，x30為常數，經過20 輪加密后，y31是平衡的.

2 個積分區分器的數據復雜度都是229×4=2116個選擇明文，低于設計者給出的積分區分器的復雜度231×4=2124個選擇明文.

3.2 擴展為22 輪積分區分器

Feistel 結構輪函數具有如下特點，有一半狀態沒有變化，直接賦值給下一輪的狀態比特，同時這半數狀態經過輪函數后和剩下的另一半狀態異或后賦值給下一輪的另一半狀態. 通過觀察WARP 輪函數的加解密代數表達式發現，每個中間狀態字都可以被它的前一輪或者后一輪的2 個狀態字、密鑰字和輪常數表示出來. 特別是，輪密鑰的異或發生在S 盒之后. 利用這一特性，可以將3.1 節所得20 輪積分區分器向解密方向和加密方向各擴展1 輪，得到22 輪積分區分器.

以20 輪積分區分器Ⅰ為例，該區分器由Td9中的有序對〈A{x8,x14,x18},q14〉與中的有序對連接而成. 我們將其置于22 輪積分區分器的第1～21輪的位置，q14為第10 輪的中間狀態字如圖4 所示.

Fig.4 A 22-round integral distinguisher圖4 22 輪積分區分器

2 個22 輪積分區分器的數據復雜度仍然是 2116個選擇明文.

Fig.5 The balanced combinations of ciphertext圖5 平衡的密文字組合

3.3 構造18 輪可實驗驗證的積分區分器

當減少構造區分器的Traild的輪數時，區分器所需的活躍明文字個數也會減少. 用一個和一個通過q14連接，構造了一個16 輪積分區分器：令{x0,x1, …,x31}中的{x5,x14,x15,x18,x19,x20,x21,x27}明文字活躍，其余的明文字為常數，加密16 輪后，y15平衡.然后將此區分器分別在解密方向和加密方向各擴展1 輪，得到一個18 輪積分區分器，即：令明文字x3,x6,x8,x16,x22,x25,x26,x29活 躍，令x7⊕S（x6）,x9⊕S（x8）,x17⊕S（x16）,x23⊕S（x22）,x27⊕S（x26）,x0,x1,x2,x4,x5,x10,x11,x12,x13,x14,x15,x18,x19,x20,x21,x24,x28,x30,x31為常數，加密18 輪后，S（y23）⊕y10平衡. 該區分器的數據復雜度為28×4=232個選擇明文，隨后在配置為Intel Xeon E5-2670 v2 @2.5 GHz, 2.49 GHz，16.00 GB RAM 的 服務器上進行了實驗，運行時間為7.1 h，證實了結論的正確性.

3.4 對WARP 算法的26 輪積分攻擊

基于22 輪積分區分器，利用部分和技巧[2,23]在區分器尾部加4 輪，對26 輪WARP 進行了密鑰恢復攻擊.

2 個表達式中包含13 個26 輪密文字和10 個輪密鑰字.

攻擊步驟有3 步：

Fig.6 The trail of the dependence on in the 22-round distinguisher圖6 22 輪區分器中對的依賴關系跡

在3.3 節給出的18 輪區分器尾部加1 輪，對19輪WARP 進行可實現的密鑰恢復攻擊，可以恢復4b密鑰本文在同一個服務器上進行了實驗，運行時間約為7.6 h，驗證了該攻擊方法的正確性.

4 總結

本文將明密文字用中間狀態字的多變量多項式來表示，通過對多變量多項式進行分析，發現了一類代數結構具有的積分特性，用該性質改進了SPN 和Feistel-SP 分組密碼積分分析的結果. 將該方法應用于WARP 算法，分析輪數由原來設計者給出的21 輪提高到26 輪. 據我們所知，該區分器和密鑰恢復攻擊是迄今為止單密鑰情境下最好的結果.

附錄A.

附錄B.

作者貢獻聲明：邢朝輝負責分析方法的理論分析、實驗設計及實現、論文撰寫；張文英提出分析思路、指導寫作并修改論文；曹梅春負責圖表整理及論文校對.