eSTREAM候選算法的安全性研究.pdf

1、序列密碼是密碼學(xué)的一個重要分支.由于具有加解密速度快、硬件實現(xiàn)簡單、沒有或只有有限的錯誤傳播等特點,序列密碼被廣泛應(yīng)用于保密通信中.為了更進一步促進序列密碼的發(fā)展,歐洲實施了eSTREAM研究項目以期征集到適合廣泛采用的新的序列密碼算法.因此,充分考量eSTREAM候選算法及獲選算法的安全性對序列密碼的發(fā)展具有重要的理論和現(xiàn)實意義.基于此,本文重點對eSTREAM計劃中的候選算法DECIMv2及獲選算法Trivium進行了安全性分析,取

2、得以下主要成果:
　　(1)針對DECIMv2的非線性部件ABSG的原型比特搜索生成器BSG,利用Martin Hell關(guān)于自縮生成器的攻擊思想,提出了一種基于多段密鑰流的概率快速密鑰恢復(fù)攻擊.與目前已知最好攻擊結(jié)果相比,該攻擊能夠?qū)⒂嬎銖?fù)雜度從O(L320.5L)降到O(L320.43L),其中L為線性反饋移位寄存器的長度.特別地,當L為96時,計算復(fù)雜度可以達到O(L320.39L),所需的數(shù)據(jù)復(fù)雜度為O(NL), N為攻擊的

3、次數(shù).實驗結(jié)果表明,隨著密鑰段數(shù)的增多,算法的計算復(fù)雜度明顯減少.
　　(2)針對具有低重量反饋多項式的BSG,利用猜測確定攻擊的思想并基于BSG序列的差分構(gòu)造特點提出一種快速密鑰恢復(fù)攻擊.具體的,由截獲的密鑰流恢復(fù)出候選差分序列并利用反饋多項式對候選差分序列進行校驗,以減少需要求解的L維線性方程系統(tǒng)的數(shù)量,從而大大減少了算法所需的計算復(fù)雜度.理論分析和仿真結(jié)果表明,對于反饋多項式重量小于10的BSG,該算法明顯優(yōu)于現(xiàn)有的攻擊方法

4、.
　　(3)對Trivium的簡化版本2輪Trivium進行分析研究,借助于輪函數(shù)的Walsh譜,找到了它的多個線性逼近方程,對其進行了多線性密碼分析.與現(xiàn)有的單線性密碼分析算法相比,該算法攻擊成功所需的數(shù)據(jù)量明顯減少.具體的,若能找到 n個線性近似方程,在達到相同攻擊成功概率的前提下,多線性密碼分析所需的數(shù)據(jù)量只有單線性密碼分析的1/n.
　　(4)對Trivium的硬件實現(xiàn)進行了分析研究,發(fā)現(xiàn)了其可用于相關(guān)能量攻擊的漏

5、洞,據(jù)此給出了Trivium相關(guān)能量攻擊的有效方案.首先通過對Trivium的初始化算法的分析可以選擇出合適的中間值函數(shù)及能量模型,進而通過引入一個修正的相關(guān)系數(shù)描述假設(shè)的能量消耗值與實際測量的能量值的關(guān)系.修正相關(guān)系數(shù)的計算可以明顯減少電子噪聲的影響,并且假設(shè)中間值可以由最大修正相關(guān)系數(shù)唯一確定.接著利用恢復(fù)出的假設(shè)中間值可以列出多個關(guān)于秘密鑰比特的方程并最終通過順序求解這些方程來得到Trivium的秘密鑰.與Fischer關(guān)于Tri

6、vium的差分能量攻擊相比,該算法更有效更穩(wěn)健.最后的軟件仿真驗證了方案的正確性和可行性.
　　(5)利用相關(guān)能量分析攻擊對eSTREAM的候選算法DECIMv2進行了安全性分析.針對DECIMv2的軟硬件實現(xiàn)的不同特點,分別選擇出合適的能量模型及中間值;然后利用選擇IV對DECIMv2進行再同步來獲得足夠的能量跡,從而計算修正相關(guān)系數(shù)可以恢復(fù)出正確的中間值并最終得到算法的秘密鑰.軟件仿真驗證了DECIMv2的相關(guān)能量攻擊方案的可