比特切片型算法差分及線性特征的快速構造*

崔雅馨, 徐 洪, 戚文峰

信息工程大學, 鄭州450001

1 引言

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

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

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

對于分組規模較小的分組算法, 借助求解器的強大資源, 可以實現遍歷所有可行域尋找最優解, 實現效率大大提高, 取得了一系列較好的研究成果. 但是針對分組規模較大的算法, 對于個人現有的計算資源, 利用MILP 建模直接去求解高輪數的特征, 在有效時間內實現還是困難的. 對于RECTANGLE、TANGRAM 等擴散層為行循環移位的比特切片型算法, 我們希望利用算法本身的結構特點和S 盒的差分(線性) 性質, 嘗試構造單輪或低輪迭代特征, 并結合MILP 自動化搜索技術高效構造長輪數的差分和線性特征.

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

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

2 預備知識

2.1 RECTANGLE 算法

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

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

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

密鑰加: 輪狀態w 和輪子密鑰K 逐比特異或加.

列替換: 每輪采用十六個相同的 4 比特 S 盒并置, 分別同時作用于每列 4 比特狀態, 得到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

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

2.2 TANGRAM 算法

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

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

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

2.3 符號說明

n: 每輪S 盒個數;

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

a: S 盒的輸入(或者輸入差分) 對應的16 進制整數;

b: S 盒的輸出(或者輸出差分) 對應的16 進制整數;

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

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

3 單輪循環特征的快速構造

對于RECTANGLE、TANGRAM 等算法, 由于其擴散層為簡單行循環移位, 當S 盒具有特定的差分/線性性質時, 可以方便構造相應的單輪循環差分/線性特征. 為此, 先引入兩個重要概念.

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

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

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

類似地, 可以定義可逆線性對和循環線性特征.

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

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

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

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

證明: 由條件知, a 和b 的重量一個為1, 一個為2, 且有一個非零比特位置相同. 不妨設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). 為保證經過行移位變換后仍然含有兩個活動S 盒, 活動S 盒相差(lp?lq)mod n 個位置.

不妨設第i 個S 盒為活動S 盒, 其輸入差分為a, 第j =(i+lq?lp)mod n 個S 盒為活動S 盒, 其輸入差分為b, 而其它S 盒的輸入差分都為0. 由于a ?b 是可逆差分對, 我們取第i 個和j 個活動S 盒的輸出差分分別為b 和a. 由于S 盒第p 個比特和第q 個比特的行移位參數分別是lp和lq, 于是經過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. 由此我們構造了一條單輪循環差分特征.

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

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

4 長輪數差分和線性特征的構造

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

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

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

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

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

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

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

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

4.2.1 TANGRAM 128 算法差分特征的構造

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

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

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

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

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

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

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

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

4.2.2 TANGRAM 128 算法線性特征的構造

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

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

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

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

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

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

4.2.3 TANGRAM 256 算法差分特征的構造

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

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

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

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

我們從單輪循環差分特征(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)出發, 迭代生成了34 輪循環差分特征, 在該迭代循環差分特征前面添加4 輪, 后面添加6 輪, 我們得到了TANGRAM 256 算法的44 輪差分特征, 其差分概率為2?254, 中間狀態的具體差分值見附錄中表9.

由于上述方法構造出的差分特征的概率較低, 我們考慮基于更高概率的低輪循環差分特征擴展構造長輪數的差分特征. 利用MILP 方法我們搜索找到了TANGRAM 256 算法的3 條3 輪循環差分特征, 其概率均為2?16, 參見附錄中的表10. 我們以3 輪循環差分特征(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) 為基礎, 迭代14 次, 得到一條42 輪差分特征, 在該差分特征前面添加2 輪, 后面添加4 輪可以得到附錄中的表11 所示的概率為2?252的48 輪差分特征, 該特征與作者設計文檔中找到的48 輪最優差分特征的概率一致.

4.2.4 TANGRAM 256 算法線性特征的構造

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

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

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

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

與TANGRAM 128 算法線性特征的構造相似, 對于TANGRAM 256 算法, 我們從單輪循環線性特征(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) 出發, 迭代生成了38 輪循環線性特征, 在該迭代循環線性特征前面添加5 輪, 后面添加1 輪, 我們得到了TANGRAM 256 算法的44 輪線性特征, 其線性相關度為2?125, 中間狀態的具體線性掩碼見附錄中表12. 需要說明的是, 作者的設計文檔中只給出了直到29 輪最優線性特征的相關度, 而利用MILP 方法我們也難以在有效時間內直接尋找44 輪線性特征. 本文利用循環線性特征方便地構造了TANGRAM 256 算法的長輪數的線性特征.

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

5 結束語

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