基于Nonce 重用的ACORN v3 狀態(tài)恢復攻擊

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

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

1 引言

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

圖1 Nonce 重用的狀態(tài)與密鑰恢復攻擊一般模型

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

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

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

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

表1 ACORN 算法狀態(tài)恢復攻擊的結果對比

2 符號說明與ACORN 算法簡介

2.1 符號說明

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

表2 符號解釋

2.2 ACORN 算法簡介

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

1) 初始化環(huán)節(jié)。加載密鑰和Nonce 并生成初始狀態(tài)。

2) 關聯(lián)數(shù)據(jù)處理環(huán)節(jié)。處理關聯(lián)數(shù)據(jù)并進行內部狀態(tài)更新。

3) 加密環(huán)節(jié)。對明文加密并進行內部狀態(tài)更新。

4) 認證碼生成環(huán)節(jié)。用于生成認證標簽。

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

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

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

圖2 ACORN v3 算法的原理

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

Step1LFSR 狀態(tài)線性更新。

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

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

Step4293 級移位寄存器狀態(tài)更新。

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

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

3 ACORN v3 狀態(tài)差分特性分析

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

3.1 ACORN 算法函數(shù)性質研究

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

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

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

2) 給出了由輸出構建關于輸入的線性方程的方法。例如，對于函數(shù)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) 給出了函數(shù)maj(?)的另外2 種表示形式及其線性化的方法，主要用于第4 部分由猜測確定的方式來構建和提取線性方程。

3.2 ACORN v3 狀態(tài)差分傳播規(guī)律

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

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

圖3 部分內部狀態(tài)差分傳播示意

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

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

4 ACORN v3 算法的狀態(tài)恢復攻擊

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

4.1 密鑰流生成函數(shù)特性分析

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

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

4.2 Nonce 重用兩次的ACORN v3 狀態(tài)恢復攻擊

4.3 復雜度分析

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

證畢。

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

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

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

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

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

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

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

表4 Nonce 多次重用的狀態(tài)恢復攻擊復雜度估計

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

4.5 基于已知初始狀態(tài)的偽造攻擊

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

5 結束語

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

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