輕量級密碼算法TWINE 的唯密文故障分析

李瑋，汪夢林，谷大武，李嘉耀，蔡天培，徐光偉

（1.東華大學計算機科學與技術學院，上海 201620；2.上海交通大學計算機科學與工程系，上海 200204；3.上海交通大學上海市可擴展計算與系統重點實驗室，上海 200204；4.上海交通大學上海市信息安全綜合管理技術研究重點實驗室，上海 200093）

1 引言

物聯網是一種物與物進行信息交換和通信的網絡。它通過智能設備和機器感知收集有關數據，提取數據中有用的信息并提供方便快捷的服務。物聯網的發展促進了大量新興領域的發展，例如智能家居、智慧醫療、精準農業、智慧交通等[1-4]。由于物聯網中的智能設備及傳感器的處理、存儲資源有限，在收集、傳送和處理網絡中的大量數據時，傳統的密碼算法較難有效地保證信息的機密性、完整性和認證性，因此，運行效率高、吞吐量小和安全性高的輕量級密碼算法適用于物聯網中的安全數據處理[5-7]。

TWINE 是2012 年在SAC（selected areas in cryptography）會議上提出的一種具有廣義Feistel結構的輕量級分組密碼，旨在保護資源受限的終端設備的數據安全[8]。現有的TWINE 的傳統密碼分析包括不可能差分故障分析、飽和分析、Biclique分析、零相關線性分析、中間相遇分析等[8-11]。但是，在物聯網環境中，攻擊者可以通過激光照射、異常時鐘、渦流磁場等方式注入故障，干擾密碼的加密過程，這些故障會使中間狀態的計算產生偏差，通過分析或者統計錯誤中間狀態即可恢復密鑰并破譯密碼，這種攻擊方法稱為故障分析（FA,fault analysis）。

故障分析是在1997 年由Boneh 等[12]提出的一種密碼分析方法，它通過在密碼設備運行過程中注入隨機的故障，干擾正常運行過程，從而恢復出密鑰并破譯密碼。后來，故障分析衍生出差分故障分析（DFA,differential fault analysis）、不可能差分故障分析（IDFA,impossible differential fault analysis）、中間相遇故障分析（MFA,meet-in-the-middle fault analysis）、統計故障分析（SFA,statistical fault analysis）和唯密文故障分析（CFA,ciphertext-only fault analysis）等[13-17]。這些分析方法是輕量級安全密碼實現的重要實際威脅之一。

根據攻擊能力的強弱，密碼分析方法的攻擊假設可以分為選擇明文攻擊（CPA,chosen-plaintext attack）、已知明文攻擊（KPA,known-plaintext attack）和唯密文攻擊（COA,ciphertext-only attack）等。針對TWINE 的傳統密碼分析、現有故障分析的攻擊假設主要集中在已知明文攻擊和選擇明文攻擊，即攻擊者需要獲取當前密鑰下的一些明文密文對，或特定明文對應的密文，這對攻擊者的能力要求較強。在資源受限的物聯網環境中，唯密文攻擊對攻擊者的能力要求最弱，攻擊者僅需獲取密文，因此容易在實際中應用，并可以有效地檢測密碼算法的實現安全性。

基于唯密文攻擊的攻擊假設，唯密文故障分析通過密碼設備運行過程中注入隨機故障，利用錯誤密文推導出的中間狀態，分析相關的統計信息，在僅獲得錯誤密文的情況下即可破譯密碼。TWINE作為廣義Feistel 結構的典型密碼之一，目前國內外都沒有針對該密碼的唯密文故障分析的相關研究，本文提出了針對TWINE 的新型唯密文故障分析方法，設計并實現了3 種新型區分器，從而降低了攻擊代價，有效地提高了攻擊效率。該方法的提出對于分析輕量級密碼算法的安全性具有參考價值，同時對于增強物聯網中信息的保護具有現實意義。

2 相關工作

密碼分析是評測密碼算法安全性的重要手段，國內外學者使用多種密碼分析技術對TWINE 進行了安全性分析。在傳統密碼分析方面，TWINE 的設計者分別利用不可能差分分析、飽和分析等對TWINE 的安全性進行評估[8]。2012 年，?oban 等[9]使用Biclique 構造和中間相遇分析搜索密鑰，對TWINE 進行了Biclique 分析。2014 年，Wang 等[10]使用改進的零相關線性分析檢驗TWINE 的安全性，利用密鑰編排方法的弱點并使用部分壓縮技術降低了零相關線性分析的計算復雜度。2016 年，Tolba 等[11]利用廣義中間相遇攻擊，通過允許將密鑰劃分為3 個子集來消除中間相遇攻擊的限制，實現對TWINE 的全密碼攻擊。以上攻擊的假設均為選擇明文攻擊或者已知明文攻擊。

在故障分析方面，2013 年，Yoshikawa 等[18]提出了差分故障分析，利用與同一明文相對應的一個正確密文和不同輪注入故障產生的錯誤密文，恢復了TWINE 的80 bit 主密鑰。2015 年，Li 等[19]對TWINE 進行了差分故障分析，在31 輪利用故障模型“與”導入半字節故障，分別利用8 個和18 個故障恢復了TWINE 的80 bit 和128 bit 主密鑰。2017 年，高楊等[20]利用S 盒的差分分布特性進行差分故障分析，采用隨機半字節模型，在33 輪、34 輪、35 輪平均注入9 個故障，即可恢復TWINE 的80 bit 主密鑰。此外，Nozaki 等[16]使用統計故障分析，通過在時鐘中插入毛刺產生故障，統計40 對正確密文和錯誤密文對應的中間狀態的漢明權重最小平均值，恢復了TWINE 的80 bit主密鑰。現有的故障分析方法都是選擇明文攻擊的假設。

本文結合唯密文攻擊的假設，對TWINE 密碼進行了唯密文故障分析。此時攻擊者僅依賴錯誤密文，攻擊能力最弱，因此，唯密文故障分析的分析方案在現實的操作環境中具有更加靈活的應用前景。TWINE-80 和TWINE-128 的安全性分析對比如表1 所示。

表1 TWINE-80 和TWINE-128 的安全性分析對比

在唯密文故障分析方面，2013 年，Fuhr 等[17]針對AES（advanced encryption standard）進行了唯密文故障分析，利用“與”故障模型，誘導隨機字節故障生成錯誤密文，接著推導出對應的錯誤中間狀態，利用平方歐氏距離（SEI，square Euclidean distance）、極大似然估計（MLE，maximum likelihood estimate）和漢明權重（HW，Hamming weight）等區分器篩選密鑰候選值。實驗結果表明，對于區分器SEI、MLE 和HW，分別導入320、224 和288 個隨機字節故障就可以恢復AES 的子密鑰。2016 年，Dobraunig 等[21]提出，攻擊者可以在基于AES 的認證加密算法中注入故障進行破譯。文獻[22-24]采用唯密文故障分析的方法分別對輕量級密碼算法LED（light encryption device）、SIMON 和MIBS等進行安全性分析，擴展了唯密文故障分析的范圍。然而，對于具有廣義Feistel 結構的TWINE能否抵御唯密文故障分析，國內外尚無文獻發表。

本文給出了TWINE 的新型唯密文故障分析，提出了新型區分器極大似然估計-直方圖估計（MLE-HE，maximum likelihood estimate-histogram estimate）、漢明權重-直方圖估計（HW-HE，Hamming weight-histogram estimate）和漢明權重-極大似然估計-直方圖估計（HW-MLE-HE，maximum likelihood estimate-hamming weighthistogram estimate）等區分器，不僅減少了故障數，而且提高了分析效率。唯密文故障分析破譯AES、LED、SIMON、MIBS 和TWINE 子密鑰的結果對比如表2 所示。

3 TWINE 密碼介紹

3.1 術語說明

記X∈({0,1}4)16為明文，Y∈({0,1}4)16為正確密文，∈{0,1}4表示第i輪中輸入的第j個半字節，其中，i∈[1,36]且j∈[0,15]。

記K為主密鑰，k l為主密鑰的第l個半字節，z表示主密鑰半字節個數，∈{0,1}4表示第i輪子密鑰的第t個半字節，為第i輪密鑰編排時的輪常數，其中，H 表示高4 位，L表示低4 位，z∈{19,31}，l∈[0,z]，i∈[1,36]且t∈[0,7]。

記F為輪函數，S為混淆層，π為擴散層。

記～為導入故障后的錯誤值，＜＜＜為循環左移，||為級聯。

3.2 TWINE 描述

TWINE的分組長度為64 bit，主密鑰長度為80 bit或 128 bit，分別表示為 TWINE-80 版本和TWINE-128 版本，迭代輪數為36 輪，TWINE 結構如圖1 所示。加密部分和解密部分的結構相同，子密鑰的使用順序相反。算法1～算法3 分別給出了TWINE 的加密算法和不同版本的密鑰編排方案。

表2 唯密文故障分析破譯AES、LED、SIMON、MIBS 和TWINE 子密鑰的結果對比

算法1TWINE 的加密算法

4 唯密文故障分析

4.1 基本假設和故障模型

唯密文故障分析的基本假設是唯密文攻擊，此時，攻擊者可以使用相同主密鑰對隨機明文進行加密，運行過程中導入隨機故障獲取相應的錯誤密文；再利用故障導入前后對應的中間狀態分布的偏離，從而破譯密碼。根據TWINE 的數據單元，本文采用了隨機半字節的“與”故障模型，即

其中，表示第i輪的第j個半字節中間狀態值，i∈[1,36]且j∈[0,15]，表示對應的錯誤中間狀態值，e表示隨機半字節故障且e∈[0,15]，&表示按位“與”操作。半字節被影響后的分布規律如圖2所示。在具體實現時，軟件通過結合中間狀態與隨機半字節故障，進行“與”代碼操作實現，硬件通過外部時鐘信號注入毛刺實現[25]。

圖1 TWINE 結構

圖2 半字節被影響后的分布規律

4.2 攻擊步驟

針對TWINE 密碼的唯密文故障分析包括以下3 個步驟。

步驟1故障注入。攻擊者使用相同主密鑰對隨機明文進行加密，在加密運行過程中注入指定輪的隨機半字節故障，并獲取相應的錯誤密文。圖3給出了半字節故障注入第33 輪隨機位置時的故障擴散路徑，以故障位置在首個半字節為例。

圖3 半字節故障注入第33 輪隨機位置時的故障擴散路徑

步驟3破譯主密鑰。利用RK36解密最后一輪，獲得第35 輪的輸出，將故障注入第32 輪，同理可恢復出倒數第二輪子密鑰RK35。依次類推，破譯TWINE-80 版本主密鑰K，最少需要3 輪子密鑰RK36、RK35和RK34，過程如下。

破譯TWINE-128 版本主密鑰K，最少需要5 輪子密鑰RK36、RK35、RK34、RK33和RK32，過程如下。

4.3 區分器

4.3.1 已有區分器

1) SEI

SEI 由Fuhr 等[17]提出，用于計算實際分布與均勻分布之間的距離。在錯誤中間狀態呈現不均勻分布時，若密鑰候選值對應的錯誤中間狀態的SEI值越大，則錯誤中間狀態的實際分布與均勻分布距離越大。此時，SEI 最大值對應于正確的子密鑰。SEI 表示為

其中，T表示半字節所有可能取值的個數，N表示與密鑰候選值相對應的一組錯誤中間狀態個數，ρ(ε)表示錯誤中間狀態值為ε的個數，T=24且ε∈[0,15]。

2) MLE

MLE 由Fuhr 等[17]提出，適用于已知錯誤中間狀態的理論分布率的情況，如圖2 所示。將每個錯誤中間狀態的理論分布率相乘，計算與密鑰候選值對應的錯誤中間狀態發生的概率。此時，MLE 值越大，表示錯誤中間狀態實際分布滿足理論分布的可能性越大，即MLE 最大值對應于正確的子密鑰。MLE 表示為

其中，P()表示錯誤中間狀態值的理論概率，N表示與密鑰候選值相對應的錯誤中間狀態個數。

3) HW

HW 由Fuhr 等[17]提出，用于計算錯誤中間狀態與相同長度的零字符串之間的漢明距離，其值等于錯誤中間狀態的非零個數。密鑰候選值對應的錯誤中間狀態的HW 值越小，表示錯誤中間狀態的零個數越多。此時，HW 最小值對應于正確的子密鑰。HW 表示為

4) GF GF 用于測量實際分布與理論分布之間的擬合度[22]。密鑰候選值對應的錯誤中間狀態的GF 值越小，表示錯誤中間狀態實際分布與理論分布之間的差異越小，即擬合度越大。此時，GF 的最小值對應于正確的子密鑰。GF 表示為

其中，T表示半字節所有可能取值的個數，ρ(ε)表示錯誤中間狀態值為ε的個數，γ(ε)表示理論上錯誤中間狀態值為ε的個數，T=24且ε∈[0,15]。

5) GF-SEI

GF-SEI 結合了GF 和SEI[22]。首先，攻擊者使用GF 過濾掉不符合理論分布的密鑰候選值，滿足

其中，表示從χ2分布上側分位數表中查找的具有確定精度α的GF 臨界值，λ表示篩選后的密鑰候選值。然后，攻擊者使用SEI 過濾保留的密鑰候選值λ，滿足

對于GF-SEI，正確的子密鑰所對應的錯誤中間狀態具有最小的GF 值和最大的SEI 值。

6) GF-MLE

GF-MLE 是由GF 和MLE 組合的雙重區分器[23]。攻擊者首先利用GF 區分器篩選出與密鑰候選值對應的錯誤中間狀態，保留符合理論分布的錯誤中間狀態，滿足

然后，攻擊者使用MLE 選擇使似然函數最大化的錯誤中間狀態所對應的密鑰候選值，滿足

對于GF-MLE，正確的子密鑰所對應的錯誤中間狀態具有最小的GF 值和最大的MLE 值。

7) Parzen-HW

Parzen-HW 結合了Parzen 和HW 的優點[24]。首先，使用Parzen 進行無參估計，縮小密鑰候選值的搜索空間。Parzen 的值越大，表示區域內樣本數越多即對應可能的密鑰候選值。Parzen 滿足

其中，f(u)是窗函數，表示以為中心，窗寬為h的區域內樣本數量，N表示與密鑰候選值對應的錯誤中間狀態個數。然后，攻擊者使用HW 對可能的密鑰候選值進行篩選，滿足

對于Parzen-HW，正確的子密鑰所對應的錯誤中間狀態具有最大的Parzen 值和最小的HW 值。

4.3.2 新型區分器

1) MLE-HE

直方圖估計（HE,histogram estimate）以直方圖法作為基礎來計算密鑰候選值的概率密度。由圖2 可知，值較小的半字節出現概率較高，因此錯誤中間狀態值的理論個數累加和占比越大，表示其出現較小半字節的次數越多，即對應正確的子密鑰，HE 表達式為

其中，N表示與密鑰候選值相對應的錯誤中間狀態個數，M表示所有密鑰候選值的個數，h()表示錯誤中間狀態的理論個數。

MLE-HE 結合了MLE 和HE 這2 種統計方法。首先，攻擊者使用MLE 統計錯誤中間狀態，篩選出部分可能的密鑰候選值，滿足

然后，攻擊者使用HE 進一步篩選。對于MLE-HE，當錯誤中間狀態同時具有最大的MLE值和HE 值，即該錯誤中間狀態的分布滿足理論分布且具有最大的概率密度時，則對應正確子密鑰。

2) HW-HE

HW-HE 結合了HW 和HE 的優點，能夠提高唯密文故障分析的效率。首先，攻擊者使用HW 篩選出具有較小漢明距離的錯誤中間狀態，滿足

然后，攻擊者使用HE 進一步篩選，概率密度最大的一組中間狀態對應正確的子密鑰，滿足

對于HW-HE，基于按位“與”操作，半字節中出現0、1 的比例為3:1。當一組錯誤中間狀態同時具有最小的HW 值和最大的HE 值時，則這組錯誤中間狀態的0 和1 比例最大，因而最接近圖2 的理論分布，那么該錯誤中間狀態對應正確子密鑰。

3) HW-MLE-HE

HW-MLE-HE 是在MLE-HE 和HW-HE 基礎上的改進。首先，攻擊者使用HW 縮小密鑰候選值的搜索空間，滿足

然后，攻擊者利用MLE 進一步統計密鑰候選值對應的錯誤中間狀態，選擇似然函數值較大的錯誤中間狀態，滿足

最后，攻擊者使用HE 在剩余的密鑰候選值中進行篩選、驗證，確定唯一正確的子密鑰。滿足

對于HW-MLE-HE，在篩選過程中，攻擊者選擇漢明權重較小的若干組錯誤中間狀態，再比較各組錯誤中間狀態的極大似然估計值，保留具有最大值的錯誤中間狀態，其對應的密鑰候選值中可能包含正確子密鑰。為了保證所篩選的密鑰的正確性和唯一性，利用HE 比較各組錯誤中間狀態的概率密度，具有最大值的錯誤中間狀態與圖2 的理論分布最接近，即對應正確子密鑰。所有區分器的對比如表3 所示。

5 實驗分析

本實驗采用Java 語言編程，利用計算機軟件來模擬故障產生和注入，在密碼算法運行過程中注入半字節故障。以TWINE-128 版本為例，唯密文故障分析每次恢復子密鑰的16 bit，重復4 次，即可恢復最后一輪子密鑰，依次類推，恢復最后5 輪子密鑰，即可推導出128 bit 主密鑰。在故障數、準確度、耗時和復雜度指標上，恢復TWINE 各版本的主密鑰與恢復子密鑰的16 bit 具有固定的比例關系。本節以恢復子密鑰的16 bit 的實驗數據為單元，計算衡量各區分器分析TWINE 各版本的效果。附錄1 給出了所有實驗數據。

5.1 故障數

故障數指破譯密碼主密鑰或子密鑰時，所需要注入的故障個數。在相同的成功率下，破譯密碼所需要的故障數越少，表明攻擊代價越少。圖4 給出了不同區分器恢復TWINE 子密鑰的16 bit 的故障數與成功率之間的關系。其中，橫坐標表示故障數，縱坐標表示成功率，不同曲線表示不同區分器唯密文故障分析的結果。以TWINE-128 版本為例，利用區分器SEI、MLE、HW、GF、GF-SEI、GF-MLE、Parzen-HW、MLE-HE、HW-HE 和HW-MLE-HE以至少99%的成功率恢復子密鑰，最少需要注入的故障數為236、144、148、224、216、216、180、132、128 和124。與已有區分器相比，本文提出的 3 種新型區分器 MLE-HE、HW-HE 和HW-MLE-HE 需要的故障數較少，攻擊效率高。此時，HW-MLE-HE 具有最少故障數。

表3 區分器對比

圖4 不同區分器恢復TWINE 子密鑰的16 bit 故障數與的成功率的關系

5.2 準確度

準確度用于衡量各區分器篩選出的密鑰候選值個數與理論值個數之間的差距。本節使用平均絕對誤差（MAE,mean absolute error）來衡量各個區分器的準確度。MAE 表示為

其中，V=1000表示實驗次數，Q v表示第v次實驗篩選出的候選值個數，第v次實驗理論候選值個數為1。MAE 值越小，表示實驗準確度越高。圖5 給出了不同區分器恢復TWINE 子密鑰的16 bit 的故障數與MAE 的關系。在相同故障數下，MLE-HE、HW-HE 和HW-MLE-HE 的MAE 值小于已有區分器的MAE 值，且快速逼近于0，此時，HW-MLE-HE具有最小MAE 值。

5.3 耗時

耗時是指恢復密鑰所花費的時間，包括導入故障、遍歷候選密鑰和統計中間狀態所消耗的時間。圖6 給出了不同區分器恢復TWINE 子密鑰的16 bit的故障數與耗時之間的關系，其中橫坐標表示故障數，縱坐標表示耗時，不同的曲線表示不同區分器。以TWINE-128 版本為例，利用區分器SEI、MLE、HW、GF、GF-SEI、GF-MLE、Parzen-HW、MLE-HE、HW-HE 和HW-MLE-HE 恢復子密鑰最少需要的時間分別為11.6 s、14 s、7.2 s、14 s、13.6 s、16.8 s、9.6 s、14.4 s、7.2 s 和8.4 s。此時，HW 和HW-HE 耗時最少，HW-MLE-HE 次之。

圖5 各區分器恢復TWINE 子密鑰的16 bit 的故障數與MAE 的關系

圖6 各區分器恢復TWINE 子密鑰的16 bit 的故障數與耗時的關系

5.4 復雜度

時間復雜度和數據復雜度用于衡量破譯密碼時所需要的時間量和數據量。表4 給出了不同區分器恢復TWINE 子密鑰的時間復雜度和數據復雜度。新型區分器MLE-HE、HW-HE 和HW-MLE-HE的復雜度均小于現有區分器的復雜度，其中HW-MLE-HE 的復雜度最小。

本節采用故障數、準確度、耗時和復雜度等指標衡量各個區分器對TWINE 密碼進行唯密文故障分析的效果。從圖4～圖6 和表4 可以看出，新型區分器MLE-HE、HW-HE 和HW-MLE-HE均有效減少了故障數，成功率達到99%及以上，其中，HW-MLE-HE 所需要的故障數較少、準確度較高、復雜度較小；HW-HE 和HW-MLE-HE耗時較少。一般情況下，故障數是衡量唯密文故障攻擊的首要標準。因此，在資源受限的物聯網環境下，建議采用HW-MLE-HE 對TWINE 密碼進行唯密文故障分析，可以達到相對較好的攻擊效果。

表4 不同區分器恢復TWINE 子密鑰的復雜度

6 結束語

本文針對TWINE 密碼抵抗唯密文故障分析的安全性進行了研究，提出的新型區分器MLE-HE、HW-HE 和HW-MLE-HE，均可以減少攻擊所需的故障數，并提高攻擊效率。研究表明，TWINE 密碼易受到唯密文故障分析的威脅，在物聯網中使用該密碼時，設計人員需采取有效措施用于抵御唯密文故障分析的攻擊。

附錄1 實驗數據

明文：隨機生成

TWINE-80 版本主密鑰：00112233445566778899

TWINE-128 版本主密鑰：00112233445566778899AABBCCDDEEFF

本文中所有實驗數據如表5～表7 所示。

表5 各區分器恢復TWINE-80 和TWINE-128 子密鑰的16 bit 的MAE 值

表6 各區分器恢復TWINE-80 和TWINE-128 子密鑰的16 bit 的成功概率

（續表6）

表7 各區分器恢復TWINE-80 和TWINE-128 子密鑰的16 bit 的時間

（續表7）