張國(guó)雙，陳曉，林東岱，劉鳳梅

（1.中國(guó)科學(xué)院信息工程研究所，北京 100093；2.中國(guó)科學(xué)院大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，北京 100049；3.信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100072）

1 引言

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

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

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

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

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

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

表1 ACORN 算法狀態(tài)恢復(fù)攻擊的結(jié)果對(duì)比

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

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

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

表2 符號(hào)解釋

2.2 ACORN 算法簡(jiǎn)介

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

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

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

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

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

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

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

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

圖2 ACORN v3 算法的原理

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

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

Step2計(jì)算并生成密鑰流比特。

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

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

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

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

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

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

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

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

性質(zhì)1～性質(zhì)5 的意義有以下幾個(gè)方面。

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

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

表3 控制比特取值與輸入比特對(duì)應(yīng)關(guān)系

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 復(fù)雜度分析

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

證畢。

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

對(duì)Nonce 重用三次、四次的情況，有以下分析結(jié)果。

對(duì)于Nonce 重用三次的情況，假設(shè)P0、P1和P2用相同的Nonce 進(jìn)行加密，為了盡可能使得到的方程是線性無(wú)關(guān)的，令P0、P1、P2滿足以下形式。

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

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

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

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

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

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

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

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

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

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

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