改進的基于掩碼AES選擇明文碰撞攻擊方法

鄭 東，王柳生，趙秉宇，張美玲

(西安郵電大學 無線網(wǎng)絡安全技術(shù)國家工程實驗室,陜西 西安 710121)

信息化時代的信息傳輸量巨大，會涉及到個人身份信息、網(wǎng)上購物支付密碼等隱私信息。與密碼相關(guān)的設備，如安全支付設備、智能穿戴設備和智能家居設備等也逐漸在生活中普及。隨著各種密碼硬件設備被應用到物聯(lián)網(wǎng)、智慧城市、區(qū)塊鏈和邊緣計算等各行各業(yè)中，其所面臨的安全威脅不應被忽視[1-2]。

1996年，Kocher等人首次提出計時攻擊之后，各種側(cè)信道攻擊方法被提出。根據(jù)密碼設備在運行過程中泄露信息的種類不同，可將側(cè)信道攻擊分為故障攻擊[3]、能量分析攻擊[4-5]、電磁輻射攻擊[6]、緩存攻擊[7]和聲音攻擊[8]等。能量分析攻擊因其實現(xiàn)簡單、花費代價小，可有效提取被加密信息中的密鑰等優(yōu)勢，自提出以來備受關(guān)注。1999年，Kocher等人提出了差分能量分析攻擊[9](Differential Power Analysis，DPA)，利用能量跡和已知的密文，通過選擇函數(shù)恢復某些子密鑰，但是其需要大量的能量跡。2004年，Brier等人提出的相關(guān)能量分析攻擊[10](Correlation Power Analysis，CPA)，利用已知明文和猜測的密鑰的假設的能量消耗，與實際能量消耗的相關(guān)性恢復密鑰。

針對已知明文輸入或密文輸出的情況，側(cè)信道攻擊對密碼設備產(chǎn)生了嚴重的威脅。如果不知道算法的輸入或者輸出，很多攻擊都無效，比如差分能量分析攻擊。2014 年，Linge等人提出了聯(lián)合概率分布攻擊[11]，首先針對高級加密標準(Advanced Encryption Standard，AES)算法的S盒輸入輸出的漢明重量(Hamming Weight，HW)，計算每個可能密鑰的理論概率分布。然后從能量跡中估計的漢明重量分布與預計算好的理論聯(lián)合概率分布求距離，距離最小的即為正確的密鑰。文獻[12]用最大似然法提升了從能量跡中提取的漢明重量的估計效率。

碰撞攻擊是指在算法的某個函數(shù)中是否有不同的輸入產(chǎn)生了相同的輸出。2003年，Schramm等人[13]首先提出了針對數(shù)據(jù)加密標準(Data Encryption Standard，DES)算法S盒的碰撞攻擊。文獻[14]提出了針對AES算法加密中第一輪的混合列變換輸出的碰撞攻擊。2007年，Bogdanov等人[15]提出了針對AES算法加密中第一輪S盒輸入的線性碰撞攻擊，通過建立不同密鑰間的關(guān)系式，用較少的能量跡恢復密鑰，但計算量較大。2010年，Moradi等人[16]提出了針對帶有隨機掩碼的AES算法S盒的相關(guān)碰撞攻擊。文獻[17]改進了針對帶有重用掩碼S盒的相關(guān)碰撞攻擊，平均需要27.5個明文就可以恢復所有的密鑰。2019年，Zheng等人[18]提出了假設檢驗法，能夠在S盒輸入發(fā)生碰撞時以較高的成功率檢測出碰撞。2019年，Ding等人[19]提出了針對帶有重用掩碼AES算法的S盒輸入的自適應選擇明文碰撞攻擊方法，假設敵手擁有和待攻擊設備相同的設備建立模板，通過選擇明文并與模板匹配可以降低密鑰搜索空間，直到找到密鑰。但是如果敵手沒有了這樣的可控硬件，那么就無法建立模板進行攻擊。

在帶有重用掩碼的AES算法中，任意兩個S盒輸入的漢明距離(Hamming Distance，HD)和歐幾里德距離(Euclidean Distance，ED)有著一一對應的關(guān)系，而密碼設備電路中的各個采樣點的能量消耗可以用漢明重量模型表示?；诖?，改進的基于掩碼AES選擇明文碰撞攻擊方法先求出能量跡的漢明重量模型表達式中的各個參數(shù)的值，然后根據(jù)表達式計算出不同的漢明距離所對應的歐幾里德距離值，建立模板。在攻擊階段，每次選擇明文攻擊后與模板匹配，排除一部分不可能的密鑰選項，降低密鑰的搜索空間，直至找到密鑰。

1 預備知識

1.1 基本符號

設AES-128算法的明文輸入為P={p1,p2,…,p16}，密鑰為K={k1,k2,…,k16}，那么S盒的輸入表示為xi=pi⊕ki，輸出表示為yi=S(pi⊕ki)，其中，pi∈P，ki∈K，i為S盒下標索引，1≤i≤16。

ti,q=si,qWH(x)+β+ri,q

(1)

如果從能量跡中截取到的關(guān)于S盒操作的采樣點段已經(jīng)對齊，那么常量si,q是與i無關(guān)的，可以簡化為sq。

針對S盒的碰撞攻擊是指不同的明文輸入產(chǎn)生相同的輸出，通過建立關(guān)于兩個密鑰的等式，進而恢復出密鑰。例如，S1和S2的輸入是相等的，即p1⊕k1=p2⊕k2，k2=k1⊕p1⊕p2，那么這兩個密鑰的搜索空間就降低到了28。如果其他密鑰與k1都建立了類似的等式，那么整個密鑰的搜索空間就從2128變成了28，遍歷搜索k1就能恢復出所有的密鑰。

密碼設備在處理相同的中間值時，消耗的能量被認為是相似的，因此，兩個能量跡中涉及相同中間值的片段往往被用來檢測碰撞。將這兩個能量跡片段(已經(jīng)求過平均)分別表示為{t1,1,t1,2,…,t1,l}和{t2,1,t2,2,…,t2,l}，兩個片段之間的相似程度可以用最小二乘法(least square method，LSM)描述，也就是其歐幾里德距離可表示為

(2)

如果D小于某個閾值，就表示檢測到了碰撞。

為了抵御側(cè)信道攻擊，邊緣計算或其他密碼設備中所采用的密碼算法會采取一些措施，掩碼方案[17]就是其中應用較為廣泛的一種。帶有掩碼的AES算法的S盒被定義為S′(xi⊕m)=S(xi)⊕M，其中，m是S盒的輸入掩碼，M是S盒的輸出掩碼，輸入和輸出的掩碼在AES算法每輪執(zhí)行前隨機產(chǎn)生，且至少在一輪加密中的16個S盒中使用相同的輸入輸出掩碼，重用掩碼方案如圖1所示。

圖1 重用掩碼方案

1.2 自適應選擇明文碰撞攻擊

模板攻擊是利用密碼設備對處理不同的數(shù)據(jù)消耗的能量有不同的特征刻畫模板，在攻擊階段將已知明文輸入的能量消耗特征與模板匹配，以獲得密鑰的信息。自適應選擇明文碰撞攻擊[18]就是一種針對重用掩碼AES算法的模板攻擊，假設敵手擁有一個和待攻擊設備相同的設備，則可控制明文密鑰建立模板。下面將以S1和S2為例進行說明。

在建立模板階段，令p1=k1=k2=0，p2的輸入空間范圍為{0,1,…,255}，使S1和S2之間輸入的漢明距離h遍歷{0,1,…,8}。對于每個明文p2：使用帶掩碼的AES算法加密明文n次，由于在攻擊階段的距離需要與模板匹配，為了降低噪聲的影響，n需足夠大；從每條能量跡截取兩個S盒輸入段子能量跡；使用最小二乘法對兩段子能量跡求距離，這個距離對應了模板中的漢明距離，即h=DH(x1,x2)。這樣就建立9個漢明距離對應歐幾里德距離的模板。

Ding等人的理論依據(jù)是帶有重用掩碼的任意兩個S盒之間的輸入漢明距離和歐幾里德距離存在以下關(guān)系[18]。

定理1如果l是固定的，Δ的取值范圍為{0,1,2,…,8}。對于任意的x1，x2∈{0,1,2,…,255}，DH(x1,x2)=Δ，則期望值可表示為

(3)

式中，E(·)為期望函數(shù)。

2 改進的選擇明文碰撞攻擊方法

2.1 能量跡的數(shù)學表達式

漢明重量為一個字節(jié)數(shù)據(jù)的二進制形式中1的數(shù)量，8比特的數(shù)據(jù)x可表示為x=x7x6x5…x0，則有

(4)

如果x是均勻分布且相互獨立的，那么WH(x)與x的個數(shù)之間的關(guān)系如表1所示。

表1 均勻分布x的漢明重量與數(shù)據(jù)個數(shù)的關(guān)系

為了方便后文描述，能量跡的數(shù)學表達式(1)可重新表示為

t=sWH(x)+β+r

(5)

研究能量跡各采樣點的方差[16]可以知道，方差較小的部分是噪聲或是與設備算法輸入無關(guān)的常量消耗，方差較高的部分反映了處理數(shù)據(jù)的不同，是與操作數(shù)據(jù)有關(guān)的采樣點，那些與S盒輸入有關(guān)的采樣點被稱為興趣點。

對式(5)兩邊求方差，一方面固定能量消耗β的方差為0，另一方面噪聲部分與操作的數(shù)據(jù)無關(guān)，由此可得能量跡的方差為

V(t)=V[sWH(x)+β]+V(r)=s2V[WH(x)]+V(r)

(6)

式中，V(r)為噪聲r的方差。假設數(shù)據(jù)x的每一個比特位是均勻分布的，那么x的漢明重量服從二項分布B(8,1/2)，則有

(7)

根據(jù)式(6)和式(7)，s可以表示為

(8)

對式(5)兩邊求數(shù)學期望，WH(x)的數(shù)學期望為4。對于固定能量消耗β，其數(shù)學期望就是其本身。噪聲r服從均值為0的正態(tài)分布。因此可得

E(t)=sE[WH(x)]+E(β)+E(r)=4s+β

(9)

一旦確定了s，那么β可以表示為

β=E(t)-4s

(10)

式中，E(t)是用興趣點處泄露能量值的平均值估計。

至此，在無掩碼的情況下，式(5)中的幾個參數(shù)都已經(jīng)得到求解。

然而，在有掩碼的情況下，式(5)變?yōu)?/p>

t=sWH(x⊕m)+β+r

(11)

密碼設備的能量消耗主要與被處理數(shù)據(jù)的漢明重量有關(guān)，而不同的漢明重量代表了不同的能量消耗。因此，將利用估計的方法區(qū)分興趣點處所代表的漢明重量。

這種區(qū)分方法依賴于能量跡中泄露的質(zhì)量，只在噪聲較小的情況下才有效。通過降低噪聲，比如使用4階累積量[21]方法，排序效果會更好。利用降低噪聲的方法可以得到較為準確的排序，但部分元素會被排序在錯誤的位置，此時需要更多的能量跡減小錯誤帶來的影響。

取出興趣點處漢明重量為4的能量跡子集合，對式(11)兩邊求方差，由于sWH(4)的方差為0，固定能量消耗β的方差也為0，而噪聲部分與操作的數(shù)據(jù)無關(guān)，由此可以得到

V(Tl)=V(r)

(12)

在不對能量跡進行排序的情況下，對式(11)兩邊求方差，得到

V(t)=V[sWH(x⊕m)+β]+V(r)=s2V[WH(x⊕m)]+V(r)

(13)

每輪的掩碼是隨機產(chǎn)生的，假設掩碼m是均勻分布的，對于任意的x∈[0,255]，x⊕m在[0,255]上仍是均勻分布的(x是固定的)，即x⊕m的每一個比特位是均勻分布的，x⊕m的漢明重量服從二項分布B(8,1/2)，則有

(14)

根據(jù)式(13)和式(14)，可以將s表示為

(15)

對式(11)兩邊求數(shù)學期望，對于固定的x和均勻分布的掩碼m，WH(x⊕m)的數(shù)學期望仍為4，可得

E(t)=sE[WH(x⊕m)]+E(β)+E(r)=4s+β

(16)

如果s被確定了，那么β可以表示為

β=E(t)-4s

(17)

其中，E(t)仍是用帶有重用掩碼的AES算法加密固定明文的興趣點處泄露能量值的平均值估計。

至此，在有掩碼的情況下，能量跡數(shù)學表達式(5)中的參數(shù)σ、β、s均已求解出。

2.2 基于理論計算的模板攻擊

針對S盒的碰撞攻擊，距離不僅指的是S盒之間的歐幾里德距離，還包括漢明距離。接下來，將充分利用S盒的歐幾里德距離和漢明距離之間的關(guān)系，排除部分不可能的明文輸入找到碰撞。

2.2.1 基本思想

以S1和S2為例，將p1固定為一個常量，例如p1=0，p2的目標值表示為β2。令k1⊕k2=Δk，那么目標值β2=p1⊕Δk。改進的基于掩碼AES選擇明文碰撞攻擊具體步驟如下。

步驟1計算式(1)中未知變量的值，并根據(jù)式(3)計算9個不同漢明距離對應歐幾里德距離期望值，建立模板。

步驟2固定p1=0，初始化p2的候選值空間范圍為0～255。

步驟3從p2的取值范圍中隨機選擇一個元素，計算x1和x2之間的歐幾里德距離，使用這個歐幾里德距離與模板匹配，得到x1和x2之間估計的漢明距離，等價于DH(p2,β2)。

步驟4根據(jù)步驟3中的漢明距離更新p2的取值范圍。

步驟5重復步驟3和步驟4，直到p2的取值范圍只剩一個值，那么這個值就是β2。

2.2.2 攻擊場景

改進的基于掩碼AES選擇明文碰撞攻擊方法包括模板建立和攻擊兩個階段。

圖2 建立模板流程

攻擊固定p1=0，初始化p2的取值范圍為0～255，表示為C0={0,1,2,…,255}。無需遍歷明文，通過循環(huán)的方式降低候選值數(shù)量。改進的選擇明文碰撞攻擊在每個循環(huán)中的具體步驟如下。

步驟1從C0中隨機選擇一個元素作為p2。

步驟2加密帶有掩碼的AES算法n次，將采集到的能量跡表示為{Tj|j=1,2,…,n}。

步驟4使用LSM計算x1和x2之間的歐幾里德距離Dj，并對n次加密結(jié)果Dj求平均，即

(18)

此時，D對應模板中ξΔ的漢明距離h=DH(p1,p2)。

步驟5將得到的歐幾里德距離與模板進行匹配，得到估計的漢明距離

(19)

h就是x1和x2之間漢明距離的估計值，也就是DH(p2,β2)=h。

步驟6將滿足條件與p2異或漢明距離為h的候選值明文p放到集合C中，即C={p|DH(p,p2)=h}，并更新p2的集合C0=C0∩C。

步驟7重復上面的過程，直到C0中只有一個元素(攻擊成功)，或C0是一個空集合(攻擊失敗)。

改進的選擇明文碰撞攻擊流程如圖3所示，其中|C0|表示C0中的元素數(shù)量。

圖3 改進的選擇明文碰撞攻擊流程

3 實驗結(jié)果及分析

利用ChipWhisperer[22]平臺完成對能量跡的采集工作，線下使用Matlab對數(shù)據(jù)進行處理分析。

3.1 對兩個密鑰字節(jié)的攻擊

在建立模板階段，利用式(3)求出兩個S盒之間漢明距離{0,1,2,…,8}對應的歐幾里德距離期望值(模板值)分別為{1.380×10-4，1.875×10-4，2.370×10-4，2.865×10-4，3.360×10-4，3.855×10-4，4.350×10-4，4.845×10-4，5.340×10-4}，如圖4所示。

圖4 9個漢明距離對應的模板值

在攻擊階段，設置k1=135，k2=78。令p1=0，在每個循環(huán)中，選擇明文加密次數(shù)n=1 000。在第一次循環(huán)中，隨機選擇明文p2=104，得到D=2.751×10-4，與模板匹配得到的漢明距離為3，即DH(p2,β2)=3，更新p2的候選值集合，|C0|中的元素數(shù)量降到了56個。在第二次循環(huán)中，從更新后的集合C0中隨機選擇p2=237，得到D=2.238×10-4，即DH(p2,β2)=2，更新集合，|C0|中的元素數(shù)量降到了15個。在之后的循環(huán)中，每次都從集合C0中隨機選擇一個元素作為p2，得到相應的距離D和與模板匹配的漢明距離DH(p2,β2)，仿真實驗結(jié)果如表2所示。

表2 實驗的中間值數(shù)據(jù)

從表2中可以看到，在第5次循環(huán)中，C0中只剩下了201一個值，其他候選值都在前面的循環(huán)中被排除了，而k1⊕k2=135⊕78=201，攻擊成功并得到了正確的目標值。

圖5給出了在5次循環(huán)中選擇明文攻擊后與模板匹配得到的漢明距離值，其中，黑色星號表示x1和x2之間的歐幾里德距離結(jié)果，虛線表示模板。

圖5 在攻擊中使用的5個明文匹配模板

圖6給出了每次循環(huán)后存活的候選值數(shù)量，在第一次循環(huán)后，剩下了56個候選值，在第二次循環(huán)后，剩下了15個候選值，在第三次循環(huán)后，剩下了6個候選值，在第四次循環(huán)后，剩下了3個候選值，最后一次循環(huán)，只有一個候選值201被保留下來。

圖6 攻擊中每個循環(huán)后存活的候選值數(shù)量

(20)

在仿真實驗中發(fā)現(xiàn)，平均需要5.2個明文找到目標值，也就是說，平均使用5.2個明文就可以檢測到碰撞。

3.2 對兩個密鑰字節(jié)的攻擊成功率對比

在不同噪聲標準差環(huán)境下，改進的基于掩碼AES選擇明文碰撞攻擊(表示為LSM)，自適應選擇明文碰撞攻擊(表示為DLSM)和相關(guān)碰撞攻擊[17](Collision-Correlation Attack，CCA)等3種攻擊方法在σ=0.002 94和σ=0.006時的成功率對比分別如圖7和圖8所示。

圖7 σ=0.002 94時3種攻擊方法的成功率對比

由圖7可以看出，當σ=0.002 94時，CCA方法在6 000條能量跡時只有73.8%的成功率，LSM方法達到95%的成功率需要5 800條能量跡，DLSM方法需要5 850條能量跡，LSM方法和DLSM方法均要優(yōu)于CCA方法。LSM方法和DLSM方法攻擊的成功率比較接近，DLSM方法各個漢明距離的模板值基本成等差數(shù)列，與LSM方法通過計算得到的模板值比較接近。

圖8 σ=0.006時3種攻擊方法的成功率對比

由圖8可以看出，當σ=0.006時，LSM方法在12 000條能量跡時只有65.6%的成功率，而DLSM方法可以達到85%的成功率，這種情況下LSM方法比DLSM方法的攻擊成功率低19.4%。

根據(jù)自糾錯能力[18](Self-Correction，SC)，驗證改進的攻擊方法建立模板攻擊成功率的極限。在不同噪聲標準差情況下，有無糾錯能力的改進的基于掩碼AES選擇明文碰撞攻擊(分別表示為SC_LSM和LSM)、有無糾錯能力自適應選擇明文碰撞攻擊(分別表示為SC_DLSM和DLSM)和CCA等5種攻擊方法在σ=0.002 94、σ=0.006、σ=0.009和σ=0.012時的成功率對比分別如圖9至圖12所示。

圖9 σ=0.002 94時5種攻擊方法的成功率對比

由圖9可以看出，當σ=0.002 94時，LSM方法在4 000條能量跡時只有90%的成功率，SC_LSM方法達到95%成功率需要3 360條能量跡，增加糾錯能力后，攻擊成功率有明顯提升。SC_DLSM達到95%的成功率需要3 511條能量跡，SC_LSM和SC_DLSM的攻擊成功率仍然比較接近，這說明通過理論計算得到的模板與使用與待攻擊設備相同的設備建立的模板，在低噪聲情況下，無論是否使用糾錯能力，改進的攻擊方法和自適應選擇明文碰撞攻擊方法的成功率比較接近。

圖10 σ=0.006時5種攻擊方法的成功率對比

由圖10可以看出，當σ=0.006時，SC_LSM方法在8 000條能量跡時只有80%的成功率，而SC_DLSM方法的成功率達到了94.4%，此時SC_LSM方法比SC_DLSM方法攻擊的成功率低14.4%。

圖11 σ=0.009時5種攻擊方法的成功率對比

進一步增加噪聲標準差，由圖11可以看出，當σ=0.009時，SC_LSM方法在16 000條能量跡時達到了 89.6%的成功率，而SC_DLSM方法攻擊的成功率只有81.4%，SC_LSM方法比SC_DLSM方法攻擊的成功率高8.2%。

圖12 σ=0.012時5種攻擊方法的成功率對比

由圖12可以看出，當σ=0.012時，SC_LSM方法在32 000條能量跡時有80.8%的成功率，SC_DLSM方法攻擊的成功率只有67.8%，SC_LSM方法比SC_DLSM方法攻擊的成功率高13%。

綜合以上情況，噪聲標準差增加到一定范圍以后，改進的攻擊方法攻擊成功率優(yōu)于自適應選擇明文碰撞攻擊方法。說明通過與待攻擊設備相同的設備建立模板只在一定噪聲范圍內(nèi)比較準確，噪聲一旦達到了某個閾值，會影響模板的準確度，不同漢明距離對應的歐幾里德距離不成線性關(guān)系。而通過理論計算得到的模板，只要參數(shù)估計準確，無論在什么樣的噪聲環(huán)境下，其模板的漢明距離對應的歐幾里德距離一定呈成線性關(guān)系，在低噪聲和某些高噪聲環(huán)境下，可以更好地刻畫密碼設備中的能量消耗特征，并且改進的攻擊方法不需要與目標設備一模一樣的可控硬件建立模板，因而在實際應用中更加靈活。

4 結(jié)語

改進的基于掩碼AES選擇明文碰撞攻擊方法利用漢明重量模型，較為準確地刻畫了電路中的能量消耗。通過求解能量跡數(shù)學表達式，得到各個參數(shù)，利用參數(shù)計算出9個漢明距離對應的9個歐幾里德距離期望值，從而建立了針對掩碼AES任意兩個S盒輸入的9個漢明距離對應9個歐幾里德距離的模板。仿真實驗結(jié)果表明，在不同噪聲環(huán)境下，改進的攻擊方法在低噪聲環(huán)境下恢復密鑰所需要能量跡的數(shù)量和自適應選擇明文碰撞攻擊方法相當。在噪聲標準差增加到一定范圍后，改進的攻擊方法建立的模板更為準確，在相同能量跡數(shù)量的情況下攻擊成功率更高，并且不需要敵手擁有一個和待攻擊設備相同的設備建立模板這一限制條件。