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

1. 戰(zhàn)略支援部隊(duì)信息工程大學(xué), 鄭州450001

2. 密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100878

1 引言

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

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

MILP 問(wèn)題是運(yùn)籌學(xué)中的一類優(yōu)化問(wèn)題, 旨在線性約束條件下求解目標(biāo)函數(shù)的最值. 最近幾年, 為了獲取分組密碼中活躍S 盒數(shù)量的下界, 進(jìn)而評(píng)估分組密碼抵抗差分和線性攻擊的能力, 很多密碼學(xué)者將該問(wèn)題轉(zhuǎn)換為MILP 問(wèn)題, 取得了非常好的結(jié)果[5,6]. 后來(lái)模加運(yùn)算差分概率的計(jì)算也轉(zhuǎn)化為了MILP 問(wèn)題, 用于搜索ARX 型分組密碼算法的區(qū)分器[7,8]. 基于MILP 自動(dòng)化搜索技術(shù)發(fā)展越來(lái)越成熟, 顯示出強(qiáng)大的密碼分析能力, 借助MILP 的求解工具Gurobi, 可以在一定的時(shí)間內(nèi)搜索得到相應(yīng)的區(qū)分器.

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

2 CHAM 算法

CHAM 是一個(gè)四分支廣義Feistel 結(jié)構(gòu)的分組密碼族, 每個(gè)密碼由CHAM-n/m 表示, 分組長(zhǎng)度為n比特, 密鑰長(zhǎng)度為m 比特. 表2 顯示了該家族的密碼及其參數(shù)列表, 在這里, r、w 和kw 分別表示迭代的輪數(shù)、一個(gè)分支（字）的長(zhǎng)度以及密鑰的字?jǐn)?shù).

2.1 CHAM 算法的輪函數(shù)

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

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

表2 CHAM 系列算法參數(shù)表Table 2 Parameters table of CHAM family

當(dāng)輪數(shù)r(0 ?i ?r) 為偶數(shù)時(shí), 輪函數(shù)為:

當(dāng)輪數(shù)r 為奇數(shù)時(shí), 輪函數(shù)為:

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

2.2 CHAM 算法的密鑰生成算法

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

其中0 ?i

3 CHAM 算法不可能差分區(qū)分器搜索

不可能差分分析由Biham[9]和Knudsen[10]分別提出, 其原理可以簡(jiǎn)單概括為: 利用概率為零的不可能差分區(qū)分器來(lái)排除錯(cuò)誤的候選密鑰, 從而恢復(fù)正確密鑰.

圖1 CHAM 算法輪函數(shù)Figure 1 Round function of CHAM

本節(jié)我們給出一個(gè)基于MILP 自動(dòng)化搜索CHAM 算法的不可能差分路徑的模型, 并利用該模型搜索得到19 輪CHAM-64 和18 輪CHAM-128 的不可能差分路徑. 對(duì)于給定的輸入和輸出差分, 我們首先把CHAM 算法的每個(gè)組件用線性不等式組等價(jià)刻畫(huà)并進(jìn)行組合, 然后將目標(biāo)函數(shù)設(shè)定為任意的常值——我們只關(guān)心不等式組是否有解而不關(guān)心目標(biāo)函數(shù)的取值. 若不等式組無(wú)解, 當(dāng)前的輸入差分和輸出差分導(dǎo)致一條不可能差分路徑; 反之, 則對(duì)應(yīng)的差分路徑存在.

3.1 差分特征傳播規(guī)律

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

對(duì)于循環(huán)移位操作, 由于它僅僅是將輸入的比特位置進(jìn)行置換, 因而我們很容易構(gòu)建線性等式組對(duì)其進(jìn)行刻畫(huà).

對(duì)于模加操作, 文獻(xiàn)[11] 進(jìn)行了刻畫(huà), 長(zhǎng)度為n 比特的差分特征(α,β,γ) 滿足α ?β =γ 當(dāng)且僅當(dāng)

其中d 是二元變量, 0

3.2 搜索策略

在上一小節(jié)中, CHAM 算法加密函數(shù)的每個(gè)運(yùn)算的差分特征傳播都用一組線性不等式進(jìn)行了刻畫(huà).通過(guò)組合所有的不等式, 整個(gè)不等式體系能夠完美刻畫(huà)差分特征在CHAM 算法中的傳播規(guī)律, 其給出的每個(gè)解就是一條可能的差分路徑. 而對(duì)于給定的輸入差分和輸出差分, 如果不等式組無(wú)解, 那么當(dāng)前的輸入輸出差分將導(dǎo)致一條不可能差分路徑. 由于時(shí)間的約束, 我們很難遍歷整個(gè)輸入差分和輸出差分空間,而僅僅搜索特定形式輸入輸出差分的集合, 通過(guò)遍歷輸入差分和輸出差分的特定集合, 我們可以確定該集合中是否存在不可能差分路徑.

因?yàn)镃HAM 算法是四分支廣義Feistel 結(jié)構(gòu), 所以我們不難得出CHAM 算法的最長(zhǎng)不可能差分路徑具有性質(zhì)1. 這里“最長(zhǎng)” 僅僅指的是在輸入或輸出差分僅含有一個(gè)非零比特塊的情況下, 并非針對(duì)所有的不可能差分區(qū)分器.

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

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

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

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

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

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

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

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

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

綜上所述, 命題得證.

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

3.3 CHAM 算法的不可能差分區(qū)分器

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

對(duì)于CHAM-64 算法, 搜索得到5 條一進(jìn)二出的19 輪不可能差分區(qū)分器, 結(jié)果如表3 所示.

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

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

4 CHAM 算法零相關(guān)線性區(qū)分器搜索

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

本節(jié)我們給出一個(gè)基于MILP 自動(dòng)化搜索CHAM 算法的零相關(guān)線性路徑的模型, 并利用該模型搜索得到19 輪CHAM-128 的零相關(guān)線性路徑. 搜索模型與基于MILP 搜索不可能差分路徑的模型相似, 同樣利用不等式組對(duì)算法的每個(gè)組件進(jìn)行等價(jià)刻畫(huà)并組合, 我們不關(guān)心目標(biāo)函數(shù)是什么, 而只關(guān)心不等式體系是否有解. 若無(wú)解, 則當(dāng)前的輸入掩碼和輸出掩碼導(dǎo)致一條零相關(guān)線性路徑.

4.1 線性掩碼傳播規(guī)律

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

假設(shè)分支操作的輸入掩碼是α, 輸出掩碼是β 和γ, 掩碼的長(zhǎng)度都為n 比特, 則可用如下等式來(lái)刻畫(huà)每個(gè)比特上的掩碼傳播:

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

假設(shè)模加操作的輸入掩碼是α 和β, 輸出掩碼是γ, 掩碼的長(zhǎng)度都為n 比特, 則可用如下等式來(lái)刻畫(huà)每個(gè)比特上的掩碼傳播:

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

4.2 搜索策略

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

為了降低搜索零相關(guān)線性路徑的時(shí)間復(fù)雜度, 我們給出CHAM 算法的最長(zhǎng)零相關(guān)線性路徑具有性質(zhì)2. 這里的“最長(zhǎng)” 僅僅指的是在輸入或輸出掩碼僅含有一個(gè)非零比特塊的情況下, 并不是針對(duì)所有的零相關(guān)線性路徑.

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

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

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

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

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

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

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

綜上所述, 命題得證.

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

4.3 CHAM 算法的零相關(guān)線性區(qū)分器

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

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

表4 CHAM-128 零相關(guān)線性路徑Table 4 Zero-correlation linear path of CHAM-128

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

5 總結(jié)

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