改進(jìn)的減輪Kiasu-BC 算法的中間相遇攻擊

李曼曼，陳少真

（1.信息工程大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，河南 鄭州 450001；2.密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100878；3.河南省網(wǎng)絡(luò)密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001）

0 引言

隨著高新技術(shù)的飛速發(fā)展，以及網(wǎng)絡(luò)支付系統(tǒng)、云計(jì)算、物聯(lián)網(wǎng)技術(shù)的日益成熟，人們對(duì)隱私保護(hù)及信息安全等相關(guān)問(wèn)題越來(lái)越重視。分組密碼由于其軟硬件實(shí)現(xiàn)效率高、易于標(biāo)準(zhǔn)化等優(yōu)點(diǎn)被廣泛用于保護(hù)信息的安全。可調(diào)分組密碼是一種帶有額外輸入調(diào)柄值的分組密碼，調(diào)柄值可以提高算法的靈活性，在構(gòu)造Hash 函數(shù)、消息認(rèn)證碼和偽隨機(jī)數(shù)發(fā)生器等領(lǐng)域應(yīng)用廣泛。近些年，可調(diào)分組密碼迅速發(fā)展，其設(shè)計(jì)方法與安全性分析得到人們諸多關(guān)注和研究。在CRYPTO 2002 上，Liskov 等[1]提出了可調(diào)分組密碼的概念。與傳統(tǒng)的分組密碼相比，可調(diào)分組密碼有一個(gè)額外的輸入調(diào)柄，這是一個(gè)完全公開(kāi)的參數(shù)，增加了分組密碼的可變性。在實(shí)際使用過(guò)程中，更換調(diào)柄比更換密鑰操作更便捷有效且成本低廉。因此，可調(diào)分組密碼被廣泛應(yīng)用于加密協(xié)議、認(rèn)證加密等場(chǎng)合，以保護(hù)數(shù)據(jù)的機(jī)密性和認(rèn)證性。

Jean 等[2]在ASIACRYPT 2014 上提出了一個(gè)可用來(lái)設(shè)計(jì)可調(diào)分組密碼的簡(jiǎn)單框架——可調(diào)密鑰（Tweakey）模型，并給出了3 個(gè)基于AES 算法輪函數(shù)的可調(diào)分組密碼的具體實(shí)例，分別是Kiasu-BC[3]、Joltik-BC[4]和Deoxys-BC[5]。近幾年，針對(duì)Kiasu-BC算法的安全性分析，研究者使用多種密碼分析方法給出了較好的分析結(jié)果。最初，Kiasu-BC 算法的設(shè)計(jì)者分析了Kiasu-BC 算法的中間相遇攻擊和差分攻擊，并且聲稱(chēng)Kiasu-BC 算法與AES-128 算法持有相同的輪函數(shù)和密鑰擴(kuò)展算法，故其抵抗密碼分析方法的能力與AES-128 算法相同。

之后，研究者對(duì)Kiasu-BC 算法安全性分析的主要結(jié)果如下。Dobraunig 等[6]利用調(diào)柄自由度構(gòu)造了4 輪區(qū)分器，實(shí)現(xiàn)了7 輪Kiasu-BC 算法的積分攻擊；Abdelkhalek 等[7]利用調(diào)柄生成的差分可抵消攻擊路徑的差分首次構(gòu)造了 8 輪Kiasu-BC 算法的不可能差分攻擊；Tolba 等[8]利用調(diào)柄差分增加區(qū)分器輪數(shù)實(shí)現(xiàn)了8 輪Kiasu-BC算法的中間相遇攻擊；Dobraunig 等[9]對(duì) 8 輪Kiasu-BC 算法的不可能差分攻擊進(jìn)行了改進(jìn)，并提出了8 輪Kiasu-BC 算法的飛去來(lái)器攻擊；Jiang等[10]借鑒調(diào)柄生成的非零差分抵消攻擊路徑差分的思想，提出了8 輪Kiasu-BC 算法的多重不可能差分攻擊。

本文主要研究Kiasu-BC 算法的中間相遇攻擊。Kiasu-BC 算法的中間相遇攻擊最初由Jean 等[3]提出。Tolba 等[8]利用Kiasu-BC 算法的調(diào)柄差分性質(zhì)，通過(guò)控制調(diào)柄差分使區(qū)分器在其第一輪處差分為0，據(jù)此將區(qū)分器的輪數(shù)擴(kuò)展到5 輪，在構(gòu)造區(qū)分器的前面增加一輪、后面增加2 輪，實(shí)現(xiàn)了8 輪中間相遇攻擊。Liu 等[11]結(jié)合差分枚舉技術(shù)選取不同于文獻(xiàn)[9]的活動(dòng)字節(jié)對(duì)中間相遇區(qū)分器進(jìn)行了改進(jìn)，更新了8 輪中間相遇攻擊的結(jié)果，降低了Kiasu-BC 算法中間相遇攻擊的時(shí)間復(fù)雜度和數(shù)據(jù)復(fù)雜度。關(guān)于Kiasu-BC 算法的中間相遇攻擊，本文在前人研究的基礎(chǔ)上，結(jié)合Kiasu-BC 算法的性質(zhì)，尋找其密鑰擴(kuò)展算法的特點(diǎn)，發(fā)現(xiàn)Kiasu-BC算法內(nèi)部密鑰間的關(guān)聯(lián)性，利用Kiasu-BC 算法密鑰擴(kuò)展的缺陷和輪變換的特點(diǎn)，構(gòu)造一個(gè)新的5 輪中間相遇區(qū)分器，然后利用該區(qū)分器，向前擴(kuò)展一輪、向后擴(kuò)展2 輪，改進(jìn)了8 輪Kiasu-BC 算法中間相遇攻擊的結(jié)果。改進(jìn)后的8 輪Kiasu-BC 算法中間相遇攻擊的存儲(chǔ)復(fù)雜度為263，時(shí)間復(fù)雜度為2114，數(shù)據(jù)復(fù)雜度為2108。

1 預(yù)備知識(shí)

1.1 符號(hào)說(shuō)明

本文用到的符號(hào)說(shuō)明如表1 所示。

表1 符號(hào)說(shuō)明

1.2 Kiasu-BC 算法介紹

Kiasu-BC 算法是在AES-128 算法的基礎(chǔ)上設(shè)計(jì)的可調(diào)分組密碼算法，采用代換?置換網(wǎng)絡(luò)（SPN,substitution-permutation network）結(jié)構(gòu)，明文分組長(zhǎng)度和密鑰長(zhǎng)度均為128 bit，加密輪數(shù)為10 輪。Kiasu-BC 算法的結(jié)構(gòu)如圖1 所示。Kiasu-BC 算法中調(diào)柄T的結(jié)構(gòu)如圖2 所示。

圖1 Kiasu-BC 算法的結(jié)構(gòu)

圖2 調(diào)柄T的結(jié)構(gòu)

Kiasu-BC 算法的128 bit 明密文及中間狀態(tài)可分成16 塊，表示為如下的4 × 4字節(jié)矩陣，每個(gè)字節(jié)可以看作 GF(28)中的一個(gè)元素。

Kiasu-BC 算法的輪函數(shù)與AES-128 算法相似，分別由字節(jié)替換（SB,SubByte）、行位移（SR,ShiftRow）、列混合（MC,MixColumn）和輪調(diào)柄密鑰加（ART,AddRoundTweakey）4 種變換構(gòu)成，其中前3 種變換與AES-128 算法相同，ART 變換就是將192 bit 輪調(diào)柄密鑰STKi與128 bit 中間狀態(tài)進(jìn)行按位異或運(yùn)算。其中，192 bit 輪調(diào)柄密鑰由128 bit輪密鑰RKi和64 bit 調(diào)柄T級(jí)聯(lián)而成。Kiasu-BC 算法的輪調(diào)柄密鑰生成如圖3 所示。

圖3 Kiasu-BC 算法的輪調(diào)柄密鑰生成

另外，在Kiasu-BC 算法的128 bit 明文進(jìn)入輪函數(shù)之前，需要先進(jìn)行一個(gè)白化的輪調(diào)柄密鑰加變換，并且最后一輪的列混合變換被省略。

Kiasu-BC算法128 bit輪密鑰RKi是由AES-128的密鑰擴(kuò)展算法得到的，對(duì)初始密鑰進(jìn)行擴(kuò)展并將其分配到加密過(guò)程的每一輪。

2 中間相遇攻擊

中間相遇攻擊是一種有效的選擇明文攻擊，由Diffie和Hellman[12]于1977 年分析DES 算法時(shí)提出，該攻擊方法利用密碼分割和時(shí)空折中2 種分析思想，在分組密碼和Hash 函數(shù)的安全性分析中均有廣泛應(yīng)用。隨著20 世紀(jì)90 年代差分攻擊的出現(xiàn)，許多密碼分析方法逐漸融合形成新的、有效的分析思想。例如，不可能差分攻擊就是利用截?cái)嗖罘衷谥虚g相遇產(chǎn)生矛盾的思想提出的，其本質(zhì)也是中間相遇攻擊。目前，研究者利用中間相遇攻擊對(duì)許多分組密碼算法進(jìn)行了有效分析。在過(guò)去幾年里，這種攻擊方法被改進(jìn)成一種名為原像攻擊的方法，然后應(yīng)用于Hash 函數(shù)的攻擊中，并據(jù)此提出許多新的技術(shù)。

2008 年，Demirci和Selcuk[13]在分析AES 算法安全性的過(guò)程中，將碰撞攻擊的思想[14]與中間相遇攻擊相結(jié)合，提出了一種新型的中間相遇攻擊模型，稱(chēng)為Demirci-Selcuk 中間相遇攻擊。其基本思想是將一個(gè)分組密碼算法E分割成連續(xù)的3 個(gè)部分，即E=E2?E0?E1，如圖4 所示。

圖4 Demirci-Selcuk 中間相遇攻擊的基本思想

攻擊過(guò)程包含離線(xiàn)部分和在線(xiàn)部分。在離線(xiàn)部分E0處，構(gòu)造一個(gè)中間相遇區(qū)分器，用一個(gè)預(yù)計(jì)算表存儲(chǔ)區(qū)分器中特定的輸入和輸出；在密鑰恢復(fù)階段即在線(xiàn)部分，猜測(cè)E1、E2的某些相關(guān)子密鑰k1、k2，加密選擇明文，同時(shí)解密對(duì)應(yīng)的密文，檢測(cè)得到的值與預(yù)計(jì)算表中存儲(chǔ)的值是否相匹配。如果匹配，那么猜測(cè)密鑰是正確的；如果不匹配，那么猜測(cè)密鑰是錯(cuò)誤的，因此排除這個(gè)錯(cuò)誤的猜測(cè)密鑰。

Dunkelman、Keller和Shamir[15]在2010 年提出了差分枚舉技術(shù)，用來(lái)解決Demirci-Selcuk 中間相遇攻擊存儲(chǔ)復(fù)雜度較大的問(wèn)題，同時(shí)提出密鑰橋技術(shù)，通過(guò)尋找密鑰間的制約關(guān)系，降低攻擊的時(shí)間復(fù)雜度。在2010 年亞密會(huì)分析AES 算法時(shí)，Dunkelman、Keller和Shamir 在Demirci思想的基礎(chǔ)上引入多重集并利用有效的差分枚舉手段，大大降低了中間相遇攻擊預(yù)計(jì)算階段的復(fù)雜度。2013 年，Derbez 等[16]利用反射攻擊的思想對(duì)差分枚舉技術(shù)進(jìn)行了改進(jìn)，利用改進(jìn)后的差分枚舉技術(shù)可以進(jìn)一步降低Demirci-Selcuk 中間相遇攻擊的存儲(chǔ)復(fù)雜度。

Li 等[17]在2015 年提出相關(guān)密鑰篩選技術(shù)，結(jié)合差分枚舉技術(shù)可以進(jìn)一步控制內(nèi)部狀態(tài)的取值范圍，降低Demirci-Selcuk 中間相遇攻擊的存儲(chǔ)復(fù)雜度。隨后，Demirci-Selcuk 中間相遇攻擊技術(shù)被用于分析各種類(lèi)型的分組密碼算法[18-21]。

在CRYPTO 2016 上，Derbez和Fouque[22]總結(jié)梳理了Demirci-Selcuk 中間相遇攻擊的攻擊模式，利用計(jì)算機(jī)語(yǔ)言將Demirci-Selcuk 中間相遇攻擊的攻擊流程進(jìn)行轉(zhuǎn)化，實(shí)現(xiàn)了Demirci-Selcuk中間相遇攻擊的自動(dòng)化搜索。借助計(jì)算機(jī)強(qiáng)大的計(jì)算能力，搜索最優(yōu)的Demirci-Selcuk 中間相遇攻擊方案。

上述關(guān)于中間相遇攻擊的改進(jìn)技巧或方法為人們今后的研究提供了理論支撐，利用差分枚舉、密鑰橋等技術(shù)可以?xún)?yōu)化攻擊結(jié)果。中間相遇攻擊的自動(dòng)化研究也是目前的一個(gè)研究熱點(diǎn)，針對(duì)具體的算法給出自動(dòng)化搜索的結(jié)果，這也是本文將要深入研究的一個(gè)問(wèn)題。

3 Kiasu-BC 算法的5 輪中間相遇區(qū)分器

本節(jié)進(jìn)一步研究密鑰擴(kuò)展算法存在的缺陷，挖掘輪密鑰間的相互制約關(guān)系，構(gòu)造了一個(gè)新的Kiasu-BC算法5輪中間相遇區(qū)分器。在分析過(guò)程中，本文明確區(qū)分輪密鑰和調(diào)柄，第i輪的輪密鑰記作第i輪的調(diào)柄記作

3.1 Kiasu-BC 算法的性質(zhì)

從密鑰擴(kuò)展算法可知，Kiasu-BC 算法每輪的最后一個(gè)變換所需要的輪密鑰是由初始密鑰經(jīng)過(guò)擴(kuò)展得到的。從上面描述的密鑰擴(kuò)展方案，本文可以得到下面的關(guān)系。

在攻擊過(guò)程中，本文還會(huì)用到下列定義和性質(zhì)。

定義1[23]算法的b-δ-集是由其2b個(gè)中間狀態(tài)構(gòu)成的集合，且這2b個(gè)中間狀態(tài)在某一個(gè)字節(jié)（活躍字節(jié)）處遍歷，在其余字節(jié)（不活躍字節(jié)）處固定。

性質(zhì)1[24]給定任意一個(gè)雙射S 盒S，Δi和Δo分別為隨機(jī)選取的非零輸入差分和非零輸出差分，則方程平均只有一個(gè)解。

3.2 構(gòu)造5 輪中間相遇區(qū)分器

本節(jié)考慮w0[0]是活躍字節(jié)，經(jīng)過(guò)5 輪Kiasu-BC算法加密后，可以計(jì)算出相應(yīng)的有序序列Δx6[0,1]。本文充分考慮密鑰擴(kuò)展算法產(chǎn)生的輪密鑰間的制約關(guān)系，提出新的Kiasu-BC 算法的5 輪中間相遇區(qū)分器，得到定理1。

這樣，就用一個(gè)5 bit 參數(shù)和11 個(gè)字節(jié)推出了第一步中的字節(jié)參數(shù)。

為了確保分析工作的嚴(yán)謹(jǐn)性，一般在選擇δ-集時(shí)，如果對(duì)于4×4狀態(tài)矩陣的每一塊是8 bit的算法，可選擇5-δ-集；如果對(duì)于4×4 狀態(tài)矩陣的每一塊是4 bit的算法，可選擇4-δ-集。選擇不同的δ-集對(duì)數(shù)據(jù)復(fù)雜度的影響比較小。本文的主要工作是發(fā)掘密鑰間的制約關(guān)系來(lái)降低存儲(chǔ)復(fù)雜度，給出截?cái)嗖罘痔卣鞯亩ɡ砻枋霾⑦M(jìn)行詳細(xì)證明。在此基礎(chǔ)上，構(gòu)造Kiasu-BC 算法新的5 輪中間相遇區(qū)分器，繼而實(shí)現(xiàn)Kiasu-BC 算法的8 輪中間相遇攻擊。

4 改進(jìn)的8輪Kiasu-BC算法的中間相遇攻擊

在一些情況下，為了降低攻擊的復(fù)雜度，需要交換列混合變換與輪調(diào)柄密鑰加變換的順序。因?yàn)檫@2 個(gè)變換都是線(xiàn)性的，可以直接交換它們的順序，同時(shí)參與異或運(yùn)算的輪密鑰相應(yīng)地變?yōu)檠芯棵荑€擴(kuò)展算法產(chǎn)生的輪密鑰間的制約關(guān)系，利用內(nèi)部密鑰間的關(guān)系減少區(qū)分器中涉及的有序序列的取值個(gè)數(shù)，構(gòu)造5 輪中間相遇區(qū)分器，在區(qū)分器的前面加一輪、后面加2 輪，實(shí)現(xiàn)對(duì)8 輪Kiasu-BC 算法進(jìn)行中間相遇攻擊，具體如圖5 所示。改進(jìn)后的8 輪Kiasu-BC 算法中間相遇攻擊的時(shí)間復(fù)雜度為2114，存儲(chǔ)復(fù)雜度為263，數(shù)據(jù)復(fù)雜度為2108。

圖5 8 輪Kiasu-BC 算法中間相遇攻擊路徑

4.1 Kiasu-BC 算法的8 輪攻擊過(guò)程

攻擊過(guò)程可以分為預(yù)計(jì)算階段（線(xiàn)下部分）和在線(xiàn)階段（線(xiàn)上部分）2 個(gè)階段。

在線(xiàn)階段。首先需要找到一對(duì)滿(mǎn)足圖5 所示的截?cái)嗖罘痔卣鞯拿魑摹Ｈ缓髽?gòu)造包含該明文對(duì)的5-δ-集，計(jì)算對(duì)應(yīng)的有序序列。最后檢測(cè)計(jì)算的序列是否存在于哈希表H中。攻擊的過(guò)程描述如下。

1) 首先定義一個(gè)明文集在(0,5,10,15)處遍歷，在其他12 個(gè)字節(jié)處固定，該集合由 232個(gè)明文組成。其次定義一個(gè)調(diào)柄集合在T[0]的前5 bit 遍歷，其余字節(jié)處固定，集合由25個(gè)調(diào)柄組成。利用這2個(gè)集合可以得到24×8+5=237個(gè)密鑰調(diào)柄組合，進(jìn)而可得到 237× (237? 1) ÷ 2 ≈ 273個(gè)滿(mǎn)足圖5 所示的截?cái)嗖罘痔卣鞯拿魑牟罘謱?duì)。2) 截?cái)嗖罘痔卣鞯母怕蕿?2?(3+1+8+6)×8=2?144，需要選取 2144?73=271個(gè)明文結(jié)構(gòu)，因此共有明文?調(diào)柄組合 271+37=2108個(gè)。

3) 查詢(xún)結(jié)構(gòu)中每個(gè)明文?調(diào)柄組合所對(duì)應(yīng)的密文，并對(duì)其進(jìn)行部分解密，得到s7的值，且滿(mǎn)足每一個(gè)消息對(duì)在s7[1,2,3,4,8,11,14,15]處的差分為0。滿(mǎn)足上面條件的消息對(duì)有 2144?8×8=280對(duì)，對(duì) 280個(gè)消息對(duì)中的每一個(gè)執(zhí)行以下步驟。

4.2 復(fù)雜度分析

攻擊復(fù)雜度的分析過(guò)程如下。

預(yù)計(jì)算階段。每個(gè)有序序列有3 1×1 6=496 ≈ 29bit，大約需要 261× 29÷ 128=263個(gè)128 bit 塊的存儲(chǔ)空間。對(duì)5-δ-集進(jìn)行部分加密，約等價(jià)于1.5 輪Kiasu-BC 加密運(yùn)算，因此預(yù)計(jì)算階段的時(shí)間 復(fù)雜度 為 261× 25× 1.5 ÷ 9 ≈ 263.6次 8 輪Kiasu-BC 加密。

在線(xiàn)階段。時(shí)間復(fù)雜度主要由4.1 節(jié)步驟3) 決定，對(duì)32 個(gè)值的計(jì)算過(guò)程約等價(jià)于一輪Kiasu-BC加密運(yùn)算，時(shí)間復(fù)雜度為 280× 232× 25× 1 ÷ 8=2114次8 輪 Kiasu-BC 加密。攻擊所需的數(shù)據(jù)量為個(gè)選擇明文。

綜上可得，該攻擊的時(shí)間復(fù)雜度為預(yù)計(jì)算階段時(shí)間復(fù)雜度與在線(xiàn)階段時(shí)間復(fù)雜度之和，約為 2114，存儲(chǔ)復(fù)雜度為263，數(shù)據(jù)復(fù)雜度為2108。

因此，改進(jìn)后的中間相遇攻擊時(shí)間復(fù)雜度為2114次8 輪Kiasu-BC 算法加密，存儲(chǔ)復(fù)雜度為263個(gè)128 bit 塊，數(shù)據(jù)復(fù)雜度為 2108個(gè)明文?調(diào)柄組合。

表2將本文對(duì)Kiasu-BC 算法的攻擊結(jié)果與其他中間相遇攻擊結(jié)果進(jìn)行了對(duì)比。

表2 Kiasu-BC 算法與其他中間相遇攻擊結(jié)果的比較

與文獻(xiàn)[8]的工作相比，本文工作主要是糾正了文獻(xiàn)[8]的中間相遇攻擊中所用到的截?cái)嗖罘痔卣鞯母怕剩⒒诿荑€擴(kuò)展算法探尋Kiasu-BC 算法輪密鑰間的關(guān)系，利用密鑰間制約關(guān)系改進(jìn)中間相遇結(jié)果，大大降低了存儲(chǔ)復(fù)雜度；與文獻(xiàn)[11]的工作相比，本文充分考慮算法自身的密鑰相關(guān)性，降低了攻擊過(guò)程的存儲(chǔ)復(fù)雜度，同時(shí)可以啟發(fā)有興趣的研究者深度發(fā)掘更多的密鑰相關(guān)性，利用密鑰橋等技術(shù)改進(jìn)現(xiàn)有的攻擊結(jié)果。深度發(fā)掘Kiasu-BC 算法的密鑰間關(guān)系，也可以為其他的攻擊方法提供更好的改進(jìn)思路，例如Kiasu-BC 算法的不可能差分攻擊。

5 結(jié)束語(yǔ)

本文主要研究了Kiasu-BC 算法的中間相遇攻擊。通過(guò)研究Kiasu-BC的密鑰擴(kuò)展算法，利用調(diào)柄自由度以及內(nèi)部密鑰間的制約關(guān)系，結(jié)合Kiasu-BC 算法輪變換中的線(xiàn)性關(guān)系，提出了新的5 輪中間相遇區(qū)分器，降低了存儲(chǔ)復(fù)雜度，對(duì)8 輪Kiasu-BC 算法中間相遇攻擊的現(xiàn)有結(jié)果進(jìn)行了優(yōu)化。改進(jìn)后的8 輪Kiasu-BC 算法中間相遇攻擊的時(shí)間復(fù)雜度為2114，存儲(chǔ)復(fù)雜度為263，數(shù)據(jù)復(fù)雜度為2108。

如何構(gòu)造較長(zhǎng)輪數(shù)的中間相遇區(qū)分器，是筆者進(jìn)一步研究的方向；將中間相遇攻擊與其他攻擊方法相結(jié)合，實(shí)現(xiàn)更多輪數(shù)的攻擊路徑，從而得到更有效的分析結(jié)果，也是筆者將要研究的工作。