輕量級(jí)分組密碼算法DoT 的模板攻擊

孫家異，韋永壯

（桂林電子科技大學(xué)廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西桂林 541004）

0 概述

2002 年，CHARI 等人［1］利用能量消耗與正在處理的數(shù)據(jù)有關(guān)這一基本事實(shí)［2］，提出了模板攻擊的概念。模板攻擊方法使用多元正態(tài)分布對(duì)采集到的數(shù)據(jù)特征進(jìn)行刻畫(huà)，在模板攻擊中，假設(shè)攻擊者可以對(duì)被攻擊設(shè)備的特征進(jìn)行刻畫(huà)，如攻擊者擁有一臺(tái)與被攻擊設(shè)備類(lèi)型相同的設(shè)備，利用該設(shè)備，攻擊者根據(jù)不同數(shù)據(jù)和固化的密鑰來(lái)執(zhí)行加密操作，即觀(guān)察加密設(shè)備的具體物理實(shí)現(xiàn)，并記錄對(duì)應(yīng)的能耗信息，然后將與（數(shù)據(jù)，密鑰）相對(duì)應(yīng)的能量跡進(jìn)行分組，估算多元正態(tài)分布的均值向量和協(xié)方差矩陣，并由此發(fā)起攻擊。模板攻擊是一種重要的側(cè)信道攻擊方法，與傳統(tǒng)的簡(jiǎn)單能量分析［3］、相關(guān)性能量分析［4］和差分能量分析［5］等相比，模板攻擊在實(shí)際的密碼算法破譯中擁有更強(qiáng)的區(qū)分能力，因此，其受到研究人員的廣泛關(guān)注［6-7］。

近年來(lái)，隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，各種資源受限的設(shè)備（如無(wú)線(xiàn)傳感器等）被廣泛應(yīng)用。由于資源受限設(shè)備大多計(jì)算與存儲(chǔ)資源少，因此在數(shù)據(jù)安全存儲(chǔ)、傳輸或處理方面存在嚴(yán)重的安全隱患。為解決資源受限環(huán)境下的數(shù)據(jù)安全問(wèn)題，輕量級(jí)密碼技術(shù)［8-10］應(yīng)運(yùn)而生。2019 年，JAGDISH 等人提出一種新的輕量級(jí)分組密碼算法DoT［11］。與著名的輕量級(jí)分組密碼算法SIMON［12］相比，DoT在軟件與硬件實(shí)現(xiàn)方面更為簡(jiǎn)單。DoT 密碼算法整體采用SP 結(jié)構(gòu)［13］以及輕型的線(xiàn)性及非線(xiàn)性運(yùn)算部件，在硬件實(shí)現(xiàn)時(shí)僅需993個(gè)等效門(mén)。設(shè)計(jì)者聲稱(chēng)DoT 算法可以抵御多種傳統(tǒng)數(shù)學(xué)攻擊，如線(xiàn)性密碼攻擊［14］、差分密碼攻擊［15］等，然而，該算法在實(shí)現(xiàn)中是否足以抵御模板攻擊仍有待探索。本文基于漢明重量模型，結(jié)合DoT 算法的結(jié)構(gòu)及S 盒的特點(diǎn)，將DOT算法S 盒的輸出作為中間值進(jìn)行密鑰恢復(fù)，提出一種針對(duì)DoT 算法的模板攻擊方法。

1 DoT 算法描述

DoT 密碼算法［11］整體結(jié)構(gòu)采用SPN 設(shè)計(jì)，其明文分組為64 bit，根據(jù)密鑰數(shù)據(jù)長(zhǎng)度的不同將該算法分為2 種版本，即80 bit 的DOT-80 和128 bit 的DOT-128。對(duì)于不同的密鑰長(zhǎng)度，DoT 算法使用不同的密鑰編排算法。DoT 算法的加密和解密過(guò)程均使用31 輪的輪函數(shù)迭代運(yùn)算，每一個(gè)輪函數(shù)包括輪密鑰加（AddRoundkey）、半字節(jié)代換（SubCells）和P 置換（Permutation）3 個(gè)步驟，如圖1 所示。

圖1 DoT 密碼算法的輪函數(shù)Fig.1 Round function of DoT cipher algorithm

1.1 輪密鑰加與密鑰編排

DoT 密碼算法的主密鑰是80 bit，記為KEY=K79K78K77…K2K1K0，它的低64 位作為子密鑰與明文分組進(jìn)行比特異或操作。在算法的每一輪加密操作中，KEY 按照如下的密鑰編排進(jìn)行更新：

1）KEY 循環(huán)左移13 bit：

KEY ＜＜＜13

2）低8 位K7K6…K2K1K0通過(guò)S 盒后將得到的結(jié)果與原數(shù)據(jù)進(jìn)行替換：

3）將KEY 中的K63K62K61K60K59與輪常數(shù)RCi進(jìn)行異或操作并替換原比特：

1.2 半字節(jié)代換

半字節(jié)代換是一個(gè)非線(xiàn)性變換操作，其將內(nèi)部狀態(tài)中的每一個(gè)半字節(jié)非線(xiàn)性變換為另一個(gè)半字節(jié)。DoT 中使用4 bit 密碼S 盒，即4 bit 輸入和4 bit輸出，如表1 所示。

表1 4 bit 密碼S 盒Table 1 4 bit cryptographic S-box

1.3 置換層

置換層的功能是加強(qiáng)數(shù)據(jù)擴(kuò)散，其本質(zhì)上是一個(gè)線(xiàn)性部件。DoT 算法中采用字節(jié)的置換層包含2 次置換和1 次循環(huán)移位，如圖1 所示。

2 模板攻擊

2.1 模板攻擊的基本思想

密碼設(shè)備所產(chǎn)生的物理泄露種類(lèi)多樣，如時(shí)間序列［16］、能耗［17］和電磁輻射［18］等。近年來(lái)的側(cè)信道分析結(jié)果表明，能耗攻擊仍然是使用最多的一種攻擊。模板攻擊分析設(shè)備在實(shí)現(xiàn)加密操作過(guò)程中發(fā)生的物理泄露，這種泄露在統(tǒng)計(jì)上依賴(lài)所涉及密鑰操作的中間值，從而使得從測(cè)量信息泄露所得的數(shù)據(jù)來(lái)推斷密鑰成為可能。需要注意的是，實(shí)現(xiàn)模板攻擊有一個(gè)重要的假設(shè)前提，即攻擊者能夠完全控制一個(gè)和被攻擊設(shè)備幾乎完全類(lèi)似的設(shè)備，可以不受限制地多次調(diào)用該設(shè)備，且參數(shù)由自己設(shè)定。這個(gè)假設(shè)前提有可能實(shí)現(xiàn)，原因是被攻擊設(shè)備通常是標(biāo)準(zhǔn)設(shè)備，與其類(lèi)似的設(shè)備可以通過(guò)合法途徑獲得。

在上述假設(shè)的基礎(chǔ)上，攻擊者可以通過(guò)該設(shè)備對(duì)算法中間值的漢明重量構(gòu)建模板，然后用同樣的方法在被攻擊設(shè)備運(yùn)行時(shí)獲取能耗信息并與已構(gòu)建好的模板進(jìn)行匹配。匹配效果最好的模板對(duì)應(yīng)的漢明重量就是可能正確的漢明重量，然后根據(jù)每一次的匹配結(jié)果得出所有可能的候選密鑰集合，進(jìn)行取交集操作，最后篩選出的一個(gè)密鑰就是所求正確密鑰。

2.2 基于漢明重量的模板攻擊

模板攻擊分為模板刻畫(huà)和密鑰恢復(fù)2 個(gè)階段［19］，本書(shū)將進(jìn)行具體闡述。

2.2.1 模板刻畫(huà)

攻擊者選定一個(gè)中間值，求出該中間值所有可能的漢明重量，通過(guò)使用一組密鑰和明文計(jì)算出一個(gè)漢明重量為mi的中間值，使用這組數(shù)據(jù)讓加密算法在密碼芯片中執(zhí)行重復(fù)加密操作并采集該過(guò)程中泄露的能耗信息，即能量跡，然后求出所得能量跡的均值，將其作為刻畫(huà)該漢明重量的模板，這個(gè)模板僅由一個(gè)均值向量表示，對(duì)于每一個(gè)可能的漢明重量，都需建立一個(gè)均值向量模板。

假設(shè)攻擊者使用密鑰key 和明文pi計(jì)算得出中間值的漢明重量為HWi，在設(shè)備中重復(fù)加密m次，采集到m條能量跡，每一條能量跡上都選取相同的n個(gè)點(diǎn)，這時(shí)攻擊者就得到一個(gè)m×n的能耗矩陣M。假設(shè)第j條能量跡為{T(j，1)，T(j，2)，…，T(j，n)}(1≤j≤m)，令M(i，k)表示漢明重量為i的均值向量模板M的第k個(gè)樣本點(diǎn)，則：

攻擊者計(jì)算出每個(gè)樣本點(diǎn)的均值，通過(guò)計(jì)算得到漢明重量為i(0 ≤i≤b)的模板對(duì)應(yīng)的均值向量為：

其中，b表示中間值的長(zhǎng)度，對(duì)于長(zhǎng)度為bbit 的中間值，攻擊者共需刻畫(huà)b+1 個(gè)模板。

2.2.2 密鑰恢復(fù)

攻擊者在目標(biāo)設(shè)備上用所求密鑰對(duì)同一個(gè)明文mj進(jìn)行多次重復(fù)加密，采集每一次加密所得的能量跡并求均值得出均值能量跡T′={T′1，T′2，…，T′n}。然后，攻擊者使用最小二乘法［20］求得能量跡T′和每個(gè)模板的相似程度，根據(jù)最大似然原理［21］，與T′相似程度最高的模板對(duì)應(yīng)的漢明重量HWi就與所求中間值的漢明重量相同。攻擊者再用所有可能的密鑰對(duì)該明文mj進(jìn)行加密并計(jì)算得到中間值的漢明重量HWk，如果HWi=HWk，則將對(duì)應(yīng)的密鑰加入集合Mk中。通過(guò)多次選取明文m1，m2，…，mj得出多個(gè)密鑰集合M1，M2，…，Mk，最后對(duì)這些集合進(jìn)行取交集操作，當(dāng)交集為一個(gè)密鑰時(shí)，該密鑰即為正確密鑰。

值得注意的是，測(cè)量得到的每一條能量跡都含有噪聲，如果攻擊者不對(duì)能量跡作預(yù)處理，噪聲可能會(huì)嚴(yán)重影響密鑰恢復(fù)階段的成功率。因此，攻擊者要對(duì)加密進(jìn)行多次重復(fù)操作，通過(guò)求均值的方式來(lái)降低噪聲的影響。最后，使用均值能量跡與模板進(jìn)行匹配以恢復(fù)正確密鑰。

3 針對(duì)DoT 分組密碼的模板攻擊

本文針對(duì)DoT 的軟件實(shí)現(xiàn)進(jìn)行攻擊測(cè)試。在攻擊中，選擇DoT 第一輪執(zhí)行S 盒的輸出作為中間值，并采用漢明重量模型構(gòu)建模板。因?yàn)镈oT 在設(shè)備上執(zhí)行時(shí)是每2個(gè)S盒相合并以進(jìn)行運(yùn)算，所以是以字節(jié)為單位，每一個(gè)字節(jié)為8 bit，因此，需要分別構(gòu)建0，1，…，8這9種漢明重量模板。攻擊過(guò)程如圖2 所示。

圖2 模板攻擊流程Fig.2 Procedure of template attack

針對(duì)DoT 的模板攻擊步驟如下：

步驟1選擇一個(gè)用于建立模板的密鑰k，使用不同的明文與密鑰k執(zhí)行加密運(yùn)算，找出加密過(guò)程中使中間值的漢明重量分別為0，1，…，8 的明文m0，m1，…，m8，測(cè)得加密過(guò)程的能量跡并選擇4 000 個(gè)采樣點(diǎn)。然后分別用明文m0，m1，…，m8與密鑰k進(jìn)行加密，對(duì)每一個(gè)明文都進(jìn)行1000 次的加密操作，最后求均值得到9 種漢明重量模板p0，p1，…，p8。

步驟2隨機(jī)選取一個(gè)明文m0′，與所求密鑰進(jìn)行1 000 次加密操作并測(cè)出能量跡，同樣選擇4 000 個(gè)采樣點(diǎn)求均值得出該明文的均值能量跡t。

步驟3采用最小二乘法，將所得均值能量跡t與所建模板p0，p1，…，p8進(jìn)行匹配，得出明文m0′對(duì)應(yīng)中間值的漢明重量p0′，根據(jù)所得漢明重量計(jì)算出所有可能的中間值，最后對(duì)這些中間值進(jìn)行逆運(yùn)算得出所有可能的密鑰集合N1={k1，k2，…，kn}。其中，n為所得漢明重量對(duì)應(yīng)的所有可能中間值的個(gè)數(shù)，如表2 所示。

表2 漢明重量i 的可能中間值數(shù)量Table 2 The number of possible median values of Hamming weight i

步驟4選取另一個(gè)不同的明文m1′重復(fù)步驟2 和步驟3，得出另一個(gè)密鑰集合N2，將其與步驟3 中求出的集合進(jìn)行取交集操作。通過(guò)多次選取不同明文mi，得出對(duì)應(yīng)密鑰集合ni，再進(jìn)行取交集操作，直至得到的交集為一個(gè)密鑰，則該密鑰即為正確的密鑰。

4 測(cè)試結(jié)果與分析

本文測(cè)試環(huán)境選用WindowsXP 系統(tǒng)，算法實(shí)現(xiàn)使用MathMagic 側(cè)信道分析儀，其中，處理器選用STC89C52，并用MM_SCA 軟件進(jìn)行波形分析。

在測(cè)試過(guò)程中，在MathMagic 側(cè)信道分析儀的STC89C52 處理器上實(shí)現(xiàn)DoT 算法。將采樣率設(shè)置為1GS/s，可以準(zhǔn)確地獲取加密過(guò)程中的能耗泄露信息，通過(guò)MM_SCA 軟件對(duì)獲取的能耗曲線(xiàn)進(jìn)行分析。首先，進(jìn)行模板創(chuàng)建得到9 種漢明重量的能耗曲線(xiàn)并作為模板，如圖3 所示；然后，采集波形并用最小二乘法將其與模板進(jìn)行匹配，如圖4 所示；最后，通過(guò)加密算法的逆運(yùn)算恢復(fù)出候選密鑰集合。

圖3 模板曲線(xiàn)Fig.3 Template curves

圖4 波形匹配Fig.4 Waveforms matching

本文在STC89C52 處理器上進(jìn)行實(shí)驗(yàn)，選擇6 組明文和一個(gè)固定的密鑰，如下：

在實(shí)際攻擊中，真正的密鑰是未知的，本文中的真正密鑰用來(lái)驗(yàn)證實(shí)驗(yàn)結(jié)果是否正確。在恢復(fù)第一個(gè)字節(jié)時(shí)，用6 組明文的第一個(gè)字節(jié)(0xA4，0x96，0x33，0xCF，0xF0，0x21)與密鑰的第一個(gè)字節(jié)進(jìn)行加密獲得6 條能量跡，在每一條能量跡上同樣選取4 000個(gè)采樣點(diǎn)，且每一條能量跡都是通過(guò)加密1000次得到的均值能量跡。然后，分別用這6 條能量跡與模板曲線(xiàn)進(jìn)行匹配得到中間值對(duì)應(yīng)的漢明重量5、4、4、4、5、1。根據(jù)第一個(gè)漢明重量計(jì)算出每一個(gè)可能的中間值以及每一個(gè)可能的密鑰組成集合，再根據(jù)第二個(gè)漢明重量得到相應(yīng)集合，將其與第一個(gè)集合進(jìn)行取交集操作，在進(jìn)行第四次實(shí)驗(yàn)后，所得交集只剩下0x11，即為正確密鑰。

在第一次測(cè)試時(shí)，模板匹配得到HW(y)=5，已知明文首字節(jié)為0xA4，通過(guò)篩選后的密鑰集合為：

在第二次測(cè)試時(shí)，模板匹配得到HW(y)=4，已知明文首字節(jié)為0x96，通過(guò)篩選后的密鑰首字節(jié)集合為：

在第三次測(cè)試時(shí)，模板匹配得到HW(y)=4，已知明文首字節(jié)為0x33，通過(guò)篩選后的密鑰首字節(jié)集合為：

在第四次測(cè)試時(shí)，模板匹配得到HW(y)=4，已知明文首字節(jié)為0xCF，通過(guò)篩選后的密鑰首字節(jié)集合為：

在第五次測(cè)試時(shí)，模板匹配得到HW(y)=5，已知明文首字節(jié)為0xF0，通過(guò)篩選后的密鑰首字節(jié)集合為：

在第六次測(cè)試時(shí)，模板匹配得到HW(y)=1，已知明文首字節(jié)為0x21，通過(guò)篩選后的密鑰首字節(jié)集合為：

經(jīng)過(guò)上述6 次篩選測(cè)試，最終捕獲正確的8 bit密鑰。

5 模板攻擊抵御方法

任何對(duì)抗側(cè)信道攻擊的方法都是使加密設(shè)備消耗的能量不依賴(lài)密碼算法執(zhí)行加密時(shí)出現(xiàn)的中間值，掩碼技術(shù)［22］是一種著名的防護(hù)對(duì)策，其通過(guò)隨機(jī)化設(shè)備處理的中間值來(lái)實(shí)現(xiàn)這一目標(biāo)。掩碼防護(hù)方法通常在算法級(jí)上進(jìn)行防御，其優(yōu)點(diǎn)是可以直接作用在密碼算法的輸入或輸出的中間狀態(tài)值上，而不必改變密碼設(shè)備的硬件器件。本文提出一種對(duì)DoT密碼S 盒的輸入和輸出進(jìn)行掩碼防護(hù)的方法。通常情況下可以將S 盒分為軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)2 種方式。文獻(xiàn)［23］指出掩碼的密碼硬件實(shí)現(xiàn)可能會(huì)降低其實(shí)現(xiàn)速度。因此，本文采用軟件實(shí)現(xiàn)方法對(duì)DoT算法進(jìn)行掩碼防護(hù)。

DoT 算法的S 盒軟件實(shí)現(xiàn)是通過(guò)使用查找表T，對(duì)于每個(gè)輸入變量v，其輸出都和表T 中的某個(gè)數(shù)據(jù)相對(duì)應(yīng)。因此，可以對(duì)表T 加Mask 來(lái)進(jìn)行掩碼保護(hù)。首先，隨機(jī)生成一個(gè)掩碼值m，使得輸入變量變成m⊕v，為了使S 盒的輸出也被掩碼防護(hù)，需要計(jì)算得出一個(gè)新的掩碼S 盒，用S′表示，原S 盒用S表示，S′需要滿(mǎn)足S′(v⊕m)=S(v)⊕m′，其中，m′在后續(xù)還原數(shù)據(jù)時(shí)用到。要保證S′的輸出異或m′后能轉(zhuǎn)變?yōu)樵瓉?lái)的數(shù)據(jù)S（v），如圖5 所示。

圖5 DoT 掩碼后的圖形化描述Fig.5 Graphical description of masked DoT

基于以上掩碼方法，本文針對(duì)DoT 密碼算法進(jìn)行編譯實(shí)現(xiàn)，并進(jìn)行相應(yīng)的模板攻擊。注意到，掩碼中引入了隨機(jī)數(shù)，導(dǎo)致敵手無(wú)法通過(guò)模板攻擊中的中間值計(jì)算直接捕獲正確密鑰，實(shí)際測(cè)試結(jié)果也證實(shí)了這一點(diǎn)。

6 結(jié)束語(yǔ)

本文基于漢明重量模型，利用DoT 算法結(jié)構(gòu)及密碼S 盒的特點(diǎn)，提出一種針對(duì)DoT 算法的模板攻擊方法。實(shí)驗(yàn)結(jié)果表明，DoT 算法在該模板攻擊下具有脆弱性。為了抵御這一攻擊，本文設(shè)計(jì)一種DoT 算法S盒掩碼方案，測(cè)試結(jié)果驗(yàn)證了其有效性。下一步將針對(duì)DoT 密碼算法設(shè)計(jì)高效的門(mén)限掩碼防護(hù)方案。