削減輪數(shù)的Khudra-64 積分攻擊*

李艷俊 梁 萌 林 昊 袁 峰

北京電子科技學(xué)院，北京市 100070

引言

隨著物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，體積小、資源受限的設(shè)備的日漸普及對密碼算法提出了新的要求。 在資源有限的條件下，輕量級分組密碼既能夠有效地提供安全性保障，又能實(shí)現(xiàn)較好的運(yùn)行效率，能夠很好地滿足物聯(lián)網(wǎng)技術(shù)發(fā)展對密碼技術(shù)的要求。 近年來，有很多的輕量級分組密碼被 提 出， 如 Midori[1]、 Piccolo[2]、 MIBS[3]、 等。Khudra[4]算法是由Souvik Kolay 等人于2014 年提出的總輪數(shù)為18 輪的輕量級分組密碼算法。

積分攻擊[5]、差分攻擊[6]、線性攻擊[7]是目前最主要的三種密碼分析方法，用來對密碼算法進(jìn)行安全性的評估。 積分攻擊通過分析加密過程中積分性質(zhì)的傳播變化過程，確認(rèn)區(qū)分器的活躍比特、常數(shù)比特和平衡比特的位置，進(jìn)行積分區(qū)分器的構(gòu)建。 利用得到的積分區(qū)分器的性質(zhì)，可以以更好的時(shí)間和數(shù)據(jù)復(fù)雜度，對密碼算法進(jìn)行更多輪數(shù)的密鑰恢復(fù)攻擊。

近年來，自動化搜索技術(shù)的提出與不斷發(fā)展，也進(jìn)一步推動了密碼分析領(lǐng)域的發(fā)展。 區(qū)分器的搜索和構(gòu)建也更加便捷。 向澤軍[8]等人在Todo[9]提出的可分性的基礎(chǔ)上，進(jìn)一步與MILP思想結(jié)合，提出來基于比特可分性的MILP 積分區(qū)分器搜索技術(shù)，能夠更加方便高效地對密碼算法的積分安全性進(jìn)行評估。

密鑰恢復(fù)攻擊是一種常見的密碼算法安全性分析方法。 其主要思想是，利用密碼算法的某些固有特性規(guī)律或設(shè)計(jì)缺陷，通過某些巧妙的操作和處理，使得最終能夠獲得加密過程中某些密鑰比特的信息素。 本文利用搜索得到的積分區(qū)分器，對Khudra-64 算法進(jìn)行了9 輪，10 輪和11輪的密鑰恢復(fù)攻擊。 對Khudra-64 在積分安全性方面進(jìn)行了較為完善的總體評估。

1 預(yù)備知識

1.1 Khudra 算法介紹

Khudra 算法是由Souvik Kolay 等人于2014年針對FPGAs 環(huán)境提出的對稱分組加密算法，在軟硬件實(shí)現(xiàn)中都具有較好的表現(xiàn)，同時(shí)也能夠較好地抵抗各種密碼攻擊方法。 Khudra 算法的分組長度為64 比特，主密鑰長度為80 比特，共進(jìn)行18 輪加密，在第一輪與最后一輪加密時(shí)需要加入白化密鑰。

算法中的F 函數(shù)的結(jié)構(gòu)與算法的加密結(jié)構(gòu)較為相似，是一個(gè)循環(huán)6 輪的Feistel 加密結(jié)構(gòu)。F 函數(shù)為16 進(jìn)16 出的加密部件，當(dāng)F 函數(shù)的輸入為x[1，16]，輸出為y[1，16]， 則輸入和輸出之間有如下關(guān)系:

y[1，4]＝Sbox(Sbox(Sbox(Sbox(Sbox(x[1，4]) ⊕x[5，8]) ⊕x[9，12]) ⊕Sbox(x[9，12]) ⊕x[13，16])

⊕Sbox(Sbox(x[9，12]) ⊕x[13，16]) ⊕x[1，4]) ⊕Sbox(Sbox(Sbox(x[9，12]) ⊕x[13，16]) ⊕x[1，4]) ⊕x[5，8]

y[5，8]＝Sbox(Sbox(Sbox(Sbox(Sbox(Sbox(x[1，4]) ⊕x[5，8]) ⊕x[9，12]) ⊕Sbox(x[9，12]) ⊕x[13，16])

⊕Sbox(Sbox(x[9，12]) ⊕x[13，16]) ⊕x[1，4]) ⊕Sbox(Sbox(Sbox(x[9，12]) ⊕x[13，16]) ⊕x[1，4]) ⊕x[5，8])

⊕Sbox(Sbox(Sbox(Sbox(x[9，12]) ⊕x[13，16]) ⊕x[1，4]) ⊕Sbox(x[1，4]) ⊕x[5，8])

⊕Sbox(Sbox(x[1，4]) ⊕x[5，8]) ⊕x[9，12]

y[9，12]＝Sbox(Sbox(Sbox(Sbox(Sbox(x[9，12]) ⊕x[13，16]) ⊕x[1，4]) ⊕Sbox(x[1，4]) ⊕x[5，8])

⊕Sbox(Sbox(x[1，4]) ⊕x[5，8]) ⊕x[9，12]) ⊕Sbox(Sbox(Sbox(x[1，4]) ⊕x[5，8]) ⊕x[9，12])y[13，16]＝

⊕Sbox(x[9，12]) ⊕x[13，16]

Sbox(Sbox(Sbox(Sbox(Sbox(Sbox(x[9，12]) ⊕x[13，16]) ⊕x[1，4]) ⊕Sbox(x[1，4]) ⊕x[5，8])

⊕Sbox(Sbox(x[1，4]) ⊕x[5，8]) ⊕x[9，12]) ⊕Sbox(Sbox(Sbox(x[1，4]) ⊕x[5，8]) ⊕x[9，12])

⊕Sbox(x[9，12]) ⊕x[13，16]) ⊕Sbox(Sbox(Sbox(Sbox(x[1，4]) ⊕x[5，8]) ⊕x[9，12])

⊕Sbox(x[9，12]) ⊕x[13，16]) ⊕Sbox(Sbox(x[9，12]) ⊕x[13，16]) ⊕x[1，4]

1.2 基于比特可分性搜索獲得的積分區(qū)分器

可分性是由Todo 提出的一種廣義的積分性質(zhì)，可以用來幫助評估分組密碼的積分安全性。向澤軍等人在此基礎(chǔ)上，利用MILP 方法進(jìn)行可分性的建模，對幾種常見的密碼算法進(jìn)行搜索，均成功地獲得了較好的區(qū)分器結(jié)果。 在此前的文章中，已經(jīng)通過對Khudra 算法進(jìn)行MILP 建模搜索得到了兩個(gè)6 輪積分區(qū)分器和一個(gè)7 輪區(qū)分器。 通過搜索得到的7 輪積分區(qū)分器如下:

輸入:(ccccccccaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaa)

輸出:(??????????????????????????????????? b????????????????????????????)

在上述的積分區(qū)分器中，a 表示在輸入的明文集中，該位置為活躍位置，取值需要取遍0 和1。 c 表示在輸入的明文集中，該位置為常數(shù)位置，取值可以為0 或1，但所取值需要保持不變。b 表示經(jīng)過7 輪加密之后輸出結(jié)果的平衡位置。將明文集對應(yīng)的加密結(jié)果的平衡位置的值進(jìn)行異或后，值必然為0。? 表示輸出結(jié)果中的未知位置，這些位置的性質(zhì)難以確定，不具有規(guī)律性。

該區(qū)分器所代表的的含義為:將輸入的第9到64 位設(shè)定為活躍比特位，取相應(yīng)的明文集進(jìn)行7 輪加密之后，加密結(jié)果密文集求和后的第36 位比特為平衡位置，值為0。 本文的攻擊是基于搜索到的上述7 輪積分區(qū)分器進(jìn)行的。

2 積分攻擊

取符合區(qū)分器的輸入的明文集。 將常數(shù)比特位設(shè)為定值，取遍所有活躍比特位的所有的值，遍歷后得到攻擊所需的明文集。 明文集內(nèi)共有256個(gè)不同的明文。 在攻擊中的一些符號所表示含義如下:

rkxi: 第x 個(gè)子密鑰中的第i 比特的值。rkx[i，j]:第x 個(gè)子密鑰中的第i 到第j 比特的值。

A＝B:可以從B 的值中推得A 相應(yīng)的比特的值。

2.1 Khudra 算法的9 輪密鑰恢復(fù)攻擊

將明文集進(jìn)行9 輪加密，取加密結(jié)果的第4位比特，第49 到64 位比特的值，攻擊過程如下:

CT掃描需要較長的時(shí)間，這個(gè)過程中，掃描對象如果發(fā)生形狀、位置的變化，會降低CT成像質(zhì)量。運(yùn)動偽影主要分為剛體運(yùn)動偽影和非剛體運(yùn)動偽影。

將加密結(jié)果的第49 到64 位比特的值代入F 函數(shù)中，可以推得:

2.2 Khudra 算法的10 輪密鑰恢復(fù)攻擊

將明文集進(jìn)行10 輪加密，取加密結(jié)果的第52 位比特，第17 到48 位比特的值，攻擊過程如下:

根據(jù)Khudra 算法的細(xì)節(jié)可以推得:

2.3 Khudra 算法的11 輪密鑰恢復(fù)攻擊

將明文集進(jìn)行11 輪加密，取加密結(jié)果的第36 位比特，第1 到32 位，第49 到64 位比特的值，攻擊過程如下:

根據(jù)Khudra 算法的細(xì)節(jié)可以推得:

在整個(gè)攻擊過程中，共需要猜測34 比特的密鑰值。 需要34 個(gè)特定的明文集，才可以得到唯一正確的

3 結(jié)論

在基于比特可分性進(jìn)行MILP 建模搜索得到的7 輪積分區(qū)分器的基礎(chǔ)上，使用部分和技術(shù)，對Khudra-64 算法進(jìn)行了9 輪，10 輪和11輪的積分攻擊。 9 輪積分攻擊的時(shí)間復(fù)雜度為256.08次9 輪加密，數(shù)據(jù)復(fù)雜度為256。 10 輪積分攻擊的時(shí)間復(fù)雜度為263.87次10 輪加密，數(shù)據(jù)復(fù)雜度為260.09。 11 輪積分攻擊的時(shí)間復(fù)雜度為280.63次11 輪加密，數(shù)據(jù)復(fù)雜度為261.09。 算法的主密鑰為80 位比特，在9 輪，10 輪積分攻擊中，時(shí)間復(fù)雜度優(yōu)于窮搜攻擊，在11 輪攻擊中，時(shí)間復(fù)雜度基本與對主密鑰進(jìn)行窮搜攻擊相等。 這是首次較為全面的對Khudra-64 的積分性質(zhì)評估。

迄今為止，很多作者對Khudra 算法進(jìn)行了安全性評估。 在參考文獻(xiàn)[16]和[17]中，分別做到了16 輪的相關(guān)密鑰矩形攻擊和全輪的相關(guān)密鑰不可能差分攻擊。 在16 輪的矩形攻擊中，時(shí)間復(fù)雜度為278.7， 數(shù)據(jù)復(fù)雜度257.82；全輪的不可能差分攻擊的時(shí)間復(fù)雜度為268.5， 數(shù)據(jù)復(fù)雜度263。 綜上，兩種攻擊的輪數(shù)比我們的積分攻擊輪數(shù)要長，復(fù)雜度也基本優(yōu)于我們的積分攻擊。 由此可見，Khudra-64 算法結(jié)構(gòu)在抵抗積分性評估時(shí)表現(xiàn)更好，也就是說，Khudra-64 能夠較好地抵抗可分性方面的自動化搜索和密鑰恢復(fù)攻擊，具有較好的積分性質(zhì)，為算法設(shè)計(jì)提供了一定的思路。