非入侵式攻擊之交叉相關分析原理與實戰

非入侵式攻擊之交叉相關分析原理與實戰

背景介紹

非入侵式攻擊測試利用了隱藏在密碼模塊中或周圍的物理量的有偏性，這種依賴于秘密信息的有偏量被稱為泄露，測試泄露是否存在的測試即為泄露分析。簡單能量分析（Simple Power Analysis，SPA）和差分能量分析（Differential Power Analysis，DPA）都是《GB/T 37092-2018 信息安全技術 密碼模塊安全要求》中規定的非入侵式攻擊測試項。SPA需要直接（例如，通過視覺）分析密碼模塊在執行密碼過程中各指令的能量消耗模式。通過監視密碼模塊能量消耗的變化，可以發現所執行密碼算法的模式和實現方法，從而獲取密鑰值，文獻^[1] 給出了一種Cross-Correlation方法，屬于SPA的代表方法。

一階DPA具有相同的目的，但是為了分析密碼模塊能量消耗的變化，使用了統計方法（例如，均值差、相關系數）對能量消耗進行統計分析，從而獲取密鑰值。文獻^[2]中提出的方法也稱為Cross-Correlation，但這是一種DPA類型的統計分析方法，它源自文獻^[3]的碰撞相關攻擊。本文主要討論這種DPA型的Cross-Correlation。

Cross-Correlation分析^[2]，中文譯為交叉相關分析。根據采集到的能量波形，可執行交叉相關分析來檢索密碼算法指令序列，進行DPA泄露檢測。該功能可以獲得波形中與密鑰信息相關的敏感操作在何處執行的信息，其結果圖也可以幫助測評人員識別針對側信道分析的一些防護對策。

分析原理

在已知加密算法結構的條件下，對采集到的一組不同明文、相同密鑰加密得到的若干條波形進行交叉相關分析時，設定兩個指針沿橫軸滑動，每滑動到一個地方，都計算一下兩個指針所指的兩列波形點之間的相關系數。當滑動位置遍歷所有橫坐標后，兩個指針對應的相關系數可以形成一張二維的圖，命名為交叉相關圖。該實驗圖能夠可視化對齊后的多條波形中不同橫坐標受明文影響的關系，進而有助于幫助我們區分不同操作。在交叉相關圖中，用亮點來表示相關性的強弱。色帶上亮點明顯的位置，相關性比較強，表示一個特定值在運行過程中的多次泄露，這與碰撞攻擊是類似的。我們可以由此對敏感操作進行定位，進而通過識別這些操作來恢復出密鑰。

圖片來源：文獻[2]

功能說明

北京數緣科技有限公司自主研發的側信道分析測評軟件Detector集成了交叉相關分析，該功能的參數設置界面如圖所示。

交叉相關分析控制面板

對話框中的文本框含義如下：

• 起始點、點長度：用于做交叉相關分析的起始采樣點與長度，這部分的參數可以通過選中波形中的一部分進行自動填寫。
• 起始波形：所選處理波形的起始編號。
• 波形條數：所選出來波形的總條數。

通過文本框確定待分析波形段后，點擊“確認”執行交叉相關分析，在窗體下方生成計算出來的交叉相關圖，圖中綠色代表正相關，紅色代表負相關，相關性性越強顏色越亮。消耗時間會通過日志進行顯示。

案例實現

我們基于一款STM32F4系列單片機的開發板實現了無防護的RSA算法，采用數緣科技自主研發的多功能側信道分析儀采集其能量波形。RSA算法的密鑰信息主要落在平方和乘法的操作上，因而可以通過計算交叉相關系數，生成一張交叉相關圖作為可視化結果，以達到定位不同運算操作、恢復密鑰的目的。

多功能側信道分析儀能量分析連線圖

首先需要采集一組符合要求的RSA加密的波形。這里為了有明顯直觀的效果，采集了1000條波形。示例波形如下圖所示。

RSA示例波形

選中待分析的波形段，點擊“確認”執行交叉相關分析，在窗體下方生成了計算得到的交叉相關圖，如下圖所示。取平方對應的Square操作簡稱為S操作，而乘法對應的Mulitiply操作簡稱為M操作，圖中S、M操作都已標出。色帶顏色較亮，且都是表示正相關關系的綠色，說明對應的是取平方的S操作；色帶為紅綠相間，且顏色較暗，說明對應的是乘法的M操作。一個S操作后緊跟一個M操作對應密鑰1，而一個S操作后還是S操作，說明前一個S操作對應密鑰0。由圖可以識別出操作SMSSSMSSSMSSMSMSMSMSMSMSSMSMSSSSSM，對應密鑰1001001011111101100001。

交叉相關圖

適用場景

交叉相關分析的強大之處在于，它能夠有效攻破RSA算法的多種防護對策。其一，是Multiply-Always，也就是添加偽操作。該措施具體執行時，逐比特掃描密鑰，當密鑰為0時，執行完取平方操作后再乘以底數（或隨機數），但是將計算結果丟棄不用。也就是說，再掃描下一比特的密鑰時，不使用乘以底數之后的值，而是使用取平方操作后、乘以底數之前的值，因此乘以底數這個偽操作并不影響加密結果，只是使掃描每一比特密鑰時都有一個取平方操作和一個乘法操作。其二則是掩碼，當模冪運算的底數或模數被隨機掩碼掩蓋時，交叉相關分析仍然有效，因為它關心的是兩處泄露的值是否總是相同，只要二者相同，哪怕被相同的隨機掩碼掩蓋住，這種“相同泄露值”的情況仍然能被發現。

交叉相關分析可適用于添加防護對策的RSA算法加密。以兩種泄露情況為例：

第一種情況：這種情況下交叉相關分析利用的是：真正的乘法操作因為都需要調用明文而產生了相關性。如果是正常的乘法操作，同一條波上的多個乘法操作都需要調用到相同的明文，這些乘法操作之間具有相關性；而乘以一個隨機數的偽操作沒有調用明文，因此不具有相關性。以此可以區分哪些乘法操作是模冪運算的一部分，而哪些乘法操作只是偽操作。

如下圖所示，首先，同一操作之間的較強的相關關系，在圖中以白色方塊表示；對于正常的乘法操作，也就是圖中白色的M操作，都需要調用到相同的明文，它們之間存在相關性，在圖中以橘色的方塊表示。若當前操作為偽操作，在圖中以紅色的M操作表示，乘數是一個隨機數而不是明文，那么該操作與正常的乘法操作之間不具有相關性，在圖中仍是黑色的方塊。

第一種情況交叉相關圖

第二種情況：這種情況下交叉相關分析利用的是：前一個操作的輸出結果可能是后一個操作的輸入內容。如果是正常的操作，那么前一個操作的輸出結果就是后一個操作的輸入內容，前一個操作與后一個操作之間因為調用了同一個值，會產生相關性；如果當前的乘法操作為偽操作，乘以一個隨機數之后就將該計算結果丟棄，那么下一操作的輸入并不是該操作的輸出，而是上一操作的輸出，所以下一個操作會與上一個操作之間，也就是與偽操作相鄰的兩個取平方操作之間具有相關性。

如圖所示，同樣地，同一操作之間的較強的相關關系，在圖中以白色方塊表示；對于正常的操作，也就是圖中白色的S、M操作，后一個操作的輸入是前一個操作的輸出，故前后兩個相鄰的操作之間存在相關性，在圖中以黃色的方塊表示。若是當前操作為偽操作，在圖中以紅色的M操作表示，乘以一個隨機數之后就將該計算結果丟棄，那么與偽操作相鄰的兩個取平方操作之間具有相關性，在圖中以橘色方塊表示。

第二種情況交叉相關圖

參考資料

[1] Thomas S. Messerges, Ezzy A. Dabbish, Robert H. Sloan. Power Analysis Attacks of Modular Exponentiation in Smartcards. CHES 1999, LNCS 1717, pp. 144?157, 1999.

[2] Marc F. Witteman, Jasper G.J. van Woudenberg, Federico Menarini. Defeating RSA Multiply-Always and Message Blinding Countermeasures. CT-RSA 2011, LNCS 6558, pp. 77-88, 2011.

[3] Christophe Clavier, Benoit Feix, Georges Gagnerot, Myl`ene Roussellet, and Vincent Verneuil. Improved Collision-Correlation Power Analysis on First Order Protected AES. CHES 2011, LNCS 6917, pp. 49-62, 2011.