ARX 型密碼算法的設(shè)計(jì)與分析*

孫思維, 胡 磊, 劉田雨, 牛鐘鋒, 汪達(dá)超, 張英杰

1.中國(guó)科學(xué)院大學(xué) 密碼學(xué)院, 北京 100049

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

3.中國(guó)科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 北京 100049

4.隆德大學(xué) 電子信息系, 隆德

5.北京雁棲湖應(yīng)用數(shù)學(xué)研究院, 北京 101408

6.清華大學(xué) 丘成桐數(shù)學(xué)科學(xué)中心, 北京 100084

1 引言

ARX 型密碼是一類(lèi)基于模加、(循環(huán)) 移位和異或等位運(yùn)算構(gòu)造的對(duì)稱(chēng)密碼算法.由于現(xiàn)代微處理器對(duì)這些操作的原生支持, ARX 型密碼的軟件實(shí)現(xiàn)代碼緊湊、效率高.另外, 由于模加可以同時(shí)提供擴(kuò)散和混淆功能, 與使用S 盒作為非線性組件的對(duì)稱(chēng)密碼相比, ARX 型密碼避免了查表操作, 在一定程度上可以更好地抵抗基于時(shí)間的側(cè)信道攻擊.學(xué)界和工業(yè)界設(shè)計(jì)了一系列ARX 型對(duì)稱(chēng)密碼, 包括分組密碼、序列密碼、密碼學(xué)置換、雜湊函數(shù)、消息認(rèn)證碼和認(rèn)證加密算法等.

ARX 型密碼在實(shí)際中應(yīng)用廣泛.HIGHT 和LEA 都是ISO/IEC 國(guó)際標(biāo)準(zhǔn)分組密碼算法.ChaCha20-Poly1305 序列密碼在SSL 和TLS 安全協(xié)議中被廣泛使用.ZUC-128[1]和SNOW 系列序列密碼作為ISO/IEC 和3GPP LTE 算法標(biāo)準(zhǔn), 被廣泛應(yīng)用于4G 通信領(lǐng)域.類(lèi)Unix 軟件包GNU 核心工具組的b2sum 命令實(shí)現(xiàn)了BLAKE2 雜湊函數(shù).BLAKE2 在RAR 和7-Zip 壓縮工具中應(yīng)用于文件校驗(yàn).SipHash算法被應(yīng)用于網(wǎng)絡(luò)流量驗(yàn)證和防御Hash-flooding 拒絕服務(wù)攻擊等.Chaskey 作為ISO/IEC 的輕量級(jí)消息認(rèn)證碼標(biāo)準(zhǔn), 被廣泛應(yīng)用在微處理器中.SM3 雜湊函數(shù)則是ISO/IEC 標(biāo)準(zhǔn)及中國(guó)國(guó)家標(biāo)準(zhǔn), 在商用密碼領(lǐng)域應(yīng)用廣泛.另一方面, 由于模加運(yùn)算操作數(shù)的寬度一般為16 位、32 位或64 位等, 很難通過(guò)窮舉的方式刻畫(huà)其差分和線性等密碼學(xué)性質(zhì).因此, 對(duì)ARX 型密碼的分析往往比分析基于小型S 盒的設(shè)計(jì)更困難.本文對(duì)ARX 型密碼算法的設(shè)計(jì)和分析進(jìn)行了歸納總結(jié), 并提出了多個(gè)ARX 型密碼分析研究中亟待解決的開(kāi)放問(wèn)題.

2 代表性ARX 型對(duì)稱(chēng)密碼

2.1 ARX 型分組密碼

ARX 型分組密碼包括FEAL[2]、RC5[3]、TEA、XTEA[4]、Bel-T[5]、HIGHT[6]、LEA[7]、SPECK[8]、SPARX[9]、CHAM[10]、Ballet[11]、CRAX[12]和TRAX[12]等.其中, FEAL[2]是第一個(gè)公開(kāi)提出的ARX 型分組密碼,對(duì)FEAL 的分析, 促進(jìn)了差分分析和線性分析研究的發(fā)展.

FEAL分組密碼.FEAL 是由Shimizu 和Miyaguchi 在1987 年提出的[2],與DES 相比,FEAL 更適用于軟件實(shí)現(xiàn).FEAL 的分組長(zhǎng)度和密鑰長(zhǎng)度均為64 比特, 總輪數(shù)為8 輪, 其輪函數(shù)如圖1 所示.FEAL 的加密過(guò)程見(jiàn)算法1, 記第i個(gè)輪函數(shù)(i ∈{0,1,···,7}) 的輸入為(Li,Ri), 其中,Li=(L0i,L1i,L2i,L3i)∈(F82)4,Ri= (R0i,R1i,R2i,R3i)∈(F82)4.Kj= (K0j,K1j)∈(F82)2(j ∈{0,1,···,15}) 是由主密鑰K ∈F642生成的, 具體生成方式見(jiàn)文獻(xiàn)[2].

圖1 FEAL 密碼算法的第i 輪輪函數(shù)Figure 1 The i-th round function of FEAL

SPECK分組密碼.SPECK 是由美國(guó)國(guó)家安全局Beaulieu 等人在2013 年提出的, 正式發(fā)表于DAC 2015[13].根據(jù)不同的分組長(zhǎng)度和密鑰長(zhǎng)度, 該算法有十個(gè)版本, 每個(gè)版本的輪函數(shù)結(jié)構(gòu)相同.分組長(zhǎng)度為2n比特的SPECK 算法加密過(guò)程的第i輪如圖2(左) 所示.密鑰長(zhǎng)度為mn比特的SPECK 算法的密鑰編排如圖2(右) 所示(其中Ri為圖2 左圖使用常數(shù)i作為輪密鑰的輪函數(shù)).

圖2 左: SPECK 密碼算法的輪函數(shù); 右: SPECK 密碼算法的密鑰編排算法Figure 2 Left: Round function of SPECK cipher; Right: Key schedule of SPECK cipher

LEA分組密碼.LEA[7]是由Hong 等人在2013 年提出的, 目前是韓國(guó)標(biāo)準(zhǔn)分組密碼之一.該密碼算法有三個(gè)版本: LEA-128、LEA-192 和LEA-256, 分組長(zhǎng)度均為128 比特, 密鑰長(zhǎng)度分別為128、192 和256).比特, 對(duì)應(yīng)輪數(shù)分別為24、28 和32, 每個(gè)版本的加密過(guò)程使用相同的輪函數(shù)結(jié)構(gòu), 如圖3 所示.LEA 采用了純線性的密鑰編排算法, 具體情況請(qǐng)參考文獻(xiàn)[7].

算法1 FEAL 密碼算法的加密過(guò)程(L0,R0) ←(L0,R0)⊕(K8,K9,K10,K11);R0 ←R0 ⊕L0;for 1 ≤i ≤8 do Ri ←Li?1 ⊕F(Ri?1,Ki?1);Li ←Ri?1;end L8 ←L8 ⊕R8;(R8,L8) ←(R8,L8)⊕(K12,K13,K14,K15

圖3 LEA 密碼算法的輪函數(shù)Figure 3 Round function of LEA cipher

Ballet 分組密碼.Ballet 是由崔婷婷等人設(shè)計(jì)提出的, 是2019 年全國(guó)密碼算法設(shè)計(jì)競(jìng)賽中獲得一等獎(jiǎng)的算法之一[11].該密碼算法有三個(gè)版本: Ballet-128/128、Ballet-128/256 和Ballet-256/256,(Ballet-u/v的分組長(zhǎng)度為u比特, 密鑰長(zhǎng)度為v比特) 輪數(shù)分別為46、48 和74.每個(gè)版本均使用相同的輪函數(shù)結(jié)構(gòu), 如圖4 所示, 最后一輪省略最后一個(gè)線性置換操作.記分組長(zhǎng)度為4n比特的Ballet 的第i輪輪函數(shù)的輸入為(xi0,xi1,xi2,xi3)∈F4n2, (skLi,skRi)∈F2n2為第i輪的輪密鑰.Ballet 使用了線性密鑰編排算法, 細(xì)節(jié)見(jiàn)文獻(xiàn)[11].

圖4 Ballet 密碼算法的輪函數(shù)Figure 4 Round function of Ballet cipher

圖5 左: SPARKLE 密碼算法的第s 步; 右: SPARKLE 密碼算法中的ARX-box Alzette (Ac)Figure 5 Left: The s-th step of SPARKLE cipher; Right: The ARX-box Alzette (Ac) in SPARKLE cipher

2.2 ARX 型密碼學(xué)置換

密碼學(xué)置換通常在其他對(duì)稱(chēng)密碼中作為組件使用, 尤其是在基于海綿結(jié)構(gòu)的雜湊函數(shù)和認(rèn)證加密中經(jīng)常使用.本節(jié)只介紹一個(gè)典型的ARX 型密碼學(xué)置換SPARKLE[14].SPARKLE 是由Beierle 等人在2019 年提出的, 基于該置換構(gòu)造的輕量級(jí)認(rèn)證加密方案和雜湊函數(shù)參與了NIST 輕量級(jí)密碼競(jìng)賽并進(jìn)入第三輪.

2.3 ARX 型序列密碼

典型的ARX 序列密碼包括Salsa[15]和ChaCha.廣義上講, 在其算法中使用模加操作的對(duì)稱(chēng)密碼都可以稱(chēng)為ARX 型密碼.因此, SNOW 家族(包括SNOW[16]、SNOW 2.0[17]、SNOW 3G[18]和SNOW-V[19])和ZUC[20]等序列密碼都可以被歸類(lèi)為ARX 型密碼.

ChaCha 序列密碼.ChaCha 是由 Bernstein 在 2008 年提出的, 是 eSTREAM 獲勝算法Salsa20 的改進(jìn)版本[21].ChaCha 的密鑰流輸出過(guò)程見(jiàn)算法2, 其中使用了一個(gè)所謂的1/4 輪函數(shù)QuarterRound(a,b,c,d), 如圖6 所示.ChaCha 的初始輸入可以看成一個(gè)4×4 的矩陣:

圖6 ChaCha 密碼算法的1/4 輪函數(shù)QuarterRound(a,b,c,d)Figure 6 QuarterRound(a,b,c,d), the 1/4 round-function of ChaCha

其中,ci為常數(shù),ki為密鑰,mi為nonce,ci,ki,mi的長(zhǎng)度均為4 字節(jié).

算法2 ChaCha 密碼算法(x0,x1,x2,x3) ←(c0,c1,c2,c3); (x4,x5,··· ,x11) ←(k0,k1,··· ,k7);(x12,x13,x14,x15) ←(m0,m1,m2,m3); (y0,y1,··· ,y15) ←(x0,x1,··· ,x15);for 1 ≤i ≤r do if i is odd then QuarterRound(x0,x4,x8,x12); QuarterRound(x1,x5,x9,x13);QuarterRound(x2,x6,x10,x14); QuarterRound(x3,x7,x11,x15);else QuarterRound(x0,x5,x10,x15); QuarterRound(x1,x6,x11,x12);QuarterRound(x2,x7,x8,x13); QuarterRound(x3,x4,x9,x14);end end(x0,x1,··· ,x15) ←(x0,x1,··· ,x15)?(y0,y1,··· ,y15).

SNOW-V 序列密碼.SNOW-V 是由Ekdahl 等人在2019 年提出的[19], SNOW-V 是為了滿足5G 通信系統(tǒng)中的高速加密需求設(shè)計(jì)的, 可以視為SNOW-3G 的改進(jìn)版本.SNOW-V 的內(nèi)部狀態(tài)(T0,T1,T2,T3,R1,R2,R3)∈F128×72按算法3 由線性反饋移位寄存器(LFSR) 和有限狀態(tài)機(jī)(FSM) 進(jìn)行更新.其初始化階段及密鑰流生成階段分別如圖7 和圖8 所示, 其中兩個(gè)AES 加密對(duì)應(yīng)的輪函數(shù)的輪密鑰設(shè)為零,σ為字節(jié)置換.在初始化階段, FSM 的更新依賴(lài)于整個(gè)狀態(tài)(T2,R1,R2,R3), 因此需要先執(zhí)行FSM 的更新,再執(zhí)行LFSR 的更新.SNOW-V 中LFSR 的更新如圖9 所示, LFSR-A 與LFSR-B 滿足

圖7 SNOW-V 初始化階段的輪函數(shù)Figure 7 Round function of initialization phase ofSNOW-V

圖8 SNOW-V 密碼算法產(chǎn)生密鑰流工作階段的輪函數(shù)Figure 8 Round function of keystream generationphase of SNOW-V

圖9 SNOW-V 密碼算法中的LFSRFigure 9 LFSR in SNOW-V

其中,α,β分別表示F2[x] 上兩個(gè)不可約多項(xiàng)式gA(x),gB(x) 的根,α?1,β?1是相應(yīng)域中的逆.gA(x) =x16+x15+x12+x11+x8+x3+x2+x+1,gB(x) =x16+x15+x14+x11+x8+x6+x5+x+1.若x ∈F216,x=(x15,x14,···,x0),在多項(xiàng)式gA(x)中αx=(x14,x13,···,x0,0)⊕x15·(100110010000111),(100110010000111) 為gA(x) 小于16 次冪的多項(xiàng)式系數(shù); 多項(xiàng)式gB(x) 中同理.依次對(duì)LFSR-A 與LFSR-B 對(duì)應(yīng)的等式進(jìn)行8 輪計(jì)算,每一輪計(jì)算后將結(jié)果放在最高位a15,b15,原其他各位a15,···,1,b15,···,1向低位移動(dòng)一位至a14,···,0,b14,···,0, 省略原最低位a0,b0.

算法3 SNOW-V 密碼算法// 初始化階段T3 = (a15,a14,··· ,a8) ←(k7,k6,··· ,k0);T2 = (a7,a6,··· ,a0) ←(iv7,iv6,··· ,iv0);T1 = (b15,b14,··· ,b8) ←(k15,k14,··· ,k8);T0 = (b7,b6,··· ,b0) ←(0,0,··· ,0);(R1,R2,R3) ←(0,0,0);for 1 ≤t ≤16 do z ←(R31 ?T31,R21 ?T21,R11 ?T11,R01 ?T01)⊕R2;FSM update();LFSR update();T3 ←T3 ⊕z;if t = 15 then R1 ←R1 ⊕(k7,k6,··· ,k0);end if t = 16 then R1 ←R1 ⊕(k15,k14,··· ,k8);end end// 產(chǎn)生密鑰流工作階段, 計(jì)算n 個(gè)密鑰分組z while n > 0 do Output z ←(R31 ?T31,R21 ?T21,R11 ?T11,R01 ?T01)⊕R2;FSM update();LFSR update();n ←n ?1 end

2.4 ARX 型雜湊函數(shù)

具有代表性的ARX 型雜湊函數(shù)包括SKEIN 家族[22]、BLAKE 家族[23]、ESCH[14]和我國(guó)商用密碼標(biāo)準(zhǔn)算法SM3[24]等.

SKEIN 雜湊函數(shù).SKEIN 是由Atighehchi 等人在2010 年提出的, 是SHA-3 競(jìng)賽中進(jìn)入決賽的5個(gè)算法之一[25].SKEIN 采用了所謂的唯一分組迭代(unique block iteration, UBI) 結(jié)構(gòu)和可調(diào)分組密碼THREEFISH 構(gòu)造.SKEIN 算法根據(jù)輸出的摘要長(zhǎng)度有三個(gè)版本, 分別為SKEIN-256、SKEIN-512 和SKEIN-1024.這里只介紹SKEIN-256.首先, SKEIN-256 中的可調(diào)分組密碼THREEFISH-256 的密鑰長(zhǎng)度與分組長(zhǎng)度均為256 比特, 調(diào)柄長(zhǎng)度為128 比特.THREEFISH-256 共有72 輪, 每4 輪通過(guò)模加注入一次輪子密鑰,其4 輪結(jié)構(gòu)及其中的Mix 函數(shù)如圖10 所示, 共Nr輪.Mix 是ARX 結(jié)構(gòu)的函數(shù), 其移位參數(shù)Rd,j與Mix 在THREEFISH-256 中的位置相關(guān), 而Permute 是一個(gè)比特置換操作.令(k0,k1,k2,k3)∈F4×642 為主密鑰,T= (t0,t1)∈F2×642 為調(diào)柄,k4= 0x1BD11BDAA9FC1A22⊕k0⊕k1⊕k2⊕k3,t2=t0⊕t1,Ks,i代表第s個(gè)子鑰Subkeys的第i個(gè)字, 其計(jì)算過(guò)程如下:

圖10 左: SKEIN 雜湊函數(shù)中THREEFISH-n 的前4 輪輪函數(shù); 右: Mix 函數(shù)結(jié)構(gòu)圖Figure 10 Left: First four round functions of THREEFISH-n in SKEIN hash function; Right: Structure of Mix

SKEIN-256 的結(jié)構(gòu)如圖11 所示.其中, 初始鏈接值為256 比特的的全0 字符串, Config 為256 比特的配置字符串, 調(diào)柄值Ts= (first,final,Ttype,B,0119?log2len,len)∈F1282, 其中first、final、len 的值如圖11 所示,Ttype∈{Tcfg,Tmsg,Tout}?F62,B ∈F2,B=1 表示分組的最后一個(gè)字節(jié)輸入不足8 比特, 否則B=0.

圖11 SKEIN 雜湊函數(shù)結(jié)構(gòu)圖Figure 11 Structure of SKEIN hash function

圖12 BLAKE2 雜湊函數(shù)的壓縮函數(shù)Figure 12 Compress function of BLAKE2 hash function

圖13 BLAKE2 壓縮函數(shù)Compress 中的函數(shù)G 的輪函數(shù)Figure 13 G function in compress function of BLAKE2

G函數(shù)的輸入狀態(tài)

然后對(duì)狀態(tài)重復(fù)如下操作10 輪:

ESCH 雜湊函數(shù).ESCH 是由Beierle 等人在2019 年基于海綿結(jié)構(gòu)和SPARKLE 置換設(shè)計(jì)的雜湊函數(shù)[14], 該算法參與了NIST 輕量級(jí)密碼競(jìng)賽并進(jìn)入了第三輪.對(duì)于任意長(zhǎng)度的消息, ESCH256 可以產(chǎn)生256 比特的雜湊值, ESCH384 可以產(chǎn)生384 比特的雜湊值.這里只介紹主要版本ESCH256, 其結(jié)構(gòu)圖如圖14 所示.其中的SPARKLEnns為分組長(zhǎng)度為n、步數(shù)為ns的SPARKLE 算法.在ESCH256 中, 基于的密碼學(xué)置換為SPARKLE384, 函數(shù)Mhb的具體實(shí)例為M3, 如式(1)所定義.

圖14 ESCH 雜湊函數(shù)結(jié)構(gòu)圖Figure 14 Structure of ESCH hash function

在ESCH 雜湊函數(shù)中, 需首先將消息M填充, 先補(bǔ)1 再補(bǔ)若干個(gè)0, 使填充后的消息長(zhǎng)度為128 的倍數(shù)(若已滿足此條件則無(wú)需填充), 并將消息分為長(zhǎng)度為128 比特的消息分組, 記為P0,P1,···,P??1,?為消息分組個(gè)數(shù)(如果消息為空, 則給P0填充至r比特).若最后一個(gè)消息分組有填充, 則記常數(shù)cM= (0,0,···,0,1)∈F1922, 否則記常數(shù)cM= (0,0,···,1,0)∈F1922.在消息吸收階段, 初始狀態(tài)為S=(0,0,···,0,0)∈F3842, 對(duì)于前? ?1 個(gè)SPARKLE 置換, 記為SPARKLE3847, 輸入為S ⊕(P′j,0192), 即將P′j異或到狀態(tài)的左半部分上, 其中P′j=M3(Pj||064),j=0,1,···,? ?2, 輸出仍記為S.對(duì)于第?個(gè)SPARKLE, 記為SPARKLE38411, 輸入為S⊕(P′??1||0192)⊕cM, 其中P′??1=M3(P??1||064), 輸出仍記為S.在擠出階段, 截取狀態(tài)S的左半部分128 比特, 記為D0; 在進(jìn)行SPARKLE3847計(jì)算后, 截取狀態(tài)S的左半部分128 比特, 記為D1最后的雜湊值即為(D0,D1).

SM3 雜湊函數(shù).SM3 雜湊函數(shù)是2010 年公布的中國(guó)商用密碼雜湊算法標(biāo)準(zhǔn), 與SHA-256 等算法一樣為Merkle–Damg?rd 結(jié)構(gòu), SM3 的安全性也與SHA-256 相當(dāng).首先, SM3 密碼算法將消息長(zhǎng)度填充至512的倍數(shù), 在消息填充中, 需填充一個(gè)1, 再填充k個(gè)0, 其中k為滿足(len+1+kmod 512=448) 的最小正整數(shù), len 為消息長(zhǎng)度比特.隨后, 添加64 比特的數(shù)據(jù)長(zhǎng)度len 的二進(jìn)制表示.初始鏈接值IV∈F2562設(shè)置為0x7380166F 4914B2B9 172442D7 DA8A0600 A96F30BC 163138AA E38DEE4D B0FB0E4E; 壓縮函數(shù)每次吸收一消息塊m ∈F5122, 將鏈接值h= (A,B,C,D,E,F,G,H)∈F2562與消息塊m作為輸入, 壓縮為h′∈F2562, 將h ⊕h′作為下一個(gè)消息塊的鏈接值; 在吸收最后一個(gè)消息塊后, 將更新的鏈接值作為雜湊函數(shù)的256 比特輸出.SM3 密碼算法的壓縮函數(shù)為一個(gè)ARX 結(jié)構(gòu)的迭代函數(shù), 迭代輪數(shù)為64 輪, 如圖15 所示, 其中, 壓縮函數(shù)中的置換函數(shù)P0, 算法常量Tj ∈F322, 布爾函數(shù)FFj、GGj分別如式(2)–(5)所示.

圖15 SM3 壓縮函數(shù)結(jié)構(gòu)圖Figure 15 Structure of compress function of SM3

對(duì)于壓縮函數(shù)的消息擴(kuò)展算法,512 比特?cái)?shù)據(jù)的消息塊m劃分為16 個(gè)32 比特消息字(W0,W1,···,W15),并以此16 個(gè)消息字生成另外的116 個(gè)消息字.消息字W16,W17,···,W67的生成過(guò)程為

其中, 消息擴(kuò)展中的置換函數(shù)P1(X)=X ⊕(X?15)⊕(X?23).

2.5 ARX 型消息認(rèn)證碼

ARX 型消息認(rèn)證碼(MAC) 通?；贏RX 型雜湊函數(shù)及密碼學(xué)置換構(gòu)造.雜湊函數(shù)可天然地構(gòu)造MAC, 如基于BLAKE2 構(gòu)造的MAC[27]和SipHash[28]等.其中, SipHash 由Aumasson 和Bernstein于2012 年設(shè)計(jì), 是一族帶密鑰的哈希函數(shù), 與HMAC 的構(gòu)造方法類(lèi)似, 設(shè)計(jì)時(shí)參考并結(jié)合了BLAKE 和SKEIN 等雜湊函數(shù)的特點(diǎn), 其設(shè)計(jì)目的是為了應(yīng)對(duì)2011 年底發(fā)生的一系列Hash-flooding 拒絕服務(wù)攻擊.基于ARX 型密碼學(xué)置換構(gòu)造的MAC 如Chaskey[29]等.Chaskey 由Mouha 等于2014 年提出, 其置換的初始輪數(shù)為8 輪, 后改為12 輪, 12 輪版本的Chaskey 是ISO/IEC 輕量級(jí)消息認(rèn)證碼標(biāo)準(zhǔn)[30]之一.

Chaskey 消息認(rèn)證碼.Chaskey 消息驗(yàn)證碼是由Mouha 等在2014 年設(shè)計(jì)提出的基于置換的消息驗(yàn)證碼算法[29], Chaskey 密碼算法中的置換函數(shù)π是基于ARX 結(jié)構(gòu)設(shè)計(jì)的, 置換π的輪函數(shù)如圖16 所示.

圖16 Chaskey 密碼算法中置換π 的輪函數(shù)Figure 16 Round function of permutation π in Chaskey cipher

Chaskey 密碼算法如算法4 所示, 其中Subkeys(·) 將密鑰K ∈F1282擴(kuò)展為(K1,K2)∈F2×1282.其中,K1是由K擴(kuò)展而來(lái);K2是由K1擴(kuò)展而來(lái):

K ?1 為將K左移1 位.

在計(jì)算第i個(gè)消息分組mi ∈F1282, 1≤i ≤? ?1, 置換π的輸入為第i個(gè)π的輸出hi與mi的異或(h1=K), 置換π對(duì)每個(gè)輸入進(jìn)行12 輪計(jì)算, 輸出為hi+1.若最后一個(gè)消息分組m?的長(zhǎng)度正好為128比特, 則令h? ⊕m? ⊕K1作為最后一個(gè)置換π的輸入, 將輸出結(jié)果與K1異或得到h?+1; 若最后一個(gè)消息分組的長(zhǎng)度不足128 比特, 需先補(bǔ)1 再補(bǔ)若干個(gè)0 填充至128 比特, 并記為m?; 且將h? ⊕m? ⊕K2作為π的輸入, 將置換π的輸出與K2異或得到h?+1.最后, Chaskey 的輸出MAC 值為h?+1的后t位.

算法4 Chaskey 密碼算法(K1,K2) ←SubKeys(K); (m1||m2||···||ml) ←m; h1 ←K;for 1 ≤r ≤(l ?1) do hi+1 ←π(hi ⊕mi);end if (|ml| = n) then L ←K1;else ml ←ml||10n?|ml|?1;L ←K2;end hl+1 ←π(hl ⊕ml ⊕L)⊕L;τ ←hl+1[n ?t+1,n].

2.6 ARX 型認(rèn)證加密

ARX 型帶關(guān)聯(lián)數(shù)據(jù)的認(rèn)證加密方案(AEAD) 通?；贏RX 型序列密碼和密碼學(xué)置換等構(gòu)造.基于ARX 型序列密碼構(gòu)造的AEAD, 如基于ChaCha20 構(gòu)造的ChaCha20-Poly1305[31]和基于SNOW 3G和ZUC 構(gòu)造的LTE 機(jī)密性和完整性方案[32,33]等.基于ARX 型密碼學(xué)置換構(gòu)造的AEAD, 如基于SPARKLE 構(gòu)造的SCHWAEMM[14]等.

Schwaemm AEAD 認(rèn)證加密.Schwaemm 關(guān)聯(lián)數(shù)據(jù)的認(rèn)證加密(AEAD) 是由Beierle 等人在2019 年基于SPARKLE 結(jié)構(gòu)設(shè)計(jì)的密碼算法[14], 其為一輕量級(jí)認(rèn)證加密算法參與了NIST 輕量級(jí)密碼競(jìng)賽并進(jìn)入了第三輪, 對(duì)于給定密鑰K、Nonce 值N、任意長(zhǎng)度的關(guān)聯(lián)數(shù)據(jù)A以及消息M(關(guān)聯(lián)數(shù)據(jù)A與消息M的長(zhǎng)度不要求相同), 輸出一個(gè)與消息M等長(zhǎng)的密文C以及一個(gè)固定長(zhǎng)度的認(rèn)證標(biāo)簽T.Schwaemm AEAD 的4 個(gè)版本對(duì)應(yīng)的參數(shù)如表1 所示, 其中的SPARKLEnns為分組長(zhǎng)度為n、步數(shù)為ns的SPARKLE算法, 以其主要版本Schwaemm256-128 進(jìn)行介紹, 如圖17 所示.

表1 Schwaemm AEAD 的參數(shù)設(shè)定Table 1 Parameters of Schwaemm AEAD

在Schwaemm256-128 AEAD 的加密過(guò)程中, 首先對(duì)關(guān)聯(lián)數(shù)據(jù)A與消息M進(jìn)行填充, 先補(bǔ)1 再補(bǔ)若干個(gè)0, 使填充后的關(guān)聯(lián)數(shù)據(jù)A的長(zhǎng)度與消息M的長(zhǎng)度均為256 的倍數(shù)(若已滿足此條件則無(wú)需填充), 并將其按256 比特分成若干分組.若A的最后一個(gè)分組有填充, 則常數(shù)ConstA ∈F3842設(shè)置為0x0⊕(0x1?2), 否則設(shè)置為ConstA= (0x0)⊕(0x1?2); 若M的最后一個(gè)分組有填充, 則ConstM ∈F3842設(shè)置為0x2⊕(0x1?2), 否則設(shè)置為0x3⊕(0x1?2).在初始化階段, 其初始狀態(tài)為(N,K), 經(jīng)過(guò)SPARKLE38411, 輸出為(SL,SR), 其中N,SL ∈F2562,K,SR ∈F1282.隨后吸收?A個(gè)關(guān)聯(lián)數(shù)據(jù), 對(duì)于第j個(gè)關(guān)聯(lián)數(shù)據(jù), 0≤j ≤?A ?2, 首先將(SL,SR)變換為(ρ1(SL,Aj)⊕W128,256(SR),SR), 其中W128,256(x,y)=(x,y,x,y),x,y ∈F642;ρ1(S,D)=FeistelSwap(S)⊕D,S,D ∈F2562; FeistelSwap(S)=(S2,S2⊕S1),S= (S1,S2),S1,S2∈F1282.隨后進(jìn)行SPARKLE3847運(yùn)算, 輸出為(SL,SR).對(duì)于第?A個(gè)關(guān)聯(lián)數(shù)據(jù), 首先要異或一個(gè)常量, 即SR=SR ⊕ConstA, 隨后, 進(jìn)行相似的運(yùn)算, 但唯一不同點(diǎn)為使用的置換為SPARKLE38411.在加密階段, 對(duì)于第j個(gè)消息, 0≤j ≤?M ?1, 輸出Cj=Mj ⊕SL作為密文.對(duì)于第j個(gè)消息的吸收, 0≤j ≤?M ?2, 首先將(SL,SR) 變換為(ρ1(SL,Mj)⊕W128,256(SR),SR)運(yùn)算, 其中W128,256(x,y) = (x,y,x,y),x,y ∈F642;ρ1(S,D) = FeistelSwap(S)⊕D,S,D ∈F2562;FeistelSwap(S) = (S2,S2⊕S1),S= (S1,S2),S1,S2∈F1282.接著進(jìn)行SPARKLE3847運(yùn)算, 輸出為(SL,SR).對(duì)于第?M個(gè)消息的吸收, 首先要異或一個(gè)常量, 即SR=SR ⊕ConstM, 隨后, 進(jìn)行相似的運(yùn)算, 輸出密文C?M并吸收消息M?M; 但唯一不同點(diǎn)為使用的置換為SPARKLE38411.最后, 輸出SR ⊕K作為認(rèn)證標(biāo)簽T ∈F1282.

3 對(duì)ARX 型密碼算法的分析

ARX 算法作為對(duì)稱(chēng)密碼算法的一大子類(lèi), 針對(duì)基于S 盒設(shè)計(jì)的對(duì)稱(chēng)密碼算法的分析方法也“自然”地適用于ARX 算法.在目前已知的密碼分析中, 一般都是通過(guò)挖掘非線性部件的密碼學(xué)性質(zhì), 來(lái)實(shí)現(xiàn)對(duì)整個(gè)加密算法的分析; 在基于S 盒設(shè)計(jì)的對(duì)稱(chēng)密碼算法中, 由于非線性部件S 盒的規(guī)模較小, 可以采用枚舉所有可能輸入的方式來(lái)獲取其密碼學(xué)性質(zhì); 然而,在ARX 型密碼算法中,由于其唯一的非線性運(yùn)算—模加操作的規(guī)模比較大, 一般為32 比特的字, 枚舉方式是不可行的, 相關(guān)的理論發(fā)展以及分析ARX 算法的工具往往是滯后的, 密碼分析者需要去構(gòu)建新的計(jì)算方法來(lái)挖掘模加操作的密碼學(xué)性質(zhì)進(jìn)而實(shí)現(xiàn)對(duì)ARX算法的密碼分析.本節(jié)將介紹模加操作在五種常用密碼分析技術(shù)中的分析方法.這五種分析技術(shù)是: 差分分析、線性分析、差分-線性分析、可分性分析和飛來(lái)去器分析.為了明確模加操作中數(shù)值的比特長(zhǎng)度, 本節(jié)使用符號(hào)“?” 來(lái)表示模2n的模加操作.

3.1 差分分析

差分分析是在1990 年由Shamir 等人提出的.在ARX 算法的差分分析中, 需要精確地刻畫(huà)模加操作的差分概率: Prl,r∈Fn2[(l?r)⊕((l ⊕?l)?(r ⊕?r))=?o], 記作(?l,?r)??→?o, 其中,l ∈Fn2,r ∈Fn2,(?l,?r)∈Fn2×Fn2是輸入差分, ?o ∈Fn2是輸出差分.模加運(yùn)算差分概率比特向量形式的快速計(jì)算方法最先由Lipmaa 和Moriai 在FSE 2001 上給出[34].2013, Schulte-Geers 通過(guò)CCZ 等價(jià)類(lèi)的方法給出了相同的結(jié)果[35].之后, Wallén 等人給出了矩陣表達(dá)形式的計(jì)算公式[36].Mouha 等人從S-functions 的角度給出了相同的計(jì)算公式[37].Lipmaa 和Moriai 的計(jì)算方法在ARX 算法的差分分析以及自動(dòng)化搜索中被廣泛應(yīng)用[38,39], 因而本節(jié)只介紹該計(jì)算方法.對(duì)于其他表達(dá)形式, 需參考相應(yīng)的文獻(xiàn).最后, 在給出相關(guān)計(jì)算方法前, 首先給出模加運(yùn)算與異或運(yùn)算的關(guān)系:

結(jié)合模加的差分概率定義及上述定義, Lipmaa 等[34]給出了模加的差分概率計(jì)算方法.如定理1 和定理2 所述.

定理1 (?l,?r)??→?O非零的充分必要條件為:

(1) ?l[0]⊕?r[0]⊕?o[0]=0;

(2) 對(duì)于任意i ∈[1,n ?1], 若有?l[i ?1] = ?r[i ?1] = ?o[i ?1], 則?l[i ?1] = ?r[i ?1] =?o[i ?1]=?l[i]⊕?r[i]⊕?o[i].

在實(shí)際使用中, 由于漢明重量的計(jì)算也可以使用位運(yùn)算技巧將時(shí)間復(fù)雜度優(yōu)化到O(logn), 故上述概率計(jì)算方法的復(fù)雜度可以優(yōu)化到O(logn).

3.2 旋轉(zhuǎn)差分分析

旋轉(zhuǎn)差分分析是在ARX 算法分析中對(duì)差分分析的一種推廣, 最早由Khovratovich 等人在FSE 2010上提出[40].在文獻(xiàn)[40] 中, 對(duì)于ARX 算法E(x), Khovratovich 等人考慮了旋轉(zhuǎn)不變概率, 即E(←?x)⊕←?E(x)= 0 成立的概率.類(lèi)似于差分分析, Khovratovich 等人假定ARX 算法中的每個(gè)非線性操作(模加)均相互獨(dú)立, 整個(gè)算法E(x) 的旋轉(zhuǎn)不變概率等于每個(gè)模加旋轉(zhuǎn)不變概率的乘積(旋轉(zhuǎn)參數(shù)均一致).對(duì)于單個(gè)模加x?y, 在循環(huán)移位參數(shù)γ, 0≤γ ≤n ?1 下的旋轉(zhuǎn)不變概率定義為:

在FSE 2017 上, Ashur 等人給出了模加的旋轉(zhuǎn)差分概率計(jì)算公式[42], 并成功應(yīng)用到了輕量級(jí)分組密碼算法SPECK 上.此外, 該公式類(lèi)似于文獻(xiàn)[34], 可以寫(xiě)成比特向量的形式; 模加的旋轉(zhuǎn)差分概率計(jì)算公式的相關(guān)細(xì)節(jié)可以參考文獻(xiàn)[42], 這里不做詳細(xì)介紹.

3.3 線性分析

給定n比特的線性掩碼Λl,Λr,?！蔉n2, 模加操作的線性逼近表達(dá)式為?！?l?r)⊕Λl·l ⊕Λr·r, 其中,l,r ∈Fn2.該線性逼近表達(dá)式的相關(guān)性定義為

記作cor?(Γ,Λl,Λr).

在2003 年, Wallén 給出公式(8)的快速計(jì)算方法[43], 解決了模加操作的線性分析中一大計(jì)算難題.之后, 在對(duì)SNOW 2.0 的分析中, Nyberg 和Wallén 又進(jìn)一步給出更為通用的方法[44], 用于計(jì)算任意個(gè)加數(shù)的模加操作中的線性相關(guān)性.這兩個(gè)研究工作中的線性分析理論都很長(zhǎng)且復(fù)雜.這里不介紹過(guò)多理論細(xì)節(jié), 只針對(duì)一個(gè)模加的情況, 簡(jiǎn)述得到的最終結(jié)論, 如定理3 所述.

定理3 在cor?(Γ,Λl,Λr) 中, 用Λl[i] 表示掩碼Λ∈Fn2的第i個(gè)比特, 對(duì)于Λr,?！蔉n2也有相同的記法.設(shè)向量u=(u[n?1],u[n?2],···,u[0])∈Zn8,其中,對(duì)于0≤i

推論1 公式(9)從左到右的計(jì)算過(guò)程對(duì)應(yīng)于圖18 中的有限狀態(tài)自動(dòng)機(jī).狀態(tài)轉(zhuǎn)移箭頭上的數(shù)字i代表當(dāng)前要右乘的矩陣為Mi.如果自動(dòng)機(jī)停機(jī)時(shí)的狀態(tài)是“0”, 則線性相關(guān)性的計(jì)算結(jié)果為0.否則, 計(jì)算結(jié)果為±2?k, 其中k表示在圖18 中標(biāo)記為實(shí)線狀態(tài)轉(zhuǎn)移的轉(zhuǎn)移次數(shù).而正負(fù)號(hào)由{3,4}出現(xiàn)的次數(shù)決定, 出現(xiàn)偶數(shù)次則為正號(hào), 反之為負(fù)號(hào).

圖18 模加操作的線性性質(zhì)所對(duì)應(yīng)的有限狀態(tài)自動(dòng)機(jī)Figure 18 Finite state automaton in linear cryptanalysis of a modular addition

此外, 關(guān)于模加的線性相關(guān)性計(jì)算, 也存在比特向量形式的計(jì)算方法, 該結(jié)果在2013 年由Schulte-Geers 通過(guò)CCZ 等價(jià)類(lèi)的方法給出[35].具體理論可查閱相關(guān)文獻(xiàn).

3.4 差分-線性分析

差分-線性分析是將差分分析和線性分析結(jié)合起來(lái)的一類(lèi)密碼分析方法[45], 即通過(guò)短輪的差分區(qū)分器與線性區(qū)分器去構(gòu)造長(zhǎng)輪的區(qū)分器.其基本思想如下: 對(duì)于分組密碼算法E=E2?E1,E,E1,E2:Fn2→Fn2,假設(shè)E1存在差分概率為p的短輪差分區(qū)分器: ?→δ(?,δ ∈Fn2),E2存在線性偏差為?的短輪線性

其中, ?l,?r,Λ∈Fn2.在文獻(xiàn)[47] 中, 作者利用劃分的方法, 成功解決了公式(10)的計(jì)算問(wèn)題.這里只簡(jiǎn)單闡述其最終的計(jì)算方法, 如定理5 所述, 而具體的理論細(xì)節(jié)需參考文獻(xiàn)[47].

定理4 在公式(10)中, 用?l[i] 表示輸入差分?l ∈Fn2的第i個(gè)比特.對(duì)于?r,Λ∈Fn2也有相同的記法.設(shè)向量u=(u[n?1],u[n?2],···,u[0])∈Zn8,其中,對(duì)于0≤i

旋轉(zhuǎn)差分分析是差分分析一“自然” 推廣, 并成功應(yīng)用到了ARX 算法的分析中[40–42,48].Liu 等人提出了利用旋轉(zhuǎn)差分特征替換差分-線性攻擊中標(biāo)準(zhǔn)差分特征的方法[49,50]; 并且作者考慮了線性逼近部分輸出掩碼為單比特向量的特殊情形, 給出了復(fù)雜度評(píng)估的方法, 將其應(yīng)用到了Alzette、Siphash 這兩個(gè)ARX 算法上; 并提出了輸出掩碼為任意情況時(shí)如何計(jì)算旋轉(zhuǎn)差分-線性相關(guān)度的公開(kāi)問(wèn)題.即在數(shù)學(xué)形式上, 需要研究如下表達(dá)式的值.

其中, ?l,?r ∈Fn2, Λ∈Fn2為輸出掩碼.

隨后, 在2022 年美密會(huì)上, Niu 等人解決了該公開(kāi)問(wèn)題[47], 他們基于計(jì)算單個(gè)模加差分-線性連接相關(guān)系數(shù)的方法, 將其進(jìn)一步一般化, 給出了計(jì)算單個(gè)模加旋轉(zhuǎn)差分-線性連接相關(guān)系數(shù)的方法.這里只簡(jiǎn)單闡述其最終的計(jì)算方法, 如定理5 所述, 而具體的理論細(xì)節(jié)需參考文獻(xiàn)[47].

定理5 在公式(12)中, 用?l[i] 表示輸入差分?l ∈Fn2的第i個(gè)比特.對(duì)于?r,Λ∈Fn2也有相同的記法.記γ為循環(huán)移位參數(shù).設(shè)向量u= (u[n ?1],u[n ?2],···,u[0])∈Zn8, 其中, 對(duì)于0≤i

隨后, Niu 等人基于上述理論, 給出了針對(duì)ARX 算法的(旋轉(zhuǎn)) 差分-線性分析相關(guān)度評(píng)估的方法[47],并利用該方法對(duì)Alzette、Siphash、SPECK 和ChaCha 進(jìn)行分析, 大幅度改進(jìn)了已有的分析結(jié)果.

近幾年, 針對(duì)ARX 的算法, 基于差分-線性區(qū)分器的最有效的密鑰恢復(fù)技術(shù)之一為概率中立比特(PNB) 技術(shù)[51], 其主要思想如為:

對(duì)于R+r輪的密碼算法, 假定有R輪的差分-線性區(qū)分器: ?→λ.隨機(jī)選取一對(duì)明文對(duì)滿足差分?, 進(jìn)行加密, 假定在第R輪的中間結(jié)果為m,m′; 對(duì)于解密密鑰的第i個(gè)比特, 若將其進(jìn)行比特反轉(zhuǎn), 并對(duì)得到密文對(duì)進(jìn)行解密r輪, 得中間結(jié)果n,n′; 如果λ·(m ⊕m′⊕n ⊕n′) = 0 的概率大于顯著因子γ,那么解密密鑰的第i個(gè)比特為R輪差分-線性區(qū)分器: ?→λ的概率中立比特.對(duì)解密密鑰的每一個(gè)比特逐一判定, 篩選出所有的概率中立比特.在恢復(fù)解密密鑰的時(shí)候, 只需將概率中立比特設(shè)為定值; 對(duì)非概率中立比特位置, 進(jìn)行猜測(cè)并解密r輪, 利用R輪差分-線性區(qū)分器進(jìn)行密鑰恢復(fù).該密鑰恢復(fù)技術(shù)通過(guò)后續(xù)的不斷發(fā)展[52–57], 基于該技術(shù)的差分-線性分析得到了對(duì)ChaCha 算法與Salsa 算法最好的分析結(jié)果.

此外, 借鑒多重線性分析的思想, 利用“特殊” 的多條差分-線性區(qū)分器(基于“Partition” 技術(shù)[58], 即考慮輸出在一特定集合上的線性逼近) 并結(jié)合額外的技術(shù), 給出了目前對(duì)Chaskey 算法最有效的密鑰恢復(fù)攻擊, 詳細(xì)細(xì)節(jié)見(jiàn)文獻(xiàn)[52,59,60].

3.5 可分性分析

可分性分析是由Todo 在2015 年提出的新的密碼分析方法[61].該方法是對(duì)積分分析的擴(kuò)展, 可以找到傳統(tǒng)積分分析方法無(wú)法找到的區(qū)分器, 同時(shí)也推動(dòng)了自動(dòng)化積分分析技術(shù)的發(fā)展.這里參考文獻(xiàn)[61,62], 先介紹可分性性質(zhì)的定義.由于模加中采用的是比特級(jí)別的可分性分析, 這里著重于比特級(jí)別的可分性性質(zhì).對(duì)于任意兩個(gè)n比特值k,k′∈Fn2, 若對(duì)于0≤i

定義2 設(shè)X 為一個(gè)多重集合, 其中的元素均為Fm2中的m比特值.當(dāng)X 滿足如下條件時(shí), 稱(chēng)其具有

為了在模加操作中運(yùn)用比特級(jí)別的可分性分析, 需要將輸入值和輸出值都表示為二進(jìn)制形式.具體地,設(shè)模加操作的兩個(gè)輸入值為兩個(gè)比特向量x ∈Fn2和y ∈Fn2, 輸出結(jié)果為z ∈Fn2, 應(yīng)用前文中的公式(6),并記c=carry0(x,y), 可以得到

(1)z0=x0⊕y0⊕c0,c0=0;

(2) 對(duì)于1≤i ≤n ?1, 有ci=(xi?1∧yi?1)⊕((xi?1⊕yi?1)∧ci?1) 和zi=xi ⊕yi ⊕ci.

最后, 運(yùn)用上述可分性性質(zhì)的三條規(guī)則, 可以得到模加的可分性性質(zhì)的傳播規(guī)則, 相關(guān)細(xì)節(jié)見(jiàn)文獻(xiàn)[62].

除了上述所介紹的可分性分析方法外, Todo 等人還提出可以進(jìn)一步對(duì)公式(13)中的未知情況進(jìn)行劃分, 得到更為準(zhǔn)確的可分性性質(zhì), 該性質(zhì)稱(chēng)為“使用三子集的可分性性質(zhì)”[63].文獻(xiàn)[64] 中對(duì)模加操作的分析就采用了這個(gè)性質(zhì), 其規(guī)則與本節(jié)所介紹的分析規(guī)則是相似的, 但需要的規(guī)則會(huì)更多.

3.6 飛來(lái)去器分析

飛來(lái)去器分析的基本思想與差分-線性分析相似, 都是通過(guò)短輪區(qū)分器去構(gòu)造長(zhǎng)輪區(qū)分器, 唯一不同的是, 飛來(lái)去器分析的區(qū)分器是由兩條短輪的差分區(qū)分器構(gòu)造.相對(duì)其他的分析方法, 模加的飛來(lái)去器分析發(fā)展較為緩慢, 其主要原因是模加有關(guān)飛來(lái)去器的密碼學(xué)性質(zhì)尚未完全研究清楚.在飛來(lái)去器分析中, 密碼算法E被拆分為三部分:E1?Em ?E0.其中, 對(duì)于E0和E1, 需要分別找到一條差分路徑.對(duì)于Em部分, 需要分析兩條差分路徑(跡) 的連接情況, 本節(jié)只介紹Em為一個(gè)模加的情況.

此時(shí), 模加的飛來(lái)去器分析就要求尋找圖19 中飛來(lái)去器性質(zhì).該性質(zhì)由如下概率表達(dá)式所描述.

圖19 模加操作的飛來(lái)去器分析Figure 19 Boomerang cryptanalysis of a modular addition

該表的定義最早由Cid 等人給出[65].之后的研究工作[66–68]對(duì)該定義進(jìn)一步完善, 并給出其快速計(jì)算方法, 其計(jì)算方式均為矩陣形式.但需要指出, 文獻(xiàn)[68] 給出了一種通用的矩陣尺寸約簡(jiǎn)方法, 可以將矩陣大小約簡(jiǎn)至最優(yōu).因此, 這里以參考文獻(xiàn)[68] 的結(jié)論進(jìn)行簡(jiǎn)述.

設(shè)向量u= (u[n ?1],u[n ?2],···,u[0])∈Zn16, 其中u[i] 的值為8?l[i]+4?r[i]+2?l[i]+?r[i].那么, BCT 表中每一項(xiàng)的計(jì)算公式為

這個(gè)公式與線性相關(guān)性的計(jì)算公式在形式上是相似的, 但公式(9)中的矩陣存在很多相同的情況, 而這里的16 個(gè)矩陣都是完全不同的.這里不再一一列出, 它們的具體值參考文獻(xiàn)[68] 給出的生成方法.同時(shí), 在線性分析中, 8 個(gè)矩陣具有的特殊性質(zhì)使得我們可以構(gòu)建出圖18, 從而簡(jiǎn)化計(jì)算以及進(jìn)行自動(dòng)化搜索建模.但在飛來(lái)去器分析中, 目前沒(méi)有發(fā)現(xiàn)這16 個(gè)矩陣有類(lèi)似的性質(zhì).

3.7 連續(xù)多個(gè)模加操作的分析

本節(jié)主要介紹了單個(gè)模加操作的分析技術(shù), 但部分密碼算法的分析會(huì)涉及到連續(xù)多個(gè)模加操作, 通常可簡(jiǎn)化為圖20 的情形.

圖20 連續(xù)的模加操作Figure 20 Consecutive modular additions

這種情況下, 通常有兩種解決方法: 采用獨(dú)立性假設(shè)對(duì)每一個(gè)模加操作進(jìn)行單獨(dú)分析, 再合并結(jié)果;將單個(gè)模加操作的計(jì)算公式推廣到多個(gè)的情況.對(duì)于第一種方法, 由于獨(dú)立性假設(shè)不一定總是成立, 最終結(jié)果與真實(shí)值存在一定差距.而在第二種方法中, 同時(shí)處理多個(gè)模加操作會(huì)增大分析的難度, 也會(huì)導(dǎo)致自動(dòng)化模型過(guò)于復(fù)雜.目前, 這方面的研究工作較少, 主要集中于差分和線性分析.在差分分析中, 2010年Mouha 等人提出了S-functions 方法[37], 可以很自然地應(yīng)用到任意多個(gè)模加操作的情況.同時(shí), 針對(duì)SPECK, Dinur 還提出兩輪密鑰恢復(fù)技術(shù)[69].該技術(shù)應(yīng)用到SPECK 的差分攻擊中.關(guān)于旋轉(zhuǎn)差分分析, Khovratovich 在文獻(xiàn)[41] 討論了多個(gè)模加操作的旋轉(zhuǎn)不變性分析問(wèn)題.在線性分析方面, Nyberg 和Wallén 將線性相關(guān)性計(jì)算推廣到任意多個(gè)模加操作的情形[43,44].在差分-線性分析中, Beierle 等人在提出新的劃分方法時(shí)也進(jìn)一步考慮了連續(xù)兩個(gè)模加操作的分析[52], 但相應(yīng)的結(jié)果是通過(guò)采樣實(shí)驗(yàn)得到的.在其他復(fù)雜的分析方法中, 如飛來(lái)去器分析, 目前還缺少相關(guān)工作, 其分析過(guò)程中主要采取獨(dú)立性假設(shè)來(lái)簡(jiǎn)化研究.

4 自動(dòng)化分析

4.1 差分分析的自動(dòng)化分析

針對(duì)ARX 密碼的差分自動(dòng)化分析方法最早是由Leurent 基于S-functions 實(shí)現(xiàn)的, 相應(yīng)的軟件工具為ARXtools[70].但該工具無(wú)法搜索最優(yōu)差分路徑, 僅對(duì)差分路徑的驗(yàn)證效果較好.相比于Leurent 的建模方法, 后續(xù)發(fā)展起來(lái)的SAT 和MILP 建模方法更方便, 而且可以實(shí)現(xiàn)搜索與驗(yàn)證.因此, 這里僅介紹基于SAT 和MILP 的方法, 見(jiàn)文獻(xiàn)[39,71].這兩種方法的理論基礎(chǔ)為定理1 和定理2.

在SAT 模型中, 由于第3.1 節(jié)中兩個(gè)定理的表述以邏輯表達(dá)式為主, 因此可以很方便地將它們整理成如下的邏輯表達(dá)式, 即SAT 模型.

唯一的不同為差分概率值的表達(dá).定理2 中的概率值為一個(gè)含冪指數(shù)的表達(dá)式, 該形式不利于構(gòu)建SAT模型.因此, 取對(duì)數(shù)作為模型中的變量, 即

在SPECK 中, 根據(jù)獨(dú)立性假設(shè)和堆積引理, 最終的目標(biāo)函數(shù)就是所有模加運(yùn)算的W值的總和, 通過(guò)設(shè)置約束W ≤k; 并將k由小到大嘗試, 直至SAT 模型輸出可行解, 即為搜索到的最優(yōu)差分路徑.對(duì)其他結(jié)構(gòu)復(fù)雜的ARX 密碼算法, 目標(biāo)函數(shù)通常也是關(guān)于W的線性函數(shù).

4.2 線性分析的自動(dòng)化分析

線性分析作為對(duì)稱(chēng)密碼分析的另一種方法, 其自動(dòng)化分析同樣受到廣泛的關(guān)注.與差分自動(dòng)化分析不同, 推論1 中的有限自動(dòng)機(jī)更適合MILP 建模.而對(duì)于SAT 建模, 需要尋找新的線性相關(guān)性計(jì)算方法.文獻(xiàn)[73]從CCZ 等價(jià)角度得到的邏輯表達(dá)式,給出了適合SAT 建模的計(jì)算方法.本小節(jié)將簡(jiǎn)單介紹MILP建模和SAT 建模.

關(guān)于基于SAT 建模的自動(dòng)化分析方法, 文獻(xiàn)[73] 的方法涉及到CCZ 等價(jià)的知識(shí), 這里不對(duì)細(xì)節(jié)進(jìn)行描述, 只簡(jiǎn)述最終的SAT 模型.在線性分析中, 掩碼Λl、Λr和Γ 需滿足如下約束, 其中0≤i ≤n ?1且0≤j ≤n ?3.

在上述約束中, 由于異或運(yùn)算可以轉(zhuǎn)化為邏輯表達(dá)式輸入到SAT 求解器中.但對(duì)于不等式的轉(zhuǎn)化, 該文獻(xiàn)采用了一種編碼方法來(lái)解決這個(gè)問(wèn)題, 這里只介紹結(jié)論.不等式∑i xi ≤k可以轉(zhuǎn)化為如下邏輯表達(dá)式組, 其中1

至此, 結(jié)合上述邏輯表達(dá)式, 即可得到對(duì)應(yīng)的SAT 模型.

4.3 差分-線性的自動(dòng)化分析

差分-線性是對(duì)ARX 算法的比較有效的一類(lèi)分析方法.然而,相比于差分分析與線性分析,ARX 算法的差分-線性自動(dòng)化搜索發(fā)展緩慢, 僅在近幾年有所發(fā)展.在CT-RSA 2023 上, Bellini 等人利用MQCP(混合二次約束規(guī)劃) 對(duì)差分-線性的中間層Em進(jìn)行建模[74], 首次實(shí)現(xiàn)了ARX 算法的差分-線性自動(dòng)化分析.其建模過(guò)程如下.首先, 若已知各個(gè)比特上的差分分布, 且在各個(gè)比特上差分分布相互獨(dú)立的情況下, 經(jīng)過(guò)模加x?n y及異或x ⊕y后各個(gè)比特上的差分分布可以由以下定理計(jì)算.

定理6[49,75]令x,y,x′及y′為n比特串, 滿足Pr[xi ?=x′i]=pi及Pr[yi ?=y′i]=qi.那么,x?n y上各個(gè)比特的差分分布為: Pr[(x?n y)i ?=(x′?n y′)i]=pi+qi ?2piqi ?2pisi+4piqisi.其中,s0=0 且

在MQCP 模型中, 由于目標(biāo)函數(shù)必須是線性函數(shù); 但與差分分析以及線性分析相比, 差分-線性區(qū)分器的相關(guān)度并不是2 的整數(shù)次冪.因此, 為了用線性函數(shù)表示函數(shù)?log(|r|), Bellini 等人基于分段線性插值來(lái)逼近非線性函數(shù)的思想[74], 將區(qū)間分成若干段, 在每段區(qū)間上用線性插值, 將?log(|r|) 表示為:

對(duì)于差分部分與線性部分的建模, 采用前面提及的MILP 建模, 從而完成了對(duì)差分-線性搜索的MQCP 建模; Bellini 等人將該自動(dòng)化方法應(yīng)用到了SPECK 算法上[74], 找到了一系列可實(shí)踐驗(yàn)證的差分-線性區(qū)分器, 且這些區(qū)分器都是目前最優(yōu)的.

4.4 可分性的自動(dòng)化分析

作為積分分析的擴(kuò)展, 可分性的自動(dòng)化分析在近幾年受到廣泛關(guān)注.因此, 成功實(shí)現(xiàn)對(duì)積分分析的自動(dòng)化分析成為一個(gè)非常重要的問(wèn)題.如第3.5 小節(jié)所述, 模加運(yùn)算的可分性性質(zhì)可由三條基本規(guī)則構(gòu)成, 只需為這三條基本規(guī)則構(gòu)建相應(yīng)的MILP 模型和SAT 模型, 就可以組合出可分性的自動(dòng)化分析模型.對(duì)于MILP 建模, 文獻(xiàn)[76] 給出了三條基本規(guī)則的MILP 建模, 分別如下.

4.5 飛來(lái)去器的自動(dòng)化分析

飛來(lái)去器分析雖然作為差分分析的擴(kuò)展, 但是其在ARX 密碼上的發(fā)展很緩慢.Leurent 在2013 年給出ARXtools 也同樣適用于飛來(lái)去器分析[70], 但其只能驗(yàn)證區(qū)分器, 無(wú)法尋找新的區(qū)分器.之后, 直到2020 年, Kim 等人才給出中間層的概率計(jì)算公式[66].但該工作并未涉及ARX 密碼的飛來(lái)去器自動(dòng)化分析, 其采用的策略依然為先尋找差分路徑再?lài)L試進(jìn)行兩兩拼接.在2023 年, 我國(guó)學(xué)者Wang 等人給出了第一個(gè)自動(dòng)化分析方法[68].由于篇幅限制, 本小節(jié)僅簡(jiǎn)述其思路.

該方案采用的為SAT 建模.最大的問(wèn)題為對(duì)公式(15)的建模, 但由于最終的結(jié)果不是2 的整數(shù)次冪,無(wú)法與差分分析一樣取對(duì)數(shù)作為目標(biāo)函數(shù).文獻(xiàn)[68] 通過(guò)分析矩陣的性質(zhì), 給出一個(gè)新的建模方法來(lái)避開(kāi)該問(wèn)題.在公式(15)中, 對(duì)于0≤i ≤n ?2, 記

該研究工作將其應(yīng)用到了SPECK 上, 成功找到目前SPECK 最好的飛來(lái)去器區(qū)分器.但對(duì)于ARX 密碼的飛來(lái)去器自動(dòng)化分析, 目前還缺乏足夠的研究, 有待后續(xù)研究者去研究新的自動(dòng)化方案.

5 討論與公開(kāi)問(wèn)題

在ARX 算法分析中, 目前仍然存在很多未解決的重要問(wèn)題.首先, 在針對(duì)Chaskey、ChaCha、Salsa等算法的差分-線性攻擊中, 使用了大量實(shí)驗(yàn)型差分-線性區(qū)分器[52–57,59,60].對(duì)這些區(qū)分器的相關(guān)度計(jì)算缺少理論方法.盡管目前有一些對(duì)ChaCha 差分-線性區(qū)分器相關(guān)度進(jìn)行理論解釋的嘗試[78], 但相關(guān)方法不具一般性, 只對(duì)個(gè)別特殊情況有效.特別是對(duì)于Chaskey 算法的差分-線性區(qū)分器[52,59,60], 目前沒(méi)有任何理論解釋的工作.

第二, 對(duì)于基于ARX 型置換構(gòu)造的密碼方案, 雖然可以較為容易地搜索到這些密碼方案底層置換的區(qū)分器(例如, 4 輪Alzette 存在相關(guān)度為1 的差分-線性區(qū)分器[47]), 但如何利用這些區(qū)分器構(gòu)造上層方案更有意義的攻擊(如原像攻擊、碰撞攻擊、密鑰恢復(fù)攻擊等) 也是非常值得關(guān)注的問(wèn)題.

第三, 對(duì)于ARX 算法的可分性分析, 目前的方法還是首先將模加運(yùn)算分解成比特級(jí)與運(yùn)算和異或運(yùn)算, 然后再根據(jù)可分性特征在這些基本運(yùn)算中的傳播規(guī)律去刻畫(huà)可分性特征在整體模加運(yùn)算中的傳播特征.從單項(xiàng)式預(yù)測(cè)方法的角度看, 這種方法有可能忽略一些單項(xiàng)式的相消現(xiàn)象, 從而不能精確描述可分性特征在模加運(yùn)算中的傳播規(guī)則.另一方面, 盡管模加運(yùn)算會(huì)導(dǎo)致較高的代數(shù)次數(shù), 從而似乎可以更好地抵抗可分性分析.但有趣的是, 在基于長(zhǎng)軌跡策略設(shè)計(jì)的SPARX 系列算法中, 基于可分性的密鑰恢復(fù)攻擊是目前最好的[9], 因此, 針對(duì)ARX 算法的可分性分析工作是值得進(jìn)一步挖掘的.

最后, 關(guān)于ARX 算法的飛來(lái)去器分析, 與差分-線性分析相似, 都是通過(guò)覆蓋較短輪數(shù)的顯著的區(qū)分器去構(gòu)造覆蓋較長(zhǎng)輪數(shù)的區(qū)分器.但相比于基于小型S 盒構(gòu)造的對(duì)稱(chēng)密碼算法[79–83], 針對(duì)于ARX 型密碼的飛來(lái)去器分析工作進(jìn)展緩慢.在基于S 盒構(gòu)造的對(duì)稱(chēng)密碼中, 由于S 盒的規(guī)模一般較小, 對(duì)其飛來(lái)去器的密碼學(xué)性質(zhì), 可以通過(guò)遍歷所有的輸入來(lái)得到.此外, 在由S 盒構(gòu)成的非線性層中, 每個(gè)S 盒都是獨(dú)立的, 可以通過(guò)局部飛來(lái)去器密碼性質(zhì)推導(dǎo)出整體輪函數(shù)的飛來(lái)去器密碼學(xué)性質(zhì).然而, 對(duì)于ARX 算法,由于模加運(yùn)算的規(guī)模比較大, 通過(guò)遍歷所有的輸入來(lái)得到飛來(lái)去器密碼學(xué)性質(zhì)是不可行的.另外, 由于進(jìn)位比特的影響, 使得模加當(dāng)中的任意兩個(gè)比特都有聯(lián)系, 難以通過(guò)局部的規(guī)律得到整個(gè)輪函數(shù)的密碼學(xué)性質(zhì).而從目前僅有的一些對(duì)ARX 算法的飛來(lái)去器分析工作來(lái)看[84,85], 針對(duì)ARX 算法的飛來(lái)去器分析工作值得進(jìn)一步發(fā)展.