對OCB算法側信道泄漏位置的細粒度分析

背景介紹

在CHES 2022會議上，Berti等人對OCB3算法的側信道泄漏位置進行了細粒度分析，該算法是CAESAR競賽獲勝的算法之一。首先，作者發現可以使用DPA方法對算法中的某些密碼模塊（初始化模塊或相關數據處理）進行攻擊；接著，假設上述描述的密碼模塊受到了保護，此時仍可以對其他的分組密碼模塊進行攻擊，一種方法是使用未知輸入的DPA攻擊，更有效的方法是利用連續加密模塊之間，輸入的白化值的水平關系進行DPA攻擊；最后，作者考慮了當所有的密碼調用塊都受到了保護，但針對線性操作可以進行SPA，進而獲取白化值的信息，并證明恢復白化值會對OCB3算法的機密性和完整性造成威脅^[1]。

OCB3算法

1、OCB3算法結構

圖1為OCB3算法的結構，算法的輸入為消息m，消息分為一些塊ｍ_i分別使用加密塊BC加密生成密文塊。這里使用AES-128初始化BC，故將消息m分為128比特的ｍ_i。

用戶需要輸入nonce使用初始化函數，得到δ₀，然后使用更新函數Inc計算其余的δ_i。每個消息塊ｍ_i在進入BC前，都需異或上δ_i，在經過BC的加密計算后，再次異或δ_i，生成密文塊。對于最后一個密文塊ｍ_l，若ｍ_l是128比特，則按照正常的BC加密，若ｍ_l小于128比特，則需要經過填充的ｍ_l異或BC(δ_l-1⊕l_*)，其中l_*的定義見第2節。對于認證來說，需要使用消息的校驗和生成一個標簽τ，具體的計算過程見圖1中最后一個BC塊的計算。

若對關聯數據進行處理，處理方式與消息的處理方式基本一致，用關聯數據塊代替消息塊。然而，在消息處理的情況下，δ₀的初始化值取決于隨機數的加密；在關聯數據處理的情況下，δ₀的初始化值始終為0。

圖1 OCB3算法結構

2、初始化函數更新函數

初始化函數的主要目的是生成白化值δ₀，算法的主要流程如下圖2所示。該算法主要分成兩個部分，第一部分是通過用戶輸入的nonce值，計算得到中間值top。第二部分是將top輸入到BC塊中，使用密鑰加密得到ktop。

圖2 初始化函數（Init）流程

更新函數的主要算法流程如下圖3所示，其中doule(x)表示在有限域上x的2倍，ntz(x)表示x的二進制表示尾部0的個數。該算法主要分為兩個部分，第一部分計算得到l₀=4_*BC_k(0)，第二部分是使用初始化函數中得到的δ₀，利用公式δ_i=δ_i-1⊕l_nte(i)計算δ_i。

圖3 更新函數（Inc）流程

泄漏分析

1、對無防護的OCB3算法進行側信道攻擊

（1）對OCB算法的初始化函數進行攻擊：

圖2為初始化函數流程，其中ktop=BC_k(top)泄漏了密鑰信息，可以用DPA進行攻擊。在這里為了計算白化值，使用用戶隨機輸入的nonce和密鑰進行加密，其中加密塊的輸入是已知可控隨機的，符合DPA攻擊的條件。

（2）針對關聯數據處理的DPA攻擊：

在對關聯數據處理時，δ₀的初始化值始終為0，則說明第一個BC塊的輸入δ₁始終為固定的數。則可以通過兩步DPA完成攻擊，第一步，攻擊BC塊加密的第一輪，可以得到δ₁⊕k，第二步，攻擊BC塊加密的第二輪，得到第二輪的子密鑰，推導得到密鑰。

2、對安全初始化的OCB3算法進行側信道攻擊

假設在1節中描述的初始化函數中的泄漏被很好的進行了防護，作者仍找了可以進行攻擊的位置，即計算密文需要的加密塊BC，這里的攻擊難度是BC的輸入δi是未知的。

（1）基礎的DPA攻擊

處理這個問題最直觀的想法是將δi當作掩碼值進行處理，選擇兩處攻擊位置。第一處是BC塊的輸入值即δ_i⊕m_i，第二處是第一輪S盒的輸出，可以得到δ_i⊕m_i⊕k。

（2）改進的DPA攻擊

在基礎DPA攻擊中，需要波形條數大大增加，為了降低所需的數據復雜度，提出了改進的DPA攻擊。

由于δ_i=δ_i-1⊕l_net(i)，故BC的輸入可以全部轉換為僅與δ₀相關的輸入，下圖4為轉換結果。又因為一次加密過程中的δ₀是一樣的，故可以將δ₀作為密鑰的一部分，即假設h=δ₀⊕k₀。在將輸入轉換的過程中，會產生多余的值，該部分也應該被猜測，由于l_i=double(l_i-1)，故若增加l₀到l_n，則時間復雜度從2⁸增加至2¹⁶⁺ⁿ。具體的算法流程如下圖5所示。

圖4 BC輸入的轉換結果

圖5 改進的DPA攻擊流程

（3）實驗結果

在ARM Cortex-M0上實現OCB3算法，為了更加精確，作者通過計算中間值得到信噪比SNR的值，以此確認波形中的興趣點。分別使用基礎的DPA攻擊和改進的DPA攻擊，得到如下圖6所示的實驗結果。

其中x軸為需要的波形條數，y軸為攻擊成功的準確率。可以看出，使用基礎的DPA攻擊方法，在攻擊成功率為100%時，大約需要125條波形，而改進的DPA方法，在攻擊成功率為100%時，大約需要10條波形，改進的DPA方法使用的波形數量更少。

圖6 兩種方法進行攻擊的實驗結果

3、對安全加密塊的OCB3算法進行側信道攻擊

當第1、2節所描述的泄漏位置均加以防護之后，即與密鑰相關的計算均加上了防護，此時，無法再通過側信道的方法獲取密鑰的信息。作者證明若得到OCB3算法中的l₀值，會對算法的安全性和機密性造成很大的威脅，具體的證明過程見該論文的6.3、6.4節。此處不再給出詳細證明過程，下面對如何使用側信道的方法獲取l₀值進行介紹。

此時可以利用的泄漏位置是δ_i=δ_i-1⊕l_net(i)和BC_k(input)=δ_i⊕m_i。因為ntz(x)表示x的二進制表示尾部0的個數，故假設當前加密塊為n個，則使用到l₀的次數為n/2，同時利用l₀、l₁…的關系進行SPA，重新組合它們之間的泄漏信息，獲取更加精準的l₀的值，具體的算法流程如下圖7所示。

圖7 使用SPA猜測l₀的流程

總結

本文作者就“OCB中的所有操作都需要保護嗎？如果需要，它們需要相同級別的保護嗎？”的問題展開討論，作者通過展示針對不同保護級別的OCB的幾次攻擊來回答這個問題。首先，作者表明，可以針對初始化函數和關聯數據的處理進行最簡單的DPA攻擊。接下來，假設第一級保護可以防止上述提到的攻擊，作者對用于生成密文塊的加密塊進行了攻擊，可以使用兩種方法，第一種是簡單的將白化值作為掩碼進行二階DPA攻擊，同時還提供了一種改進的（一階）DPA攻擊方法，以更高的（時間）密鑰猜測復雜度為代價，降低了二階攻擊的數據復雜度。最后，作者考慮了這樣一種情況，即所有的分組密碼塊都受到了強有力的保護。作者表明，使用SPA的方法可以得到白化值l₀，該數值的恢復會對OCB3算法的完整性和機密性造成威脅。

參考資料

[1] Berti, F., S. Bhasin, J. Breier, X. Hou, R. Poussier, F.-X. Standaert, and B. Udvarhelyi. “A Finer-Grain Analysis of the Leakage (Non) Resilience of OCB”. IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2022, no. 1, Nov. 2021, pp. 461-8, doi:10.46586/tches.v2022.i1.461-481.