基于MMO-GIFT 安全性研究*

竇山雀 毛 明 李艷俊

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

2.中國(guó)電子科技集團(tuán)公司第十五研究所，北京市 100083

引言

隨著信息技術(shù)的快速發(fā)展，移動(dòng)互聯(lián)網(wǎng)技術(shù)廣泛應(yīng)用于生活的各個(gè)方面。 比如：AI 智能機(jī)器、無(wú)人檢測(cè)技術(shù)、大數(shù)據(jù)分析和各類智能定位技術(shù)。 但是，物聯(lián)網(wǎng)設(shè)備存儲(chǔ)、計(jì)算、能耗等資源的限制，導(dǎo)致我們需要更為輕便高效的密碼算法和協(xié)議。 于是，在2018 年NIST 向全球征集輕量級(jí)的密碼算法，得到了很多優(yōu)秀的輕量級(jí)認(rèn)證算法，對(duì)于這些算法學(xué)者提出了一些認(rèn)證模式。 目前，主流的輕量級(jí)密碼算法主要有GIFT［1］、PRENSENT［2］、CLEFIA［3］、PRINCE［4］、SPECK［5］、LBOCK［6］、SIMON［5］等。 這些輕量級(jí)算法可以通過(guò)認(rèn)證模式構(gòu)造新的散列函數(shù)。 其中GIFT 算法是由Banik 等人2017 年在CHES上提出的一種類似PRESENTF 的新型輕量級(jí)分組密碼算法。 在CTRSA2019 上，朱［7］等人對(duì)GIFT 進(jìn)行了第一次第三方密碼分析，包括對(duì)GIFT－64 和GIFT128 分別進(jìn)行了密鑰恢復(fù)攻擊。Sasaki［8］等人改進(jìn)了GIFT－64 上的中間相遇攻擊（MitM）。 周［9］等列出了GIFT－64 的一些最佳差分特征。

目前，學(xué)者對(duì)輕量級(jí)密碼算法的安全性做了大量的分析和研究，而針對(duì)散列函數(shù)模型的安全性研究并沒(méi)有受到太多的關(guān)注。 直到2020 年，Sasaki［10］等人在EUROCRYPT 針對(duì)具體散列函數(shù)提出了專用的量子碰撞攻擊。 使得散列函數(shù)的安全性再次受到關(guān)注。 即使壓縮函數(shù)Ek在經(jīng)典環(huán)境中是安全的，但基于該壓縮函數(shù)的散列函數(shù)仍可能存在碰撞。 因此，深入研究、評(píng)估散列函數(shù)的安全性是十分有必要的。

1 散列函數(shù)

散列函數(shù)［11］（雜湊函數(shù)或Hash 函數(shù)）是將任意長(zhǎng)度的消息壓縮成唯一的、固定長(zhǎng)度的散列值，其主要應(yīng)用在數(shù)字簽名、數(shù)據(jù)完整性的檢測(cè)中。 一個(gè)安全的散列算法必須滿足抗原像攻擊、抗第二原像攻擊、抗碰撞攻擊這3 條基本的安全屬性。 隨著現(xiàn)代科學(xué)技術(shù)的廣泛應(yīng)用，對(duì)數(shù)字簽名、數(shù)據(jù)完整性的應(yīng)用需求越來(lái)越高，散列函數(shù)被應(yīng)用到各個(gè)場(chǎng)景的關(guān)鍵技術(shù)中，占有舉足輕重的地位。 隨著MD5、SHA 算法的破解，評(píng)估散列函數(shù)的安全性已經(jīng)變得越來(lái)越重要。

散列函數(shù)的結(jié)構(gòu)主要有Merkle-Damgard 結(jié)構(gòu)［12］、Tree 結(jié)構(gòu)［13］、Sponge 結(jié)構(gòu)［14］等。 其設(shè)計(jì)采用了分組迭代，處理過(guò)程是將消息格式化處理分組，然后將每塊分組消息放入分組迭代中進(jìn)行處理。 其迭代結(jié)構(gòu)如圖1 所示。

圖1 散列函數(shù)的迭代結(jié)構(gòu)

Merkle-Damgard（MD）結(jié)構(gòu)是經(jīng)典的散列迭代結(jié)構(gòu)，具有該結(jié)構(gòu)的散列函數(shù)對(duì)于多碰撞攻擊、第二原像攻擊、擴(kuò)展長(zhǎng)度攻擊有弱抵抗性。針對(duì)MD 結(jié)構(gòu)的缺陷，后續(xù)也出現(xiàn)了改進(jìn)的MD結(jié)構(gòu)，主要有隨機(jī)散列、寬管道結(jié)構(gòu)、HAIFA 結(jié)構(gòu)。 Tree 結(jié)構(gòu)主要用于構(gòu)造數(shù)字簽名認(rèn)證。Sponge 結(jié)構(gòu)主要由初始化、吸收、擠壓三部分組成，但是短消息加密效率沒(méi)有長(zhǎng)消息占優(yōu)勢(shì)。

目前，現(xiàn)有關(guān)于散列函數(shù)的分析方法主要有：生日攻擊［15］、差分攻擊［16］、原像攻擊［17］、中間相遇攻擊［18］等。 隨著量子信息技術(shù)越來(lái)越多地被用到分組密碼等多個(gè)密碼算法的分析研究。2020 年Sasaki［10］在EUROCRYPT 提出了第一個(gè)針對(duì)哈希函數(shù)的專用量子攻擊——反彈攻擊，這項(xiàng)工作使得我們的研究不僅僅停留在生日界上，為我們對(duì)散列函數(shù)抵抗量子攻擊的安全性的研究開辟了一個(gè)新的視角。

2 GIFT 密碼算法

GIFT 算法是基于PRESENT 算法的基本結(jié)構(gòu)而改進(jìn)的一個(gè)算法，GIFT 算法取其“禮物”之意，是2017 年Subhadeep Banik 等人為慶祝PRENSENT 算法發(fā)表十周年提出的。 相比于SIMON、SKINNY 算法等輕量級(jí)分組密碼算法，該算法的算法設(shè)計(jì)更加簡(jiǎn)潔、清楚，運(yùn)行速度快、功耗低。 GIFT 算法采用的是SPN 結(jié)構(gòu)，兩個(gè)版本分組長(zhǎng)度是64 比特和128 比特，都采用128 比特長(zhǎng)度密鑰，迭代輪數(shù)分別是28 輪和40 輪。 關(guān)于數(shù)據(jù)狀態(tài)的最右側(cè)為最低比特位，形式為bn－1bn－2…b0，n ＝64 或128。

GIFT 不僅僅是“禮物”之意，其算法設(shè)計(jì)者也是用打包“禮物”的方式來(lái)描述該算法。 該算法的輪函數(shù)是由S 盒、P 置換、密鑰加組成，把內(nèi)容放到S 盒里，然后將P 置換作為絲帶包裹盒子，最后用密鑰加來(lái)打結(jié)。 關(guān)于GIFT－64 的輪函數(shù)結(jié)構(gòu)如圖2 所示。

圖2 2 輪GIFT－64 算法

S 盒：GIFT－64 和GIFT－128 都是使用相同的4 比特S 盒，該S 盒是非線性部件，結(jié)構(gòu)如表1 所示。

表1 GIFT 算法的S 盒

P 置換：線性層都是采用比特置換，置換表如表2 所示。

表2 GIFT 算法置換表

密鑰加：這部分由輪密鑰和輪常數(shù)組成，GIFT 算法密鑰都是采用128 比特，主密鑰通過(guò)密鑰擴(kuò)展取32 比特和64 比特的輪密鑰RK ＝U｜｜V，其中U ＝us－1…u0，V ＝vs－1...v0，對(duì)于GIFT－64，s 為16，GIFT－128 的s 為32。 也就是說(shuō)，對(duì)于GIFT－64 和GIFT－128，每一輪分別有32 比特和64 比特輪密鑰參與運(yùn)算。

對(duì)于GIFT－64，U和V分別與b4i＋1和b4i相異或。

b4i＋1←b4i＋1⊕ui，b4i←b4i⊕vi，?i∈｛0，…，15｝

對(duì)于GIFT－128，U和V分別與b4i＋1和b4i相異或。

b4i＋2←b4i＋2⊕ui，b4i＋1←b4i＋1⊕vi，?i∈｛0，…，31｝

輪密鑰均是根據(jù)

k7‖k6‖k5‖k4‖k3‖k2‖k1‖k0←k1＞＞2‖k0＞＞12‖k7‖k6‖k5‖k4‖k3‖k2

來(lái)更新（注意：第一輪的密鑰直接提取即可）。 之后我們的數(shù)據(jù)還需要與輪常數(shù)相異或。對(duì)于GIFT-n（n ＝128／256），單獨(dú)的比特“1”和6比特的輪常數(shù)C ＝｛c5，c4，c3，c2，c1，c0｝ 分別與第n－1，23，19，15，11，7，3 個(gè)比特相異或。 輪常數(shù)C初始化為0，并按照

（c5，c4，c3，c2，c1，c0）←（c4，c3，c2，c1，c0，c5⊕c4⊕1）

更新每一輪的輪常數(shù)。

3 MMO-GIFT 的安全性研究

散列函數(shù)的散列模型主要有DM、MMO、MP等，如圖3 所示。 通過(guò)對(duì)MMO 模型的研究，假設(shè)密鑰輸入k固定為初始值iv，Eiv的差分路線概率為p，其輸入和輸出異或公共值Δ。 給定大約1／p對(duì)具有異或值Δ 的輸入消息，預(yù)計(jì)有一對(duì)（m，m⊕Δ）遵循這種差異路線：Eiv（m） ⊕Eiv（m⊕Δ）＝Δ。 如果密文異或與明文異或相匹配，通過(guò)前饋操作后其輸出的值為0，即（m⊕Eiv（m）） ⊕（m⊕Eiv（m⊕Δ））＝Δ⊕Δ ＝0。 也就是說(shuō)，如果輸入和輸出的有效字節(jié)位置以及實(shí)際的差異是相同的，就會(huì)產(chǎn)生碰撞，MMO 模型的安全性就會(huì)大大降低。 因此，對(duì)于該模型實(shí)例化最低安全輪數(shù)的尋找十分重要。

圖3 DM、MMO 和MP 散列模型

針對(duì)GIFT－64，其空間大小為2－64， 只有找到差分概率高于2－64的差分路線才是有意義的。目前，朱寶玉［19］等人使用MILP 對(duì)輕量級(jí)分組密碼算法GIFT 的差分分析，作者將算法分為外層和內(nèi)層，針對(duì)外層部分，搜索活躍S 盒的數(shù)量盡可能少的截?cái)嗖罘致肪€；算法內(nèi)層是在外層約束下進(jìn)一步搜索概率高的差分路線。運(yùn)用這樣的MILP 算法找到多條GIFT 差分路線，對(duì)這些差分路線進(jìn)行分析，發(fā)現(xiàn)有一部分12 輪差分路線是由4 輪循環(huán)路線迭代而成。在這些12 輪的差分路線中第1 輪輸入差分、第5 輪輸入差分、第9 輪輸入差分和最后一輪輸出差分的比特狀態(tài)是完全一致的，這12 輪的差分路線是由完全相同的三個(gè)4 輪循環(huán)路線首位鏈接組成，本文整理了GIFT－64 所有的4 輪循環(huán)差分路線，如表3 所示。 這些迭代路線首尾組合之后組成的差分路線包含24 個(gè)活躍S盒。 選取迭代路線組成一條12 輪概率為2－60的差分路線。 如表4 所示。

表3 GIFT－64 的4 輪差分迭代路線

表4 GIFT－64 的12 輪差分路線

輪數(shù)差分特征概率4 0000 0050 0000 00502－20 Input0005 0000 0005 00001 1 0000 0000 2020 00002－6 0050 0000 0050 00002－10 3 0000 0000 0000 20202－16 4 0005 0000 0005 00002－20 Input0000 0202 0000 00001 1 0000 0500 0000 05002－4 2 0202 0000 0000 00002－10 3 0000 5000 0000 50002－14 4 0000 0202 0000 00002－20 Input0000 000a 0000 000a1 1 0000 0000 0000 01012－4 2 000a 0000 000a 00002－10 3 0000 0000 0000 10102－14 4 0000 000a 0000 000a2－20 Input0000 00a0 0000 00a01 1 0101 0000 0000 00002－4 2 a000 0000 a000 00002－10 3 0000 0000 1010 00002－14 4 0000 00a0 0000 00a02－20 2

本文主要是對(duì)MMO 模型實(shí)例化MMO-GIFT的安全性進(jìn)行分析研究。 根據(jù)對(duì)GIFT－64 的分析整理，之前對(duì)GIFT 算法迭代差分路線的研究都是只有4 輪，其認(rèn)為尋找輪數(shù)更大、概率更高的迭代差分路線也是有意義的，但對(duì)于更高輪數(shù)并沒(méi)有進(jìn)行過(guò)多的研究。 本文利用MILP 的搜索算法對(duì)GIFT 算法進(jìn)行了進(jìn)一步新的搜索、分析，首次提出了一條概率為2－60的6 輪迭代差分路線。 相比于4 輪迭代差分路線，在概率相同的情況下，其迭代輪數(shù)更大。 如果將該路線經(jīng)過(guò)兩輪迭代，就能夠得到一條全新的12 輪差分路線，如表5 所示。 這條路線的提出有利于我們對(duì)GIFT 算法的認(rèn)識(shí)以及后續(xù)的研究。

表5 GIFT－64 新的6 輪差分迭代路線

通過(guò)對(duì)GIFT 差分路線的搜索、分析和研究，我們對(duì)基于GIFT 新構(gòu)造的散列函數(shù)進(jìn)行了安全性分析。 通過(guò)將GIFT 輪函數(shù)作為散列模式MMO 中的壓縮函數(shù)，構(gòu)造相應(yīng)的散列函數(shù)。將這樣的壓縮函數(shù)插入迭代結(jié)構(gòu)，這樣就可以得到MMO-GIFT 散列。 針對(duì)我們之前對(duì)散列模型研究發(fā)現(xiàn)如果密文差異與明文差異匹配，MMO模式通過(guò)前饋操作后輸出的差分就會(huì)為零，即

（m⊕Eiv（m））⊕（m⊕Eiv（m⊕Δ））＝Δ⊕Δ ＝0

這樣的情況其安全性會(huì)極大降低。 所以，針對(duì)MMO-GIFT 散列函數(shù)其輪數(shù)大于12 輪的才是安全的。

4 結(jié)論

本文主要通過(guò)研究散列模型的結(jié)構(gòu)特性，發(fā)現(xiàn)如果散列函數(shù)中密文異或和明文異或相匹配，那么經(jīng)過(guò)MMO 模式的前饋操作后就會(huì)導(dǎo)致輸出的結(jié)果為零，這樣散列函數(shù)是不安全的。 為了避免攻擊者利用這一性質(zhì)發(fā)起攻擊，本文對(duì)散列模型的MMO 結(jié)構(gòu)實(shí)例化安全性研究，將GIFT算法作為置換函數(shù)，構(gòu)造GIFT 散列，首次提出了6 輪迭代差分路徑，在此基礎(chǔ)上發(fā)現(xiàn)12 輪差分路線的GIFT 散列函數(shù)安全性會(huì)降低。

通過(guò)對(duì)GIFT 散列函數(shù)的安全性研究，可以知道當(dāng)我們使用GIFT 作為輪函數(shù)的散列函數(shù)時(shí)，其輪數(shù)大于12 輪安全性極大提高。 所以，研究各種分組密碼算法作為置換函數(shù)的散列函數(shù)，為散列函數(shù)提供了最小安全輪數(shù)。 只要大于這樣的最小安全輪數(shù)，其構(gòu)成的散列函數(shù)就是安全的。