輕量級可調(diào)分組密碼算法CRAFT 的唯密文故障分析

蔡天培

（東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620）

0 引言

近年來隨著物聯(lián)網(wǎng)和邊緣計(jì)算的飛速發(fā)展，射頻識別標(biāo)簽、傳感器、智能設(shè)備等小型物聯(lián)網(wǎng)設(shè)備被廣泛運(yùn)用。由于物聯(lián)網(wǎng)設(shè)備體積和性能的限制，相比傳統(tǒng)設(shè)備而言，這類設(shè)備內(nèi)存更小、計(jì)算速度更慢、功耗更低。這些限制使物聯(lián)網(wǎng)設(shè)備難以在保證通信即時(shí)性的同時(shí)，還能運(yùn)行安全性較高、且性能開銷較大的傳統(tǒng)密碼算法，因此有必要?jiǎng)?chuàng)建新型輕量級密碼算法，在設(shè)計(jì)時(shí)將設(shè)備的物理限制納入考量，使密碼算法能夠在資源受限的設(shè)備中正常運(yùn)行，并獲得與傳統(tǒng)密碼相當(dāng)?shù)陌踩珜傩?。在此背景下，輕量級密碼算法甫經(jīng)提出就受到了國內(nèi)外學(xué)者的高度關(guān)注，相關(guān)設(shè)計(jì)與分析也已成為密碼學(xué)的主流研究方向之一。

CRAFT 是由Beierle 等學(xué)者在2019 年的國際對稱密碼學(xué)期刊（ToSC）中提出的可調(diào)輕量級分組密碼。該算法適合用于物聯(lián)網(wǎng)中資源受限的設(shè)備，具有低功耗、高效率、高安全性的特點(diǎn)。由于可調(diào)參數(shù)的加入，CRAFT 在加解密的變換上更加復(fù)雜。自CRAFT 公布以來，國內(nèi)外學(xué)者已經(jīng)發(fā)表多種不同的密碼分析方法分析其安全性，其中包括故障分析、差分分析、積分分析以及相關(guān)分析等。

故障分析作為一種主要的旁路攻擊方法，與其他攻擊方式相比，攻擊速度上要更快、威力更強(qiáng)。由于物聯(lián)網(wǎng)設(shè)備更加脆弱，攻擊者較為容易地就能以故障導(dǎo)入的方式得到錯(cuò)誤信息。攻擊者借由錯(cuò)誤信息推導(dǎo)出密碼內(nèi)部狀態(tài)信息，如此在短時(shí)間內(nèi)則可完成密碼破譯。

根據(jù)攻擊者監(jiān)聽加密通信能力的不同，對密碼的攻擊有多種不同的假設(shè)，其中唯密文攻擊對攻擊者要求最低。統(tǒng)計(jì)故障分析是一種基于唯密文攻擊的攻擊方式，攻擊者能夠僅使用隨機(jī)密文破譯密鑰。唯密文攻擊與其它假設(shè)相比，更接近物聯(lián)網(wǎng)的應(yīng)用環(huán)境。研究表明，多種輕量級密碼算法，例如LED、PRESENT 等均不能抵御統(tǒng)計(jì)故障分析。

本文提出了新型覆寫故障模型，并設(shè)計(jì)了能夠與覆寫故障模型相適應(yīng)的多種新型區(qū)分器，包括決定系數(shù)、雅卡爾相似系數(shù)、泊松偏差、余弦相似指數(shù)等。在統(tǒng)計(jì)故障攻擊中，上述的故障模型和新型區(qū)分器可以使故障注入的輪數(shù)更深、所使用的故障數(shù)更少、攻擊時(shí)間更短、攻擊效果更好。不同情況下破譯CRAFT 所需的故障數(shù)見表1。由表1 可知，利用新故障模型和區(qū)分器的統(tǒng)計(jì)故障分析能夠?yàn)镃RAFT 密碼算法抵御該類型的攻擊提供了重要參考。

表1 不同情況下破譯CRAFT 所需的故障數(shù)Tab.1 Fault numbers required to break CRAFT

1 CRAFT 算法

輕量級可調(diào)分組密碼CRAFT 具有代換置換網(wǎng)絡(luò)結(jié)構(gòu)。分組長度、密鑰和可調(diào)參數(shù)分別為64 比特、128 比特和64 比特。算法包含加密過程、解密過程和密鑰編排算法，其中解密為加密的逆運(yùn)算。加密算法共有32 輪運(yùn)算，每一輪包含列混合、常數(shù)加、可調(diào)密鑰加、P 置換和S 盒。特別地，最后一輪僅包含列混合、常數(shù)加和可調(diào)密鑰加。加密算法和加密密鑰編排算法的代碼設(shè)計(jì)詳見如下。

自CRAFT 提出以來，國際對其安全性進(jìn)行了深入分析與研究。2019 年，Beierle 等學(xué)者在提出該密碼算法時(shí)分析認(rèn)為CRAFT 在相關(guān)可調(diào)參數(shù)模型中具有124 比特的安全性。同年，ElSheikh 等學(xué)者利用16 個(gè)相關(guān)密鑰，對CRAFT 采用全輪差分分析的方式分析密鑰。2020 年，Guo 等學(xué)者使用明文的差分和一對相關(guān)的可調(diào)參數(shù)和密鑰，對CRAFT 做出15 輪分析。同年，Hadipour 等學(xué)者采用相關(guān)可調(diào)參數(shù)零相關(guān)分析的方法，利用可調(diào)參數(shù)作為輸入?yún)?shù)的特性，通過分析零相關(guān)性的線性堆的方法實(shí)現(xiàn)了CRAFT 在14 輪下的分析。2021年，Hadipour 等學(xué)者通過分析CRAFT 的故障傳播路徑，發(fā)現(xiàn)CRAFT 的加密算法存在飛去來器效應(yīng)，并從隨機(jī)組合中區(qū)分出經(jīng)過CRAFT 算法6～8輪加密的密文。

2 對CRAFT 的唯密文故障分析

2.1 基本假設(shè)

本文采用唯密文攻擊的基本假設(shè)，即攻擊者擁有監(jiān)聽加密通信的能力，但過程中僅可以獲取密文。上述內(nèi)容是攻擊者能力最弱的假設(shè)，在實(shí)際攻擊中具有強(qiáng)大的威脅性。攻擊者可以在密碼設(shè)備的運(yùn)算過程中向某一輪加密過程注入故障，從而導(dǎo)致算法在運(yùn)行中有了發(fā)生錯(cuò)誤的能力，但攻擊者并不能確定發(fā)生故障的位置的原始值和故障后的值。

2.2 故障模型

在傳統(tǒng)的故障分析中，攻擊者主要利用改變中間狀態(tài)值的手段來導(dǎo)入故障，進(jìn)而使得算法設(shè)備輸出錯(cuò)誤密文。傳統(tǒng)的統(tǒng)計(jì)故障攻擊方法的攻擊位置一般集中在中間狀態(tài)存儲中，攻擊面較小，且攻擊目標(biāo)單一。密碼設(shè)計(jì)人員較容易實(shí)施物理上的防御措施。

指令跳過是指干擾處理器運(yùn)行指令，使程序指令中的一部分出現(xiàn)被跳過的故障。指令跳過通過電磁場或激光射線觸發(fā)。2010 年Trichina 等學(xué)者在Cortex M3 微處理器上實(shí)現(xiàn)破譯系統(tǒng)，通過1～2 次的指令跳過，迫使CRT-RSA 算法在運(yùn)行過程中出現(xiàn)故障，執(zhí)行錯(cuò)誤的流程，并利用錯(cuò)誤輸出破譯密碼。

本文基于指令跳過故障模型對分組密碼的特定指令中所造成的影響，提出覆寫故障模型，該故障模型使用指令跳過故障以達(dá)到數(shù)值覆寫的故障效果。從而導(dǎo)致密碼算法的中間狀態(tài)發(fā)生異常，最終將輸出錯(cuò)誤密文。在對CRAFT 的攻擊中，該故障模型的目標(biāo)指令位于P 置換層，攻擊的示意如圖1 所示。在圖1 中，中間狀態(tài)0 號位、15 號位的值經(jīng)過P 置換變換、即將寫回原存儲空間時(shí)，由于指令跳過故障使得0 號位的值因?yàn)槲茨艹晒Ω露?5 號位的值覆寫。在該故障模型中，未更新的0 號位半字節(jié)稱為故障半字節(jié)，值相同而成功更新的15 號位半字節(jié)稱為源半字節(jié)。

圖1 CRAFT 算法的對PN 層覆寫故障模型Fig.1 Overwritten faults model on PN layer of CRAFT

2.3 主要過程

在本節(jié)中，通過將覆寫故障模型應(yīng)用于CRAFT，并采用唯密文故障分析的方式，結(jié)合使用6個(gè)不同的區(qū)分器來分析所得的中間狀態(tài)。首先，攻擊者需要在某一輪加密過程中導(dǎo)入故障并取得相應(yīng)的錯(cuò)誤密文。由于密文受到半字節(jié)覆寫故障模型的影響，根據(jù)故障模型的特征，在故障發(fā)生的時(shí)刻會有2 個(gè)半字節(jié)擁有相同的值。經(jīng)過故障傳播，最終得到的錯(cuò)誤密文將會是不均勻的。故障傳播示意圖如圖2 所示。

圖2 CRAFT 算法的故障傳播路徑Fig.2 Faults propagation path of CRAFT

隨后，將錯(cuò)誤密文與候選密鑰代入?yún)^(qū)分器進(jìn)行運(yùn)算，利用故障的偏差，不同的密文與密鑰結(jié)合會產(chǎn)生不同的區(qū)分器值。根據(jù)區(qū)分器的特性，攻擊者可以選取一組候選密鑰，使得這組密鑰對應(yīng)的區(qū)分器值最大或者最小，該組候選密鑰就是恢復(fù)出來的可調(diào)子密鑰的值。攻擊者不斷重復(fù)上述過程，直到所有的可調(diào)子密鑰均被恢復(fù)。每一次恢復(fù)可調(diào)子密鑰的步驟如下。

攻擊者在第28 輪的PN 層注入故障。所有的錯(cuò)誤密文由不同的隨機(jī)明文使用相同的主密鑰和可調(diào)參數(shù)加密得出。根據(jù)CRAFT 的密鑰編排算法，這也意味著加密時(shí)使用的可調(diào)子密鑰相同。

本步驟的目標(biāo)是恢復(fù)最后3 輪使用的可調(diào)子密鑰、和，其中包含了對CRAFT故障傳播的利用和區(qū)分器的使用。由圖1 可知，在PN 層導(dǎo)入故障后，可以利用公式倒推得出故障注入時(shí)的中間狀態(tài)。通過區(qū)分器對目標(biāo)半字節(jié)的統(tǒng)計(jì)學(xué)分析并結(jié)合目標(biāo)半字節(jié)的概率值列表，攻擊者可以使用不同的可調(diào)子密鑰計(jì)算出不同的區(qū)分器值。隨后，攻擊者通過選定區(qū)分器值的最大值或最小值，最終確定本次恢復(fù)的可調(diào)子密鑰。倒推公式如下：

在恢復(fù)可調(diào)子密鑰后，本步驟嘗試恢復(fù)主密鑰。當(dāng)可調(diào)參數(shù)作為公共輸入時(shí)，攻擊者可使用可調(diào)子密鑰、可調(diào)參數(shù)和盒恢復(fù)完整的128比特主密鑰。當(dāng)可調(diào)參數(shù)不公開時(shí)，攻擊者不能恢復(fù)完整的主密鑰，但可以將主密鑰的數(shù)量限定在16個(gè)。將與異或，攻擊者可以通過如下公式計(jì)算出：

根據(jù)CRAFT 的密鑰編排方案，（）是可調(diào)參數(shù)的一個(gè)排列，因此中的每一個(gè)半字節(jié)符合如下公式：

其中，∈［0，15］。

攻擊者知道的值，且一旦得知可調(diào)參數(shù)中任意一個(gè)半字節(jié)值，通過圖3 給出的值與值之間的異或關(guān)系圖，可調(diào)參數(shù)的所有值都可計(jì)算得出。在最糟糕的情況下，即使不知道可調(diào)參數(shù)的值，亦可以通過其他進(jìn)一步的分析，從16 個(gè)現(xiàn)有的候選主密鑰中選出正確的主密鑰。

圖3 Tk中的異或關(guān)系圖Fig.3 XOR relations among Tk

2.4 區(qū)分器

2.4.1 已有區(qū)分器

平方歐式距離（）將恢復(fù)出來的值序列與理論平均值映射到高維歐幾里德空間中的2 點(diǎn)，并計(jì)算這2 點(diǎn)的距離。該區(qū)分器可以評估恢復(fù)出來的分布到平均分布的距離。Fuhr 等學(xué)者首先將區(qū)分器應(yīng)用到對AES 的字節(jié)隨機(jī)故障模型的分析中。該指數(shù)的計(jì)算方式如下：

漢明重量（HW）定義為一個(gè)二進(jìn)制比特串與零串之間不同比特的數(shù)量。Fuhr 等學(xué)者將漢明重量應(yīng)用在對AES 的分析中。在CRAFT 中，正確的密鑰將使得漢明重量區(qū)分器值最小。漢明重量區(qū)分器值可通過如下方式進(jìn)行計(jì)算：

2.4.2 提出的區(qū)分器

（1）余弦相似指數(shù)（）。通過計(jì)算2 個(gè)非零向量夾角的余弦值來測量2 個(gè)向量相似程度的指數(shù)。攻擊者可以通過構(gòu)造2 個(gè)向量，分別包含所有源半字節(jié)和故障半字節(jié)。由于正確的密鑰可以使源半字節(jié)和故障半字節(jié)的值相同，2 個(gè)向量的重合程度最大，余弦相似指數(shù)值達(dá)到最大。該指數(shù)可通過如下公式計(jì)算求出：

（2）決定系數(shù)（）。用于統(tǒng)計(jì)線性回歸模型中觀察值與期望值的差異，描述了數(shù)據(jù)與觀察之間的符合程度。決定系數(shù)區(qū)分器在覆寫模型中觀測源半字節(jié)與目標(biāo)半字節(jié)的差異。當(dāng)候選密鑰為正確密鑰時(shí)，源半字節(jié)與目標(biāo)半字節(jié)的差異最小，此時(shí)區(qū)分器值最小。該區(qū)分器值的計(jì)算公式具體如下：

（3）雅卡爾相似系數(shù)（）。通過計(jì)算2 個(gè)集合的交集占這2 個(gè)集合的并集的比例，測量2 個(gè)集合的相似程度。在二進(jìn)制中，雅卡爾相似系數(shù)可以測量2 個(gè)比特串的相似程度。在覆寫模型中，雅卡爾相似系數(shù)區(qū)分器通過計(jì)算源半字節(jié)與故障半字節(jié)的重疊程度區(qū)分正確密鑰。正確密鑰可以使被恢復(fù)的源半字節(jié)與故障半字節(jié)相同，其雅卡爾相似系數(shù)區(qū)分器值將最大。雅卡爾相似系數(shù)區(qū)分器值的計(jì)算方式如下：

（4）泊松偏差（）。用于比較2 個(gè)廣義泊松回歸模型的相似度。該偏差值描述了模型與數(shù)據(jù)的符合程度。在覆寫模型的條件下，該區(qū)分器描述了源半字節(jié)與故障半字節(jié)的符合程度。正確的密鑰可以使得源半字節(jié)與故障半字節(jié)的符合程度最高。泊松偏差區(qū)分器值的計(jì)算方式如下：

3 實(shí)驗(yàn)

本實(shí)驗(yàn)利用計(jì)算機(jī)軟件模擬隨機(jī)故障導(dǎo)入，在PC 機(jī)上使用Python 語言編程進(jìn)行分析，并且對每種故障模型區(qū)分器組合運(yùn)行1000 次實(shí)驗(yàn)。本節(jié)以恢復(fù)密鑰為實(shí)驗(yàn)?zāi)繕?biāo)，并以故障數(shù)和成功率為指標(biāo)，評測不同故障模型以及不同區(qū)分器的效果。

3.1 成功率

成功率是指不同區(qū)分器破譯CRAFT 密碼的概率。研究中分別統(tǒng)計(jì)了在2 種故障模型中，各個(gè)區(qū)分器恢復(fù)密鑰時(shí)，不同故障數(shù)對應(yīng)的成功率如圖4所示。圖4 中，橫軸和縱軸分別表示故障數(shù)和破譯成功率，不同顏色曲線代表不同區(qū)分器。當(dāng)使用覆寫故障模型時(shí)，余弦相似指數(shù)、決定系數(shù)、雅卡爾相似系數(shù)和泊松偏差區(qū)分器均可以高于99%的概率恢復(fù)主密鑰，相比而言，使用隨機(jī)與故障模型和平方歐式距離區(qū)分器的情況下，恢復(fù)密鑰的概率僅有96%，其他故障模型也需要更多的故障數(shù)才能恢復(fù)正確的主密鑰。

圖4 不同情況下區(qū)分器恢復(fù)密鑰的成功率Fig.4 Success rate of key recovery on various conditions

3.2 故障數(shù)

故障數(shù)是指不同區(qū)分器以最大概率破譯密碼所需最少故障數(shù)。由圖4 可知，在使用覆寫故障模型時(shí)，破譯密碼所需要的故障數(shù)大幅降低，攻擊能力極強(qiáng)。在覆寫故障模型下，余弦相似指數(shù)、決定系數(shù)、雅卡爾相似系數(shù)需要72 個(gè)故障來恢復(fù)密鑰，泊松偏差則僅需64 個(gè)故障。在使用置0 故障模型時(shí)，漢明重量區(qū)分器需要80 個(gè)故障，平方歐式距離則需要288 個(gè)。在隨機(jī)與故障模型下，漢明重量區(qū)分器需要624 個(gè)故障。

4 結(jié)束語

本文展示了使用唯密文故障分析的分析方式，結(jié)合6 個(gè)去分析和面向半字節(jié)的覆寫故障模型，來分析CRAFT 密碼系統(tǒng)。在最優(yōu)情況下，本分析方式能夠使用最少64 個(gè)故障破譯CRAFT。該結(jié)果展示出唯密文故障分析是在物聯(lián)網(wǎng)領(lǐng)域?qū)RAFT 的一個(gè)巨大威脅，為密碼設(shè)計(jì)人員提供了CRAFT 密碼安全性檢測的方法，也對輕量級可調(diào)分組密碼實(shí)現(xiàn)安全研究有著不可低估的參考價(jià)值。