比特切片型算法差分及線性特征的快速構(gòu)造*

崔雅馨, 徐 洪, 戚文峰

信息工程大學(xué), 鄭州450001

1 引言

分組密碼是密碼學(xué)的重要分支, Feistel、SPN、Lai-Massey 等是常見的分組密碼算法結(jié)構(gòu). 以AES算法為典型代表, SPN 結(jié)構(gòu)通常是由兩個重要組件構(gòu)成: 非線性函數(shù)S 和可逆線性變換P. 非線性函數(shù)S 作為混淆層, 可逆線性變換P 則發(fā)揮擴(kuò)散作用. 除AES 算法外, Serpent[1]、ARIA[2]、PRESENT[3]、RECTANGLE[4]、Skinny[5]、GIFT[6]以及我國分組密碼算法競賽提交的uBlock[7]、FESH[8]、TANGRAM[9]等都是來自SPN 結(jié)構(gòu)的典型算法.

比特切片技術(shù)起初由Biham 等人[10]在1997 年提出用于加速DES 算法的軟件實(shí)現(xiàn)效率, 之后Anderson 等人采用比特切片的思想設(shè)計了Serpent 算法[1]. 比特切片技術(shù)主要優(yōu)勢體現(xiàn)在可以高效提升算法的軟件實(shí)現(xiàn)性能: 對于n 個S 盒并置構(gòu)成的混淆層,每個S 盒需要查表一次,整個混淆層需要做n 次查表操作, 可以把S 盒每個輸出比特通過輸入比特的若干邏輯指令計算得到, 如果每個S 盒是相同的, 則對于n 個S 盒的相同位置比特只需要一次相同的邏輯指令計算完成. 對于RECTANGLE、TANGRAM等擴(kuò)散層采用行循環(huán)移位的比特切片型分組算法, 本文將利用其結(jié)構(gòu)特點(diǎn), 對其安全性做進(jìn)一步分析.

差分分析和線性分析是分組密碼最重要的兩類分析方法. 如何求解最小活動S 盒數(shù)目以估計差分概率(線性偏差) 的安全界, 和如何尋找具有最大差分概率(線性偏差) 的密碼特征是其中面臨的關(guān)鍵問題.2011 年, Mouha 等人[11]利用混合整數(shù)線性規(guī)劃方法(mixed integer linear program, MILP) 給出了基于字節(jié)的最小活動S 盒個數(shù)的自動化搜索. 隨后, 孫思維等人[12,13]進(jìn)一步擴(kuò)展了Mouha 等人的想法,提出了基于比特的MILP 模型, 將S 盒的具體差分樣式轉(zhuǎn)化為相應(yīng)的不等式組, 更加精確地刻畫最小活動S 盒個數(shù)和最優(yōu)差分特征. 此后MILP 自動化搜索技術(shù)被廣泛應(yīng)用于求解各類算法的區(qū)分器. 2016 年,Xiang 等人[14]建立MILP 模型, 搜索SIMON、PRESENT 等6 個輕量級算法的積分區(qū)分器. 2018 年Zhu 等人[15]利用MILP 自動化搜索技術(shù), 提出兩階段搜索策略求解GIFT 差分特征. 2019 年Zhou 等人[16]通過分別征服的思想提出了基于MILP 技術(shù)的搜索算法, 搜索了PRESENT、TWINE 等算法的差分特征.

對于分組規(guī)模較小的分組算法, 借助求解器的強(qiáng)大資源, 可以實(shí)現(xiàn)遍歷所有可行域?qū)ふ易顑?yōu)解, 實(shí)現(xiàn)效率大大提高, 取得了一系列較好的研究成果. 但是針對分組規(guī)模較大的算法, 對于個人現(xiàn)有的計算資源, 利用MILP 建模直接去求解高輪數(shù)的特征, 在有效時間內(nèi)實(shí)現(xiàn)還是困難的. 對于RECTANGLE、TANGRAM 等擴(kuò)散層為行循環(huán)移位的比特切片型算法, 我們希望利用算法本身的結(jié)構(gòu)特點(diǎn)和S 盒的差分(線性) 性質(zhì), 嘗試構(gòu)造單輪或低輪迭代特征, 并結(jié)合MILP 自動化搜索技術(shù)高效構(gòu)造長輪數(shù)的差分和線性特征.

本文中我們引入單輪循環(huán)差分(線性) 特征的概念, 針對RECTANGLE 型比特切片型算法, 根據(jù)算法的行移位參數(shù)和S 盒的可逆差分(線性) 對, 給出了快速構(gòu)造單輪循環(huán)差分(線性) 特征的方法. 進(jìn)而以找到的單輪循環(huán)特征為基礎(chǔ), 結(jié)合MILP 方法找到了一些具有特定輸入和輸出的低輪最優(yōu)差分(線性) 特征, 由此快速構(gòu)造了一些長輪數(shù)的差分(線性) 特征. 進(jìn)一步, 針對可逆差分(線性) 對概率優(yōu)勢不明顯的算法, 搜索了更優(yōu)的低輪循環(huán)差分(線性) 特征. 對于RECTANLE 算法, 可以構(gòu)造概率為的循環(huán)差分特征和線性相關(guān)度為的循環(huán)線性特征, 最后可以分別得到14 輪差分特征和13 輪線性特征; 對于TANGRAM算法, 可以構(gòu)造兩種類型的線性相關(guān)度均為的循環(huán)線性特征, 兩種類型的概率為的循環(huán)差分特征. 進(jìn)一步,找到了TANGRAM 128 算法的三種類型概率均為的3 輪循環(huán)差分特征, TANGRAM 256 算法的3 輪循環(huán)差分特征, 以及2 輪和4 輪循環(huán)線性特征. 最終, 可以快速構(gòu)造出TANGRAM 128 算法的24 輪差分特征和23 輪線性特征, 均與作者設(shè)計文檔中所給出的最優(yōu)差分和線性特征的概率相同. 并且可以快速構(gòu)造出TANGRAM 256 算法的48 輪差分特征和44 輪線性特征, 其中算法設(shè)計者僅給出了直到29 輪最優(yōu)線性特征的概率.

本文主要安排大致如下: 第2 節(jié)介紹必要的預(yù)備知識和涉及的相關(guān)符號, 第3 節(jié)詳細(xì)介紹了如何快速構(gòu)造單輪循環(huán)特征及構(gòu)造所需的條件, 第4 節(jié)針對RECTANGLE 和TANGRAM 算法, 運(yùn)用循環(huán)特征快速構(gòu)造方法構(gòu)造了更長輪數(shù)的差分和線性特征, 第5 節(jié)簡要總結(jié)本文的主要工作.

2 預(yù)備知識

2.1 RECTANGLE 算法

RECTANGLE 算法[4]是由張文濤等人于2015 年提出SPN 結(jié)構(gòu)的輕量級分組密碼算法. 該算法采用比特切片的設(shè)計思想, 便于多平臺的軟硬件實(shí)現(xiàn). 算法分組長度為64 比特, 密鑰長度為80 比特或128比特, 迭代輪數(shù)為25 輪. 每輪輪變換主要包含三個步驟: 密鑰加、列代替和行移位.

設(shè)RECTANGLE 算法某輪的輸入狀態(tài)為w = (w63w62···w0), 則它可以用圖1 所示的4×16 的矩型數(shù)組表示, 或者用二維數(shù)組(ai,j) 表示, 其中0 ≤i ≤15, 0 ≤j ≤3. 為表述方便, 我們也常用各列對應(yīng)的16 進(jìn)制整數(shù)(a15a14···a0) 表示狀態(tài)w.

圖1 RECTANGLE 算法的輪狀態(tài)及其二維表示Figure 1 State of RECTANGLE and its two-dimensional representation

密鑰加: 輪狀態(tài)w 和輪子密鑰K 逐比特異或加.

列替換: 每輪采用十六個相同的 4 比特 S 盒并置, 分別同時作用于每列 4 比特狀態(tài), 得到S(ai,3,ai,2,ai,1,ai,0), 其中所采用的S 盒是4 比特到4 比特的雙射, 具體描述見表1.

表1 RECTANGLE 算法的S 盒Table 1 True table of S-box of RECTANGLE

行移位: 以行為單位進(jìn)行整體的左循環(huán)移位, 第一行保持不動, 第二行循環(huán)左移1 比特, 第三行循環(huán)左移12 比特, 第四行循環(huán)左移13 比特.

2.2 TANGRAM 算法

TANGRAM 算法[9]是張文濤等人提交分組密碼算法競賽的入選算法, 其整體設(shè)計思想延續(xù)了RECTANGLE 算法, 但是分組長度較大, 包含128 比特和256 比特兩個版本, 其中TANGRAM 128算法密鑰長度可選128 比特和256 比特兩種. TANGRAM 128/128 算法總輪數(shù)為44 輪, TANGRAM 128/256 算法為50 輪, TANGRAM 256/256 算法則為82 輪. 每輪操作和RECTANGLE 算法類似, 采用了不同的S 盒和行移位變換, 其中S 盒的具體描述見表2.

行移位變換時, TANGRAM 128 算法保持第一行不動, 第二行循環(huán)左移1 比特, 第三行循環(huán)左移8 比特, 第四行循環(huán)左移11 比特, 即相應(yīng)的移位參數(shù)分別為0, 1, 8, 11. 而TANGRAM 256 算法的行移位參數(shù)分別為0, 1, 8 和41.

表2 TANGRAM 算法的S 盒Table 2 True table of S-box of TANGRAM

2.3 符號說明

n: 每輪S 盒個數(shù);

Si: 第i 個S 盒, 0 ≤i ≤n ?1, 最左邊為第n ?1 個S 盒;

a: S 盒的輸入(或者輸入差分) 對應(yīng)的16 進(jìn)制整數(shù);

b: S 盒的輸出(或者輸出差分) 對應(yīng)的16 進(jìn)制整數(shù);

ai: a 的第i 比特, 0 ≤i ≤3 , 其中a0為最低比特位;

lj: P 變換中第j 行的行移位比特數(shù), 0 ≤j ≤3.

3 單輪循環(huán)特征的快速構(gòu)造

對于RECTANGLE、TANGRAM 等算法, 由于其擴(kuò)散層為簡單行循環(huán)移位, 當(dāng)S 盒具有特定的差分/線性性質(zhì)時, 可以方便構(gòu)造相應(yīng)的單輪循環(huán)差分/線性特征. 為此, 先引入兩個重要概念.

定義1 (S 盒的可逆差分對) 對于4 比特的S 盒, 若存在一對非零比特串a(chǎn) = (a3a2a1a0) 和b =(b3b2b1b0), 使得: 當(dāng)S 盒輸入差分為a 時存在輸出差分b, 并且當(dāng)S 盒輸入差分為b 時存在輸出差分a,則稱差分對a 和b 為可逆差分對, 簡記為a ?b.

以下用α=(un?1un?2···u0) 表示RECTANGLE 型算法的輪狀態(tài)或者狀態(tài)差分, 其中ui為16 進(jìn)制整數(shù).

定義2 (循環(huán)差分特征) 設(shè)α = (un?1un?2···u0) →β = (vn?1vn?2···v0) 是某算法的一條單輪差分特征. 如果β 為α 的循環(huán)移位, 則稱α →β 為一條單輪循環(huán)差分特征. 更一般的, 設(shè)δ = (δ0→δ1→···→δr) 是某算法的一條r 輪差分特征, 如果δr為δ0的循環(huán)移位, 則稱δ 為一條r 輪循環(huán)差分特征.

類似地, 可以定義可逆線性對和循環(huán)線性特征.

下面以RECTANGLE 算法為例說明如何構(gòu)造單輪循環(huán)差分特征. 通過分析S 盒的差分分布表, 可得其存在可逆差分對(0010) ?(0110), 其中(0010) →(0110) 的差分概率為2?3, (0110) →(0010)的差分概率為2?2. 基于這個可逆差分對, 如下構(gòu)造一條單輪循環(huán)差分特征(0200 0060 0000 0000) →(2000 0600 0000 0000), 其中輸入差分(0200 0060 0000 0000) 經(jīng)過S 盒和行移位操作的狀態(tài)差分比特表示如下:

其中S 表示S 盒變換, P 是行移位變換. 注意到RECTANGLE 第二行第三行的循環(huán)左移位比特數(shù)分別為1 和12, 當(dāng)?shù)?4 和第9 個S 盒的輸入差分分別為2 和6, 輸出差分分別為6 和2 時, 經(jīng)行循環(huán)移位后, 第二行的第14 和第9 位的兩個1 差分移到第15 和第10 位, 第三行的第14 位的1 差分移到了第10位, 故單輪變換后恰好第15 和第10 個S 盒的輸出差分非零, 且差分樣式與S 盒輸入差分一樣, 由此得到一條單輪循環(huán)差分特征(0200 0060 0000 0000)→(2000 0600 0000 0000), 重復(fù)上面的過程還可以構(gòu)造其它循環(huán)差分特征.

更一般的, 考慮形如RECTANGLE 的擴(kuò)散層為行循環(huán)移位的比特切片型算法. 假設(shè)算法有n 個4比特的S 盒, 依次為Sn?1Sn?2···S0, 且行移位量分別為lj, 0 ≤j ≤3. 對于這類算法, 定理1 給出了一個存在單輪循環(huán)差分特征的充分條件.

定理1 對于形如RECTANGLE 的擴(kuò)散層為行循環(huán)移位的比特切片型算法, 如果其S 盒存在可逆差分對a ?b, 并且該可逆差分對滿足wt(a)≤2, wt(b)≤2 且wt(a ⊕b)=1, 則其存在單輪循環(huán)差分特征.

證明: 由條件知, a 和b 的重量一個為1, 一個為2, 且有一個非零比特位置相同. 不妨設(shè)wt(a)=1,wt(b)=2. 其中ap=bp=1, bq=1, 0 ≤p ≤3, 0 ≤q ≤3 且p=q.

類似于RECTANGLE 算法的分析, 我們選擇輸入差分使得其恰有兩個活動S 盒, 兩個活動S 盒的輸入差分為(a,b), 輸出差分為(b,a). 為保證經(jīng)過行移位變換后仍然含有兩個活動S 盒, 活動S 盒相差(lp?lq)mod n 個位置.

不妨設(shè)第i 個S 盒為活動S 盒, 其輸入差分為a, 第j =(i+lq?lp)mod n 個S 盒為活動S 盒, 其輸入差分為b, 而其它S 盒的輸入差分都為0. 由于a ?b 是可逆差分對, 我們?nèi)〉趇 個和j 個活動S 盒的輸出差分分別為b 和a. 由于S 盒第p 個比特和第q 個比特的行移位參數(shù)分別是lp和lq, 于是經(jīng)過P層后, 第p 行的第i, j 位的兩個1 差分移到第(i+lp)mod n 和(j+lp)=(i+lq)mod n 位, 第q 行的第i 位的1 差分移到了第(i+lq)mod n 位, 因此輸出差分仍只有兩個活動S 盒, 分別為第(i+lp)mod n和第(i+lq)mod n 個S 盒, 且其輸入差分分別為a 和b. 由此我們構(gòu)造了一條單輪循環(huán)差分特征.

根據(jù)上面的分析, 單輪輸出差分仍然恰有兩個活動S 盒, 其輸出差分仍然是a 和b, 且活動S 盒仍然相差(lp?lq)mod n 個位置, 因此上面的過程可以一直繼續(xù)下去, 得到多條循環(huán)差分特征.

上面介紹的RECTANGLE 算法的例子中, 選擇的兩個活動S 盒恰好相差(12 ?1)mod 16 = 11 個位置, 活動S 盒的輸入差分分別為2 和6, 也滿足定理1 的條件, 可以按定理中的方法構(gòu)造各條循環(huán)差分特征. 對于線性特征, 如果其S 盒存在可逆線性對a ?b, 并且可逆線性對滿足wt(a) = 1, wt(b) = 2 且wt(a ⊕b)=1, 類似可以按定理1 構(gòu)造循環(huán)線性特征.

4 長輪數(shù)差分和線性特征的構(gòu)造

近年來自動化搜索手段被廣泛應(yīng)用于分析各類密碼算法的安全性, 在差分和線性分析方面, 孫思維等人[12,13]提出了基于比特的MILP 自動化搜索模型, 用于求解最小活動S 盒個數(shù)及最優(yōu)差分(線性) 特征. 然而, 隨著算法分組長度的增加, 以及所需求解輪數(shù)的增大, 受限于計算資源, 利用自動化工具在有限時間內(nèi)求解到一條或者多條最佳特征是困難的.

針對RECTANGLE 型擴(kuò)散層為行循環(huán)移位的SPN 型算法, 利用上一節(jié)介紹的方法可以根據(jù)S 盒的差分和線性分布表, 快速構(gòu)造出單輪循環(huán)差分或線性特征, 繼而構(gòu)造出多輪迭代循環(huán)差分或者線性特征.為了構(gòu)造差分概率或者線性偏差更大的差分或者線性特征, 我們可以選擇適當(dāng)長輪數(shù)的迭代循環(huán)特征并借助MILP 方法搜索該迭代循環(huán)特征向前后擴(kuò)展時具有給定輸出或輸入的更優(yōu)的差分或線性特征. 對于64,128, 256 比特三種分組長度的SPN 型算法, 利用MILP 方法, 我們可以在有效時間內(nèi)求解直到10 輪最優(yōu)差分(線性) 特征. 更一般的, 我們還可以利用MILP 方法搜索低輪數(shù)的循環(huán)差分(線性) 特征, 并從這些低輪循環(huán)特征和迭代單輪循環(huán)特征中選擇更優(yōu)的擴(kuò)展構(gòu)造高輪數(shù)的差分(線性) 特征, 得到的主要結(jié)論如下.

4.1 RECTANGLE 算法的差分特征和線性特征

同第3 節(jié)快速構(gòu)造單輪循環(huán)差分特征的方法, 分析RECTANGLE 算法S 盒的差分分布表發(fā)現(xiàn), 存在滿足定理1 條件的可逆差分對(0010) ?(0110), 其中(0010) →(0110) 的差分概率為2?3, (0110) →(0010) 的差分概率為2?2. 因此, 可以按照定理1 的方法構(gòu)造RECTANGLE 算法的單輪循環(huán)差分特征,其中第i 個S 盒Si和第j 個S 盒Sj為活動S 盒, j =(i+12 ?1)mod 16, 兩個活動S 盒的輸入差分分別為(0010) 和(0110), 這條單輪循環(huán)差分特征相應(yīng)的差分概率為2?5.

先利用MILP 方法建立搜索多輪最佳差分特征的模型, 得到低輪數(shù)的最優(yōu)差分特征及概率作為參考依據(jù). 遍歷活動S 盒Si所有可能的位置, 構(gòu)造出若干條單輪循環(huán)差分特征. 選取合適的迭代循環(huán)差分特征, 并利用MILP 方法向前后擴(kuò)展搜索具有給定輸入或輸出差分的低輪最優(yōu)差分特征, 由這些低輪差分特征拼接出長輪數(shù)的差分特征. 特別的, 對于RECTANGLE 算法, 基于一條7 輪的迭代單輪循環(huán)差分特征,在其前面添加1 輪, 并在其后面添加6 輪, 我們得到了一條差分概率為2?61的14 輪差分特征, 具體見表3, 該特征與現(xiàn)有的RECTANGLE 算法最佳差分特征的輪數(shù)及概率相同[4].

類似地, 分析RECTANGLE 算法的線性逼近表, 我們發(fā)現(xiàn)存在滿足條件的可逆線性對(1000) ?(1001), 其中(1000)→(1001) 線性特征的線性相關(guān)度為2?1, (1001)→(1000) 線性特征的線性相關(guān)度為2?2. 因此, 可以類似構(gòu)造RECTANGLE 算法的單輪循環(huán)線性特征, 其中第i 個S 盒Si和第j 個S 盒Sj為活動S 盒, j =(i ?13)mod 16, 兩個活動S 盒的輸入線性掩碼分別為(1000) 和(1001), 相應(yīng)的相關(guān)度為2?3. 我們從單輪循環(huán)線性特征(0080 0000 0000 0009)→(0090 0000 0000 0008) 出發(fā), 迭代生成了7 輪循環(huán)線性特征, 并在其前面添加5 輪后面添加1 輪, 得到了RECTANGLE 算法的一條線性相關(guān)度為2?32的13 輪線性特征, 其具體中間狀態(tài)的線性掩碼值見表4.

表4 RECTANGLE 算法的13 輪線性特征Table 4 13-round linear characteristic of RECTANGLE

4.2 TANGRAM 算法的差分特征和線性特征

4.2.1 TANGRAM 128 算法差分特征的構(gòu)造

對于TANGRAM 128 算法, 根據(jù)第3 節(jié)中快速構(gòu)造單輪循環(huán)差分特征的方法, 分析TANGRAM 算法的差分分布表發(fā)現(xiàn), 存在滿足定理1 條件的可逆差分對(0010) →(0110), (1000) →(1100). 基于這兩個可逆差分對, 對于TANGRAM 128 算法, 選擇兩個活動S 盒Si和Sj, 我們可以如下構(gòu)造兩類循環(huán)差分特征:

(1) 活動S 盒Si和Sj的輸入差分分別是(0010) 和(0110), 輸出差分分別是(0110) 和(0010), 其中j = (i+8 ?1)mod 32, (0010) →(0110) 和(0110) →(0010) 的差分概率均為2?3, 構(gòu)造出的單輪循環(huán)差分特征的概率為2?6.

(2) 活動S 盒Si和Sj的輸入差分分別是(1000) 和(1100), 輸出差分分別是(1100) 和(1000), 其中j =(i+8 ?11)mod 32, (1000)→(1100) 和(1100)→(1000) 的差分概率均為2?3, 構(gòu)造出的單輪循環(huán)差分特征的概率為2?6.

遍歷上述兩類單輪循環(huán)差分特征中活動S 盒Si的位置, 我們一共可以得到64 種單輪循環(huán)差分特征.

通過MILP 方法建模并求解TANGRAM 128 算法的低輪最優(yōu)差分特征和概率. 以前面得到的64種單輪循環(huán)差分特征為基礎(chǔ)迭代生成多輪循環(huán)差分特征, 并向前后擴(kuò)展生成高輪數(shù)的差分特征, 選擇其中的最優(yōu)差分特征輸出. 我們從單輪循環(huán)差分特征(0000 0000 0000 0000 0000 0000 6000 0002) →(0000 0000 0000 0000 0000 0000 2000 0006) 出發(fā), 迭代生成了13 輪循環(huán)差分特征, 在該迭代循環(huán)差分特征前面添加4 輪, 后面添加6 輪, 得到了TANGRAM 128 算法的一條差分概率為2?128的23 輪差分特征, 其中間狀態(tài)的具體差分值見表5.

表5 TANGRAM 128 算法的23 輪差分特征Table 5 23-round differential characteristic of TANGRAM 128

由于上述方法構(gòu)造出的差分特征的概率較低, 我們考慮基于更高概率的低輪循環(huán)差分特征擴(kuò)展構(gòu)造長輪數(shù)的差分特征. 利用MILP 方法我們搜索找到了TANGRAM 128 算法的3 條3 輪循環(huán)差分特征, 參見附錄中的表8. 我們以3 輪循環(huán)差分特征(0000 0000 0000 0000 8001 0000 0000 0000) →(0000 0000 0000 0000 0001 0000 0008 0000) 為基礎(chǔ), 迭代6 次, 得到一條18 輪差分特征, 在該差分特征前面添加2 輪, 后面添加4 輪可以得到如表6 所示的概率為2?124的24 輪差分特征, 該特征的概率與作者設(shè)計文檔中找到的最優(yōu)24 輪差分特征的概率一樣.

表6 TANGRAM 128 算法的24 輪差分特征Table 6 24-round differential characteristic of TANGRAM 128

4.2.2 TANGRAM 128 算法線性特征的構(gòu)造

類似地, 分析TANGRAM 算法的線性逼近表, 我們發(fā)現(xiàn)其存在滿足條件的可逆線性對(0001) →(0011) 和(0001)→(1001). 基于這兩個可逆線性對, 對于TANGRAM 128 算法, 選擇兩個活動S 盒Si和Sj, 我們可以構(gòu)造以下兩類單輪循環(huán)線性特征:

(1) 活動S 盒Si和Sj的輸入線性掩碼分別為(0001) 和(0011), 輸出線性掩碼分別為(0011) 和(0001), 其中j =(i+1)mod 32, (0001)→(0011) 線性特征相關(guān)度為2?2, (0011)→(0001) 線性特征相關(guān)度為2?1, 構(gòu)造出的單輪循環(huán)線性特征的線性相關(guān)度為2?3.

(2) 活動S 盒Si和Sj的輸入線性掩碼分別為(0001) 和(1001), 輸出線性掩碼分別為(1001) 和(0001), 其中j = (i+11)mod 32, (0001) →(1001) 線性特征相關(guān)度為2?1, (1001) →(0001)線性特征相關(guān)度為2?2, 構(gòu)造出的單輪循環(huán)線性特征的線性相關(guān)度為2?3.

遍歷上述兩類單輪循環(huán)線性特征中活動S 盒Si的位置, 我們一共可以得到64 種單輪循環(huán)線性特征.

通過MILP 方法建模并求解TANGRAM 128 算法的低輪最優(yōu)線性特征和相關(guān)度. 以前面得到的64 種單輪循環(huán)線性特征為基礎(chǔ)迭代生成多輪循環(huán)線性特征, 并向前后擴(kuò)展生成高輪數(shù)的線性特征, 選擇其中的最優(yōu)線性特征輸出. 我們從單輪循環(huán)線性特征(0000 0000 0000 0009 0000 0000 0010 0000) →(0000 0000 0000 0001 0000 0000 0090 0000) 出發(fā), 迭代生成了17 輪循環(huán)線性特征, 在該迭代循環(huán)線性特征前面添加5 輪后面添加1 輪, 我們得到了TANGRAM 128 算法的一條線性相關(guān)度為2?62的23 輪線性特征, 其中間狀態(tài)的具體線性掩碼見表7, 該特征的相關(guān)度與作者設(shè)計文檔中找到的最優(yōu)23 輪線性特征的相關(guān)度一樣.

表7 TANGRAM 128 算法的23 輪線性特征Table 7 23-round linear characteristic of TANGRAM 128

4.2.3 TANGRAM 256 算法差分特征的構(gòu)造

TANGRAM 256 算法和TANGRAM 128 算法采用相同的S 盒, 因此存在和TANGRAM 128 算法相同的可逆差分對和可逆線性對. 由于TANGRAM 256 算法和TANGRAM 128 算法的行移位參數(shù)不同, TANGRAM 256 算法的單輪循環(huán)特征不同點(diǎn)在于兩個活動S 盒的間距與TANGRAM 128 不同. 具體地, TANGRAM 256 算法存在如下兩類單輪循環(huán)差分特征:

(1) 活動S 盒Si和Sj的輸入差分分別是(0010) 和(0110), 輸出差分分別是(0110) 和(0010), 其中j =(i+8 ?1)mod 64, 單輪循環(huán)差分特征的概率為2?6.

(2) 活動S 盒Si和Sj輸入差分分別為(1000) 和(1100), 輸出差分分別是(1100) 和(1000), 其中j =(i+8 ?41)mod 64, 單輪循環(huán)差分特征的概率為2?6.

遍歷上述兩類單輪循環(huán)差分特征中Si的位置, 一共可以得到128 種單輪循環(huán)線性特征.

我們從單輪循環(huán)差分特征(0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 6000 0002) →(0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 2000 0006)出發(fā), 迭代生成了34 輪循環(huán)差分特征, 在該迭代循環(huán)差分特征前面添加4 輪, 后面添加6 輪, 我們得到了TANGRAM 256 算法的44 輪差分特征, 其差分概率為2?254, 中間狀態(tài)的具體差分值見附錄中表9.

由于上述方法構(gòu)造出的差分特征的概率較低, 我們考慮基于更高概率的低輪循環(huán)差分特征擴(kuò)展構(gòu)造長輪數(shù)的差分特征. 利用MILP 方法我們搜索找到了TANGRAM 256 算法的3 條3 輪循環(huán)差分特征, 其概率均為2?16, 參見附錄中的表10. 我們以3 輪循環(huán)差分特征(0000 0000 0000 0000 0100 0000 0000 0000 0000 0000 0000 0000 8000 0000 0000) →(0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0000 0008 0000 0000 0000 0000) 為基礎(chǔ), 迭代14 次, 得到一條42 輪差分特征, 在該差分特征前面添加2 輪, 后面添加4 輪可以得到附錄中的表11 所示的概率為2?252的48 輪差分特征, 該特征與作者設(shè)計文檔中找到的48 輪最優(yōu)差分特征的概率一致.

4.2.4 TANGRAM 256 算法線性特征的構(gòu)造

TANGRAM 256 算法和TANGRAM 128 算法采用相同的S 盒, 因此存在和TANGRAM 128 算法相同的可逆線性對, 利用這兩個可逆線性對, 可以構(gòu)造如下兩類單輪循環(huán)線性特征:

(1) 活動S 盒Si和Sj輸入線性掩碼分別為(0001) 和(0011), 輸出掩碼分別為(0011) 和(0001),其中j =(i+1)mod 64, 單輪線性相關(guān)度為2?3.

(2) 活動S 盒Si和Sj輸入線性掩碼分別為(0001) 和(1001), 輸出掩碼分別為(1001) 和(0001),其中j =(i+41)mod 64, 單輪線性相關(guān)度為2?3.

遍歷上述兩類單輪循環(huán)線性特征中Si的位置, 一共可得到128 條單輪循環(huán)線性特征.

與TANGRAM 128 算法線性特征的構(gòu)造相似, 對于TANGRAM 256 算法, 我們從單輪循環(huán)線性特征(0000 0000 0000 0000 0000 0090 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001) →(0000 0000 0000 0000 0000 0090 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001) 出發(fā), 迭代生成了38 輪循環(huán)線性特征, 在該迭代循環(huán)線性特征前面添加5 輪, 后面添加1 輪, 我們得到了TANGRAM 256 算法的44 輪線性特征, 其線性相關(guān)度為2?125, 中間狀態(tài)的具體線性掩碼見附錄中表12. 需要說明的是, 作者的設(shè)計文檔中只給出了直到29 輪最優(yōu)線性特征的相關(guān)度, 而利用MILP 方法我們也難以在有效時間內(nèi)直接尋找44 輪線性特征. 本文利用循環(huán)線性特征方便地構(gòu)造了TANGRAM 256 算法的長輪數(shù)的線性特征.

另外, 利用MILP 方法我們搜索找到了TANGRAM 256 算法的1 條2 輪循環(huán)線性特征和2 條4 輪循環(huán)線性特征, 但其較單輪循環(huán)特征的線性相關(guān)度并沒有提高, 因此不采用多輪循環(huán)線性特征進(jìn)行構(gòu)造.

5 結(jié)束語

本文對于采用比特切片思想設(shè)計的RECTANGLE 等算法進(jìn)行了結(jié)構(gòu)性分析, 根據(jù)行移位量和S 盒的差分及線性分布之間的關(guān)系, 提出了快速構(gòu)造單輪循環(huán)特征的方法. 進(jìn)一步, 擴(kuò)展單輪循環(huán)特征的思想,利用MILP 自動化搜索方法搜索了低輪數(shù)的循環(huán)特征, 再由這些單輪循環(huán)特征或者低輪循環(huán)特征迭代生成較長輪數(shù)的特征, 并向前后擴(kuò)展構(gòu)造更長輪數(shù)的差分和線性特征. 應(yīng)用于RECTANGLE、TANGRAM 128 和TANGRAM 256 算法, 分別給出差分和線性特征. 針對分組規(guī)模較大的SPN 型算法, 我們的方法可以根據(jù)算法組件特點(diǎn)判斷并構(gòu)造長輪數(shù)特征, 具有明顯的實(shí)用價值. 然而我們的構(gòu)造方法在很大程度依賴于算法S 盒的設(shè)計, 無法保證求解所得到的特征是否為最優(yōu)解, 如何利用MILP 方法快速求解最優(yōu)解仍是我們下個階段重要的研究工作.