針對重用掩碼AES 算法的隨機明文碰撞攻擊

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

（1.西安郵電大學 網(wǎng)絡(luò)空間安全學院，西安 710121；2.西安郵電大學 無線網(wǎng)絡(luò)安全技術(shù)國家工程實驗室，西安 710121）

0 概述

密碼算法在加密設(shè)備上進行實現(xiàn)，加密設(shè)備在執(zhí)行算法的過程中不可避免地會泄露不同形式的物理信息，例如能量消耗、電磁輻射、聲音等，這些信息統(tǒng)稱為側(cè)信道信息。側(cè)信道攻擊是密碼學研究的熱點方向，自從KOCHER 在1996 年提出計時攻擊思想以來［1］，研究人員提出了大量側(cè)信道攻擊方法，例如差分能量分析攻擊［2］、碰撞攻擊［3］、相關(guān)能量分析攻擊［4］、模板攻擊［5］等。隨著側(cè)信道攻擊方法的出現(xiàn)，與其相關(guān)的能量跡定位方法［6］和側(cè)信道信息泄露評估方法［7-8］也陸續(xù)被提出。側(cè)信道分析攻擊能夠從物理信道泄露的能量消耗等物理信息中獲取密碼設(shè)備運算時與密鑰相關(guān)的中間值信息，并且能夠分段恢復較長的密鑰，對加密設(shè)備造成了很大的安全威脅。

碰撞攻擊是側(cè)信道攻擊中的一種，關(guān)注的是加密設(shè)備在加密或解密過程中算法中間值是否存在碰撞，即是否出現(xiàn)相同的中間值，可以從泄露能量中有效地提取密鑰相關(guān)信息。2003 年，SCHRAMM 等［3］提出針對數(shù)據(jù)加密標準（Data Encryption Standard，DES）的側(cè)信道碰撞攻擊。2004 年，SCHRAMM 等［9］又提出針對高級加密標準（Advanced Encryption Standard，AES）的列混合變換輸入字節(jié)的碰撞檢測攻擊方法。2007 年，BOGDANOV［10］提出針對AES的線性碰撞攻擊，該方法改進了SCHRAMM 等提出的針對AES 的碰撞檢測攻擊。在實際應(yīng)用中，為了抵抗側(cè)信道攻擊［11-12］，加密設(shè)備［13-14］一般會采取一系列的對策，掩碼技術(shù)［15-16］就是其中一種。2010 年，MORADI 等［17］提出一種能夠識別使用掩碼技術(shù)的AES 算法S 盒間碰撞的方法。2011 年，CLAVIER等［18］利用重用掩碼的特點，建立不同的S 盒間帶掩碼數(shù)據(jù)的碰撞關(guān)系。2012 年，BOGDANOV 等［19］提出一種將DPA 和側(cè)信道碰撞攻擊相結(jié)合的攻擊方法，大幅提高了碰撞攻擊效率。2019 年，NIU 等［20］提出一種能抵抗3 種典型掩碼方案的碰撞攻擊思路，利用掩碼和被掩碼數(shù)據(jù)處理方式相同的特點，選擇AES 的列混合變換作為攻擊點并實現(xiàn)了很好的攻擊效果；DING 等［21］提出自適應(yīng)選擇明文碰撞攻擊，通過建立能量跡歐氏距離與中間值漢明距離的聯(lián)系，用能量跡泄露的距離信息減小密鑰候選值空間；ZHENG 等［22］提出基于假設(shè)檢測的側(cè)信道碰撞攻擊，利用假設(shè)檢測方法確定一個合理的碰撞閾值，該方法提高了碰撞檢測的成功率。

文獻［18］提出的改進型相關(guān)性碰撞攻擊需要預先確定1 個碰撞閾值，通過比較2 段能量跡之間的相關(guān)系數(shù)和碰撞閾值之間的大小關(guān)系來確定是否發(fā)生碰撞，閾值的準確性會影響碰撞檢測的成功率，進而影響攻擊的成功率。該攻擊方法只能利用能量跡中發(fā)生碰撞的信息，未發(fā)生碰撞的信息會被忽略。文獻［21］提出的自適應(yīng)選擇明文碰撞攻擊在攻擊之前需要攻擊者擁有一個和目標設(shè)備相同的設(shè)備用于建立攻擊模板，實施復雜且具有一定的局限性。由以上分析可知：文獻［18，21］中提出的方法都需要控制每次加密的明文，在攻擊者不能操作和目標設(shè)備相同的設(shè)備并且只能獲得一定數(shù)量的隨機明文和對應(yīng)能量跡的情況下，這2 種方法均會失效。

本文基于重用掩碼AES 算法任意2 個S 盒之間輸入的漢明距離和歐式距離之間的關(guān)系［21］，提出一種高效的隨機明文碰撞攻擊方法。該方法無需預先確定碰撞閾值及建立攻擊模板，即可有效利用能量跡中未發(fā)生碰撞的信息。此外，該方法屬于隨機明文攻擊方法，因此當攻擊者不能對目標設(shè)備進行操作時也可實施攻擊。

1 相關(guān)工作

1.1 漢明重量模型

漢明重量模型［5］是指設(shè)備泄露的能量與被處理數(shù)據(jù)的漢明重量相關(guān)，計算公式如下：

其中：q表示能量跡采樣點的序號；tq表示對數(shù)據(jù)x進行處理時在采樣點q處泄露的能量消耗值；sq表示采樣點q處的系數(shù)；rq表示對應(yīng)能量跡在采樣點q處的噪聲，并且服從正態(tài)分布；HW(x)表示求x的漢明重量。

1.2 重用掩碼方案

重用掩碼方案在AES 算法加密的每一輪中僅產(chǎn)生2 個隨機掩碼值，在同一輪中16 個S 盒的輸入用同一掩碼，16 個S 盒的輸出用同一掩碼，也就是在一輪中只需要預計算1個新的S 盒置換表S′。新的S 盒置換表與普通的置換表之間的關(guān)系為S′(xi⊕mask1)=S(xi)⊕mask2，其中，i∈[1，16]，mask1是S 盒的輸入掩碼，mask2是S 盒的輸出掩碼，重用掩碼方案的框圖如圖1 所示。

圖1 重用掩碼方案框圖Fig.1 Block diagram of reused mask scheme

1.3 漢明距離和歐式距離

漢明距離是指使用重用掩碼的AES 算法同一輪加密中2 個S 盒的輸入之間的漢明距離。如圖2 所示，2 個不同的S 盒的輸入分別為x1⊕mask1和x2⊕mask1，那么它們之間的漢明距離就是x1=p1⊕k1和x2=p2⊕k2之間的漢明距離，即HD(x1，x2)，其中HD(x1，x2)表示求x1和x2之間的漢明距離。

圖2 漢明距離示意圖Fig.2 Schematic diagram of Hamming distance

歐氏距離計算以前2個S盒為例，對1個明文加密，采集其對應(yīng)的能量跡，將能量跡中對應(yīng)于圖2 中處理數(shù)據(jù)x1⊕mask1和x2⊕mask1的2 段能量跡分別截取出來并對齊，然后根據(jù)式（2）計算歐氏距離ED(x1，x2)。

其中：ti，q是第i個S 盒所對應(yīng)的能量跡中的第q個采樣點的采樣值，l是第i個S 盒所對應(yīng)的能量跡中的采樣點的個數(shù)。通過式（2）可以看出，歐氏距離本質(zhì)上就是采用最小二乘法計算同一輪加密中2 段能量跡之間的累積距離。

在本文中，如果沒有特殊說明，則漢明距離均指使用重用掩碼的AES 算法同一輪加密中2 個不同S盒的輸入之間的漢明距離，歐氏距離均指同一輪加密中2 個不同S 盒的輸入位置所對應(yīng)2 段能量跡間的累積距離。

1.4 漢明距離和歐式距離之間的關(guān)系

對同一Δhd下的N個明文進行加密，分別求每個Δhd對應(yīng)的歐氏距離的均值，計算公式如下：

其中：sq是漢明重量模型中的系數(shù)；σ2是加密設(shè)備的噪聲方差，該值對所有的采樣點都是近似相等的。

由此可見，歐氏距離的均值和漢明距離之間滿足線性關(guān)系。

2 攻擊原理

2.1 歐式距離歸類

使用猜測的漢明距離將歐氏距離進行歸類，通過某個明文分別與256 個密鑰異或值求得256 個猜測的漢明距離，利用這256 個猜測的漢明距離分別與該明文對應(yīng)的歐氏距離進行歸類。

假設(shè)某個隨機明文的前2 個字節(jié)分別為p1=143、p2=59，其對應(yīng)歐氏距離為ED(p1，p2)。如表1 所示，通過p1和p2以及猜測的密鑰異或值Δ求得漢明距離HD，然后將HD 和Δ分別作為行號和列號對歐氏距離進行歸類。對于明文p1和p2，通過Δ=0，1，…，255 分別可以求得漢明距離HD=4，5，…，4，假設(shè)第i行第j列位置處原來的累積歐氏距離為edi，j，則這次加密后對2 個S 盒之間的歐氏距離歸類的結(jié)果如表1 所示，其中灰色位置為歐氏距離歸類時的位置。從表1 可以看出，每個位置所存放的是累積歐氏距離，也就是在已經(jīng)確定一個歐氏距離的位置之后，需要將該歐氏距離與這個位置原來的值相加，得到該位置處新的累積值。

表1 明文字節(jié)p1和p2對應(yīng)歐氏距離歸類后的結(jié)果Table 1 Results of Euclidean distance classification of plaintext bytes p1 and p2

2.2 歸類結(jié)果分析

為方便歸類結(jié)果的分析，使用式（5）來描述式（4）中漢明距離和歐式距離均值之間的線性關(guān)系。

其中：x表示實際的漢明距離；y表示x對應(yīng)的歐氏距離的均值；a=和b=2σ2l是2 個常系數(shù)。由式（5）可以得到表2 中的歐氏距離的均值和實際漢明距離的關(guān)系。

表2 漢明距離和歐氏距離均值的對應(yīng)關(guān)系Table 2 Relationship between Hamming distance and the mean of Euclidean distance

2 個明文字節(jié)的異或值是1 個8 bit 數(shù)據(jù)，對于1 個8 bit 的數(shù)據(jù)，共有28個可能值，這256 個值出現(xiàn)的概率相等且均為1/256?？紤]所有256 個值，根據(jù)表2 描述的關(guān)系進行歐氏距離歸類，令d表示猜測密鑰異或值和正確密鑰異或值之間的漢明距離。在歸類后，首先計算表1 中每個位置累計歐氏距離的均值，然后計算表1 中第1 列數(shù)據(jù)與后面256 列數(shù)據(jù)的均值之間的相關(guān)系數(shù)ρ，得到表3 所示的結(jié)果。

通過式（6）計算2 個長度為n的向量X和Y之間的相關(guān)系數(shù)：

其中：xi和yi分別表示向量X和Y的第i個元素；分別表示向量X和Y中所有元素的均值。

從表3 中可以看出，在理論情況下，只有d=4 時的相關(guān)系數(shù)為0，其他情況下相關(guān)系數(shù)為1 或?1。表3 中的結(jié)果是理論情況下的相關(guān)系數(shù)，本文在實驗仿真中發(fā)現(xiàn)，通過上述歸類法處理數(shù)據(jù)后，不同的d會造成歸類時歐氏距離分布的不均勻，從而影響歐氏距離的均值的準確性，最終影響相關(guān)系數(shù)的求取。相比于直接歸類分析，將隨機明文分成多組后歸類可以得到更好的分析結(jié)果，分組歸類的原理如圖3 所示，首先將明文分成N組進行歐氏距離歸類，然后將歸類結(jié)果拼接在一起，最后求矩陣A中每個位置的均值，計算V和求均值后的A中每一列的相關(guān)系數(shù)。

圖3 歐氏距離的分組歸類Fig.3 Grouping and classification of Euclidean distance

為驗證在實際情況下由于d的不同對相關(guān)系數(shù)的影響，在噪聲標準差σ=0.002 9 的情況下，加密10 組隨機明文，每組包含50 000 個明文，設(shè)置密鑰異或值Δ=85，通過仿真實驗歸類分析后進行排名。

表4 給出了排名前8 的猜測密鑰異或值，可以看出這些值對應(yīng)的d都很小。圖4 給出了所有猜測密鑰異或值對應(yīng)求得的相關(guān)系數(shù)，可以看出：排名前93 個密鑰異或值對應(yīng)相關(guān)系數(shù)接近于1 且遞減，對應(yīng)于d為0、1、2、3 的情況；從排名93 開始相關(guān)系數(shù)突然變小，排名93 到164 對應(yīng)于d為4 的情況，相關(guān)系數(shù)接近于0；排名164 到256 的相關(guān)系數(shù)接近于?1，對應(yīng)于d為5、6、7、8的情況。圖5 給出了這256 個排序后的密鑰異或值所對應(yīng)的d，可以看出：排名前10 的密鑰異或值所對應(yīng)的d比較小，為0、1、2；當d=3 時所對應(yīng)的猜測密鑰異或值位于排名36到93；93后為d≥4 所對應(yīng)的猜測密鑰異或值。

表4 排名前8 的猜測密鑰異或值所對應(yīng)的相關(guān)系數(shù)Table 4 Correlation coefficients corresponding to the top 8 guessed key XOR value

圖4 歸類分析后不同排名對應(yīng)的相關(guān)系數(shù)Fig.4 Correlation coefficients corresponding to different rankings after classification analysis

圖5 歸類分析后不同排名對應(yīng)的d 值Fig.5 d values corresponding to different rankings after classification analysis

以上結(jié)果驗證了在實際情況中，d的不同會對相關(guān)系數(shù)造成影響，且根據(jù)相關(guān)系數(shù)對猜測密鑰異或值排序后的前10 個值所對應(yīng)的d比較小，正確的密鑰異或值排名會比較靠前?；谝陨辖Y(jié)論，可以首先通過歸類分析法將正確密鑰異或值所在范圍縮小，然后本文攻擊方法利用排名靠前的密鑰異或值所對應(yīng)的d比較小的特點提出投票法，從中進一步得到正確異或值。

3 攻擊方法設(shè)計

3.1 實驗平臺介紹

采用ChipWhisperer［23］平臺作為實驗平臺，所有實驗均使用該平臺采集的能量跡，然后用MATLAB對能量跡進行分析。ChipWhisperer 是一個開源平臺，用于對硬件設(shè)備的安全性進行研究。如圖6 所示，該平臺包含主控板（左）和目標板（右）2 個模塊。主控板用于采集和傳輸能量消耗，同時用來實現(xiàn)PC和實驗板的數(shù)據(jù)傳輸以及密碼算法的下載。目標板實現(xiàn)對數(shù)據(jù)的加密。該平臺對于研究人員而言具有低成本、易操作的優(yōu)點。

圖6 ChipWhisperer 實驗平臺示意圖Fig.6 Schematic diagram of the ChipWhisperer experimental platform

實驗板主要有2 個對應(yīng)的開源軟件配合使用，分別是Capture 和Analyzer，前者用于加載加密算法、控制明密文以及捕獲能量跡，后者提供了一些分析能量跡的腳本。圖7 給出了Capture 軟件能量跡采集示意圖。

圖7 Capture 軟件能量跡采集示意圖Fig.7 Schematic diagram of Capture software energy trace acquisition

不同的實驗設(shè)備所對應(yīng)的能量跡具有不同的噪聲標準差，本文使用的平臺噪聲標準差σ為0.002 9，通過在能量跡上加入噪聲來合理增加標準差。

3.2 攻擊流程

本文方法的攻擊過程包括線上能量跡采集階段和線下數(shù)據(jù)分析階段，具體攻擊流程如下：

步驟1加密M個隨機明文，采集對應(yīng)的M條能量跡，并記錄這M個隨機明文。

步驟2將M個明文和M條能量跡分成N組，每組包含M/N個明文和M/N條能量跡。

步驟3將每條能量跡中對應(yīng)于處理16 個S 盒輸入的部分截取出來并對齊。

步驟4對每條能量跡求第1 個S 盒和第2 個S盒之間的歐氏距離，然后進行歸類，并將歸類后的矩陣拼接，得到如圖3 所示的結(jié)果。

步驟5求矩陣A中每個位置的均值，計算向量V和求均值后的矩陣A中每一列的相關(guān)系數(shù)，根據(jù)相關(guān)系數(shù)將猜測密鑰異或值進行降序排序。

步驟6用投票法將排序后排名前n的密鑰異或值進行投票，篩選出票數(shù)最少的密鑰異或值，該值是前2 個密鑰字節(jié)k1和k2的異或值Δ1，2=k1⊕k2。

步驟7重復步驟4 到步驟6，對第1 個S 盒和另外14 個S 盒進行歸類分析，最終得到如等式（7）所示的第1 個密鑰字節(jié)和其他15 個密鑰字節(jié)之間的線性關(guān)系，從而將密鑰空間從2128縮小到28。

步驟8遍歷第1 個密鑰字節(jié)，從剩下的候選密鑰中得到正確密鑰。

3.3 針對前2 個S 盒的攻擊

為驗證本文方法的可行性，將對使用重用掩碼方法的AES-128 算法進行攻擊，攻擊的目標點是第1 輪加密中前2 個S 盒的輸入位置。在對采集的能量跡進行統(tǒng)計分析之前，需要將每條能量跡所對應(yīng)16 個S 盒操作部分截取出來，如圖8所示。由于第1輪中的16個S 盒操作的實現(xiàn)方式相同且依次執(zhí)行，因此通過方差檢測可以清晰地區(qū)分出16個S盒操作在能量跡中的位置。在確定16 個S 盒的位置后，對區(qū)間內(nèi)的點進行攻擊嘗試，最終找到合適的8 個采樣點。不失一般性，在噪聲標準差σ為0.002 9 的情況下，設(shè)置前2 個密鑰字節(jié)分別為k1=43、k2=126，共加密30 組隨機明文，每組包含100 個猜測密鑰異或值，選擇排名1 到排名8 的猜測密鑰異或值作為投票對象。

圖8 AES 加密的第1 輪方差檢測結(jié)果Fig.8 Results of the first round variance test of AES encryption

表5 給出了實施歐氏距離歸類分析并根據(jù)相關(guān)系數(shù)排序后排名1 到排名8 的結(jié)果，可以看出這8 個猜測密鑰異或值Δ與正確密鑰異或值的距離d均較小，并且距離為0 時的正確密鑰異或值也包含在其中。在密鑰異或值候選空間被縮小后，用投票法篩選出正確密鑰異或值。從第1 個值93 開始分別與另外7 個值求漢明距離，對于每個值將求得的7 個漢明距離相加作為該值的投票結(jié)果。因為排名靠前的猜測密鑰異或值與正確密鑰異或值的距離均很小，所以通過投票后得到的投票值最小的猜測密鑰異或值就是正確密鑰異或值。如圖9 所示，對前8 個猜測密鑰異或值分別進行投票，然后統(tǒng)計總票數(shù)。從圖9 可看出，正確密鑰異或值的票數(shù)是9，在前8 個猜測密鑰異或值中最小。

表5 前2 個S 盒歸類分析排序后的結(jié)果Table 5 Results of classification analysis and sorting of the first two S-boxes

圖9 排名前8 的猜測密鑰異或值投票結(jié)果Fig.9 Results of the voting for the top 8 guessed key XOR value

3.4 攻擊成功率統(tǒng)計與對比

為分析本文方法的效率，實驗針對重用掩碼AES-128 算法加密的第1 輪實施大量攻擊后，統(tǒng)計成功率隨著加密次數(shù)的變化曲線。在實際攻擊中，控制明文分組為30，通過改變每個分組中隨機明文的個數(shù)來統(tǒng)計成功率。為與其他方法進行對比，在相同的實驗環(huán)境下實施另外3 種攻擊方法并統(tǒng)計其成功率。

圖10、圖11 分別給出了本文方法與文獻［18，21］方法在不同的噪聲環(huán)境下的攻擊成功率對比。文獻［18］中提出針對重用掩碼AES 算法的改進型相關(guān)性碰撞攻擊（Improved Collision-Correlation Attack，ICCA），該攻擊方法的成功率曲線對應(yīng)圖10、圖11中的ICCA方法。文獻［21］提出自適應(yīng)選擇明文碰撞攻擊，使用最小二乘法（Least Square Method，LSM）和中心矩積法（Central Moment Product，CMP）這2 種方法來計算2 段能量跡的差，并利用自修正（Self-Correction，SC）錯誤機制，大幅提升了成功率，該攻擊方法的成功率曲線對應(yīng)圖10、圖11 中的SC_LSM 和SC_CMP 方法。

從圖10、圖11 可以看出：在噪聲標準差σ為0.002 9 時，若要達到95%的成功率，則本文方法需要約1 600 條能量跡，其他3 種方法中成功率最高的SC_CMP 方法也需要約1 600 條能量跡；在噪聲標準差σ為0.006 時，若要達到95%的成功率，則本文方法需要約4 000 條能量跡，其他3 種方法中成功率最高的SC_CMP 方法需要約5 000 條能量跡。

圖10 針對重用掩碼方案的攻擊成功率對比（σ=0.002 9）Fig.10 Comparison of attack success rate for reused mask scheme（σ=0.002 9）

圖11 針對重用掩碼方案的攻擊成功率對比（σ=0.006）Fig.11 Comparison of attack success rate for reused mask scheme（σ=0.006）

由此可見，本文方法相比于SC_CMP 方法，成功率的優(yōu)勢并不明顯，但相比于其他3 種方法，除了不需要預先確定碰撞閾值及預先計算攻擊模板外，最大的優(yōu)勢在于明文的隨機性。當不允許攻擊者操作與目標設(shè)備相同的設(shè)備且只可獲得一定數(shù)量的隨機明文和其對應(yīng)能量跡時，其他3 種方法就無法實施攻擊，因為文獻［18，21］方法需要對選擇明文進行加密，在攻擊過程中需要對明文進行一定的控制，本文方法只需要獲得一定數(shù)量的隨機明文和其對應(yīng)能量跡就可實施攻擊，不需要攻擊者主動控制明文，所以不會受到此因素的影響。

表6 從無需碰撞閾值、無需攻擊模板、攻擊過程簡單、對重用掩碼方案具有高效性、可利用未發(fā)生碰撞的信息、攻擊者能夠不操作目標設(shè)備等6個方面對本文方法和文獻［18，21-22］方法進行對比，其中，√表示具備該性能優(yōu)勢，×表示不具備該性能優(yōu)勢。由表6可以看出，本文方法相比于已有方法具有一定的優(yōu)勢。

表6 4 種攻擊方法的性能對比Table 6 Performance comparison of four attack methods

4 結(jié)束語

本文針對使用重用掩碼技術(shù)的AES 算法，提出一種高效的隨機明文碰撞攻擊方法。利用能量跡中未發(fā)生碰撞的信息，采用重用掩碼AES 算法S 盒輸入的漢明距離和歐式距離的關(guān)系，從256 個密鑰異或值中找出正確的密鑰異或值。實驗結(jié)果表明，與改進型相關(guān)性碰撞攻擊、自適應(yīng)選擇明文碰撞攻擊和基于假設(shè)檢測的側(cè)信道碰撞攻擊方法相比，本文方法無需建立攻擊模板及計算碰撞閾值，并且加密的是隨機明文，實施簡單。由于筆者通過分析發(fā)現(xiàn)采用多組明文進行實驗可有效減少所需的明文總數(shù)，因此在后續(xù)工作中將研究明文組數(shù)對所需明文總數(shù)和成功率的具體影響，從而尋找到最優(yōu)的明文組數(shù)。