eSTREAM序列密碼候選算法的安全性分析.pdf

1、本論文主要對eSTREAM工程的四個候選密碼算法ABCv3、TSC-4、CryptMT v3和Grain v1進行了安全性分析：在弱密鑰條件下，破解了ABC v3和TSC-4；發(fā)現(xiàn)CryptMT v3密鑰初始化過程存在概率為1的差分特征；對Grain v1進行了弱Key-IV攻擊。 1．弱密鑰條件下破解ABC v3 ABC v3的密鑰長度為128比特，是34個參賽算法中運行速度最快的算法之一。ABC v1和v2為ABC

2、 v3之前的兩個版本。2005年，Berbain、Gilbert和Khazaei同時發(fā)現(xiàn)ABC v1的線性移位寄存器長度過短，通過分別征服攻擊破解了ABC v1。ABC v2加大LFSR的長度以彌補ABC v1的缺陷。但在SAC2006上，Wu和Preneel發(fā)現(xiàn)ABC v2存在一類弱密鑰，并且在弱密鑰條件下，ABC v2可被破解。通過修改密鑰初始化過程，消除Wu-Preneel弱密鑰，ABCv3可抵抗以前所有攻擊。 ABC系

3、列算法結(jié)構(gòu)主要由LFSR、T-函數(shù)和基于背包問題構(gòu)造的S-盒三部分組成。LFSR的最低權(quán)位32比特字與S-盒的輸出進行模232加運算后作為密鑰流輸出字。LFSR反饋多項式的項數(shù)為3，雖然可以提高運行速度，但同時也降低了安全性，易受快速相關(guān)攻擊。為此，算法設(shè)計者采用了T-函數(shù)、S-盒和模加運算等大量非線性組件來掩藏LFSR的線性。特別是基于背包問題構(gòu)造的S-盒，加大了分析的難度。本文采取以恢復LFSR的內(nèi)部狀態(tài)為首要目標、以尋找算法核心部

4、件S-盒的弱點為關(guān)鍵、以非線性模加運算的線性逼近為突破口的技術(shù)路線，發(fā)現(xiàn)ABC v3存在新型弱密鑰，其發(fā)生的概率為2-24．29。最終，在弱密鑰條件下破解了ABC v3。 2．弱密鑰條件下破解TSC-4 自Klimov和Shamir把T-函數(shù)引入密碼學以來，出現(xiàn)了很多基于T-函數(shù)設(shè)計的序列密碼算法，如Klimov-Shamir系列算法TSC-1、TSC-2和TSC-3等。但所有算法均被破解。在總結(jié)已有攻擊的基礎(chǔ)上，Moo

5、n等密碼學家設(shè)計了TSC-4。TSC-4進入eSTREAM第二評估階段，密鑰長度為80比特。在Indocrypt2006上，F(xiàn)ischer、Meier和Berbain等發(fā)現(xiàn)TSC-4的密鑰初始化過程存在一定非隨機性，但無法通過密鑰流區(qū)分，不能形成真正的攻擊。TSC-4算法結(jié)構(gòu)主要由三部分組成：兩個對稱的T-函數(shù)部件X和Y以及一個以X和Y的部分狀態(tài)為輸入以密鑰流為輸出的非線性濾波函數(shù)。其中，T-函數(shù)采用了多種非線性邏輯運算、選擇控制、S-

6、盒等技術(shù)手段，具有很強的雪崩和擴散效應(yīng)。由于很難建立數(shù)學模型，TSC-4一直沒有被破解。本文將差分分析與分別征服攻擊相結(jié)合，以計算機模擬實驗為基礎(chǔ)，從所得實驗數(shù)據(jù)中挖掘數(shù)學規(guī)律，歸納弱密鑰的特征，在弱密鑰條件下破解了TSC-4。 （1）構(gòu)造密鑰初始化過程的兩個特殊差分特征 TSC-4的密鑰初始過程首先把密鑰K和初始向量IV載入X和Y，然后進行8圈算法體的迭代。其中，每圈迭代包括三步：第一步通過非線性濾波函數(shù)把結(jié)構(gòu)X和Y

7、的信息混合后輸出一個字節(jié)；第二步，X和Y各自按行循環(huán)移位；第三步是把第一步的輸出字節(jié)混合到X和Y中。由此可見，X和Y主要是通過第一和第三步發(fā)生聯(lián)系。使部件Y差分非零，部件X差分為零，如果初始化過程中每一圈的第一步輸出差分為零，那么Y的差分就不可能擴散到X中，即X的差分可以始終保持為零。這樣就可以“切斷”部件X和Y的聯(lián)系，達到控制雪崩的目的。利用此特點，構(gòu)造出兩個特殊差分特征ΩX和ΩY，當差分特征ΩY成立時，差分特征ΩY成立的概率為1。

8、 （2）發(fā)現(xiàn)弱密鑰 首先，隨機選取密鑰K和初始向量IV，運行密鑰初始化過程，如果差分特征ΩY成立，則保留K和IV以及相對應(yīng)的X和Y狀態(tài)。第二，以狀態(tài)Y的列為單位進行x2檢驗，檢測出非隨機分布。第三，以檢測出的非隨機分布為研究對象，運用卡諾圖技術(shù)，歸納總結(jié)出高概率線性表達式。第四，按照K和IV的載入方式代換關(guān)于X和Y的高概率線性表達式，得到關(guān)于K和IV的表達式。第五，合并各關(guān)于K和IV的線性表達式，定義產(chǎn)生高概率ΩY的弱密鑰

9、空間EK和特殊IV空間EIV。第六，按照空間EK和EIV，重新運行密鑰初始化過程，得到ΩY產(chǎn)生的概率。最后，可得對于80比特的密鑰，TSC-4弱密鑰的個數(shù)約為272個。當選擇的IV對屬于空間EIV時，如果K是弱密鑰，則ΩY出現(xiàn)的概率為2-15．40；如果K為強密鑰，則ΩY出現(xiàn)的概率為2-24．74。 （3）區(qū)分并恢復弱密鑰 盡管確定了密鑰初始化過程的兩個特殊差分特征和弱密鑰，但除密鑰流已知外，X和Y的內(nèi)部狀態(tài)未知。因此，

10、需要構(gòu)造一個能夠把X和Y的差分不平衡性傳遞到密鑰流的區(qū)分器。通過實驗，本文成功構(gòu)造出此區(qū)分器。通過理論計算可得，對于每個弱密鑰，恢復出8比特密鑰約需要240．53個選擇IV對，剩余72比特密鑰可通過搜索攻擊恢復。 通過分析可知，TSC-4是不安全的。另外，本文指出TSC-4還存在其它類型的弱密鑰和攻擊方法，如相關(guān)密鑰攻擊等。 3．發(fā)現(xiàn)CryptMT v3密鑰初始化過程存在概率為1的差分特征 CryptMT v3

11、為進入eSTREAM工程第三評估階段的序列密碼，密鑰長度為128比特。由于采用乘法運算等獨特技術(shù)，目前無任何攻擊。設(shè)密鑰初始化過程為以密鑰K為參數(shù)的函數(shù)生成器：F={fK{0，1}128→{0，1}19968}。通過差分分析，本文構(gòu)造出區(qū)分器AfK，可以把fK與隨機函數(shù)以概率1區(qū)分出來，因而fK不是隨機函數(shù)。分析結(jié)果表明，CryptMT v3的密鑰初始化過程存在一定的弱點，可能被攻擊。 4．弱Key-Ⅳ條件下破解Grain v1

12、 Grain v1是eSTREAM最終獲選算法之一，其最初版本為Grain v0，密鑰加長版本為Grain-128。2005年，Khazaei、Hassanzadeh和Kiaei對Grain v0進行了區(qū)分攻擊。在FSE2006上，Berbain、Gilbert和Maximov通過恢復密鑰攻擊，破解了Grain v0。Grain v1為Grain v0的修改版本，可抵抗以前攻擊。在o．Kucuk提出的針對Grain v1/12

13、8的再同步滑動攻擊基礎(chǔ)上，o．Kucuk和Preneel等對Grainv1/128的密鑰初始化過程進行了分析，Lee等進行了相關(guān)密鑰選擇IV攻擊。以上關(guān)于Grain v1/128的攻擊本質(zhì)上均為相關(guān)密鑰攻擊。Afzal和Masood提出對Grainv1/128進行代數(shù)攻擊，但計算復雜度超過了搜索攻擊。2008年，eSTREAM最終評估報告認為Grain v1/128是很安全的，但指出密鑰初始化過程需要修改。 Grain系列算法

14、體主要由IFSR、NFSR和非線性濾波函數(shù)三部分組成。Grainv0/v1/128的密鑰長度分別為80/80/128比特，初始向量長度分別為64/64/96比特。設(shè)Grain系列密碼算法密鑰Key的長度為κ比特，初始向量IV的長度為ι比特，則不同的密鑰和初始向量對Key-IV產(chǎn)生不同的密鑰流輸出，共可產(chǎn)生2κ+ι條序列。對于一個安全的序列密碼算法，保證2κ+ι條序列中的每一條序列都具有很高的隨機性是必要的。本文以Key-IV產(chǎn)生的序列為

15、研究對象，對Grain v1進行弱Key-IV攻擊。 （1）弱Key-Ⅳ的存在性 當LFSR的內(nèi)部狀態(tài)為全‘0’時，算法只有NFSR起作用。因此，將能夠產(chǎn)生LFSR為全‘0’狀態(tài)的密鑰Key和初始向量Ⅳ為定義為一個弱Key-Ⅳ。本文給出了求取弱Key-Ⅳ的算法和弱Key-Ⅳ實例。設(shè)密鑰初始化過程后，所有內(nèi)部狀態(tài)均勻分布，則在2κ+ι個Key-Ⅳ中有2ι個弱Key-Ⅳ。 （2）區(qū)分弱Key-Ⅳ 運用循環(huán)Wa

16、lsh譜理論得到NFSR的非線性反饋函數(shù)的最佳線性逼近后，由線性逼近引理，本文構(gòu)造出Grain系列算法的區(qū)分器，對弱Key-Ⅳ進行區(qū)分攻擊，結(jié)果如下：從Grain v0/v1/128的280/280/2128個Key-Ⅳ中以99．977％的成功率區(qū)分出1個弱Key-Ⅳ各需要217．8/249．4/291．8個密鑰流比特和221．1/252．7/2110次運算。 （3）恢復弱Key-Ⅳ Grajn v1產(chǎn)生密鑰流輸出時，

17、LFSR獨立作用，NFSR的內(nèi)部狀態(tài)由自身和LFSR的內(nèi)部狀態(tài)決定，密鑰流輸出由LFSR和NFSR的內(nèi)部狀態(tài)決定。所以，密鑰流輸出可以表示為LFSR和NFSR內(nèi)部狀態(tài)的非線性函數(shù)，可得到相應(yīng)的代數(shù)方程。對于弱Key-IV，LFSR不起作用，利用Afzal和Masood的代數(shù)攻擊結(jié)果可得：在已知弱Key-IV條件下，只需150比特密鑰流輸出和230．7次異或運算即可破解Grain v1；在已知弱Key-IV條件下，破解Grain-128的