認證加密算法SUNDAE-GIFT 的故障分析

朱曉銘

（東華大學 計算機科學與技術學院，上海 201620）

0 引言

隨著信息產業(yè)的快速發(fā)展，一些軟硬件資源受限的設備，如射頻識別標簽和智能卡等，正在廣泛應用于智能農業(yè)、智慧醫(yī)療、智慧建筑等生活領域，需要密碼保護的范圍也因此變得更加廣闊［1］。但是早期的認證工作模式由于對資源有較高的要求，不再適用于資源受限的設備中。輕量級的認證加密算法在保證數據機密性、完整性和消息鑒別功能的基礎上，又降低了對資源的需求，因此受到國內外學者的高度關注，不同模式的輕量級認證加密算法的設計與分析成為研究的重點［2］。

SUNDAE-GIFT 是由Banik 等學者提出的基于SUNDAE（Small Universal Deterministic Authenticated Encryption）模式，并采用GIFT-128 為底層分組密碼的輕量級認證加密算法，入選美國國家標準與技術研究院（NIST）啟動的輕量級密碼標準化項目的第二輪評選［3］。相較于PRESENT，輕量級密碼GIFT更加安全和高效，甚至優(yōu)于輕量級密碼SKINNY 和SIMON［4］。相較于傳統(tǒng)的認證加密模式，SUNDAEGIFT 具有低功耗，高效率等特點，適合RFID 和智能卡網絡等資源受限設備。

1997 年，Boech 等學者首次利用故障分析破譯RSA 算法［5］。后來，通過結合傳統(tǒng)密碼分析和故障分析，逐漸衍生出差分故障攻擊、不可能故障分析、代數故障分析和統(tǒng)計故障分析等分析方法，具備不同的分析優(yōu)勢［6］。目前，故障分析已經成為對密碼進行安全性分析的重要方法。

自從SUNDAE-GIFT 被提出以來，已經有學者利用故障分析研究其安全性。2021 年，Sun 等［7］對SUNDAE-GIFT 進行了17 輪的線性故障分析，成功破譯了128 比特的主密鑰；同年，Liu 等［8］使用碰撞故障分析，僅以128 個錯誤密文恢復密鑰。

2013 年，F(xiàn)uhr 等［6］首次提出了針對AES 密碼算法的統(tǒng)計故障分析；2016 年，Dobraunig 等［9］提出了針對基于隨機數的認證加密算法模式的統(tǒng)計故障分析思想；2017 年，Li 等［10］首次針對輕量級分組算法LED 統(tǒng)計故障分析；2018 年，Ramezanpour 等［11］首次通過統(tǒng)計故障分析對認證加密算法進行安全性分析。本文對SUNDAE-GIFT 進行了統(tǒng)計故障分析，證明了分組密碼工作模式類的認證加密算法存在設計上的安全問題，為輕量級認證加密算法的安全設計提供了重要思路。故障分析的結果對比見表1，表明SUNDAE-GIFT 在故障數方面更具優(yōu)勢。

表1 統(tǒng)計故障分析破譯部分子密鑰的結果對比Tab.1 Comparison of statistical fault analysis on a partial subkey

1 SUNDAE-GIFT 算法

1.1 符號說明

記SC、SC-1為S盒和S盒的逆，PB、PB-1為P置換和P置換的逆，ARK為子密鑰加；

1.2 SUNDAE-GIFT 密碼

SUNDAE-GIFT 是以GIFT-128 為底層密碼的SUNDAE 結構的認證加密算法。輸入包括初始塊B、關聯(lián)數據A、明文M和密鑰K，輸出包含標簽T和密文C，分組長度為128 比特，算法結構如圖1 所示。

圖1 認證加密算法SUNDAE-GIFT 結構Fig.1 The structure of authenticated encryption algorithm SUNDAE-GIFT

GIFT 是一種SPN 結構的輕量級分組密碼。GIFT-128 是其中的一個版本，其密鑰長度為128 位，分組長度為128，輪數為40 輪，每一輪的輪函數包括S盒、P置換和輪密鑰加，算法結構如圖2 所示。

圖2 GIFT-128 算法結構Fig.2 The structure of GIFT-128

1.3 故障模型

本文采取的故障模型是半字節(jié)隨機“與”故障模型，通過在加密過程中的某一輪注入半字節(jié)隨機“與”故障，影響中間狀態(tài)值的分布律產生偏移，而不注入故障的中間狀態(tài)值的分布律呈現(xiàn)均勻分布。半字節(jié)中間狀態(tài)在注入故障后理論分布律如圖3 所示。

圖3 半字節(jié)的理論分布律Fig.3 The theoretical distribution of a nibble

1.4 攻擊步驟

本文使用統(tǒng)計故障分析破譯SUNDAE-GIFT 算法的主密鑰，主要包括以下步驟：

步驟1故障注入。攻擊者在生成密文階段通過在底層密碼GIFT-128 的第39 輪注入隨機“與”故障，使半字節(jié)中間狀態(tài)值的分布律產生偏移，最后故障擴散并生成錯誤標簽，故障擴散路徑如圖4 所示。攻擊者在故障擴散后收集錯誤密文樣本，為后續(xù)的密鑰破譯提供數據基礎。

圖4 SUNDAE-GIFT 的故障擴散路徑Fig.4 Fault diffusion path of SUNDAE-GIFT

步驟2計算中間狀態(tài)值。攻擊者依據公式（1）逆推錯誤標簽樣本集，窮舉最后兩輪子密鑰中的10 比特作為候選密鑰值樣本集，解密計算得出半字節(jié)錯誤中間狀態(tài)樣本集合為

步驟3區(qū)分器選取。攻擊者按照步驟1、2 操作，取得候選密鑰和對應的半字節(jié)錯誤中間狀態(tài)樣本集，并通過區(qū)分器進行統(tǒng)計分析，篩選出實驗分布律最接近理論分布律的半字節(jié)錯誤中間狀態(tài)所對應的密鑰候選值，即正確子密鑰。

步驟4主密鑰恢復。重復步驟1～步驟3，直至破譯RK39和RK40的全部比特。再依據公式（2）和公式（3）中的密鑰編排方案恢復主密鑰。

1.5 區(qū)分器

區(qū)分器主要用于計算樣本集的分布律，利用統(tǒng)計學的知識對樣本集進行分析并篩選出正確密鑰。本文采用Fuhr 等［6］統(tǒng)計故障分析AES 時使用的SEI、HW 和MLE 3 個區(qū)分器對SUNDAE-GIFT 算法進行分析。3 個區(qū)分器對應的公式和選取的極值見表2。

表2 不同區(qū)分器的計算公式和所取極值Tab.2 The formulas and extreme values of different distinguishers

2 實驗分析

本文實驗利用計算機軟件模擬隨機故障導入，使用Java 語言編程進行分析。本文基于成功率、故障數、耗時和復雜度等指標評測不同區(qū)分器和兩種故障分析方法的效果。

2.1 成功率

成功率是指不同區(qū)分器破譯密碼的概率。各個區(qū)分器恢復10 比特子密鑰時，不同故障數對應的成功率如圖5 所示，3 個區(qū)分器均能夠在故障數少于50 時，成功率達到100%。

圖5 不同區(qū)分器恢復部分子密鑰的成功率Fig.5 The probability of recovering a partial sub key with different distinguishers

2.2 故障數

故障數是指不同區(qū)分器以最大概率破譯密碼所需最少故障數。統(tǒng)計故障分析在恢復SUNDAEGIFT 密碼主密鑰時的故障數見表3，SEI、HW 和MLE 3 個區(qū)分器的故障數分別為768、576 和608。

表3 不同區(qū)分器破譯主密鑰的故障數Tab.3 The faults of breaking the master key with different distinguishers

2.3 耗時

耗時是指破譯SUNDAE-GIFT 算法所需要的時間，包括故障導入、密鑰猜測和統(tǒng)計分析等過程。采用各個區(qū)分器恢復子密鑰時，不同故障數對應的時間如圖6 所示。其中，橫軸與縱軸分別表示故障數和時間堆積。當成功率達到最高時，SEI、HW 和MLE 的耗時分別為7.98、5.80 和6.13 s。

圖6 不同區(qū)分器恢復部分子密鑰的耗時Fig.6 The time of recovering a partial subkey with different distinguishers

2.4 復雜度

復雜度是指破譯SUNDAE-GIFT 算法主密鑰所需的時間復雜度和數據復雜度，用于衡量統(tǒng)計故障分析的效率和占用的資源。不同區(qū)分器在破譯SUNDAE-GIFT 時的時間復雜度和數據復雜度見表4，均表現(xiàn)優(yōu)秀，其中F表示故障數，S表示密鑰搜索空間且S ＝210。

表4 不同區(qū)分器破譯主密鑰的復雜度Tab.4 The complexity of breaking the master key with different distinguishers

3 結束語

本文實現(xiàn)了針對SUNDAE-GIFT 認證加密算法的統(tǒng)計故障分析，是首次針對分組密碼工作模式類的認證加密算法的統(tǒng)計故障分析。實驗結果表明，統(tǒng)計故障分析對SUNDAE-GIFT 認證加密密碼具有較大威脅性。在物聯(lián)網中使用SUNDAE-GIFT 時，應考慮對密碼加以更多保護，該結果為輕量級認證加密算法抵御故障分析提供了有價值的參考。