CHAM 算法的安全性分析*

陳少真, 李 航, 付志新, 任炯炯

1. 戰略支援部隊信息工程大學, 鄭州450001

2. 密碼科學技術國家重點實驗室, 北京100878

1 引言

輕量級密碼算法具有資源占用量較少的優點, 特別適用于RFID (Radio Frequency Identification)、無線傳感器網絡(WSN) 等資源和計算能力有限的設備和環境. 近年來, 關于輕量級分組密碼的研究越來越受到人們的關注, 很多輕量級算法陸續被提出, 比如PRESENT[1], MIBS[2], LEA[3]等算法. 為了更好地實現安全性和效率的折中, 涌現出了一批基于ARX 結構的輕量級分組密碼. ARX 型密碼算法采用模加運算、循環移位和異或運算三種運算, 其中只有模加運算為非線性運算. 為了便于軟硬件的快速實現,ARX 型密碼算法的非線性組件規模一般較小, 但是由于模加運算的迭代次數較高, 其仍然具有較強的安全性. 為了提高LEA 算法對資源受限環境的適應性, 在ICISC 2017, Koo B 等[4]提出了一個新的分組密碼家族CHAM 算法.

在基于統計學方法的攻擊如差分類、線性類、積分類等密碼攻擊過程中, 需要尋找有效的區分器, 區分器的好壞, 直接關系到密碼攻擊的效果, 找到更長輪數的區分器, 往往意味著在密碼分析中能取得更好的攻擊結果. 自動化搜索算法充分考慮了密碼算法特點, 結合其線性和非線性組件性質, 通過計算機, 可在有效時間內給出特定條件下的所有區分器, 在具體應用中往往能比傳統方法搜索到效果更好、條數更多的區分器. 目前常用的自動化搜索算法主要包括基于SAT(布爾可滿足性問題) 的自動化搜索算法和基于MILP(混合整數規劃問題) 的自動化搜索算法.

MILP 問題是運籌學中的一類優化問題, 旨在線性約束條件下求解目標函數的最值. 最近幾年, 為了獲取分組密碼中活躍S 盒數量的下界, 進而評估分組密碼抵抗差分和線性攻擊的能力, 很多密碼學者將該問題轉換為MILP 問題, 取得了非常好的結果[5,6]. 后來模加運算差分概率的計算也轉化為了MILP 問題, 用于搜索ARX 型分組密碼算法的區分器[7,8]. 基于MILP 自動化搜索技術發展越來越成熟, 顯示出強大的密碼分析能力, 借助MILP 的求解工具Gurobi, 可以在一定的時間內搜索得到相應的區分器.

本文旨在利用不可能差分分析、零相關線性分析對CHAM 算法進行安全性分析. 首先利用不等式組對算法的每個組件進行等價刻畫, 描述了差分特征和線性掩碼的傳播規律, 其次針對CHAM 算法四分支廣義Feistel 結構的特點, 優化了不可能差分區分器和零相關線性區分器的搜索策略, 縮小了搜索空間, 進而基于MILP 工具設計了有效的搜索算法. 依靠搜索算法, 共得到CHAM-64 的5 條19 輪不可能差分區分器, CHAM-128 的1 條18 輪不可能差分區分器和15 條19 輪零相關線性區分器, 這是CHAM 算法目前找到的最長零相關特征和最長不可能差分特征. 與已有結果的對比如表1 所示.

2 CHAM 算法

CHAM 是一個四分支廣義Feistel 結構的分組密碼族, 每個密碼由CHAM-n/m 表示, 分組長度為n比特, 密鑰長度為m 比特. 表2 顯示了該家族的密碼及其參數列表, 在這里, r、w 和kw 分別表示迭代的輪數、一個分支（字）的長度以及密鑰的字數.

2.1 CHAM 算法的輪函數

明文P = (X0[0],X0[1],X0[2],X0[3]) 作為加密函數的輸入, 利用輪函數加密r 輪可以得到密文C = (Xr[0],Xr[1],Xr[2],Xr[3]). 值得注意的是, CHAM 算法的奇數輪和偶數輪對應輪函數的參數不同,

表1 CHAM 算法區分器比較Table 1 Comparison of distinguishers about CHAM family

表2 CHAM 系列算法參數表Table 2 Parameters table of CHAM family

當輪數r(0 ?i ?r) 為偶數時, 輪函數為:

當輪數r 為奇數時, 輪函數為:

以上符號“?” 表示模2w加, “⊕” 表示按位進行異或, “?” 表示循環左移. 圖1 給出了CHAM 算法2 輪加密函數, 其中(ai,bi,ci,di) 表示第i 輪的輸入.

2.2 CHAM 算法的密鑰生成算法

CHAM-n/k 的密鑰擴展算法是利用主密鑰K =(K[0],K[1],··· ,K[kw ?1]) 生成2·kw 個w 比特的輪子密鑰(rk[0],rk[1],··· ,rk[2·kw ?1]) , 生成輪子密鑰的過程如下所示:

其中0 ?i

3 CHAM 算法不可能差分區分器搜索

不可能差分分析由Biham[9]和Knudsen[10]分別提出, 其原理可以簡單概括為: 利用概率為零的不可能差分區分器來排除錯誤的候選密鑰, 從而恢復正確密鑰.

圖1 CHAM 算法輪函數Figure 1 Round function of CHAM

本節我們給出一個基于MILP 自動化搜索CHAM 算法的不可能差分路徑的模型, 并利用該模型搜索得到19 輪CHAM-64 和18 輪CHAM-128 的不可能差分路徑. 對于給定的輸入和輸出差分, 我們首先把CHAM 算法的每個組件用線性不等式組等價刻畫并進行組合, 然后將目標函數設定為任意的常值——我們只關心不等式組是否有解而不關心目標函數的取值. 若不等式組無解, 當前的輸入差分和輸出差分導致一條不可能差分路徑; 反之, 則對應的差分路徑存在.

3.1 差分特征傳播規律

輕量級分組密碼CHAM 算法的加密函數較為簡單, 僅僅包含分支運算、循環移位運算、常數異或運算以及模加運算, 其中模加運算是唯一的非線性運算, 其余均為線性運算. 我們知道, 與常數進行異或不影響差分的傳播, 分支運算同樣不改變差分, 因此僅需用不等式組刻畫循環移位操作和模加操作.

對于循環移位操作, 由于它僅僅是將輸入的比特位置進行置換, 因而我們很容易構建線性等式組對其進行刻畫.

對于模加操作, 文獻[11] 進行了刻畫, 長度為n 比特的差分特征(α,β,γ) 滿足α ?β =γ 當且僅當

其中d 是二元變量, 0

3.2 搜索策略

在上一小節中, CHAM 算法加密函數的每個運算的差分特征傳播都用一組線性不等式進行了刻畫.通過組合所有的不等式, 整個不等式體系能夠完美刻畫差分特征在CHAM 算法中的傳播規律, 其給出的每個解就是一條可能的差分路徑. 而對于給定的輸入差分和輸出差分, 如果不等式組無解, 那么當前的輸入輸出差分將導致一條不可能差分路徑. 由于時間的約束, 我們很難遍歷整個輸入差分和輸出差分空間,而僅僅搜索特定形式輸入輸出差分的集合, 通過遍歷輸入差分和輸出差分的特定集合, 我們可以確定該集合中是否存在不可能差分路徑.

因為CHAM 算法是四分支廣義Feistel 結構, 所以我們不難得出CHAM 算法的最長不可能差分路徑具有性質1. 這里“最長” 僅僅指的是在輸入或輸出差分僅含有一個非零比特塊的情況下, 并非針對所有的不可能差分區分器.

性質 1 對于 CHAM 算法的最長不可能差分路徑, 若輸入差分只有一個非零塊, 則一定形如(α,0,0,0) 或(0,0,0,β), 其中wt(α) > 0,wt(β) > 0; 若輸出差分只有一個非零塊, 則一定形如(γ,0,0,0)或(0,η,0,0), 其中wt(γ)>0,wt(η)>0.

證明: 以輸入差分的形式的證明為例, 假設 r 輪不可能差分路徑為 (α1,α2,α3,α4)r-round

?????→(β1,β2,β3,β4).

若非零塊位于第二個字, 即形如(0,α2,0,0). 根據差分的傳播規律, 輸入差分可以自然的向上傳播一輪, 得到差分(0,0,α2,0). 因此, 存在(r+1) 輪的不可能差分路徑(0,0,α2,0) →(0,α2,0,0)r-round

??????→(β1,β2,β3,β4), 與r 輪不可能差分路徑最長矛盾.

若非零塊位于第三個字, 即形如(0,0,α3,0). 根據差分的傳播規律, 輸入差分可以自然的向上傳播一輪, 得到差分(0,0,0,α3). 因此, 存在(r+1) 輪的不可能差分路徑(0,0,0,α3) ?→(0,0,α3,0)r-round

??????→(β1,β2,β3,β4), 與r 輪不可能差分路徑最長矛盾.

因此, 對于CHAM 算法的最長不可能差分路徑, 若輸入差分只有一個非零字, 則一定形如(α,0,0,0)或(0,0,0,β).

同理可證, 對于CHAM 算法的最長不可能差分路徑, 若輸出差分只有一個非零字, 則一定形如(γ,0,0,0) 或(0,η,0,0).

綜上所述, 命題得證.

在搜索輸入(輸出) 差分僅有1 個非零塊的最長不可能差分路徑時, 我們首先對路徑的輪數預估一個上界, 然后遞減輪數進行搜索, 直至找到不可能差分路徑為止. 根據性質1, 我們可以排除掉最長不可能差分路徑的輸入(輸出) 差分所不具有的形式, 而不需要遍歷全部的輸入(輸出) 差分.

3.3 CHAM 算法的不可能差分區分器

CHAM 算法的分組長度是64 比特或128 比特, 遍歷所有可能的輸入輸出差分對復雜度太高, 所以我們只考慮三種特殊的情況: 輸入、輸出差分的重量均為1 比特(稱為一進一出); 輸入、輸出差分的重量分別為1 比特、2 比特(稱為一進二出); 輸入、輸出差分的重量均為2 比特、1 比特(稱為二進一出). 在搜索時, 我們利用性質1 來降低時間復雜度.

對于CHAM-64 算法, 搜索得到5 條一進二出的19 輪不可能差分區分器, 結果如表3 所示.

表3 CHAM-64 不可能差分路徑Table 3 Impossible differential path of CHAM-64

對于 CHAM-128 算法, 搜索得到 1 條一進二出的 18 輪不可能差分區分器 (0,0,0,e30) ?(e23,0,0,e0).

4 CHAM 算法零相關線性區分器搜索

零相關分析方法由Bogdanov 和Rijmen[12]于2012 年提出, 該方法首先要構造一條零相關路徑,通常讓線性掩碼在非零偏差下從兩頭向中間傳播并相遇, 若任何一個位置產生矛盾, 則找到一條零相關路徑[13]. 構造完零相關路徑后, 就可以利用區分器對密鑰進行恢復.

本節我們給出一個基于MILP 自動化搜索CHAM 算法的零相關線性路徑的模型, 并利用該模型搜索得到19 輪CHAM-128 的零相關線性路徑. 搜索模型與基于MILP 搜索不可能差分路徑的模型相似, 同樣利用不等式組對算法的每個組件進行等價刻畫并組合, 我們不關心目標函數是什么, 而只關心不等式體系是否有解. 若無解, 則當前的輸入掩碼和輸出掩碼導致一條零相關線性路徑.

4.1 線性掩碼傳播規律

為了搜索CHAM 算法的零相關線性路徑, 需要首先考慮分支操作、循環移位操作和模加操作這些基本操作的線性掩碼傳播. 對于循環移位操作, 由于它僅僅將輸入的比特位置進行置換, 因而我們很容易構建線性等式組對其進行描述. 對于分支操作和模加操作, 文獻[14] 進行了精準刻畫.

假設分支操作的輸入掩碼是α, 輸出掩碼是β 和γ, 掩碼的長度都為n 比特, 則可用如下等式來刻畫每個比特上的掩碼傳播:

其中d 是二元變量, 0 ?i

假設模加操作的輸入掩碼是α 和β, 輸出掩碼是γ, 掩碼的長度都為n 比特, 則可用如下等式來刻畫每個比特上的掩碼傳播:

其中0 ?i < n, s[i] 是二元狀態變量. 值得注意的是, 還有一個額外的約束條件s[n] = 0, 因此, 我們可以用8n+1 個約束條件來刻畫模加操作的線性逼近.

4.2 搜索策略

在上一小節中, CHAM 算法加密函數的每個運算的線性掩碼的傳播都用一組線性不等式進行了刻畫.通過組合所有的不等式, 整個不等式體系能夠完美刻畫線性掩碼在CHAM 算法中的傳播規律. 與不可能差分路徑搜索相似的, 在模型中加入輸入掩碼和輸出掩碼的約束條件后即可搜索零相關線性路徑.

為了降低搜索零相關線性路徑的時間復雜度, 我們給出CHAM 算法的最長零相關線性路徑具有性質2. 這里的“最長” 僅僅指的是在輸入或輸出掩碼僅含有一個非零比特塊的情況下, 并不是針對所有的零相關線性路徑.

性質 2 對于 CHAM 算法的最長零相關線性路徑, 若輸入掩碼只有一個非零塊, 則一定形如(α,0,0,0) 或(0,0,0,β), 其中wt(α)>0, wt(β)>0; 若輸出掩碼只有一個非零塊, 則一定形如(γ,0,0,0)或(0,η,0,0), 其中wt(γ)>0, wt(η)>0.

證明: 以輸入掩碼的形式的證明為例, 假設 r 輪零相關線性路徑為 (α1,α2,α3,α4)r-round

??????→(β1,β2,β3,β4).

若非零塊位于第二個字, 即形如(0,α2,0,0). 根據掩碼的傳播規律, 輸入掩碼可以自然的向上傳播一輪, 得到掩碼(0,0,α2,0). 因此, 存在(r+1) 輪的零相關線性路徑(0,0,α2,0) ?→(0,α2,0,0)r-round

??????→(β1,β2,β3,β4), 與r 輪零相關線性路徑最長矛盾.

因此, 對于CHAM 算法的最長零相關線性路徑, 若輸入掩碼只有一個非零字, 則一定形如(α,0,0,0)或(0,0,0,β).

同理可證, 對于CHAM 算法的最長零相關線性路徑, 若輸出掩碼只有一個非零字, 則一定形如(γ,0,0,0) 或(0,η,0,0).

綜上所述, 命題得證.

在搜索輸入(輸出) 掩碼僅有1 個非零塊的最長零相關線性路徑時, 我們可以采取與不可能差分路徑的搜索類似的策略. 根據性質2, 我們可以排除掉最長零相關線性路徑的輸入(輸出)掩碼所不具有的形式,而不需要遍歷全部的輸入(輸出) 掩碼.

4.3 CHAM 算法的零相關線性區分器

搜索CHAM 算法的零相關線性路徑時, 我們只考慮三種特殊的情況: 輸入、輸出掩碼的重量均為1比特(稱為一進一出); 輸入、輸出掩碼的重量分別為1 比特、2 比特(稱為一進二出); 輸入、輸出掩碼的重量分別為2 比特、1 比特(稱為二進一出). 在搜索時, 我們利用性質2 來降低時間復雜度.

對于CHAM-128 算法, 搜索得到15 條二進一出的19 輪零相關線性路徑, 結果如表4 所示, 其中(0,0,e0,e31)?(e1,0,0,0) 表示當輸入掩碼的第三分支的第0 比特和第四分支的第31 比特非零、輸出掩碼的第一分支的第1 比特非零時組成一條零相關線性路徑.

表4 CHAM-128 零相關線性路徑Table 4 Zero-correlation linear path of CHAM-128

選取零相關線性路徑(0,0,e0,e31)?(e1,0,0,0) 作為區分器, 對CHAM 算法進行密鑰恢復攻擊. 將區分器前加3 輪后加1 輪, 可對CHAM-128/128 攻擊到23 輪, 攻擊的時間復雜度為2120.6次23 輪CHAM-128 加密; 將區分器前加4 輪后加4 輪, 可對CHAM-128/256 攻擊到27 輪, 攻擊的時間復雜度為2238.75次27 輪CHAM-128 加密.

5 總結

本文主要評估了CHAM 密碼算法關于不可能差分和零相關線性分析方法的安全性. 在前人工作的基礎上, 基于MILP 工具, 給出了不可能差分區分器和零相關線性區分器的搜索算法. 根據CHAM 算法四分支廣義Feistel 結構的特點, 優化了搜索策略, 縮小了搜索空間. 利用搜索算法, 找到了CHAM-64 的5條19 輪不可能差分區分器、CHAM-128 的1 條18 輪不可能差分區分器和15 條19 輪零相關線性區分器, 均為目前公開發表的最長同類型區分器. 此外, 目前對ARX 結構分組密碼的非線性組件模加運算的一些基本密碼性質尚不明確, 對其的數學刻畫也較為復雜, 對模加運算的密碼學性質進行深入研究, 簡化其數學描述, 對提升搜索算法的效率具有重要意義, 有助于進一步改進現有的密碼分析結果.