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

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

2.密碼科學(xué)技術(shù)全國重點實驗室, 北京 100878

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

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

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

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

1 引言

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

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

2 代表性ARX 型對稱密碼

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]是第一個公開提出的ARX 型分組密碼,對FEAL 的分析, 促進(jìn)了差分分析和線性分析研究的發(fā)展.

FEAL分組密碼.FEAL 是由Shimizu 和Miyaguchi 在1987 年提出的[2],與DES 相比,FEAL 更適用于軟件實現(xiàn).FEAL 的分組長度和密鑰長度均為64 比特, 總輪數(shù)為8 輪, 其輪函數(shù)如圖1 所示.FEAL 的加密過程見算法1, 記第i個輪函數(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生成的, 具體生成方式見文獻(xiàn)[2].

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

SPECK分組密碼.SPECK 是由美國國家安全局Beaulieu 等人在2013 年提出的, 正式發(fā)表于DAC 2015[13].根據(jù)不同的分組長度和密鑰長度, 該算法有十個版本, 每個版本的輪函數(shù)結(jié)構(gòu)相同.分組長度為2n比特的SPECK 算法加密過程的第i輪如圖2(左) 所示.密鑰長度為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 年提出的, 目前是韓國標(biāo)準(zhǔn)分組密碼之一.該密碼算法有三個版本: LEA-128、LEA-192 和LEA-256, 分組長度均為128 比特, 密鑰長度分別為128、192 和256).比特, 對應(yīng)輪數(shù)分別為24、28 和32, 每個版本的加密過程使用相同的輪函數(shù)結(jié)構(gòu), 如圖3 所示.LEA 采用了純線性的密鑰編排算法, 具體情況請參考文獻(xiàn)[7].

算法1 FEAL 密碼算法的加密過程(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è)計提出的, 是2019 年全國密碼算法設(shè)計競賽中獲得一等獎的算法之一[11].該密碼算法有三個版本: Ballet-128/128、Ballet-128/256 和Ballet-256/256,(Ballet-u/v的分組長度為u比特, 密鑰長度為v比特) 輪數(shù)分別為46、48 和74.每個版本均使用相同的輪函數(shù)結(jié)構(gòu), 如圖4 所示, 最后一輪省略最后一個線性置換操作.記分組長度為4n比特的Ballet 的第i輪輪函數(shù)的輸入為(xi0,xi1,xi2,xi3)∈F4n2, (skLi,skRi)∈F2n2為第i輪的輪密鑰.Ballet 使用了線性密鑰編排算法, 細(xì)節(jié)見文獻(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é)置換通常在其他對稱密碼中作為組件使用, 尤其是在基于海綿結(jié)構(gòu)的雜湊函數(shù)和認(rèn)證加密中經(jīng)常使用.本節(jié)只介紹一個典型的ARX 型密碼學(xué)置換SPARKLE[14].SPARKLE 是由Beierle 等人在2019 年提出的, 基于該置換構(gòu)造的輕量級認(rèn)證加密方案和雜湊函數(shù)參與了NIST 輕量級密碼競賽并進(jìn)入第三輪.

2.3 ARX 型序列密碼

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

ChaCha 序列密碼.ChaCha 是由 Bernstein 在 2008 年提出的, 是 eSTREAM 獲勝算法Salsa20 的改進(jìn)版本[21].ChaCha 的密鑰流輸出過程見算法2, 其中使用了一個所謂的1/4 輪函數(shù)QuarterRound(a,b,c,d), 如圖6 所示.ChaCha 的初始輸入可以看成一個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的長度均為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è)計的, 可以視為SNOW-3G 的改進(jìn)版本.SNOW-V 的內(nèi)部狀態(tài)(T0,T1,T2,T3,R1,R2,R3)∈F128×72按算法3 由線性反饋移位寄存器(LFSR) 和有限狀態(tài)機(FSM) 進(jìn)行更新.其初始化階段及密鑰流生成階段分別如圖7 和圖8 所示, 其中兩個AES 加密對應(yīng)的輪函數(shù)的輪密鑰設(shè)為零,σ為字節(jié)置換.在初始化階段, FSM 的更新依賴于整個狀態(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] 上兩個不可約多項式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),在多項式gA(x)中αx=(x14,x13,···,x0,0)⊕x15·(100110010000111),(100110010000111) 為gA(x) 小于16 次冪的多項式系數(shù); 多項式gB(x) 中同理.依次對LFSR-A 與LFSR-B 對應(yīng)的等式進(jìn)行8 輪計算,每一輪計算后將結(jié)果放在最高位a15,b15,原其他各位a15,···,1,b15,···,1向低位移動一位至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)生密鑰流工作階段, 計算n 個密鑰分組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]和我國商用密碼標(biāo)準(zhǔn)算法SM3[24]等.

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

圖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 表示分組的最后一個字節(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)

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

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

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

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

SM3 雜湊函數(shù).SM3 雜湊函數(shù)是2010 年公布的中國商用密碼雜湊算法標(biāo)準(zhǔn), 與SHA-256 等算法一樣為Merkle–Damg?rd 結(jié)構(gòu), SM3 的安全性也與SHA-256 相當(dāng).首先, SM3 密碼算法將消息長度填充至512的倍數(shù), 在消息填充中, 需填充一個1, 再填充k個0, 其中k為滿足(len+1+kmod 512=448) 的最小正整數(shù), len 為消息長度比特.隨后, 添加64 比特的數(shù)據(jù)長度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′作為下一個消息塊的鏈接值; 在吸收最后一個消息塊后, 將更新的鏈接值作為雜湊函數(shù)的256 比特輸出.SM3 密碼算法的壓縮函數(shù)為一個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

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

其中, 消息擴展中的置換函數(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è)計, 是一族帶密鑰的哈希函數(shù), 與HMAC 的構(gòu)造方法類似, 設(shè)計時參考并結(jié)合了BLAKE 和SKEIN 等雜湊函數(shù)的特點, 其設(shè)計目的是為了應(yīng)對2011 年底發(fā)生的一系列Hash-flooding 拒絕服務(wù)攻擊.基于ARX 型密碼學(xué)置換構(gòu)造的MAC 如Chaskey[29]等.Chaskey 由Mouha 等于2014 年提出, 其置換的初始輪數(shù)為8 輪, 后改為12 輪, 12 輪版本的Chaskey 是ISO/IEC 輕量級消息認(rèn)證碼標(biāo)準(zhǔn)[30]之一.

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

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

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

K ?1 為將K左移1 位.

在計算第i個消息分組mi ∈F1282, 1≤i ≤? ?1, 置換π的輸入為第i個π的輸出hi與mi的異或(h1=K), 置換π對每個輸入進(jìn)行12 輪計算, 輸出為hi+1.若最后一個消息分組m?的長度正好為128比特, 則令h? ⊕m? ⊕K1作為最后一個置換π的輸入, 將輸出結(jié)果與K1異或得到h?+1; 若最后一個消息分組的長度不足128 比特, 需先補1 再補若干個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 機密性和完整性方案[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è)計的密碼算法[14], 其為一輕量級認(rèn)證加密算法參與了NIST 輕量級密碼競賽并進(jìn)入了第三輪, 對于給定密鑰K、Nonce 值N、任意長度的關(guān)聯(lián)數(shù)據(jù)A以及消息M(關(guān)聯(lián)數(shù)據(jù)A與消息M的長度不要求相同), 輸出一個與消息M等長的密文C以及一個固定長度的認(rèn)證標(biāo)簽T.Schwaemm AEAD 的4 個版本對應(yīng)的參數(shù)如表1 所示, 其中的SPARKLEnns為分組長度為n、步數(shù)為ns的SPARKLE算法, 以其主要版本Schwaemm256-128 進(jìn)行介紹, 如圖17 所示.

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

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

3 對ARX 型密碼算法的分析

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

3.1 差分分析

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

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

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

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

(2) 對于任意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].

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

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

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

在FSE 2017 上, Ashur 等人給出了模加的旋轉(zhuǎn)差分概率計算公式[42], 并成功應(yīng)用到了輕量級分組密碼算法SPECK 上.此外, 該公式類似于文獻(xiàn)[34], 可以寫成比特向量的形式; 模加的旋轉(zhuǎn)差分概率計算公式的相關(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)的快速計算方法[43], 解決了模加操作的線性分析中一大計算難題.之后, 在對SNOW 2.0 的分析中, Nyberg 和Wallén 又進(jìn)一步給出更為通用的方法[44], 用于計算任意個加數(shù)的模加操作中的線性相關(guān)性.這兩個研究工作中的線性分析理論都很長且復(fù)雜.這里不介紹過多理論細(xì)節(jié), 只針對一個模加的情況, 簡述得到的最終結(jié)論, 如定理3 所述.

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

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

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

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

3.4 差分-線性分析

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

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

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

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

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

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

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

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

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

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

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

3.5 可分性分析

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

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

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

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

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

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

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

3.6 飛來去器分析

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

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

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

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

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

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

本節(jié)主要介紹了單個模加操作的分析技術(shù), 但部分密碼算法的分析會涉及到連續(xù)多個模加操作, 通?？珊喕癁閳D20 的情形.

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

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

4 自動化分析

4.1 差分分析的自動化分析

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

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

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

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

4.2 線性分析的自動化分析

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

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

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

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

4.3 差分-線性的自動化分析

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

定理6[49,75]令x,y,x′及y′為n比特串, 滿足Pr[xi ?=x′i]=pi及Pr[yi ?=y′i]=qi.那么,x?n y上各個比特的差分分布為: 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 等人基于分段線性插值來逼近非線性函數(shù)的思想[74], 將區(qū)間分成若干段, 在每段區(qū)間上用線性插值, 將?log(|r|) 表示為:

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

4.4 可分性的自動化分析

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

4.5 飛來去器的自動化分析

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

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

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

5 討論與公開問題

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

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

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

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