王明興 ，苗三立 ，朱明佳

(1.中國電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所，北京 102209；2.密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100878)

0 引言

序列密碼是一種對(duì)稱密碼算法，即加密密鑰和解密密鑰是相同的。序列密碼的經(jīng)典結(jié)構(gòu)包括兩個(gè)部件：驅(qū)動(dòng)部件和密鑰流輸出部件，驅(qū)動(dòng)部件通過迭代運(yùn)算更新內(nèi)部狀態(tài)，輸出部件抽取一部分內(nèi)部狀態(tài)的比特值，經(jīng)過復(fù)雜運(yùn)算產(chǎn)生密鑰流。加密時(shí)，密鑰流和明文異或產(chǎn)生密文，解密時(shí)，密鑰流和密文異或產(chǎn)生明文。通俗地講，序列密碼算法可以認(rèn)為是分組密碼的密鑰擴(kuò)展算法。

序列密碼的一個(gè)結(jié)構(gòu)特點(diǎn)是必然有內(nèi)部狀態(tài)，這使序列密碼容易受到時(shí)間存儲(chǔ)折中攻擊(Time Memory Data Tradeoff，TMD)，為了抵抗這種攻擊，通常要求序列密碼的內(nèi)部狀態(tài)的長度至少是密鑰長度的兩倍，例如序列密碼Grain[1]、Grain-128a[2]系列密碼算法，它們的內(nèi)部狀態(tài)是密鑰長度的兩倍，而Trivium 算法[3]的內(nèi)部狀態(tài)大于密鑰長度的兩倍。這導(dǎo)致序列密碼在硬件實(shí)現(xiàn)時(shí)所占用的硬件資源代價(jià)過大，例如Trivium 算法的硬件面積是2 580 門，不適用于資源受限、低功耗、物聯(lián)網(wǎng)等新的應(yīng)用場景。

為了既能抵抗TMD 攻擊，又能減小內(nèi)部狀態(tài)的長度，研究人員最近幾年提出了“小狀態(tài)”輕量級(jí)序列密碼研究。那些能夠抵抗TMD 攻擊且內(nèi)部狀態(tài)的長度小于密鑰長度的兩倍的輕量級(jí)序列密碼，稱為小狀態(tài)輕量級(jí)序列密碼(Small State Lightweight Stream Cipher)。

本文介紹了四個(gè)小狀態(tài)的輕量級(jí)序列密碼算法，依次是Sprout[4]、Fruit-80[5]、Plantlet[6]、Lizard[7]；主要介紹它們的設(shè)計(jì)理念和最新的分析結(jié)果，來發(fā)現(xiàn)存在的問題，總結(jié)研究成果，促進(jìn)小狀態(tài)的輕量級(jí)序列密碼的研究。

1 輕量級(jí)序列密碼介紹

本文介紹的四個(gè)算法都是輕量級(jí)序列密碼，都是試圖在小狀態(tài)的前提下，設(shè)計(jì)安全的密碼算法，它們整體結(jié)構(gòu)高度相似，都基于Grain 算法的驅(qū)動(dòng)結(jié)構(gòu)，采用線性或者非線性反饋移位寄存器(Linear/Nonlinear Feedback Shift Register，LFSR/NFSR)的串聯(lián)結(jié)構(gòu)，見圖1 虛線部分。LFSR 會(huì)影響NFSR,反之，LFSR 不受NFSR 的影響，后續(xù)的分析表明，這樣的結(jié)構(gòu)特點(diǎn)帶有安全隱患。以下分別描述各個(gè)算法的設(shè)計(jì)特點(diǎn)。

圖1 序列密碼Grain 算法簡圖

1.1 Sprout 算法

Sprout 算法是ARMKNECHT F 等人[4]在2015 年提出的第一個(gè)小狀態(tài)的輕量級(jí)序列密碼，其核心設(shè)計(jì)思想是，通過把內(nèi)部狀態(tài)分成2|K|等價(jià)類，使得TMD 攻擊每次至少考慮一個(gè)等價(jià)類，這里|K|是密鑰長度。實(shí)現(xiàn)這一思想的方法是密鑰一直參與內(nèi)部狀態(tài)的迭代過程。而Sprout 算法通過在Grain 結(jié)構(gòu)的基礎(chǔ)上增設(shè)一個(gè)輪密鑰函數(shù)，使得密鑰不僅參與算法初始化過程，而且參與密鑰流的產(chǎn)生過程，達(dá)到了密鑰一直參與內(nèi)部狀態(tài)的更新的目的。

Sprout 算法的驅(qū)動(dòng)部件是40 bit 長的LFSR 串聯(lián)上一個(gè)40 bit 長的NFSR，以及輪密鑰函數(shù)和計(jì)數(shù)器。密鑰長度80 bit，初始向量70 bit，一個(gè)初始向量產(chǎn)生的密鑰流不超過240bit。初始化過程中輸出密鑰流比特反饋參與移位寄存器的運(yùn)算，初始化輪數(shù)320輪，初始化完成之后，每一拍輸出1 bit 密鑰流。

1.2 Fruit-80 算法

GHAFARI V A 等人[8]于2016 年提出了Fruit 輕量級(jí)序列密碼，F(xiàn)ruit 可以看作是Sprout 算法的升級(jí)版本。隨后的公開分析結(jié)果表明，該算法的主要結(jié)構(gòu)是抵抗密鑰恢復(fù)攻擊的，但是前提條件是某些參數(shù)的選取要適當(dāng)；于是Fruit 的升級(jí)版算法Fruit-v2被提出[9]。設(shè)計(jì)者提出了四方面的改進(jìn)：使用了新的輪函數(shù)，修改了Sprout 的弱點(diǎn)；使用新的初始化方案來抵抗相關(guān)密鑰攻擊，防止密鑰輸出過程中線性移位寄存器的內(nèi)部狀態(tài)出現(xiàn)全零狀態(tài)；增加了線性反饋移位寄存器的階數(shù)，以產(chǎn)生周期更長的密鑰流序列；減少了反饋函數(shù)和輸出函數(shù)的項(xiàng)數(shù)。

2018 年Fruit 設(shè)計(jì)者接受了文獻(xiàn)[10]的建議，即在算法運(yùn)算過程中初始向量IV 一直參與混淆，而且還提出了限制使用每一個(gè)密鑰產(chǎn)生的密鑰流的長度的改進(jìn)措施，最終提出了Fruit-80 輕量級(jí)序列密碼[5]。其LFSR 長度是43 bit，NFSR 長度是37 bit，密鑰長度是80 bit，初始向量70 bit，每個(gè)密鑰和初始向量IV 所產(chǎn)生的密鑰流的長度不超過243bit，而且初始向量IV 不能重復(fù)使用。

1.3 Plantlet 算法

輕量級(jí)序列密碼Plantlet 是MIKHALEV V 等人[6]于2017 年提出的，它也可以看作是Sprout 算法的升級(jí)版。其密鑰長度80 bit，初始向量長度90 bit，內(nèi)部狀態(tài)101 bit，初始化輪數(shù)320 輪,設(shè)計(jì)安全強(qiáng)度是80 bit。

該算法硬件代價(jià)小，內(nèi)部狀態(tài)小，吞吐率高，密鑰非易失性存儲(chǔ)(Non-Volatile Memory，NVM)，在計(jì)算過程中可以持續(xù)讀取。與Sprout 算法和Fruit 算法相比，它有兩方面的改進(jìn)：一是輪密鑰不再同時(shí)依賴于密鑰和當(dāng)前狀態(tài)，而是只依賴于密鑰；二是線性反饋移位寄存器在初始化過程和密鑰流產(chǎn)生過程中使用的是不同的線性反饋移位寄存器。

1.4 Lizard 算法

輕量級(jí)序列密碼Lizard 是HAMANN M 等人[7]在2017 年提出的面向藍(lán)牙、無線局域網(wǎng)、超文本傳輸協(xié)議的應(yīng)用場景的輕量級(jí)序列密碼，密鑰長度是120 bit，初始向量64 bit，內(nèi)部狀態(tài)是121 bit，提供80 bit 安全強(qiáng)度。初始化輪數(shù)256 輪。

該算法突出的特點(diǎn)是，每一個(gè)密鑰和初始向量對(duì)(K，IV)限制產(chǎn)生的密鑰流長度是218bit，它的驅(qū)動(dòng)部件是兩個(gè)非線性反饋移位寄存器的串聯(lián)結(jié)構(gòu)，密鑰在初始化過程中兩次參與運(yùn)算，Lizard 的能耗特別低，只有2.1 μW。

不同算法的各項(xiàng)指標(biāo)對(duì)比見表1。不難發(fā)現(xiàn)，這四個(gè)輕量級(jí)序列密碼的硬件面積比Trivium 算法的一半還要小，因?yàn)閮?nèi)部狀態(tài)越小，硬件面積越小。算法的安全目標(biāo)都是80 bit。綜合而言，F(xiàn)ruit 算法的運(yùn)算效率和硬件代價(jià)都較為優(yōu)越，非常適合資源受限的應(yīng)用場景。

表1 不同算法各項(xiàng)安全指標(biāo)匯總表

2 輕量級(jí)序列密碼安全性分析結(jié)果

2.1 Sprout 算法分析結(jié)果

2015 年，LALLEMAND V 等人[11]宣稱，Sprout 的密鑰恢復(fù)攻擊的時(shí)間復(fù)雜度是270，他們聯(lián)合使用分別征服攻擊和猜測確定攻擊技術(shù)，主要是利用了移位寄存器的尺寸小，以及受輪密鑰非線性影響的更新函數(shù)與輪密鑰本身的依賴關(guān)系不夠密切的特點(diǎn)。

在當(dāng)年的印度密碼學(xué)年會(huì)上，BANIK S[12]指出，如果猜測50 bit 的內(nèi)部狀態(tài)，剩下的內(nèi)部狀態(tài)的比特值可以使用SAT 求解器恢復(fù)，基于這個(gè)假設(shè)，給出了一個(gè)區(qū)分攻擊，隨機(jī)選擇240個(gè)初始向量IV，存儲(chǔ)復(fù)雜度是248。由于LFSR 只影響NFSR，反之不受影響，那么，平均存在230個(gè)初始向量IV 使得LFSR的內(nèi)部狀態(tài)在密鑰流階段出現(xiàn)全零的情況，基于這一點(diǎn)，密鑰恢復(fù)攻擊的時(shí)間復(fù)雜度相當(dāng)于266.7次加密運(yùn)算，而存儲(chǔ)復(fù)雜度忽略不計(jì)。

在SAC2015 會(huì)議上，ESGIN M F 等人[13]也指出，聯(lián)合使用猜測確定技術(shù)和分別征服攻擊，Sprout 算法的TMD 的存儲(chǔ)復(fù)雜度為280-a，a ≤40，需要執(zhí)行271-a次加密運(yùn)算和2a次查表運(yùn)算得到2abit 密鑰流；猜測確定攻擊的時(shí)間復(fù)雜度相當(dāng)于268次加密運(yùn)算，存儲(chǔ)復(fù)雜度忽略不計(jì)。

2.2 Fruit 算法分析結(jié)果

HAMANN M 等人[10]指出Fruit-v1 和Fruit-v2 沒有達(dá)到80 bit 的安全性，他們發(fā)現(xiàn)了264個(gè)弱密鑰，利用移位寄存器的特定狀態(tài)和初始化過程的可逆性，進(jìn)行了TMD 攻擊，可以恢復(fù)密鑰。TODO Y 等人[14]也指出Fruit-80 的設(shè)計(jì)策略，即每一對(duì)密鑰和初始向量(K，IV)至多產(chǎn)生243bit 密鑰流，對(duì)安全而言是不夠的。他們利用擴(kuò)展了的相關(guān)攻擊，發(fā)現(xiàn)輪密鑰的引入具有周期性，只要找到高相關(guān)的多維線性掩碼逼近密鑰流輸出函數(shù)，利用不同初始向量產(chǎn)生的密鑰流，在時(shí)間復(fù)雜度為277.8702、存儲(chǔ)復(fù)雜度為243+21的條件下，可以恢復(fù)全輪的Fruit-80 密鑰。

2.3 Plantlet 算法分析結(jié)果

TODO Y 等人[14]指出，如果一對(duì)密鑰初始向量(K，IV)產(chǎn)生的密鑰流的長度為253bit，利用擴(kuò)展的相關(guān)攻擊可以恢復(fù)全輪的Plantlet 算法的密鑰。而Plantlet 算法的設(shè)計(jì)者限制一對(duì)密鑰、初始向量(K，IV)可以使用密鑰流的長度為230bit，顯然這有利于增強(qiáng)算法的安全性。MAITRA S 等人[15]對(duì)Plantlet 算法進(jìn)行了差分錯(cuò)誤攻擊(Differential Fault Attack，DFA)，所謂差分錯(cuò)誤攻擊，是指在FPGA 電路板卡上，使用物理手段使得算法的某些特殊狀態(tài)的比特值發(fā)生翻轉(zhuǎn)，通過分析翻轉(zhuǎn)前后的不同密鑰流之間的關(guān)系，來恢復(fù)內(nèi)部狀態(tài)。MAITRA S 等人指出只需四個(gè)錯(cuò)誤就可以實(shí)際地恢復(fù)內(nèi)部狀態(tài)，進(jìn)而恢復(fù)密鑰。但是需要指出的是，錯(cuò)誤信號(hào)的注入條件苛刻，不能說明算法在正常運(yùn)行的情況下存在安全弱點(diǎn)。

2.4 Lizard 算法分析結(jié)果

BANIK S 等人[16]發(fā)現(xiàn)，進(jìn)行258次隨機(jī)試驗(yàn)，可以找到264個(gè)三元組(K，IV0，IV1)，使得兩個(gè)密鑰、初始向量對(duì)(K，IV0)、(K，IV1)產(chǎn)生相同的密鑰流?；谶@種不同的初始向量產(chǎn)生移位關(guān)系的密鑰流序列，對(duì)Lizard 算法進(jìn)行了區(qū)分攻擊，計(jì)算復(fù)雜度是251.5次加密運(yùn)算，存儲(chǔ)復(fù)雜度是276.6。進(jìn)而，基于初始向量的碰撞性，恢復(fù)223 輪的密鑰的時(shí)間復(fù)雜度為269。MAITRA S 等人[17]對(duì)Lizard 進(jìn)行了時(shí)間存儲(chǔ)折中攻擊，恢復(fù)內(nèi)部狀態(tài)的預(yù)計(jì)算復(fù)雜度為267，在線時(shí)間復(fù)雜度是254，但是由于初始化過程不可逆，因此不能恢復(fù)密鑰。SIDDHANTI A 等人[18]對(duì)Lizard 進(jìn)行了差分錯(cuò)誤攻擊，至少需要五個(gè)錯(cuò)誤才能恢復(fù)內(nèi)部狀態(tài)，但是也沒有恢復(fù)密鑰。

總結(jié)目前的分析結(jié)果，對(duì)輕量級(jí)序列密碼的設(shè)計(jì)建議如下：

(1)輪密鑰應(yīng)線性地影響更新函數(shù)，降低輪密鑰的某些比特值被非線性函數(shù)零化掉的風(fēng)險(xiǎn)。

(2)兩個(gè)移位寄存器的長度(分別為40 bit)都太小，應(yīng)至少長50 bit，這樣猜測確定攻擊才沒有優(yōu)勢。

(3)建議使用兩個(gè)NFSR 串聯(lián)，而不是LFSR 和NFSR 的串聯(lián)。LFSR 的線性關(guān)系在輕量級(jí)算法中產(chǎn)生了安全隱患，顯然，Lizard 算法的安全性明顯高一些。

(4)初始向量與密鑰一樣都在初始化過程和密鑰流產(chǎn)生過程參與運(yùn)算，這樣初始向量和密鑰會(huì)混淆和擴(kuò)散得更加充分，更能抵抗TMD 攻擊。

(5)改變傳統(tǒng)的每次加密運(yùn)算輸出1 bit 密鑰流的方式，例如，移位寄存器每連續(xù)移位16 步，輸出它們的異或運(yùn)算和作為1 bit 密鑰流，能有效增加猜測確定攻擊的難度。

(6)根據(jù)算法實(shí)際的使用場景，限制一個(gè)密鑰、初始向量對(duì)(K，IV)產(chǎn)生的密鑰流序列的長度，這樣的密鑰流越短，算法的安全強(qiáng)度越高。

3 討論

本文介紹的輕量級(jí)序列密碼，嚴(yán)格意義上講都是不安全的。因?yàn)榕cGrain 算法相比，在內(nèi)部狀態(tài)減小的情況下，對(duì)算法的反饋函數(shù)、密鑰流輸出函數(shù)、密鑰和初始向量的引入方式以及對(duì)密鑰流的使用長度的設(shè)定都提出了很高的設(shè)計(jì)要求，設(shè)計(jì)者很難多方面兼顧。

序列密碼的小狀態(tài)的設(shè)計(jì)理念值得肯定，因?yàn)檫@樣的設(shè)計(jì)利于算法的輕量化，便于滿足實(shí)際場景的需求；但是這種基于已有驅(qū)動(dòng)模型不斷增設(shè)新的部件、復(fù)雜化的設(shè)計(jì)方法，例如增加輪密鑰函數(shù)、改變初始化過程、增加計(jì)數(shù)器等值得商榷，因?yàn)檫@違背了簡單、易分析的傳統(tǒng)的設(shè)計(jì)理念，而且從分析的結(jié)果來看，這樣做反而容易帶來安全隱患。

密鑰非易失性存儲(chǔ)的設(shè)計(jì)方法可以增強(qiáng)算法的安全性，但是增加了功耗。如何平衡安全性和功耗以及硬件資源代價(jià)是輕量級(jí)序列密碼設(shè)計(jì)的難點(diǎn)所在，這需要設(shè)計(jì)者根據(jù)應(yīng)用需求進(jìn)行靈活的選擇。

考慮到密碼算法的實(shí)際應(yīng)用場景，輕量級(jí)序列密碼算法將更加注重應(yīng)用需求，進(jìn)一步降低硬件實(shí)現(xiàn)代價(jià)，提高算法效率。通過限制使用的密鑰流的長度，使得安全性滿足應(yīng)用要求即可，實(shí)現(xiàn)算法的安全性和硬件實(shí)現(xiàn)代價(jià)的有效折中。

4 結(jié)論

輕量級(jí)序列算法Sprout、Fruit、Lizard 和Plantlet的提出以及相應(yīng)的分析結(jié)果標(biāo)志著序列密碼輕量級(jí)化取得了新的研究進(jìn)展，減小內(nèi)部狀態(tài)的設(shè)計(jì)方法得到了具體實(shí)現(xiàn)，這一設(shè)計(jì)理念得到密碼學(xué)界的逐步認(rèn)可。下一步，算法要應(yīng)用目前從分析結(jié)果中得到的一些設(shè)計(jì)技巧，而且要進(jìn)一步研究提高算法安全性的設(shè)計(jì)方法；同時(shí)，尋找新的驅(qū)動(dòng)部件來設(shè)計(jì)輕量級(jí)序列密碼將是一個(gè)有意義的研究方向。