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

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

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

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

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

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

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