針對流密碼的側信道攻擊

狀態或密鑰恢復的三步方法

背景介紹

對稱密鑰密碼學是保證當今通信安全的基石之一，且對稱密鑰密碼通常比非對稱密鑰密碼效率更高，因此，只要通信協議允許，使用對稱密鑰密碼會更好。而側信道攻擊是針對對稱密碼安全性的一個重要手段，已經引起了密碼學領域的高度關注。但是，分組密碼(和類似的結構)似乎一直都是人們關注的焦點，而對稱密碼的另一個主要分支——流密碼(和類似結構)，卻沒有被充分分析。

本文在CHES 2021破解LFSR方法（DAPA）的基礎上，提出了一種通用的恢復流密碼狀態或密鑰的自動化框架工具并開源^[1]。

攻擊方法

本文主要用到的技術包括MLP、MILP（Mixed Integer Linear Programming）以及SMT（Satisfiability Modulo Theory）。攻擊方法如下圖所示：

圖1 攻擊方法流程圖

本文攻擊方法主要包括Offline及Online兩個階段，其中Offline階段包括：

• 得到分好類的波形；
• 對ML進行訓練；
• 測試SMT(可滿足性模理論)得到容忍度ε。

其中Online階段包括：

• 用訓練好的ML進行分類；
• 增加錯誤容忍度ε；
• MILP加約束修正；
• 用SMT返回猜測的中間狀態或密鑰。

1、ML分類

圖2為錯誤容忍ε的大小與ML的準確率及SMT求解時間的關系。可見，隨著錯誤容忍ε越來越大，ML的準確率越來越高，但SMT的求解時間也越來越大，甚至到最后會無法接受，故需要選擇合適的錯誤容忍ε。

圖2 錯誤容忍ε的大小與ML的準確率及SMT求解時間的關系

2、MILP修正

經過訓練好的ML對波形進行分類后，若直接輸入到SMT中進行求解，求解時間依舊會很長，甚至會出錯，此時，本文通過先將波形分類進行MILP修正，再輸入到SMT中，大大減小了求解時間，并提高了正確率。

其中，MILP修正具體參考了一些限制準則，如：

（1）HW的變化；

（2）運算塊之間的相互作用。

此外，寄存器變化上下限、Block變化上下限以及2個塊之間的變化限制都可以作為MILP修正的依據對波形分類進行修正。

3、SMT求解預測

SMT求解預測流程如下圖3所示:

圖3 錯誤容忍ε的大小與ML的準確率及SMT求解時間的關系

實驗

本文針對國際標準流密碼算法TRIVIUM對上述方法平臺進行了實驗驗證，實現對象為Arduino開發板上的ARM Cortex M3 32-bits，并利用網格SNR的方法采集了SNR最高地方的電磁信息(使用了Riscure探頭、Lecroy示波器)。其中ML選擇了MLP模型，共使用了2362000條波，MILP采用的是Gurobi，SMT采用的是Z3。

其中一次實驗結果如下圖所示，通過平均時間可見方法效率很高：

圖4 實驗結果

總結

本文設計并實現了一個實用的框架，針對流密碼或相關結構的密碼算法，從側信道信息(功率或EM)來恢復狀態/密鑰。本文的框架能夠攻擊初始化階段(即在密碼到達偽隨機階段之前)，更重要的是，甚至在密碼到達偽隨機階段之后也能攻擊生成密鑰流。本文還通過在32位軟件平臺上實現流密碼TRIVIUM算法，并進行電磁分析，證明了框架的有效性。

參考資料

[1] Satyam Kumar, Vishnu Asutosh Dasu, Anubhab Baksi, Santanu Sarkar, Dirmanto Jap, Jakub Breier, Shivam Bhasin:Side Channel Attack On Stream Ciphers: A Three-Step Approach To State/Key Recovery. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022(2)CCF none: 166-191 (2022)