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

1. 北京電子科技學(xué)院, 北京100070

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

1 引言

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

為了更好地維護(hù)國家網(wǎng)絡(luò)和信息安全, 加快我國密碼標(biāo)準(zhǔn)化、本土化的發(fā)展, 推動我國密碼理論和應(yīng)用研究, 促進(jìn)密碼算法設(shè)計和實(shí)現(xiàn)技術(shù)進(jìn)步, 培養(yǎng)密碼人才成長, 中國密碼學(xué)會于2019 年舉辦了全國密碼算法設(shè)計競賽. TASS1[12]就是第一輪22 個參賽的分組密碼算法之一.

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

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

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

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

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

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

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

2 TASS1 算法介紹

2.1 符號說明

2.2 算法描述

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

2.2.1 TASS1 算法加密過程

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

表1 隨機(jī)池的初始值Table 1 Initial value of random pool

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

圖1 TASS1 加密過程Figure 1 TASS1 encryption

TASS1 的輪函數(shù)為7 步遞歸結(jié)構(gòu), 由異或、?1、?2、?7、異或隨機(jī)池等操作組成. 非線性移位寄存器遞歸方法如下:

(1) 將輸入的16 字節(jié)(或32 字節(jié)) 按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) 對新產(chǎn)生的A1 和A2, 計算A4=A0⊕A1⊕A2⊕A3.

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

至此, 完成了一步遞歸, 產(chǎn)生了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. 這樣, 又完成了一步遞歸,產(chǎn)生了A5,并變換了A2,A3,A4,···,重復(fù)這種遞歸,直到計算出A10=A6⊕A7⊕A8⊕A9,并使A7,A8,A9 發(fā)生了變換. 最后, (A7,A8,A9,A10) 作為非線性移位寄存器7 步遞歸的輸出結(jié)果.

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

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

2.2.2 TASS1 算法密鑰生成算法

密鑰生成包括密鑰填充和密鑰初始化兩部分. 密鑰初始化的內(nèi)容包括生成輪密鑰和加密隨機(jī)池. 當(dāng)分組長度為128 比特時, 若用戶密鑰不足32 字節(jié), 則需按照密鑰填充規(guī)則將其擴(kuò)展至32 字節(jié), 然后作密鑰初始化. 當(dāng)分組長度為256 比特時, 若用戶密鑰不足64 字節(jié), 則需要將其填充至64 字節(jié).

(1) 密鑰填充

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

(2) 密鑰初始化

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

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

(b) 四次調(diào)用加密函數(shù)將隨機(jī)池加密, 生成密化隨機(jī)池.

(c) 使用密化隨機(jī)池和加密函數(shù)分兩次將密鑰加密, 得密化密鑰, 構(gòu)成2 個輪密鑰.

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

3 TASS1-128 的40 步不可能差分區(qū)分器

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

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

差分特征的搜索思路如下: 對于輸入差分, 使其盡可能晚地到達(dá)高4 位, 從而使得該差分?jǐn)U散速度相對較慢. 對于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 可以正向推導(dǎo)8 步概率為1 的差分路徑,通過算法2 可以反向推導(dǎo)5 步概率為1 的差分路徑.

算法1: TASS1 算法差分注入正向推導(dǎo)Input: 4 個32 bit 的二進(jìn)制數(shù)A3,A2,A1,A0 Output: 4 個32 bit 的二進(jìn)制數(shù)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 算法差分注入反向推導(dǎo)Input: 4 個32 bit 的二進(jìn)制數(shù)A3,A2,A1,A0 Output: 4 個32 bit 的二進(jìn)制數(shù)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

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

圖2 中概率為1 的差分路徑是根據(jù)輸入差分特征進(jìn)行搜索得到, 不具備普適性, 因?yàn)檫@種差分特征相鄰輪數(shù)之間線性關(guān)系明顯, 所以可以通過構(gòu)建齊次線性方程組進(jìn)行推導(dǎo).

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

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

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

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

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

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

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

3.2 40 步不可能差分區(qū)分器

因?yàn)?x10CA3066?= 0x00E61085, 概率為0, 故可構(gòu)造的不可能差分路徑為28 步. 不可能差分的路徑示意圖如圖3 所示.

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

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

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

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

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

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

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

4 TASS1-256 的82 步不可能差分區(qū)分器

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

在此基礎(chǔ)上, 我們認(rèn)為TASS1-256 的安全性較TASS1-128 的安全性更差一些, 最后的分析結(jié)果顯示確實(shí)如此.

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

TASS1-256 與TASS1-128 大致相同, 不同點(diǎn)主要表現(xiàn)為輸入的分組長度. 求差分路徑的時, 僅需改變算法1 和算法2 的輸入和輸出二進(jìn)制長度即可. 將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 可以正向推導(dǎo)7 步概率為1 的差分路徑, 通過改變輸入的算法2 可以反向推導(dǎo)14 步概率為1 的差分路徑. 故可得到21 步差分路徑, 具體路徑如表4所示. TASS1-256 一步輸入輸出涉及到512 個變量, 所以x步涉及的變量總數(shù)為256×(x+1) 個. 構(gòu)建TASS1-256 的具體方程組如表5 所示, 其中x0,x1,··· ,x254,x255為256 位輸入, 為圖2 所示未進(jìn)行分支循環(huán)操作的256 位輸出.

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

4.2 82 步不可能差分區(qū)分器

根據(jù)實(shí)驗(yàn)搜索可以得到具體TASS1-256 的21 步差分路徑, 再由不可能差分構(gòu)造思想容易構(gòu)造44 步不可能差分路徑.

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

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

其中A3in表示第4 支(從低位到高位) 的輸入差分, 將上述方程作為限制條件加入表5 的方程組中進(jìn)行系數(shù)矩陣求秩, 得到方程組的秩與原方程組的秩相同, 故可知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)對應(yīng)的不等式改為等式, 約定xj(i)為第j步差分路徑的第i位, 將等式換算成方程組得:

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

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

5 結(jié)論

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

表6 TASS1 算法分析結(jié)果Table 6 Analysis results for TASS1

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