基于Nonce 重用的ACORN v3 狀態恢復攻擊

張國雙，陳曉，林東岱，劉鳳梅

（1.中國科學院信息工程研究所，北京 100093；2.中國科學院大學網絡空間安全學院，北京 100049；3.信息保障技術重點實驗室，北京 100072）

1 引言

加密和認證是密碼學的2 個基本屬性。在現代網絡保密通信中，基于密碼構建信息系統對消息進行加密和認證處理，是實現數據機密性和認證性保護的有效途徑，然而由于使用不當或惡意敵手后門植入等，可能會造成Nonce 重復使用、未按規則返回明文等情況發生，從而為潛在敵手攻擊和分析密碼算法提供便利。Nonce 重用的狀態與密鑰恢復攻擊一般模型如圖1 所示，攻擊者通過植入后門，造成發送方使用相同的Nonce 對不同消息進行加密處理，從而獲得不同結構的明文所對應的不同密文。利用這些密文，可對密鑰或狀態進行恢復分析，一旦成功地恢復出密鑰或狀態，就可以對保密通信進行實時解密監聽或篡改偽造。

圖1 Nonce 重用的狀態與密鑰恢復攻擊一般模型

為進一步提升認證加密算法的安全強度，增強人們對認證加密算法的認識和信心，2013 年，國際密碼協會（IACR,International Association for Cryptologic Research）面向全球發起了征集認證加密算法的CAESAR（competition for authenticated encryption:security,applicability,and robustness），旨在遴選安全高效的認證加密算法。CAESAR 自2013年開始至2019 年結束持續6 年時間，最終有6 個算法勝出并作為認證加密算法的代表，ACORN v3算法便是其中之一。ACORN 算法由Wu[1]提出，是一個面向比特的輕量認證加密算法，并以其新穎的設計和輕量化高效實現引起了國內外密碼學界的廣泛關注和研究興趣。

ACORN 算法自發布以來歷經了3 個版本[1-3]，目前的最新版本是ACORN v3。針對ACORN 算法安全性的研究很多[4-19]。其中，關于ACORN 算法的狀態或密鑰恢復攻擊，Liu 等[4]根據ACORN v1的滑動特性，利用差分代數技術給出了Nonce 重用兩次時ACORN v1 的狀態恢復攻擊；Chaigneau 等[5]研究并給出了Nonce多次重用時ACORN v1的密鑰恢復攻擊；Wang 等[6]研究和評估了Nonce 重用情況下ACORN v2 的狀態恢復攻擊和復雜度；針對ACORN v2 和v3，Zhang 等[7]進一步研究并給出了Nonce 重用三次情況下的狀態恢復攻擊。

然而，在實際應用中，Nonce 重用本身是小概率事件，出現Nonce 多次重用的概率就更小，同時，密碼系統可能會采用一定的手段來減少Nonce 重用情況的發生。因此，攻擊所需要的Nonce 重用次數越多，則實際實施的難度越高，因此Nonce 重用次數的多少是此類攻擊是否容易實施的關鍵指標。

針對以上問題，本文給出了一種僅需Nonce 重用兩次的ACORN v3 狀態恢復攻擊，該攻擊通過對中間變量的猜測以期構造盡可能多關于內部狀態的線性方程。結果顯示，即使Nonce 僅重用兩次，對于ACORN v3 同樣存在低于窮搜索復雜度的狀態恢復攻擊，攻擊所需的計算復雜度為122.52c，其中，c是求解293 bit 變元線性方程組的復雜度，數據復雜度和存儲復雜度可忽略不計。此外，基于本文方法對Nonce 多次重用時的安全性進行分析發現，由于ACORN v3 采用了較之前版本復雜的濾波函數，從而有效避免了通過增加Nonce 重用次數來顯著降低狀態恢復攻擊復雜度的潛在問題。研究結果也進一步印證了ACORN 算法安全性聲明中強調的Nonce 不能被重用的要求。表1 給出了ACORN算法狀態恢復攻擊的結果對比。

表1 ACORN 算法狀態恢復攻擊的結果對比

2 符號說明與ACORN 算法簡介

2.1 符號說明

本文使用的符號解釋如表2 所示。本文約定所有計數從0 開始，并且數據的左側為最低位，右側為最高位。

表2 符號解釋

2.2 ACORN 算法簡介

ACORN 算法利用128 bit 的密鑰和128 bit Nonce 可以完成對長度不超過642 的明文和關聯數據的保護，并產生長度不超過128 bit 的認證標簽。ACORN 采用特定設計的序列密碼結構，由6 個不同的線性移位寄存器和一個4 bit 的緩存器構成293 bit 狀態移位寄存器，整體采用二次的反饋函數，根據額外的輸入比特對內部狀態進行更新，并使用二次的密鑰流生成函數，每一拍生成1 bit 的密鑰，其認證加密過程包含以下4 個環節。

1) 初始化環節。加載密鑰和Nonce 并生成初始狀態。

2) 關聯數據處理環節。處理關聯數據并進行內部狀態更新。

3) 加密環節。對明文加密并進行內部狀態更新。

4) 認證碼生成環節。用于生成認證標簽。

與ACORN v1 相比，ACORN v2 對初始化過程進行了修改，并調整了4 個環節迭代的拍數；相對于ACORN v2，ACORN v3 對密鑰流生成函數和反饋函數進行了調整。以下簡要介紹與本文分析有關的ACORN v3 的主要變換環節。ACORN v3 算法的原理如圖2 所示。

圖2 中，kt、ft和mt分別是密鑰比特、狀態更新比特和輸入比特；at和bt是2 個控制比特，影響ft的計算；maj(?)和ch(?)是定義在GF(2)上的2 個三元布爾函數；密鑰流生成函數和更新比特生成函數分別用于生成密鑰比特和狀態更新比特。令t時刻ACORN v3 的內部狀態，則有密鑰流生成函數k t=G(St)。

ACORN v3 的狀態更新變換包括LFSR（linear feedback shift register）狀態線性更新、計算并生成密鑰流比特、計算并生成非線性反饋比特和293 級移位寄存器狀態更新。記狀態更新變換為

圖2 ACORN v3 算法的原理

則狀態更新變換的具體過程如下。

Step1LFSR 狀態線性更新。

Step2計算并生成密鑰流比特。

Step3計算并生成狀態更新比特。

Step4293 級移位寄存器狀態更新。

ACORN v3 的4 個環節（初始化環節、關聯數據處理環節、加密環節和認證碼生成環節）中控制比特at、bt取值與輸入比特mt的對應關系如表3所示。

K和N分別表示128 bit 的密鑰和Nonce，K′表示將K的最高比特位取反其余比特位保持不變，AD 和P分別表示待處理的關聯數據和明文數據。密文比特ct=pt⊕kt，認證碼T由最后lbit 的密鑰流給定。

3 ACORN v3 狀態差分特性分析

本節挖掘了maj(?)和ch(?)的4 條性質，并結合文獻[5]中提出的一條性質，共同推出了ACORN v3加密過程的狀態差分傳播規律。

3.1 ACORN 算法函數性質研究

maj(?)和ch(?)是ACORN 算法中用到的2 個最基本的非線性函數。2015 年，Chaigneau 等[5]在對ACORN v1 的狀態恢復攻擊中發現，maj(?)函數具有性質1。

性質1～性質5 的意義有以下幾個方面。

1) 給出了函數maj(?)和ch(?)特定形式輸入差分所對應的輸出差分的形式。例如，對于函數maj(x,y,z)，若輸入差分Δx=1，Δy=Δz=0，由性質1 可知，對應的輸出差分為y⊕z。

2) 給出了由輸出構建關于輸入的線性方程的方法。例如，對于函數ch(x,y,z)，若已知輸出a和b，并且Δx=1，Δy=Δz=0，則由性質4 可以建立關于(x,y,z)的2 個線性方程，分別為y⊕z=a⊕b和(a⊕b)x=a⊕z。

表3 控制比特取值與輸入比特對應關系

3) 給出了函數maj(?)的另外2 種表示形式及其線性化的方法，主要用于第4 部分由猜測確定的方式來構建和提取線性方程。

3.2 ACORN v3 狀態差分傳播規律

由前面算法介紹可知，在ACORN v3 的加密過程中，每拍生成的密鑰比特不進行反饋，狀態更新變換根據輸入的明文比特對內部狀態進行更新。此時在選擇明文攻擊條件下，攻擊者可以通過控制明文輸入來影響內部狀態，從而得到對其攻擊有利的內部狀態和密鑰流，進而對內部狀態或密鑰進行攻擊。下面，假設攻擊者可以控制明文輸入比特的差分，對ACORN v3 加密過程的內部狀態差分傳播情況進行分析。

設初始內部狀態差分ΔS0=(0,0,…,0)，明文輸入比特差分tmΔ 滿足

圖3 部分內部狀態差分傳播示意

同理可以得出101≤ t≤148時內部狀態差分ΔSt的形式，詳細推理過程這里不再給出，具體形式如附錄（式(7)～式(14)）所示。以上分析說明，ACORN v3 算法加密過程的內部狀態差分具有特定的傳播規律。對于Nonce 重用的情況，假設關聯數據相同，由于使用了相同的密鑰和Nonce，因此加密起始時刻的內部狀態相同，若加密的明文差分滿足式(1)的形式，則上述狀態差分傳播規律同樣成立，對此有以下結論。

命題1對于ACORN v3 算法，假設用相同的密鑰和 Nonce 分別對消息M0=AD||P0和消息M1=AD||P1進行處理，記加密過程起始時刻的內部狀態差分為ΔS0，若明文 P0和 P1的前49 bit 差分為1，后99 bit 差分為0，其余位置差分不做要求，則當1≤ t≤148時，內部狀態差分ΔSt具有式(2)～式(14)的形式和傳播規律。

4 ACORN v3 算法的狀態恢復攻擊

本節基于上文所述內部狀態差分傳播規律，利用差分代數技術，給出由密鑰流差分通過猜測確定的方式建立關于內部狀態線性方程的方法和具體過程，進而對ACORN v3 算法的狀態恢復攻擊和復雜度進行評估。

4.1 密鑰流生成函數特性分析

為了減少硬件開銷，ACORN v3 算法采用了基于比特的二次布爾函數作為密鑰流生成函數，且形式上比較簡單，關于該函數本文給出以下性質。

上述證明中，對于每一種情況的猜測方式可能是不唯一的。例如，4)中也可以通過猜測來構建線性方程，這里僅給出其中的一種，更多的不再列出。性質6 同時給出了通過猜測確定方式，由密鑰流及其差分建立關于內部狀態線性方程的基本思想和方法，具體如下。若已知輸出的密鑰流和經線性更新后的內部狀態差分，假設內部狀態差分的第235、193、230 分位的不全為0，并且第12、61、111、66 分位的差分均為0，由性質6 可知，此時進行1 bit 猜測，可以得到關于內部狀態的3 個線性方程?；诖?，下面給出Nonce 重用兩次的ACORN v3 狀態恢復攻擊。

4.2 Nonce 重用兩次的ACORN v3 狀態恢復攻擊

4.3 復雜度分析

算法1 需要2(148 +l) bit 的密鑰流，其中l≥0，其計算復雜度主要由Step2 和Step3 決定，Step1 和Step5 的計算復雜度可忽略不計，假設Step2 需要進行nbit 猜測，Step3 中求解293 bit 變元線性方程組的復雜度記為c，并假設Step4 中候選值的個數相對于nbit 的猜測是可忽略的，則攻擊算法1 的計算復雜度約為2nc。下面對Step2 需要進行猜測的比特個數進行估計。前148 bit 用于Step2 線性方程的構建，并且k0,t的最后lbit 用于Step4 中對候選值進行驗證和篩選，本文選擇l=293，因此算法1 所需的數據復雜度為2 ×1 48 +293 bit 的選擇明文；Step1 和Step5 的計算復雜度可忽略不計，記Step3 中求解293 bit 變元線性方程組的復雜度為c，Step2 平均進行123.25 bit的猜測，可以得到294.75 個關于內部狀態的線性方程，假設線性無關的方程的個數是293，則Step3有唯一解，此時Step2 和Step3 的計算復雜度約為2123.25c；如果Step2 中進行122.25 bit 的猜測，則平均可以得到292.75 個線性方程，假設這些方程是線性無關的，則Step2 和Step3 的計算復雜度約為2122.5c；另外，假設對于Step2 中錯誤的猜測在Step3中以很大概率無解，即Step4 中候選值的個數遠小于Step2 的猜測量，則Step4 的計算復雜度相對于2122.5c是可忽略的，綜合可得，算法1 的計算復雜度約為 2122.5c，算法所需的存儲復雜度可忽略不計。

證畢。

4.4 Nonce 多次重用的安全性分析

對Nonce 重用三次、四次的情況，有以下分析結果。

對于Nonce 重用三次的情況，假設P0、P1和P2用相同的Nonce 進行加密，為了盡可能使得到的方程是線性無關的，令P0、P1、P2滿足以下形式。

其中，n是需要猜測的變量αt的個數，此時通過引入49+n個新增變量，可以得到294+5n個線性方程和49 個二次方程，由文獻[7]可知，這49 個二次方程能夠以20.32 的復雜度進行線性化，對應得到49 個線性方程，此時若要使方程有唯一解，需294+5n+49≥293+49+n，即n≥0，因此需要猜測的變量個數為98，對應的狀態恢復攻擊的復雜度為 220.3×298c=2118.3c。

對于Nonce 重用四次的情況，根據上述分析，令需要猜測的變量αt的個數為0，需要猜測的變量βt的個數為n，此時通過引入 98 個新變量，可以得147+2n個線性方程和98 個二次方程，98 個二次方程能夠以40.62 的復雜度進行線性化，對應得到98 個線性方程，當n≥73時，147 +2n+98 ≥293 +98恒成立，此時選擇P0、P1、P2、P3形式如下。

通過對73 個變量βt進行猜測和對98 個二次方程的線性化，恰好可以得到391 個線性方程，對應的狀態恢復攻擊的復雜度為 240.6×273c=2113.6c。

類似地，可以對Nonce 重用更多次的情況進行分析，狀態恢復攻擊復雜度估計如表4 所示。

表4 Nonce 多次重用的狀態恢復攻擊復雜度估計

表4 中可以選擇l=293。由表4 的數據和結果可以看出，相對于之前的版本（ACORN v2 和ACORN v1），由于ACORN v3 采用了相對復雜的濾波函數，增加了冗余，使通過增加Nonce 重用次數來大幅降低攻擊復雜度的方法很難奏效，從而有效降低了Nonce 多次重用時的安全風險。

4.5 基于已知初始狀態的偽造攻擊

由于ACORN 算法采用了特定設計的序列密碼結構，因此初始狀態對算法整體安全性的影響至關重要，對于早期的ACORN v1，由于其初始化過程是可逆的，一旦恢復初始狀態，就可以利用初始化過程的逆變換逐步求解和恢復密鑰，從而實現對密碼算法的完全破解；對于ACORN v2和ACORN v3，由于采用了不可逆的初始化過程，很難由初始狀態來恢復和求解密鑰，盡管如此，攻擊者仍然可以利用所恢復的初始狀態實現對任意消息的加密和認證標簽的生成，從而進行偽造攻擊。

5 結束語

本文分析了ACORN v3在Nonce重用兩次情況下的安全性，結果表明，基于差分代數的方法，通過對中間變量進行猜測來對ACORN v3 的密鑰流生成函數進行線性化，可以由密鑰流及其差分構造足夠多的關于內部狀態的線性方程，進而通過求解線性方程組實現對ACORN v3 的狀態恢復攻擊。盡管本文的分析結果遠沒到實際可行的程度，但進一步完善了ACORN v3算法Nonce重用條件下的安全性分析結果。另外，基于本文方法對Nonce 多次重用情況的安全性進行的分析和評估發現，由于ACORN v3 采用了較之前版本復雜的濾波函數，避免了通過增加Nonce 重用次數來顯著降低狀態恢復攻擊復雜度的潛在問題。最后，關于ACORN 算法的可證明安全性研究是很必要的，可以從差分和線性指標的可控性等方面對算法的可證明安全性進行研究，這將是下一步研究工作的重點。

附錄 101≤t≤1 48時內部狀態差分ΔS t形式