張國雙, 陳 曉, 王 安, 劉鳳梅

1. 中國科學院 信息工程研究所 信息安全國家重點實驗室, 北京 100093

2. 中國科學院大學 網絡空間安全學院, 北京 100049

3. 北京理工大學 計算機學院, 北京 100081

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

1 引言

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

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

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

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

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

2 符號說明與ACORN 算法簡介

2.1 符號說明

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

表1 符號解釋Table 1 Notations

2.2 ACORN 算法簡介

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

圖1 ACORN v3 認證碼生成過程示意圖Figure 1 Schematic diagram of ACORN v3’s authentication code generation process

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

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

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

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

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

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

Step2: 計算并生成認證比特

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

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

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

3 攻擊模型和相關定義

3.1 攻擊模型

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

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

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

(3) 攻擊者可以觀察每次產生的認證碼.

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

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

離線階段:

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

(2) 計算每個差分串所對應的標簽.

在線階段:

(1) 運行密碼設備, 利用初始的密鑰和IV 計算并生成正確的認證碼;

(2) 基于相同的初始密鑰和IV 重啟和運行密碼設備, 向認證比特產生前的內部狀態(tài)隨機注入1 比特故障, 計算并生成相應的認證碼, 重復以上過程并進行多次故障注入;

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

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

3.2 相關定義

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

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

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

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

4 差分標簽生成算法

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

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

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

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

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

算法1 差分標簽的概率生成算法Input: 故障注入位置τ, 差分串長度l, 參數(shù)N = 220 Output: 差分串?Zτ, 概率簽名Tτ, 確定性標簽Dτ 以及非確定性標簽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 并計算Z ←(z0,z1,··· ,zl?1);6 根據(jù)初始狀態(tài)S0j 和故障注入位置τ, 執(zhí)行ACORN v3 并計算Zτ ←(zτ0,zτ1,··· ,zτl?1);7 由Z 和Zτ 計算?Zτ;8 for i 從0 到l ?1 do 5 隨機選擇初始狀態(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τ 分別計算Dτ 和Uτ;24 Return ?Zτ, Tτ, Dτ, Uτ.

我們通過計算機實驗的方式對算法1 的正確性進行了驗證, 實驗結果顯示, 當選擇l= 107 時, 由算法1 所得到的各抽頭位置所對應的差分串與附錄A 在形式上是一致的. 另外, 由算法1 得到的l= 128 時各抽頭位置τ ∈C對應的差分標簽見附錄B.

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

5 定位故障位置

5.1 唯一定位故障位置

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

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

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

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

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

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

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

由定理2, 根據(jù)附錄B, 當差分串長度l ≥102 時, ACORN v3 可唯一定位故障位置的個數(shù)與長度l的對應情況如表2.

表2 可唯一定位故障位置個數(shù)與長度l 對應表Table 2 Correspondence of number of fault location that can be uniquely located and length l

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

?

對于以上算法2, 我們通過計算機實驗的方式對l= 128 時每個故障位置可唯一定位的概率進行了估計, 具體如表3.

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

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

5.2 改進的故障定位算法

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

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

對于差分串?Zα和?Zβ,α ?=β, 對應的非確定性標簽分別為Uα和Uβ, 則關系

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

例如, 對于差分比特串?A12和非確定性差分標簽U12

則

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

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

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

對于算法3, 我們通過計算機實驗的方式對l=128 時每個故障位置可唯一定位的概率進行了計算, 具體如表4.

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

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

6 恢復內部狀態(tài)

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

6.1 差分方程形式分析

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

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

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

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

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

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

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

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

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

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

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

6.2 建立方程

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

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

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

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

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

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

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

6.3 方程求解

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

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

對于第一種情形產生的二次方程, 其具有以下形式:

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

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

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

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

7 結束語

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