邢朝輝 張文英 曹梅春

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

2 （山東交通學(xué)院理學(xué)院 濟南 250357）

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

（3613452@qq.com）

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

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

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

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

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

1 預(yù)備知識

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

1.1 積分分析

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

1.2 二元關(guān)系

定義1[22]. 由2 個元素x和y（x，y可屬于不同集合）按一定順序排列成的二元組稱作一個有序?qū)Γ涀鳌磝,y〉,其中x是第1 元素，y是第2 元素.

定義2[22]. 如果一個集合滿足條件之一：1） 集合非空，且它的元素都是有序?qū)Γ?） 集合是空集. 則稱該集合為一個二元關(guān)系.

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

1.3 WARP 算法描述

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

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

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

2 利用代數(shù)結(jié)構(gòu)構(gòu)造積分區(qū)分器的框架

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

Fig.1 The round function of WARP圖1 WARP 算法的輪函數(shù)

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

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

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

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

3 對WARP 算法的積分分析

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

3.1 構(gòu)造20 輪積分區(qū)分器

根據(jù)第2 節(jié)給出的框架，分3 步來構(gòu)造WARP的積分區(qū)分器.

步驟1. 構(gòu)造Te.

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

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

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

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

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

步驟2. 構(gòu)造Td.

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

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

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

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

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

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

2 個積分區(qū)分器的數(shù)據(jù)復(fù)雜度都是229×4=2116個選擇明文，低于設(shè)計者給出的積分區(qū)分器的復(fù)雜度231×4=2124個選擇明文.

3.2 擴展為22 輪積分區(qū)分器

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

以20 輪積分區(qū)分器Ⅰ為例，該區(qū)分器由Td9中的有序?qū)Α碅{x8,x14,x18},q14〉與中的有序?qū)B接而成. 我們將其置于22 輪積分區(qū)分器的第1～21輪的位置，q14為第10 輪的中間狀態(tài)字如圖4 所示.

Fig.4 A 22-round integral distinguisher圖4 22 輪積分區(qū)分器

2 個22 輪積分區(qū)分器的數(shù)據(jù)復(fù)雜度仍然是 2116個選擇明文.

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

3.3 構(gòu)造18 輪可實驗驗證的積分區(qū)分器

當(dāng)減少構(gòu)造區(qū)分器的Traild的輪數(shù)時，區(qū)分器所需的活躍明文字個數(shù)也會減少. 用一個和一個通過q14連接，構(gòu)造了一個16 輪積分區(qū)分器：令{x0,x1, …,x31}中的{x5,x14,x15,x18,x19,x20,x21,x27}明文字活躍，其余的明文字為常數(shù)，加密16 輪后，y15平衡.然后將此區(qū)分器分別在解密方向和加密方向各擴展1 輪，得到一個18 輪積分區(qū)分器，即：令明文字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為常數(shù)，加密18 輪后，S（y23）⊕y10平衡. 該區(qū)分器的數(shù)據(jù)復(fù)雜度為28×4=232個選擇明文，隨后在配置為Intel Xeon E5-2670 v2 @2.5 GHz, 2.49 GHz，16.00 GB RAM 的 服務(wù)器上進行了實驗，運行時間為7.1 h，證實了結(jié)論的正確性.

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

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

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

攻擊步驟有3 步：

Fig.6 The trail of the dependence on in the 22-round distinguisher圖6 22 輪區(qū)分器中對的依賴關(guān)系跡

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

4 總結(jié)

本文將明密文字用中間狀態(tài)字的多變量多項式來表示，通過對多變量多項式進行分析，發(fā)現(xiàn)了一類代數(shù)結(jié)構(gòu)具有的積分特性，用該性質(zhì)改進了SPN 和Feistel-SP 分組密碼積分分析的結(jié)果. 將該方法應(yīng)用于WARP 算法，分析輪數(shù)由原來設(shè)計者給出的21 輪提高到26 輪. 據(jù)我們所知，該區(qū)分器和密鑰恢復(fù)攻擊是迄今為止單密鑰情境下最好的結(jié)果.

附錄A.

附錄B.

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