面向ACORN v3 消息認(rèn)證碼的隨機(jī)差分故障分析*

張國(guó)雙, 陳 曉, 王 安, 劉鳳梅

1. 中國(guó)科學(xué)院 信息工程研究所 信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京 100093

2. 中國(guó)科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 北京 100049

3. 北京理工大學(xué) 計(jì)算機(jī)學(xué)院, 北京 100081

4. 數(shù)據(jù)通信技術(shù)研究所, 北京 100191

1 引言

加密和認(rèn)證是密碼的兩個(gè)基本屬性. 現(xiàn)代網(wǎng)絡(luò)保密通信中, 幾乎所有的網(wǎng)絡(luò)安全協(xié)議都需要同時(shí)具備加密和認(rèn)證兩種功能. 2013 年, 國(guó)際密碼協(xié)會(huì)IACR (International Association for Cryptologic Research) 面向全球發(fā)起了征集認(rèn)證加密算法的CAESAR (Competition for Authenticated Encryption:Security, Applicability, and Robustness) 競(jìng)賽活動(dòng), 旨在遴選安全高效的認(rèn)證加密算法, 進(jìn)一步增強(qiáng)網(wǎng)絡(luò)保密通信的安全性. 整個(gè)競(jìng)賽活動(dòng)持續(xù)6 年時(shí)間, 最終有6 個(gè)算法勝出, ACORN v3 算法便是其中之一.

ACORN 算法由伍宏軍[1]提出, 采用特定設(shè)計(jì)的序列密碼結(jié)構(gòu), 是一個(gè)面向比特的輕量級(jí)認(rèn)證加密算法, 其新穎的設(shè)計(jì)和輕量化的高效實(shí)現(xiàn)特點(diǎn)引起了國(guó)內(nèi)外密碼學(xué)界的廣泛關(guān)注和研究興趣. ACORN 算法自發(fā)布以來(lái)歷經(jīng)三個(gè)版本[1–3], 目前的最新版本是ACORN v3. 當(dāng)前, 針對(duì)ACORN 算法安全性研究主要有以下幾類: 基于Nonce 重用的狀態(tài)恢復(fù)攻擊[4–7]、初始化輪數(shù)縮減的Cube 攻擊[8–13]、差分故障分析[14–17]、基于SAT 求解器密鑰/狀態(tài)恢復(fù)攻擊[18]以及其它類型的攻擊和分析[19–22].

差分故障分析是密碼分析的常用方法. 1997 年, Biham 和Shamir[23]首次將差分分析的思想引入到故障攻擊[24]中, 提出了差分故障分析的概念, 并對(duì)DES 類的密碼算法進(jìn)行了攻擊. Hoch 和Shamir[25]將差分故障分析應(yīng)用到序列密碼分析中, 其允許攻擊者通過(guò)利用激光槍或時(shí)鐘脈沖[26,27]等可以向內(nèi)部狀態(tài)注入1 比特或多比特故障, 然后通過(guò)分析正確密鑰流和錯(cuò)誤密鑰流的差異, 得到關(guān)于內(nèi)部狀態(tài)或密鑰的信息. 目前差分故障分析已經(jīng)應(yīng)用到一些序列密碼算法的分析中, 如Grain-128[28,29]、Trivium[30,31]、MICKEY 2.0[32,33]等. 相關(guān)研究結(jié)果[25–38]表明, 差分故障分析針對(duì)序列密碼的攻擊非常有效, 已經(jīng)成為密碼學(xué)研究的熱點(diǎn)之一. Parkash 等[14]基于特定位置硬故障注入的假設(shè), 給出了ACORN v1 和v2在Nonce 不重用情況下的故障攻擊; Siddhanti 等[15]基于SAT 求解器給出了ACORN v3 用于加密時(shí)的差分故障攻擊; Zhang 等[16,17]通過(guò)引入差分集的概念, 研究并給出了隨機(jī)故障注入模型下ACORN v2 和v3 用于加密時(shí)的故障攻擊, 指出由于加密時(shí)ACORN v3 的反饋函數(shù)較ACORN v2 簡(jiǎn)單, 相對(duì)于ACORN v2 來(lái)講, ACORN v3 更容易受到差分故障攻擊的威脅. 然而, 對(duì)于ACORN v3 用于認(rèn)證時(shí)的差分故障攻擊, 目前尚沒(méi)有相關(guān)研究結(jié)果.

本文針對(duì)ACORN v3 用于認(rèn)證時(shí)基于MAC 的差分故障分析進(jìn)行了研究, 主要貢獻(xiàn)有以下三個(gè)方面: 針對(duì)MAC 長(zhǎng)度有限造成唯一定位故障概率不高的問(wèn)題, 給出了提高唯一定位故障概率的交互驗(yàn)證策略和改進(jìn)的高概率優(yōu)先策略, 進(jìn)而給出了改進(jìn)的故障定位算法; 通過(guò)對(duì)ACORN v3 內(nèi)部結(jié)構(gòu)和變換規(guī)律的分析, 證明了認(rèn)證比特差分代數(shù)表達(dá)式的形式具有特定的規(guī)律, 據(jù)此大幅降低了方程求解中的猜測(cè)復(fù)雜度; 利用差分代數(shù)方法, 給出了由認(rèn)證比特差分建立關(guān)于內(nèi)部狀態(tài)低次方程的算法和基于方程求解的狀態(tài)恢復(fù)攻擊及復(fù)雜度評(píng)估, 進(jìn)一步完善了ACORN v3 的安全性分析結(jié)果.

文章其余部分安排如下: 第2 節(jié)給出了相關(guān)符號(hào)說(shuō)明和ACORN 算法簡(jiǎn)介; 第3 節(jié)給出了差分故障分析的攻擊模型和相關(guān)定義; 第4 節(jié)研究并給出了差分標(biāo)簽的確定性生成算法和概率生成算法; 第5 節(jié)研究了可唯一定位故障位置的條件, 給出了故障定位算法; 第6 節(jié)研究了ACORN v3 用于認(rèn)證時(shí)由輸出認(rèn)證比特建立的差分方程的形式, 給出了基于方程求解的狀態(tài)恢復(fù)攻擊及復(fù)雜度分析; 第7 節(jié)是結(jié)論與總結(jié).

2 符號(hào)說(shuō)明與ACORN 算法簡(jiǎn)介

2.1 符號(hào)說(shuō)明

本文使用的符號(hào)解釋如表1 所示. 本文約定所有計(jì)數(shù)從0 開始, 并且數(shù)據(jù)的左側(cè)為最低位, 右側(cè)為最高位.

表1 符號(hào)解釋Table 1 Notations

2.2 ACORN 算法簡(jiǎn)介

ACORN 算法利用128 比特的密鑰和128 比特Nonce 可以完成對(duì)長(zhǎng)度不超過(guò)264的明文和關(guān)聯(lián)數(shù)據(jù)的保護(hù), 并產(chǎn)生長(zhǎng)度不超過(guò)128 比特的認(rèn)證碼. 結(jié)構(gòu)上, ACORN 算法采用特定設(shè)計(jì)的序列密碼結(jié)構(gòu),由6 個(gè)不同的線性移存器和1 個(gè)4 比特的緩存器構(gòu)成293 比特狀態(tài)移存器, 整體上采用二次的反饋函數(shù),根據(jù)額外的輸入比特對(duì)內(nèi)部狀態(tài)進(jìn)行更新, 并使用二次的密鑰流生成函數(shù), 每一拍生成1 比特的密鑰, 其認(rèn)證加密過(guò)程包括初始化環(huán)節(jié)、關(guān)聯(lián)數(shù)據(jù)處理環(huán)節(jié)、加密環(huán)節(jié)和認(rèn)證碼生成環(huán)節(jié)共4 個(gè)步驟. 由于初始化環(huán)節(jié)、關(guān)聯(lián)數(shù)據(jù)處理環(huán)節(jié)以及加密環(huán)節(jié)在以下分析當(dāng)中并未涉及, 因此下面僅對(duì)ACORN v3 算法的認(rèn)證碼生成環(huán)節(jié)(原理如圖1 所示) 做簡(jiǎn)要介紹, 關(guān)于ACORN v3 的更詳細(xì)介紹可以參考文獻(xiàn)[1].

圖1 ACORN v3 認(rèn)證碼生成過(guò)程示意圖Figure 1 Schematic diagram of ACORN v3’s authentication code generation process

認(rèn)證比特生成函數(shù)zt=G(St):

更新比特生成函數(shù)ft=F(St):

其中, Maj(·) 和Ch(·) 是算法中用到的兩個(gè)基本的非線性函數(shù), 定義如下:

由于認(rèn)證碼生成環(huán)節(jié)的輸入比特mt恒為0(圖1 所示), 此時(shí)輸入比特mt對(duì)狀態(tài)更新過(guò)程不產(chǎn)生任何作用, 因此, 可以記認(rèn)證碼生成環(huán)節(jié)的狀態(tài)更新變換為:

則狀態(tài)更新變換的具體過(guò)程如下:

Step1: LFSR 狀態(tài)線性更新

Step2: 計(jì)算并生成認(rèn)證比特

Step3: 計(jì)算并生成狀態(tài)更新比特

Step4: 293 級(jí)移位寄存器狀態(tài)更新

易見, 認(rèn)證碼生成環(huán)節(jié)的狀態(tài)更新變換是可逆的. 在狀態(tài)更新過(guò)程中, 首先對(duì)當(dāng)前狀態(tài)進(jìn)行線性更新,然后根據(jù)更新后的狀態(tài)分別生成認(rèn)證比特和更新比特, 最后基于更新比特對(duì)293 級(jí)移存器狀態(tài)進(jìn)行非線性更新. 假設(shè)待生成的認(rèn)證碼的長(zhǎng)度為l, 則l比特認(rèn)證碼生成的偽代碼表示如下:

3 攻擊模型和相關(guān)定義

3.1 攻擊模型

在給出ACORN v3 的差分故障分析之前, 我們首先對(duì)文獻(xiàn)[7] 中提出的差分故障攻擊模型進(jìn)行簡(jiǎn)單介紹, 該模型中假設(shè)攻擊者完全掌握并可以訪問(wèn)密碼設(shè)備, 并且已知IV 和對(duì)應(yīng)的密鑰流, 攻擊者的目標(biāo)是通過(guò)向內(nèi)部狀態(tài)注入故障得到相應(yīng)的錯(cuò)誤密鑰流, 以期根據(jù)正確密鑰流和錯(cuò)誤密鑰流之間的關(guān)系獲得關(guān)于內(nèi)部狀態(tài)的信息, 進(jìn)而恢復(fù)密鑰或進(jìn)行偽造攻擊. 基于以上模型, 對(duì)攻擊者的能力作如下約定:

(1) 攻擊者可以利用初始密鑰和IV 或初始密鑰和不同的IV 重置密碼設(shè)備, 并可以多次重啟認(rèn)證碼生成過(guò)程;

(2) 攻擊者可以向認(rèn)證比特產(chǎn)生前的內(nèi)部狀態(tài)隨機(jī)注入1 比特故障, 但是不能選擇故障注入的位置;

(3) 攻擊者可以觀察每次產(chǎn)生的認(rèn)證碼.

注意到以上攻擊模型中, 我們假設(shè)攻擊者可以向認(rèn)證比特產(chǎn)生前的內(nèi)部狀態(tài)每次隨機(jī)注入一個(gè)故障,主要考慮是: 一方面由于ACORN v3 的關(guān)聯(lián)數(shù)據(jù)處理過(guò)程、加密過(guò)程和認(rèn)證碼生成過(guò)程由控制比特進(jìn)行分割, 造成每個(gè)過(guò)程的更新比特生成函數(shù)不同, 假設(shè)攻擊者可以利用這一差異所引起的硬件實(shí)現(xiàn)電路的變化判斷每個(gè)過(guò)程的起始時(shí)刻; 另一方面, 在差分故障分析中, 每次故障注入所能獲得的差分比特串長(zhǎng)度直接影響到故障定位的準(zhǔn)確率, 進(jìn)而影響到攻擊的復(fù)雜度, 因此總是希望每次故障注入所能夠得到的可利用比特串長(zhǎng)度盡可能的長(zhǎng), 由于ACORN v3 認(rèn)證碼的長(zhǎng)度有限且不超過(guò)128 比特, 為了提高故障定位的準(zhǔn)確率, 這里假設(shè)攻擊者可以向認(rèn)證比特產(chǎn)生前的內(nèi)部狀態(tài)注入故障, 并約定認(rèn)證碼的長(zhǎng)度為128 比特.

基于認(rèn)證碼的ACORN v3 差分故障攻擊包含離線階段和在線階段兩個(gè)步驟, 其中, 離線階段不需要運(yùn)行密碼設(shè)備, 直接根據(jù)算法工作原理計(jì)算和生成差分串; 在線階段需要反復(fù)運(yùn)行和多次重啟密碼設(shè)備,根據(jù)所產(chǎn)生正確的認(rèn)證碼和錯(cuò)誤的認(rèn)證碼定位故障注入的位置, 并建立關(guān)于內(nèi)部狀態(tài)的低次方程, 對(duì)這些方程進(jìn)行求解從而恢復(fù)內(nèi)部初始狀態(tài), 進(jìn)而嘗試進(jìn)行密鑰恢復(fù)或偽造攻擊. 具體為:

離線階段:

(1) 遍歷所有可能的故障注入位置, 由確定型算法或概率型算法計(jì)算對(duì)應(yīng)于每個(gè)故障注入位置的差分串;

(2) 計(jì)算每個(gè)差分串所對(duì)應(yīng)的標(biāo)簽.

在線階段:

(1) 運(yùn)行密碼設(shè)備, 利用初始的密鑰和IV 計(jì)算并生成正確的認(rèn)證碼;

(2) 基于相同的初始密鑰和IV 重啟和運(yùn)行密碼設(shè)備, 向認(rèn)證比特產(chǎn)生前的內(nèi)部狀態(tài)隨機(jī)注入1 比特故障, 計(jì)算并生成相應(yīng)的認(rèn)證碼, 重復(fù)以上過(guò)程并進(jìn)行多次故障注入;

(3) 由正確的認(rèn)證碼和錯(cuò)誤的認(rèn)證碼分別計(jì)算每次故障注入的差分比特串, 根據(jù)差分串的標(biāo)簽判斷可能的故障注入位置;

(4) 在確定了故障注入位置后, 由故障注入位置所對(duì)應(yīng)差分串以及差分比特串建立關(guān)于內(nèi)部狀態(tài)的方程組, 通過(guò)求解方程組嘗試恢復(fù)內(nèi)部狀態(tài).

3.2 相關(guān)定義

以上給出了基于認(rèn)證碼的ACORN v3 差分故障攻擊模型和步驟, 本節(jié)對(duì)所涉及到一些基本概念進(jìn)行定義.

由上面定義, 概率簽名Tτ由差分串?Zτ決定, 并且其每個(gè)分位的取值等于差分串對(duì)應(yīng)分位差分代數(shù)表達(dá)式等于0 的概率, 反映和刻畫了故障注入后輸出差分的特征. 如果取值為1, 表示該分位差分恒為0, 如果取值為0, 表示該分位差分恒為1, 即差分取值與內(nèi)部狀態(tài)S0無(wú)關(guān); 否則表示該分位差分以一定概率取值為0, 并且差分取值由內(nèi)部狀態(tài)S0決定. 確定性差分標(biāo)簽Dτ給出了Tτ中取值恒為0 或1 的分布情況, 而非確定性差分標(biāo)簽Uτ則給出了Tτ中取值屬于區(qū)間(0,1) 的分布情況. 例如, 對(duì)于例1中的差分串?Z12, 與其對(duì)應(yīng)的概率簽名T12、確定性差分標(biāo)簽D12以及非確定性差分標(biāo)簽U12分別如下:

以下在不引起混淆的情況下, 將確定性差分標(biāo)簽和非確定性差分標(biāo)簽分別簡(jiǎn)稱為確定性標(biāo)簽和非確定性標(biāo)簽, 并統(tǒng)稱為差分標(biāo)簽.

以上差分串和差分比特串的區(qū)別在于: 差分串是將內(nèi)部狀態(tài)S0視作符號(hào)變量, 差分串的每個(gè)分位是關(guān)于這些符號(hào)變量的代數(shù)表達(dá)式, 刻畫了特定故障注入下的輸出差分的特征, 據(jù)此來(lái)生成概率簽名和進(jìn)行故障定位; 差分比特串是由給定的內(nèi)部狀態(tài)S0∈GF(2)293通過(guò)計(jì)算得到的0/1 比特串, 根據(jù)差分比特串各分位取值可以建立關(guān)于內(nèi)部狀態(tài)的方程.

4 差分標(biāo)簽生成算法

本節(jié)討論計(jì)算和生成差分標(biāo)簽的方法, 由前面定義, 差分標(biāo)簽與概率簽名之間存在對(duì)應(yīng)關(guān)系, 而概率簽名可由差分串計(jì)算而得, 并且差分串是將內(nèi)部狀態(tài)S0視作符號(hào)變量, 其每個(gè)分位是關(guān)于這些符號(hào)變量的代數(shù)表達(dá)式, 對(duì)于任意故障注入位置τ, 差分串?Zτ可根據(jù)定義1進(jìn)行計(jì)算, 并且若差分串?Zτ的具體形式已知, 就可以根據(jù)上述定義計(jì)算相應(yīng)的概率簽名和差分標(biāo)簽, 具體算法不再贅述.

為了對(duì)故障進(jìn)行定位, 需要遍歷所有可能的故障注入位置τ, 0≤τ ≤292, 并計(jì)算相應(yīng)的差分串?Zτ和差分標(biāo)簽, 由文獻(xiàn)[16,36] 的研究和分析知, 對(duì)基于比特的移存器型密碼算法, 僅需考慮和計(jì)算故障注入位于各抽頭位置時(shí)所對(duì)應(yīng)的差分串即可, 對(duì)不屬于抽頭位置的故障注入的差分串可以由這些抽頭位置所對(duì)應(yīng)的差分串經(jīng)變換和平移而得到, 為此有以下命題.

以上命題1 說(shuō)明, 對(duì)于每個(gè)可能的故障注入位置τ, 我們不需要每次都根據(jù)定義來(lái)計(jì)算差分串?Zτ,僅需計(jì)算故障注入位于各抽頭位置時(shí)所對(duì)應(yīng)的差分串即可, 其它位置的差分串可以通過(guò)這些抽頭位置的差分串經(jīng)變換和平移來(lái)得到. 對(duì)于ACORN v3, 其抽頭位置集合

因此只需要計(jì)算差分串?Zτ(τ ∈C), 具體形式見附錄A.

注意到在計(jì)算差分標(biāo)簽時(shí), 需要根據(jù)差分串?Zτ各分位的代數(shù)表達(dá)式來(lái)計(jì)算Pr(?zτi=0), 若分位代數(shù)表達(dá)式是關(guān)于多個(gè)變?cè)姆蔷€性函數(shù), 此時(shí)精確的計(jì)算Pr(?zτi=0) 將變得非常耗時(shí); 另外, 在由符號(hào)計(jì)算方式生成差分串?Zτ時(shí), 隨著迭代拍數(shù)的增加, 由于內(nèi)存溢出等原因, 可能很難顯式地確定出各分位的代數(shù)表達(dá)式, 針對(duì)以上問(wèn)題, 考慮采用概率的方式, 通過(guò)隨機(jī)選擇N個(gè)初始狀態(tài), 不妨設(shè)N= 220, 由算法原理和故障注入位置τ直接計(jì)算差分比特串的各分位取值為0 的個(gè)數(shù)N0, 由N0/N作為對(duì)Pr(?zτi=0) 的估計(jì), 根據(jù)Pr(?zτi=0) 的取值對(duì)差分串?Zτ的形式進(jìn)行估計(jì), 具體如算法1.

算法1 差分標(biāo)簽的概率生成算法Input: 故障注入位置τ, 差分串長(zhǎng)度l, 參數(shù)N = 220 Output: 差分串?Zτ, 概率簽名Tτ, 確定性標(biāo)簽Dτ 以及非確定性標(biāo)簽Uτ 1 for i 從0 到l ?1 do 2 Ni0 ←0 3 end 4 for j 從0 到N ?1 do j ∈GF(2)293, 執(zhí)行ACORN v3 并計(jì)算Z ←(z0,z1,··· ,zl?1);6 根據(jù)初始狀態(tài)S0j 和故障注入位置τ, 執(zhí)行ACORN v3 并計(jì)算Zτ ←(zτ0,zτ1,··· ,zτl?1);7 由Z 和Zτ 計(jì)算?Zτ;8 for i 從0 到l ?1 do 5 隨機(jī)選擇初始狀態(tài)S0 9 if ?zτ i 等于0 then 10 Ni0 ←Ni0 +1;11 end 12 end 13 end 14 for i 從0 到l ?1 do 15 θτ i ←Ni 0/N;16 if θτ i = 0 或者θτi = 1 then i ←1 ?θτi 18 else 17 ?zτ 19 記差分串?Zτ 第i 分位的形式為?zτi;20 end 21 end 22 Tτ ←(θτ0,θτ1,··· ,θτl?1);23 根據(jù)Tτ 分別計(jì)算Dτ 和Uτ;24 Return ?Zτ, Tτ, Dτ, Uτ.

我們通過(guò)計(jì)算機(jī)實(shí)驗(yàn)的方式對(duì)算法1 的正確性進(jìn)行了驗(yàn)證, 實(shí)驗(yàn)結(jié)果顯示, 當(dāng)選擇l= 107 時(shí), 由算法1 所得到的各抽頭位置所對(duì)應(yīng)的差分串與附錄A 在形式上是一致的. 另外, 由算法1 得到的l= 128 時(shí)各抽頭位置τ ∈C對(duì)應(yīng)的差分標(biāo)簽見附錄B.

需要注意的是, 算法1 通過(guò)概率的方式根據(jù)Pr(?zτi= 0) 的取值來(lái)生成差分串?Zτ, 只是對(duì)差分串各分位是否恒為0 或1、亦或是關(guān)于內(nèi)部狀態(tài)的函數(shù)進(jìn)行估計(jì), 而并不能確定函數(shù)的具體表達(dá)式, 但這并不影響我們后面的分析和討論, 主要是因?yàn)? 一方面在故障定位階段只需要根據(jù)差分標(biāo)簽來(lái)判斷可能的故障注入位置, 并不需要知道每個(gè)分位的具體代數(shù)表達(dá)式, 另一方面在內(nèi)部狀態(tài)恢復(fù)階段, 為了由差分串各分位的代數(shù)表達(dá)式建立關(guān)于內(nèi)部狀態(tài)的低次代數(shù)方程, 我們選擇差分串長(zhǎng)度l= 107, 并且實(shí)驗(yàn)結(jié)果表明,當(dāng)l ≤110 時(shí), 由定義通過(guò)符號(hào)計(jì)算的方式可以精確的計(jì)算出差分串各分位的代數(shù)表達(dá)式, 因此, 在故障定位階段, 可以選擇l=128, 由算法1 通過(guò)概率的方式來(lái)計(jì)算差分標(biāo)簽; 在內(nèi)部狀態(tài)恢復(fù)階段, 選擇l=107由定義通過(guò)符號(hào)計(jì)算來(lái)生成差分串的具體形式.

5 定位故障位置

5.1 唯一定位故障位置

由前面差分故障攻擊模型, 當(dāng)故障隨機(jī)注入到內(nèi)部狀態(tài)中時(shí), 可以得到一條差分比特串?Aτ, 此時(shí)需要根據(jù)其與差分標(biāo)簽的關(guān)系, 對(duì)故障注入的位置進(jìn)行判斷和定位, 基本思想是通過(guò)對(duì)比差分比特串與差分標(biāo)簽各分位的取值和匹配關(guān)系, 來(lái)確定可能的故障注入位置.

定義5–7 實(shí)際上也給出了定位故障位置的具體方法, 即根據(jù)差分比特串的性質(zhì), 由差分比特串與差分標(biāo)簽的匹配關(guān)系來(lái)確定可能的故障注入位置. 在實(shí)際故障定位過(guò)程中, 我們更加關(guān)心故障注入位置是否可唯一定位, 以及可唯一定位的條件, 針對(duì)該問(wèn)題, 有以下結(jié)論.

引理1故障注入位置τ為可唯一定位故障位置的必要條件是: 不存在故障注入位置α ?=τ, 使得對(duì)任給ω ∈{i|dαi ?=?,0≤i ≤l ?1}都有dαω=dτω成立.

定理1對(duì)于ACORN v3, 每個(gè)故障注入位置都可以唯一定位的必要條件是差分串的長(zhǎng)度l ≥102.

定理1 說(shuō)明, 對(duì)于ACORN v3, 當(dāng)差分串長(zhǎng)度小于102 時(shí), 總存在故障位置不能唯一定位, 另外需要注意的是, 定理1 作為必要而非充分條件, 即使差分串的長(zhǎng)度l ≥102, 對(duì)于差分比特串?Aτ, 仍然可能存在#?(?Aτ)>1 的情況.

定理2對(duì)于ACORN v3, 故障注入位置τ為可唯一定位故障位置的充分條件是: 對(duì)于任意的故障注入位置α ∈[0,292],α ?=τ, 都存在ω ∈{i|dτi ?=?,0≤i ≤l ?1}使得dαω ?=?, 并且dαω ⊕dτω=1.

證明:由引理2 直接可得.

由定理2, 根據(jù)附錄B, 當(dāng)差分串長(zhǎng)度l ≥102 時(shí), ACORN v3 可唯一定位故障位置的個(gè)數(shù)與長(zhǎng)度l的對(duì)應(yīng)情況如表2.

表2 可唯一定位故障位置個(gè)數(shù)與長(zhǎng)度l 對(duì)應(yīng)表Table 2 Correspondence of number of fault location that can be uniquely located and length l

由表2 可以看出, 對(duì)于ACORN v3, 即使差分串長(zhǎng)度選擇為最大值128, 仍然有很多故障位置不是可唯一定位的. 需要說(shuō)明的是, 盡管某個(gè)故障注入位置τ不是可唯一定位的, 但是可能存在某些內(nèi)部狀態(tài)所對(duì)應(yīng)的差分比特串?Aτ是可以唯一定位故障的, 即#?(?Aτ)=1, 換言之, 故障位置τ是以一定概率可唯一定位的. 由上面討論, 基于確定性標(biāo)簽的故障定位算法如算法2 所示.

?

對(duì)于以上算法2, 我們通過(guò)計(jì)算機(jī)實(shí)驗(yàn)的方式對(duì)l= 128 時(shí)每個(gè)故障位置可唯一定位的概率進(jìn)行了估計(jì), 具體如表3.

以表3, 隨機(jī)選擇100 萬(wàn)個(gè)初始狀態(tài), 對(duì)每個(gè)故障位置可唯一定位的概率進(jìn)行統(tǒng)計(jì), 結(jié)果顯示, 對(duì)于所有可能的故障注入位置, 平均每次故障注入可唯一定位的概率為97.47%, 并且當(dāng)故障注入位置0≤τ ≤243 時(shí), 大部分故障注入位置可唯一定位的概率超過(guò)99%; 然而其中的個(gè)別位置, 尤其是當(dāng)τ ≥283 時(shí), 可唯一定位故障的概率很低. 另外, 對(duì)比表2 中當(dāng)l= 128 時(shí)可唯一定位故障位置的個(gè)數(shù)為124, 而表3中結(jié)果顯示可以以概率1 定位的故障位置為166, 造成該偏差主要是因?yàn)楸? 根據(jù)定理2(充分條件) 計(jì)算得到的是可唯一定位故障位置個(gè)數(shù)的下界所致.

表3 l = 128 時(shí)各故障位置可唯一定位的概率Table 3 Probability of each fault location could be uniquely located when l = 128

5.2 改進(jìn)的故障定位算法

以上討論了由確定性標(biāo)簽Dτ進(jìn)行唯一定位故障位置的情況, 結(jié)果顯示, 對(duì)于ACORN v3, 有很多故障位置不是可唯一定位的, 而是以一定概率可唯一定位的. 針對(duì)該問(wèn)題, 受文獻(xiàn)[17,22] 思想的啟發(fā), 本節(jié)給出利用非確定性標(biāo)簽Uτ以及不同故障注入位置所對(duì)應(yīng)的差分串之間的關(guān)系來(lái)改進(jìn)和提高唯一定位概率的方法, 最后給出改進(jìn)的故障定位算法.

交互驗(yàn)證策略通過(guò)研究發(fā)現(xiàn), 不同故障位置所對(duì)應(yīng)的差分串之間存在很多確定性的關(guān)系, 并且這些關(guān)系與內(nèi)部狀態(tài)無(wú)關(guān), 因此在故障位置定位過(guò)程中, 對(duì)于待定位的差分比特串?Aτ, 不僅可以利用?Aτ本身的信息, 還可以參考和利用已經(jīng)唯一定位的差分比特串的信息來(lái)輔助對(duì)?Aτ進(jìn)行定位. 以下是關(guān)于差分串的兩個(gè)關(guān)系.

對(duì)于差分串?Zα和?Zβ,α ?=β, 對(duì)應(yīng)的非確定性標(biāo)簽分別為Uα和Uβ, 則關(guān)系

以上RE(α,β) 表示差分串?Zα和?Zβ中代數(shù)表達(dá)式確定性相同的位置,RN(α,β) 表示差分串?Zα和?Zβ中代數(shù)表達(dá)式確定性不同的位置, 并且這些位置的取值均不為0 或1. 在對(duì)比特串?Aτ進(jìn)行故障定位時(shí), 基于這兩個(gè)關(guān)系可將?(?Aτ) 中的部分候選位置做進(jìn)一步的篩選, 從而提高唯一定位故障的概率.

例如, 對(duì)于差分比特串?A12和非確定性差分標(biāo)簽U12

則

改進(jìn)的高概率優(yōu)先策略給定差分比特串?Aτ, 已知#?(?Aτ)> 1, 根據(jù)定義8, 對(duì)所有的α ∈?(?Aτ) 分別計(jì)算C(α,?Aτ), 選擇使得C(α,?Aτ) 取值最大的α作為對(duì)故障位置τ的估計(jì).

基于以上討論, 下面給出改進(jìn)的故障定位算法.

算法3 改進(jìn)的故障定位算法Input: 差分比特串?Zτ0,?Zτ1,··· ,?Zτn?1, 差分串長(zhǎng)度l Output: 故障注入位置? = {α0,α1,··· ,αn?1}1 ? ←?;2 for i 從0 到n ?1 do 3 由?Zτi 根據(jù)確定性標(biāo)簽計(jì)算?(?Zτi);4 if ?(?Zτi) 中只包含一個(gè)候選位置αi then? ←? ∪{αi};6 else 5 7利用交互驗(yàn)證策略對(duì)?(?Zτi) 中的候選位置進(jìn)行排除;8 if 排除候選位置后?(?Zτi) 中只包含一個(gè)元素αi then? ←? ∪{αi};10 else 9 11 對(duì)?(?Zτi) 的每一個(gè)候選位置計(jì)算其與?Zτi 的相容度;12 記使相容度取值最大的候選位置為αi;13 ? ←? ∪{αi};14 end 15 end 16 end 17 Return ?.

對(duì)于算法3, 我們通過(guò)計(jì)算機(jī)實(shí)驗(yàn)的方式對(duì)l=128 時(shí)每個(gè)故障位置可唯一定位的概率進(jìn)行了計(jì)算, 具體如表4.

對(duì)比表3 和表4, 相比于僅利用確定性標(biāo)簽的故障定位算法2, 基于交互驗(yàn)證策略和改進(jìn)的高概率優(yōu)先策略的故障定位算法, 可唯一定位故障的概率有了顯著的提高, 平均每次故障注入可唯一定位的概率為99.85%, 并且當(dāng)τ ≥244 時(shí), 部分故障位置可唯一定位的概率有大幅改善和提高.

表4 改進(jìn)的各故障位置可唯一定位的概率Table 4 Improved probability of each fault location could be uniquely located

6 恢復(fù)內(nèi)部狀態(tài)

當(dāng)故障注入位置確定后, 就可以根據(jù)故障注入位置所對(duì)應(yīng)的差分串和差分比特串構(gòu)造關(guān)于初始狀態(tài)S0的方程, 當(dāng)進(jìn)行足夠多次的故障注入, 構(gòu)造了足夠多的關(guān)于狀態(tài)S0的方程后, 就可以通過(guò)方程求解來(lái)恢復(fù)初始狀態(tài)S0. 本節(jié)給出構(gòu)造方程的算法, 以及利用猜測(cè)確定技術(shù)和線性化技術(shù)求解方程的復(fù)雜度估計(jì).

6.1 差分方程形式分析

由前面討論, 差分串的每個(gè)分位是關(guān)于內(nèi)部初始狀態(tài)的函數(shù), 為了由差分串和輸出的認(rèn)證比特差分建立關(guān)于內(nèi)部狀態(tài)的低次方程, 下面對(duì)差分串各分位代數(shù)表達(dá)式的形式進(jìn)行分析.

性質(zhì)1對(duì)于Maj(x,y,z), 若輸入差分為(?x,?y,?z), 則輸出差分?Maj(?x,?y,?z) 滿足:

性質(zhì)2對(duì)于Ch(x,y,z), 若輸入差分為(?x,?y,?z), 則輸出差分?Ch(?x,?y,?z) 滿足:

(3) 當(dāng)100≤t ≤106 時(shí), ?zt作為關(guān)于狀態(tài)S0和新增變量V的函數(shù), 具有以下形式:

以上Lti表示t時(shí)刻第i分位的關(guān)于S0和V的線性表達(dá)式,i ∈{61,66,111,193,230,235};Ltj表示t時(shí)刻第j分位的差分關(guān)于?S0和?ω的線性表達(dá)式,j ∈{193,230,235};ak,b ∈GF(2).

由狀態(tài)差分?S0∈GF(2)293的任意性易知, 對(duì)于故障注入位置τ, 關(guān)于差分串?Zτ有以下結(jié)果.

(1) 當(dāng)0≤t ≤57 時(shí), ?zt是關(guān)于狀態(tài)S0的線性或仿射函數(shù);

(2) 當(dāng)58≤t ≤62 時(shí), ?zt作為關(guān)于狀態(tài)S0和新增變量V的函數(shù)具有式(1)的形式;

(3) 當(dāng)63≤t ≤99 時(shí), ?zt作為關(guān)于狀態(tài)S0和新增變量V的函數(shù)具有式(2)的形式;

(4) 當(dāng)100≤t ≤106 時(shí), ?zt作為關(guān)于狀態(tài)S0和新增變量V的函數(shù)具有式(3)的形式.

證明:由于向S0的第τ位引入故障, 因此?S0的第τ位為1, 其余分位全為0, 由命題2 和命題5 立即可得結(jié)論成立.

6.2 建立方程

前面對(duì)差分串分位代數(shù)表達(dá)的形式進(jìn)行了分析, 下面給出由故障注入位置所對(duì)應(yīng)的差分串和差分比特串構(gòu)建關(guān)于初始狀態(tài)的方程, 并利用猜測(cè)確定技術(shù)和線性化技術(shù)進(jìn)行方程求解的方法.

算法4 中, 由新增變量和輸出的認(rèn)證比特可以建立關(guān)于狀態(tài)S0的49 個(gè)二次方程; 另外, 實(shí)驗(yàn)數(shù)據(jù)表明, 當(dāng)差分串長(zhǎng)度為107 時(shí), 通過(guò)引入新增變量V, 一次故障注入平均可得到9.747 個(gè)線性方程和4.597個(gè)二次方程, 記#?=n, 那么由這n個(gè)故障注入平均可得到9.747n個(gè)線性方程和4.597n個(gè)二次方程.

可以看出, 隨機(jī)故障注入模型下, 通過(guò)計(jì)算機(jī)實(shí)驗(yàn)的方式對(duì)多次故障注入下所能得到的不同方程的個(gè)數(shù)進(jìn)行模擬統(tǒng)計(jì), 實(shí)驗(yàn)結(jié)果與理論值是一致的.

前面我們提到, 通過(guò)引入新增變量V可以使我們得到更多的線性方程, 通過(guò)計(jì)算發(fā)現(xiàn), 如果不引入新增變量V, 長(zhǎng)度為107 時(shí)所有差分串?Zτ中不同的線性表達(dá)式的個(gè)數(shù)為497, 不同的次數(shù)為2 的代數(shù)表達(dá)式的個(gè)數(shù)為1235, 不同的次數(shù)為3 的代數(shù)表達(dá)式的個(gè)數(shù)為189, 此時(shí), 進(jìn)行n次故障注入平均可以得到不同方程的情況如表6.

表6 n 次故障注入平均可以得到的不同方程個(gè)數(shù)(不引入新變量)Table 6 Average number of different equations obtained by n times of fault injection (without introducing new variables)

對(duì)比表5 和表6 不難看出, 通過(guò)引入新增變量V, 可有效的增加故障注入時(shí)可以建立的不同線性方程的個(gè)數(shù), 如果不引入新增變量, 將會(huì)得到許多二次方程和三次方程, 這將對(duì)后續(xù)的方程求解是十分不利的.

表5 n 次故障注入平均可以得到的不同方程個(gè)數(shù)Table 5 Average number of different equations obtained by n times of fault injection

6.3 方程求解

上面建立的方程中有很多二次方程, 下面給出利用猜測(cè)確定技術(shù)和線性化技術(shù)來(lái)對(duì)這些二次方程進(jìn)行線性化的方法, 進(jìn)而通過(guò)求解線性方程組來(lái)恢復(fù)初始狀態(tài), 并對(duì)整個(gè)過(guò)程的復(fù)雜度進(jìn)行分析.

線性化二次方程注意到以上二次方程的生成主要有兩種情形, 一是由新增變量和輸出的認(rèn)證比特建立的關(guān)于狀態(tài)S0的49 個(gè)二次方程; 二是根據(jù)故障注入位置τ, 由長(zhǎng)度為107 的差分串?Zτ和差分比特串?Aτ建立的關(guān)于S0和V的二次方程.

對(duì)于第一種情形產(chǎn)生的二次方程, 其具有以下形式:

由文獻(xiàn)[21], 函數(shù)Maj(x,y,z) 可以以3/4 的概率進(jìn)行線性化, 因此以上的二次方程可以以3/4 的概率進(jìn)行線性化.

復(fù)雜度分析假設(shè)故障注入次數(shù)為n,n次故障注入可以得到的線性方程和二次方程個(gè)數(shù)分別記為N1和N2, 由上面分析, 平均進(jìn)行0.713nbit 的猜測(cè)就可以將所有的二次方程線性化, 觀察式(1)–式(3)的形式, 式(1)至少以1/2 的概率得到一個(gè)線性方程, 式(2)至少以3/4 的概率得到一個(gè)線性方程, 式(3)至少以7/8 的概率得到一個(gè)線性方程, 因此N2個(gè)二次方程至少可以得到N2/2 個(gè)線性方程; 另外, 由新增變量和認(rèn)證比特可以建立49 個(gè)二次方程, 設(shè)需要線性化的方程個(gè)數(shù)為N3,N3≤49, 則可以得到的總的線性方程的個(gè)數(shù)滿足:

如果0.713n+N1+N2/2+N3≥342, 就可以通過(guò)求解線性方程的方式嘗試對(duì)S0和V進(jìn)行恢復(fù),整個(gè)過(guò)程的計(jì)算復(fù)雜度約為20.713·n+0.415·N3·c, 其中,c是求解342 比特變?cè)€性方程組的復(fù)雜度, 由文獻(xiàn)[39],c<219.95, 攻擊所需要的數(shù)據(jù)復(fù)雜度為128(n+1) bit, 存儲(chǔ)復(fù)雜度可忽略不計(jì). 具體故障注入次數(shù)與復(fù)雜度對(duì)應(yīng)如表7.

如果內(nèi)部狀態(tài)為S0被恢復(fù), 就可以恢復(fù)出ACORN v3 算法的初始狀態(tài), 進(jìn)而就可以對(duì)任意明文進(jìn)行加密, 并得到相應(yīng)的密文和認(rèn)證碼, 從而進(jìn)行偽造攻擊.

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

根據(jù)差分故障攻擊模型, 本文給出了基于MAC 的ACORN v3 隨機(jī)差分故障分析, 針對(duì)MAC 長(zhǎng)度有限所造成的唯一定位故障概率不高的問(wèn)題, 給出了提高唯一定位故障概率的交互驗(yàn)證策略和改進(jìn)的高概率優(yōu)先策略; 通過(guò)對(duì)ACORN v3 內(nèi)部結(jié)構(gòu)和變換規(guī)律的分析, 證明了認(rèn)證比特差分代數(shù)表達(dá)式的形式具有特定的規(guī)律, 據(jù)此大幅降低了方程求解過(guò)程中的猜測(cè)復(fù)雜度; 利用差分代數(shù)方法, 給出了由認(rèn)證比特差分建立關(guān)于內(nèi)部狀態(tài)低次方程的算法和基于方程求解的狀態(tài)恢復(fù)攻擊及復(fù)雜度評(píng)估, 進(jìn)一步完善了ACORN v3 的安全性分析結(jié)果.