針對密碼算法的高階DPA攻擊方法研究

趙東艷，何 軍

（北京南瑞智芯微電子科技有限公司，北京 100192）

近幾年來，針對密碼算法的DPA攻擊得到越來越多的關注。通過對設備的功耗進行分析發(fā)現，密碼設備在執(zhí)行相同指令的情況下，功耗與參與運算的密鑰有一定的關系。攻擊者利用這種關系對采集到的能量跡進行DPA攻擊，可以分析出密鑰[1-3]。

為了防御DPA攻擊，一種有效的技術是對參與運算的數據進行隨機掩碼，也稱為信息盲化[4]。加了掩碼的數據在進行密碼運算時，包含密鑰信息的中間數據被掩碼保護起來，因此能夠抵抗一階DPA攻擊。然而這種防御技術仍然可以用高階DPA進行攻擊。相對一階DPA攻擊來說，高階DPA需要攻擊者了解更多的算法實現細節(jié)，并且需要選擇恰當的攻擊模型，所以攻擊過程也比一階DPA復雜得多。

1 能量泄露模型和DPA攻擊原理

1.1 能量泄露模型

設備的功耗可以通過在設備的GND管腳和地之間插入一個電阻，然后用示波器測量電阻兩端的電壓變化來獲得。為了建立能量泄露模型，用P[t]表示設備在特定t時刻的功耗。P[t]可以分成兩部分，第一部分是與運算相關的功耗d[t]，第二部分是所有與運算無關的功耗n，包括常量部分以及各種噪聲。因此P[t]可以表示為[5]：

其中a是刻畫d[t]對P[t]貢獻度的常量系數。

在指令相同的情況下，與運算相關的功耗d[t]可以用中間數據的漢明重量表示，即：

其中D是密碼算法在t時刻的中間值。

根據式(1)、式(2)，設備的能量泄露模型可以表示為：

如果D是均勻分布的隨機變量，長度為m位，則W[D]的期望為μW=m/2、方差為σW2=m/4。在統計學理論上，引入功耗P和漢明重量之間的相關系數ρPW來表示上述線性模型的匹配度：

如果在m位中僅s位是可預測的，則功耗和漢明重量之間的偏相關系數為：

上述相關系數在中間值漢明重量完全正確時達到最大值。

1.2 DPA攻擊原理

DPA的攻擊理論正是利用功耗與中間值之的相關性，對密碼算法的一小段子密鑰進行窮舉，然后計算在該假設密鑰下中間值漢明重量W′和功耗P之間的相關系數。當相關系數達到最大值時，可以推斷出假設的子密鑰為正確密鑰。中間值漢明重量和功耗之間的相關系數計算如下：

1.3 高階DPA攻擊

1.3.1 高階DPA攻擊原理

高階DPA攻擊的思想是在進行DPA攻擊時，同時考慮一條能量跡曲線上的k個點。這k個點對應了k個不同的中間值，應用組合函數將k個中間值組合成一個中間值，然后對新生成的中間值進行DPA攻擊，這種攻擊稱為 k階 DPA攻擊[6]。

1.3.2 高階DPA攻擊的組合函數

組合函數的選擇已有相關文獻進行過討論[6]。常見的組合函數包括乘積函數、絕對差函數以及和平方函數等。對于二階DPA攻擊來說，乘積函數計算兩點之積，即 comp(tx，ty)=tx·ty；絕對差函數計算兩點之差的絕對值，即comp(tx，ty)=|tx-ty|；和平方函數計算兩點之和的平方，comp(tx，ty)=(tx+ty)2。

在二階DPA攻擊中，假設被攻擊的設備采用布爾掩碼，組合假設中間值為ξ＝ξ1⊕ξ2。如果設備泄露漢明重量，可以采用漢明重量模型將組合假設中間值映射為假設功耗值：

分別用 HW(ξ1)和 HW(ξ2)代表能量跡上 tx和 ty兩點的真實功耗，兩點的真實功耗通過組合函數生成組合功耗P：

由此可以計算出假設功耗值和組合功耗之間的相關系數：

比較相關系數在不同組合函數以及不同中間值位數情況下的差異，可以確定各種組合函數的優(yōu)劣。

從表1可以看出，在泄露漢明重量的情況下，使用絕對差組合函數能達到更好的效果。

2 掩碼技術和高階DPA攻擊

2.1 掩碼技術原理

掩碼技術的核心思想是使密碼設備的功耗不依賴于設備所執(zhí)行的密碼算法的中間值。掩碼技術通過隨機化密碼設備所處理的中間值來實現這個目標。掩碼方案可以用下式來表示：

表1 不同情況下的相關系數

其中ξ表示密碼運算過程中的中間值；m是掩碼，通常是一個內部產生的隨機數；ξm是經過掩碼的掩碼中間值；運算*通常根據密碼算法所使用的操作進行定義，一般為布爾“異或”運算、模加運算或者模乘運算。

2.2 DES掩碼方案

下面介紹一種經典的DES變形掩碼方案[4]。在算法開始時，消息通過64 bit的隨機數使用布爾“異或”運算進行掩碼。該掩碼方案的關鍵是在每輪開始都帶上X1的掩碼，為了實現這個目標，掩碼方案對S盒進行了修改。修改后的S盒滿足以下輸入輸出關系：

其中P-1表示P置換的逆過程。掩碼方案在最后的FP置換之前，將結果“異或”X，消除掩碼得到正確的加密結果。計算過程如圖1所示。

圖1 變形掩碼方案運算過程

2.3 變形掩碼方案的高階DPA攻擊

在上述掩碼方案中，整個加密過程每個中間值都帶著掩碼，因此可以抵抗一階DPA攻擊。掩碼方案為了保證每輪運算的結構相同，在輪運算結束時通過非線性的SBOX變換將掩碼重新設置為每輪開始的的掩碼值X132-63。

根據高階DPA攻擊的原理，可以選擇第一輪開始和結束的中間值作為攻擊對象，將兩點“異或”后得到不帶掩碼的中間值ξ=R0⊕R1=L0⊕R0⊕P(SBox(E(R0)⊕K1))，如圖2所示。

圖2 二階DPA攻擊的組合中間值

在S盒的運算結果經過P置換后，每個字節(jié)都和所有的48 bit子密鑰有關，如圖3所示。因此不能直接選擇單個輸出字節(jié)作為中間值。

圖3 第一輪運算P置換后的輸出結果

在硬件密碼設備中，DES協處理器中每輪運算的8個S盒實現是并行的，每個S盒的輸出占P置換后的4 bit(1/8長度)，因此不管S盒輸出在P置換后位置如何變化，其對能量的影響是始終存在的。如果以一個S盒的6 bit子密鑰作為攻擊目標，那么在P置換輸出結果中除了該S盒的4 bit輸出外，其余28 bit輸出結果都是噪聲。

根據前述的能量泄露模型，6 bit的密鑰假設可以達到的最大相關系數為：

即猜測6 bit密鑰時相關系數是猜測全部密鑰的0.35倍。為了提高信噪比，可以選擇同時攻擊12 bit密鑰，即2個S盒的密鑰。在這種情況下，相關系數可以提高到猜測全部密鑰的0.5倍，信噪比會大大提高。

在同時攻擊12 bit子密鑰時，密鑰組合為212個，即需要攻擊4 096個假設密鑰。

3 高階DPA攻擊實驗驗證

基于以上分析，對FPGA上實現的帶變形掩碼方案的DES算法進行了攻擊實驗。首先在DES運算過程中采集2 000條能量跡，在該能量跡上可以清晰地識別出每輪DES運算過程，如圖4所示。

圖4 DES運算的能量跡

為了找到每輪運算相同操作（例如S盒運算）間隔的精確時間，采用模板匹配的方法對能量跡進行處理。其原理是首選選擇一段具有代表性的模板，然后用該模板與能量跡進行相關性計算，相關性高的位置將會出現尖峰，如圖5、圖6所示。

圖5 在某一輪上選擇匹配模板

圖6 模板匹配相關性曲線

通過測量模板匹配相關性曲線上相鄰尖峰的距離，可以計算出每輪運算的時間間隔。在第一輪運算曲線上找出可能出現的所有間隔為σ的兩點組合。這些兩點組合經過組合函數處理后，形成一條新的曲線。

最后，對組合中間值和新生成的曲線進行相關性運算。在所有4 096個相關系數曲線中，峰值最高的曲線所對應的密鑰值就是正確的密鑰，如圖7所示。在成功獲得12 bit密鑰后，還需要經過3次攻擊共獲得48 bit密鑰，剩余的8 bit密鑰可以通過窮舉獲得。

圖7 正確的子密鑰產生的相關系數峰值

為了抵抗DPA攻擊，掩碼技術越來越多地被采用。但掩碼方案可能受到高階DPA的攻擊，因此在設計掩碼方案時，需要充分考慮抵抗高階DPA攻擊的措施。本文首先介紹了能量泄露模型以及一階和高階DPA的攻擊原理。然后結合變形掩碼方案，從理論上證明可以采用二階DPA實施攻擊，并且論述了組合函數的選擇以及在攻擊中提高信噪比的方法。本文最后在FPGA上對掩碼方案的硬件實現進行了攻擊實驗，并成功獲得密鑰。

[1]KOCHER P，JAFFE J，JUN B.Introduction to differential power analysis and related attacks[A].Cryptography Research Inc.，1998.

[2]KOCHER P，JAE J，JUN B.Differential power analysis[C].In Proceedings of CRYPTO'99，Springer-Verlag，1999.

[3]MESSERGES T S，DABBISH E A，SLOAN R H,Investigations of power analysis attacks on smartcards[C].In Proceedings of the USENIX Workshop on Smartcard Technology，Chicago，1999.

[4]AKKAR M L，GIRAUD C.An implementation of DES and AES secure against some attacks[C].In Proceedings of CHES'2001，Springer-Verlag，2001.

[5]BRIER E，CLAVIER C，OLIVIER F.Correlation power analysis with a leakage model[C].In Cryptographic Hardware and Embedded Systems-CHES 2004，Springer-Verlag，2004.

[6]MESSERGES T S.Using second-order power analysis to attack DPA resistant software[C].In Proceedings of CHES’2000，Springer-Verlag，2000.