一種針對Saber密鑰封裝機制的側信道攻擊
背景介紹
CHES 2022上，來自南京農業大學李延斌教授的團隊提出了第一種針對Toom-Cook算法的基于軟分析側信道攻擊（SASCA）的單能量跡攻擊方法[1]，并通過優化因子圖、改進置信度傳播（BP）等方式優化攻擊流程，大大增強了攻擊的實用性。
Toom-Cook是一種經典的基于分治思想的多項式乘法算法。自NIST（美國國家標準與技術研究院）的后量子標準化程序開始以來，基于Toom-Cook的多項式乘法算法重新受到關注。作者以基于Toom-Cook乘法實現的密鑰封裝機制Saber為實例，研究后量子密碼在嵌入式密碼設備上的實現安全性。
相關知識
1、Saber中的多項式乘法
在Saber中，密文和密鑰都是255階的多項式，為了方便快捷地求取它們的乘積，采用Toom-Cook-4和二階Karatsuba算法將256*256的多項式乘法轉變為16*16的多項式乘法。
圖1 Saber中的多項式乘法
2、SASCA
SASCA是2014年提出的一種側信道攻擊方法，它將泄露的側信息以類LDPC編碼的形式表示。其攻擊方法可以簡單描述為構建因子圖模型，計算泄露的中間變量的后驗分布概率，然后在算法的整個計算過程中互相傳播分布信息，最終計算得到密鑰的邊緣分布的過程。SASCA結合了模板匹配和BP算法，能夠有效地利用攻擊中的任何泄露。
攻擊及優化方法
1、攻擊方法
對應Saber中的Schoolbook、Karatsuba和Toom-Cook三種乘法，作者分別構建SFG、KFG和TFG三類因子圖。
圖2 三類因子圖
這三類因子圖構成了Saber中的多項式乘法的完整因子圖。
圖3 Saber多項式乘法的完整因子圖
BP算法消息傳遞包括從變量節點到因子節點uxn→fm和從因子節點到變量節點ufm→xn。
從變量到因子的消息傳播：
從因子到變量的消息傳播：
結合構建好的完整因子圖，BP將上述消息規則應用于所有節點，然后通過傳播迭代，得到密鑰的概率分布，這樣就完成了一次完整的攻擊。
2、攻擊優化
（1） 選用漢明重量模型
作者采用漢明重量模型構建模板而不是以所有可能的值作為模板，將原始模板數量從216?144?7降至17?144?7=17136個。
（2） 結合深度學習
作者結合深度學習，建立多層感知機架構MLP，設置隱藏層激活函SeLU、輸出層激活函數Softmax，將能量波形輸入訓練網絡，用中間值的漢明重量作為訓練標簽，輸出概率向量。
（3） 優化因子圖
作者結合Bayes定理計算邊緣概率，將因子圖中的節點歸一化。簡化后的SFG從原有的33個變量節點變為2個，降低了BP的時間和內存復雜性。
圖4 基于Bayes的SFG
（4） 改進BP算法
在KFG中有很多長度為4的循環，且都與因子f5add相連。由于短周期循環十分影響BP算法的性能，因此將與f5add相關的節點與其他節點剝離開，整個環狀BP分為兩個步驟依次執行，以減輕性能下降。
圖4 KFG上的改進BP算法
實驗結果
作者基于Saber的C語言實現進行模擬實驗，證明了上述優化方法的有效性：（1）在成功率相同的情況下，貝葉斯SFG所用時間約為原始SFG時間的1/2甚至更低；（2）改進BP算法的攻擊成功率優于傳統BP算法，同時減少了攻擊時間；（3）基于深度學習的SASCA比傳統模板攻擊的SASCA成功率更高。
進一步地，作者對STM32 Nuncleo-64板上的STM32F103RB（ARM Cortex-M3）電磁輻射控制器進行實際攻擊，驗證了攻擊的實用性。
圖5 實驗設備與電磁波形
結論
作者展示了如何使用SASCA攻擊Saber中的Toom-Cook乘法，并進一步結合深度學習優化攻擊，減少傳統SASCA的模板數量。同時基于貝葉斯定理將因子圖中的節點歸一化，簡化了SFG；改進BP算法，降低因子圖中短周期對BP算法的性能影響，實現了攻擊優化。這些技術對其他執行Toom-Cook算法的密碼方案的安全性研究起到了十分重要的借鑒意義。
