輕量級序列密碼研究進展

王明興 ，苗三立 ，朱明佳

(1.中國電子信息產業(yè)集團有限公司第六研究所，北京 102209；2.密碼科學技術國家重點實驗室，北京 100878)

0 引言

序列密碼是一種對稱密碼算法，即加密密鑰和解密密鑰是相同的。序列密碼的經典結構包括兩個部件：驅動部件和密鑰流輸出部件，驅動部件通過迭代運算更新內部狀態(tài)，輸出部件抽取一部分內部狀態(tài)的比特值，經過復雜運算產生密鑰流。加密時，密鑰流和明文異或產生密文，解密時，密鑰流和密文異或產生明文。通俗地講，序列密碼算法可以認為是分組密碼的密鑰擴展算法。

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

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

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

1 輕量級序列密碼介紹

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

圖1 序列密碼Grain 算法簡圖

1.1 Sprout 算法

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

Sprout 算法的驅動部件是40 bit 長的LFSR 串聯上一個40 bit 長的NFSR，以及輪密鑰函數和計數器。密鑰長度80 bit，初始向量70 bit，一個初始向量產生的密鑰流不超過240bit。初始化過程中輸出密鑰流比特反饋參與移位寄存器的運算，初始化輪數320輪，初始化完成之后，每一拍輸出1 bit 密鑰流。

1.2 Fruit-80 算法

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

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

1.3 Plantlet 算法

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

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

1.4 Lizard 算法

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

該算法突出的特點是，每一個密鑰和初始向量對(K，IV)限制產生的密鑰流長度是218bit，它的驅動部件是兩個非線性反饋移位寄存器的串聯結構，密鑰在初始化過程中兩次參與運算，Lizard 的能耗特別低，只有2.1 μW。

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

表1 不同算法各項安全指標匯總表

2 輕量級序列密碼安全性分析結果

2.1 Sprout 算法分析結果

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

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

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

2.2 Fruit 算法分析結果

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

2.3 Plantlet 算法分析結果

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

2.4 Lizard 算法分析結果

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

總結目前的分析結果，對輕量級序列密碼的設計建議如下：

(1)輪密鑰應線性地影響更新函數，降低輪密鑰的某些比特值被非線性函數零化掉的風險。

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

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

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

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

(6)根據算法實際的使用場景，限制一個密鑰、初始向量對(K，IV)產生的密鑰流序列的長度，這樣的密鑰流越短，算法的安全強度越高。

3 討論

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

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

密鑰非易失性存儲的設計方法可以增強算法的安全性，但是增加了功耗。如何平衡安全性和功耗以及硬件資源代價是輕量級序列密碼設計的難點所在，這需要設計者根據應用需求進行靈活的選擇。

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

4 結論

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