TASS1 算法的不可能差分區分器搜索*

李艷俊, 林 昊, 孫 瑩, 梁 萌

1. 北京電子科技學院, 北京100070

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

1 引言

隨著社會網絡信息化的快速發展, 信息安全問題變得尤為突出. 密碼算法一直是信息安全中最核心、最關鍵的技術, 在維護國家政治穩定、經濟繁榮中起到了強有力的保障作用, 在很大程度上為國家的國防安全、軍事發展提供了堅實支撐. 進入21 世紀以來, 各個國家都在積極進行密碼算法標準化工作建設, 美國于1997 年啟動AES 計劃, 并在2001 年確定了Rijndael[1]算法為其數據加密標準. 繼美國提出AES計劃后, 歐洲于2000 年啟動了NESSIE 計劃, 并于2003 年確定了Camellia[2]、MISTY1[3]、SHACAL-2[4]三個分組密碼算法連同AES 作為歐洲新世紀的分組密碼標準算法. 同時日本于2000 年4 月啟動了CRYPTREC 密碼評估項目, 并于2003 年5 月公布了他們評選出的密碼, 推薦的分組密碼除了上述的幾種分組密碼, 還包括日本研究人員設計的CIPHERUNICORN-E[5]和CIPHERUNICORN-A[6],Hierocrypt-L1[7]和Hierocrypt-3[8], SC2000[9]. 韓國于2004 年確定了ARIA[10]算法為其分組密碼標準(KS X 1213). 中國國家密碼管理局于2006 年1 月公布了無線局域網產品中適用的建議密碼算法, 其中包括SMS4[11]分組密碼.

為了更好地維護國家網絡和信息安全, 加快我國密碼標準化、本土化的發展, 推動我國密碼理論和應用研究, 促進密碼算法設計和實現技術進步, 培養密碼人才成長, 中國密碼學會于2019 年舉辦了全國密碼算法設計競賽. TASS1[12]就是第一輪22 個參賽的分組密碼算法之一.

TASS1 分組密碼算法支持128 和256 比特兩種分組長度, 支持可變長度的密鑰規模. 基于廣義Feistel 結構設計, 算法迭代輪數為7 輪, 每輪7 步, 共49 步. 算法輪函數包括寄存器遞歸變換和輪密鑰加, 特色之處在于引入了“隨機池” 的概念, 即非線性部件采用密化隨機池查詢: 對于TASS1-128, 隨機池是一個4 進32 出的查找表; 對于TASS1-256, 隨機池是一個4 進64 出的查找表. 初始隨機池公開, 在算法加密開始前隨機池會和主密鑰相互作用, 生成加密所需的密化隨機池和8 個輪密鑰.

差分密碼分析[13]是Biham 和Shamir 于1991 年提出的, 他們利用這種方法攻擊了DES 密碼算法, 其主要思想是通過分析特定明文對的差值對密文對差值的影響來恢復某些密鑰比特的信息. 不可能差分密碼分析是差分密碼分析的特殊形式, 最早由Knudsen[14]和Biham[15]分別獨立提出, 其核心思想就是連接兩段概率為1 的差分路徑, 而這兩段差分路徑在“連接處” 是矛盾的. 利用這種矛盾的性質, 可知導致這些差分路徑的密鑰均為錯誤密鑰, 將這些錯誤密鑰排除, 從而得到正確密鑰.

本文對TASS1 算法做的主要工作包括以下三個方面:

(1) 根據TASS1 算法的加密特性, 通過控制差分盡可能遲的到達高4 位來控制差分的擴散速度, 之后對差分比特單元建立大規模線性方程組求解得到TASS1-128 的19 步概率為1 的差分特征, 基于該差分特征構造40 步不可能差分區分器.

(2) 基于同樣的思路, 通過建立大規模線性方程組求解得到TASS1-256 的40 步概率為1 的差分特征, 在此基礎上, 構建TASS1-256 的82 步(全輪為49 步) 不可能差分區分器.

(3) 給出了對于TASS1 算法在設計方面、安全性方面的一些建議.

本文整體結構如下: 第2 節介紹了TASS1 算法及其符號說明; 第3 節給出了TASS1-128 的差分特征, 并基于該差分特征構建不可能差分區分器; 第4 節給出了TASS1-256 的差分特征, 并基于該差分特征構建不可能差分區分器; 第5 節總結全文并給出了對于TASS1 算法設計方面、安全性分析方面的建議.

2 TASS1 算法介紹

2.1 符號說明

2.2 算法描述

TASS1 分組密碼算法支持128 和256 比特兩種分組長度, 支持可變長度的密鑰規模. 基于廣義Feistel 結構設計, 算法迭代輪數為7 輪, 每輪7 步, 共49 步. 算法輪函數包括寄存器遞歸變換和輪密鑰加, 特色之處在于引入了“隨機池” 的概念, 即非線性部件采用密化隨機池查詢: 對于TASS1-128, 隨機池是一個4 進32 出的查找表; 對于TASS1-256, 隨機池是一個4 進64 出的查找表. 初始隨機池公開, 在算法加密開始前隨機池會和主密鑰相互作用, 生成加密所需的密化隨機池和8 個輪密鑰.

2.2.1 TASS1 算法加密過程

首先, 介紹TASS1 算法的特殊之處在于使用密化隨機池來代替S 盒實現非線性的功能. 算法中使用的是由16 個存儲單元構成的隨機池, 隨機池的初始值如表1.

表1 隨機池的初始值Table 1 Initial value of random pool

隨機池的初始值可以作為秘密在一個用戶群中共享, 在進行加密時, 經過密鑰作用下的一系列變換,隨機池被加密成秘密數值, 將其稱之為密化隨機池. 加解密過程中調用的是密化隨機池中的值. TASS1 算法采用廣義的Feistel 結構, 輪函數采用非線性移位寄存器遞歸方法, 加密流程如圖1 所示.

圖1 TASS1 加密過程Figure 1 TASS1 encryption

TASS1 的輪函數為7 步遞歸結構, 由異或、?1、?2、?7、異或隨機池等操作組成. 非線性移位寄存器遞歸方法如下:

(1) 將輸入的16 字節(或32 字節) 按32 位字(或64 位字) 存入A0,A1,A2,A3.

(2) 將A3 的最高位4 比特取出, 記作x3, 計算A=(A3?1)⊕rp[x3], 并將A異或到A2 中.

(3) 將新A2 的最高位4 比特取出, 記作x2, 計算A=(A2?2)⊕rp[x2], 并將A異或到A1 中.

(4) 對新產生的A1 和A2, 計算A4=A0⊕A1⊕A2⊕A3.

(5) 令Y=A1⊕A2, 將Y的最高位4 比特取出, 記作x12, 計算A=(Y?7)⊕rp[x12], 并將A異或到A3 中.

至此, 完成了一步遞歸, 產生了A4, 并變換了A1,A2,A3. 同樣地, 由A4 和其高位4 比特值x4, 計算A=(A4?1)⊕rp[x4],將A異或到A3; 由新A3 及高位4 比特值x3 計算A=(A3?2)⊕rp[x3],將A異或到A2; 使用新的A2,A3,計算A5=A1⊕A2⊕A3⊕A4. 同樣地, 由A2⊕A3 改造A4. 這樣, 又完成了一步遞歸,產生了A5,并變換了A2,A3,A4,···,重復這種遞歸,直到計算出A10=A6⊕A7⊕A8⊕A9,并使A7,A8,A9 發生了變換. 最后, (A7,A8,A9,A10) 作為非線性移位寄存器7 步遞歸的輸出結果.

TASS1 算法的一步遞歸過程如圖2 所示.

圖2 TASS1 的一步遞歸Figure 2 1-step recursion of TASS1

2.2.2 TASS1 算法密鑰生成算法

密鑰生成包括密鑰填充和密鑰初始化兩部分. 密鑰初始化的內容包括生成輪密鑰和加密隨機池. 當分組長度為128 比特時, 若用戶密鑰不足32 字節, 則需按照密鑰填充規則將其擴展至32 字節, 然后作密鑰初始化. 當分組長度為256 比特時, 若用戶密鑰不足64 字節, 則需要將其填充至64 字節.

(1) 密鑰填充

當分組長度為128 比特時, 若所用密鑰少于32 字節, 設密鑰長為n字節, 14≤n ＜32, 記密鑰為K0,K1,··· ,K(n ?1), 則對i=n,n+1,··· ,31, 約定Ki=i+K(i ?n)mod 256. 例如, 用戶的20 字節密鑰為“0x64, 0x83, 0x02,···, 0xa6”, 則第21 字節密鑰K20 = 20+0x64 = 0x78,第22 字節K21=21+0x83=0x98.分組長度為256 比特時, 若所用密鑰少于64 字節, 則需要將其填充到64 字節. 將n字節密鑰記作K0,K1,··· ,K(n ?1), 16≤n ＜64, 則對i=n,n+1,··· ,63, 約定Ki=i+K(i ?n)mod 256.

(2) 密鑰初始化

密鑰初始化的基本過程如下:

(a) 由完成填充后的密鑰與隨機池共同簡單地生成8 個初級輪密鑰.

(b) 四次調用加密函數將隨機池加密, 生成密化隨機池.

(c) 使用密化隨機池和加密函數分兩次將密鑰加密, 得密化密鑰, 構成2 個輪密鑰.

(d) 由密化密鑰和密化隨機池組合出4 個輪密鑰, 明確8 個實用輪密鑰.

3 TASS1-128 的40 步不可能差分區分器

TASS1 算法的主要非線性部件在于查詢密化隨機池, 且密化隨機池是根據密鑰而定的, 故密碼性能指標未知. 根據加密函數可知真正對隨機池中的值起影響作用的是Ai的最高4 位.

3.1 概率為1 的19 步差分特征

差分特征的搜索思路如下: 對于輸入差分, 使其盡可能晚地到達高4 位, 從而使得該差分擴散速度相對較慢. 對于TASS1-128, 將4 個32 位輸入從高到低分別記為A3,A2,A1,A0. 在A3[2,3,6,9] 注入差分為1,A2[0,2,5,8,10] 注入差分為1,A1[1,5,6,7,10] 注入差分為1,A0[1,5,6,7,10] 注入差分為1. 通過算法1 可以正向推導8 步概率為1 的差分路徑,通過算法2 可以反向推導5 步概率為1 的差分路徑.

算法1: TASS1 算法差分注入正向推導Input: 4 個32 bit 的二進制數A3,A2,A1,A0 Output: 4 個32 bit 的二進制數C3,C2,C1,C0 1 while 1 do Break;5 end 6 C2 ?2 ⊕A1 →C1 7 A0 ⊕C1 ⊕C2 ⊕A3 →C0 8 if C1 ⊕C2 的高四位是0 then 2 A3 ?1 ⊕A2 →C2 3 if C2 的高四位是0 then 4 Break;10 end 11 (C1 ⊕C2) ?7 ⊕A3 →C3 12 將C3,C2,C1,C0 互換至C2,C1,C0,C3 13 end 9算法2: TASS1 算法差分注入反向推導Input: 4 個32 bit 的二進制數A3,A2,A1,A0 Output: 4 個32 bit 的二進制數C3,C2,C1,C0 1 while 1 do Break;4 end 5 (A1 ⊕A0) ?7 ⊕A2 →C3 6 if C3 的高四位是0 then 2 if A1 ⊕A0 的高四位是0 then 3 Break;8 end 9 C3 ?1 ⊕A1 →C2 10 if A1 的高四位是0 then 7 11 Break;12 end 13 A1 ?2 ⊕A3 →C1 14 C3 ⊕A0 ⊕A1 ⊕A3 →C0 15 end

根據以上算法的推導, 可以得到13 步概率為1 的差分路徑, 具體差分路徑如表2 所示.

圖2 中概率為1 的差分路徑是根據輸入差分特征進行搜索得到, 不具備普適性, 因為這種差分特征相鄰輪數之間線性關系明顯, 所以可以通過構建齊次線性方程組進行推導.

由于TASS1 算法的輪函數大部分采用了線性結構,相鄰輪數的數據之間容易構建齊次線性方程組,由方程組得到系數矩陣, 根據系數矩陣的秩和自由變量個數的比較, 可以確定該方程組是否有解. 將TASS1的輸入按位確定變量, 128 位輸入即存在128 個變量, 128 位輸出即存在另外128 個變量,所以一步涉及到256 個變量. 每一步的輸出可作為下一步的輸入,所以假設當前步數為x,則涉及的變量數為128×(x+1).

表2 TASS1-128 的13 步差分路徑Table 2 13-step differential path of TASS1-128

已知TASS1 算法的主要非線性部件是密化隨機池, 影響該隨機池的值為該輸入的最高4 比特. 考慮輸入差分時只需保證該輸入的最高4 比特為0, 即可使得差分傳遞線性化, 由此可構造限制條件方程.

構建TASS1-128 的具體方程組如表3 所示, 其中x0,x1,··· ,x126,x127為128 位輸入,y0,y1,···,y126,y127為圖2 所示未進行分支循環操作前的128 位輸出.

表3 TASS1-128 差分特征方程組Table 3 Differential characteristic equations of TASS1-128

對于19 步TASS1-128 得到規模為2660×2560 的系數矩陣, 調用python 的numpy 庫對該系數矩陣進行求解, 得到秩為2558. 因為系數矩陣的秩小于變量數, 即2558＜2660, 所以該方程組存在非零解,且有3 個非零解. 考慮求解線性方程組, 利用高斯消元法的時間復雜度為O(n3), 給出求解該線性方程組的時間復雜度＜O(236).

當遞歸步數增加時(＞19 步), 得到的秩始終等于變量個數, 即對應齊次線性方程組只有零解. 所以TASS1-128 算法至少存在3 條概率為1 的19 步差分路徑.

3.2 40 步不可能差分區分器

因為0x10CA3066?= 0x00E61085, 概率為0, 故可構造的不可能差分路徑為28 步. 不可能差分的路徑示意圖如圖3 所示.

圖3 TASS1-128 的28 步不可能差分路徑Figure 3 28-step impossible differential path of TASS1-128

其中A3,A2,A1,A0 字長為n, 則由此路徑可以構造2r+2 步不可能差分區分器.

首先, 將(1)式方程作為限制條件加入表3 的方程組進行系數矩陣求秩, 得到方程組的秩與原方程組的秩相同, 故19 步差分路徑滿足該條件.

其次, 將(2)式的不等式改為等式, 約定xj(i)為第j步差分路徑的第i位, 將等式換算成方程組得:

將上述方程作為限制條件加入表3 的方程組進行系數矩陣求秩, 得到秩等于變量數, 即齊次線性方程組沒有非零解. 故該等式不成立, 即(2)式成立.

綜上所述, 每條概率為1 的19 步差分路徑均可以構造40 步不可能差分區分器.

TASS1-128 共有49 步, 目前由3 條概率為1 的19 步差分路徑可組合構造r(3≤r ≤8) 條40 步不可能差分路徑.

4 TASS1-256 的82 步不可能差分區分器

TASS1-256 與TASS1-128 的非線性部件同樣采用高4 位查詢隨機池的方式. 根據遞歸算法可知TASS1-128 中只有12 比特起到非線性作用, 而當分組長度由128 比特增加到256 比特時, TASS1-256 中也只有12 比特起到非線性作用, 因此更容易利用差分特征對該算法進行分析.

在此基礎上, 我們認為TASS1-256 的安全性較TASS1-128 的安全性更差一些, 最后的分析結果顯示確實如此.

4.1 概率為1 的40 步差分特征

TASS1-256 與TASS1-128 大致相同, 不同點主要表現為輸入的分組長度. 求差分路徑的時, 僅需改變算法1 和算法2 的輸入和輸出二進制長度即可. 將4 個64 位輸入從高到低分別記為A3,A2,A1,A0.在A3[0,1,4,9,10] 注入差分為1,A2[1,2,4,7,10,11] 注入差分為1,A1[0,1,5,6,9] 注入差分為1,A0[0,1,5,6,9] 注入差分為1. 通過改變輸入的算法1 可以正向推導7 步概率為1 的差分路徑, 通過改變輸入的算法2 可以反向推導14 步概率為1 的差分路徑. 故可得到21 步差分路徑, 具體路徑如表4所示. TASS1-256 一步輸入輸出涉及到512 個變量, 所以x步涉及的變量總數為256×(x+1) 個. 構建TASS1-256 的具體方程組如表5 所示, 其中x0,x1,··· ,x254,x255為256 位輸入, 為圖2 所示未進行分支循環操作的256 位輸出.

顯然, 這個方程組的系數矩陣更加稀疏, 根據以上方程可以得到40 步的規模為10720×10496 的系數矩陣, 調用python 中的numpy 庫對該系數矩陣進行求解, 得到秩為10490. 因為系數矩陣的秩小于變量數, 即10490＜10496, 可得該方程存在非零解, 且有63 個解. 所以TASS1-256 存在63 條概率為1 的40 步差分路徑. 考慮求解線性方程組, 利用高斯消元法的時間復雜度為O(n3), 給出求解該線性方程組的時間復雜度＜O(242).

4.2 82 步不可能差分區分器

根據實驗搜索可以得到具體TASS1-256 的21 步差分路徑, 再由不可能差分構造思想容易構造44 步不可能差分路徑.

根據方程組的系數矩陣秩求解, 證明存在40 步概率為1 的差分路徑, 結合不可能差分區分器構造條件(推論1), 可以構造82 步不可能差分區分器.

首先, 針對TASS1-256 對推論1 中的(1)式進行變換得到,

其中A3in表示第4 支(從低位到高位) 的輸入差分, 將上述方程作為限制條件加入表5 的方程組中進行系數矩陣求秩, 得到方程組的秩與原方程組的秩相同, 故可知40 步差分路徑滿足推論1 的第一個條件.

表4 TASS1-256 的21 步差分路徑Table 4 21-step differential path of TASS1-256

表5 TASS1-256 差分特征方程組Table 5 Differential characteristic equations of TASS1-256

其次, 將推論1 中的(2)對應的不等式改為等式, 約定xj(i)為第j步差分路徑的第i位, 將等式換算成方程組得:

將上述方程作為限制條件加入表5 的線性方程組進行系數矩陣求秩, 得到秩等于變量數, 即齊次線性方程組沒有非零解. 故該等式不成立, 即(2)式成立.

綜上所述, 可知每條概率為1 的40 步差分路徑均滿足推論1, 即每條概率為1 的40 步差分路徑均可以構造82 步不可能差分區分器. TASS1-256 的總步數為49 步, 已知存在82 步的不可能差分區分器, 這比它本身存在的49 步要更多, 所以可以證明TASS1-256 算法無法對抗不可能差分攻擊, 該算法不安全.

5 結論

本文評估了分組密碼算法TASS1 抵抗差分和不可能差分的安全性. 當算法分組長度為128 比特時,通過對相鄰輪的狀態比特構造線性方程組, 測試系數矩陣的秩小于自變量個數, 推得方程組存在非零解,從而理論證明可得到19 步概率為1 的差分路徑, 由此路徑可以構造40 步不可能差分路徑; 而當分組長度為256 比特時, 構造類似的線性方程組并求秩, 理論證明可得到40 步概率為1 的差分路徑, 由此路徑可以構造82 步(全輪為49 步) 不可能差分路徑. TASS1 分組密碼算法迭代一共為49 步, 根據以上分析結果, 可以得到TASS1 算法無論是128 比特還是256 比特版本的安全性都是不夠的.

表6 TASS1 算法分析結果Table 6 Analysis results for TASS1

對于TASS1 算法的改進意見, 建議在算法的兩個部件進行完善: 首先, 對隨機池密化環節進行簡化,使其密碼指標更加清晰明了, 這樣設計者對算法的安全性評估會更準確; 其次, 對輪函數進行改進, 修改非線性部件的設計, 加大參與非線性混亂的比特量, 使得較短輪數內數據的混亂更加充分, 由此加強算法抵抗高概率差分分析的能力.