流密碼Sosemanuk的區(qū)分攻擊

李順波，胡予濮，王艷

(1.西安電子科技大學(xué)理學(xué)院，陜西西安710071;2.西安電子科技大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室，陜西西安710071;3.西安建筑科技大學(xué) 理學(xué)院，陜西西安710055)

流密碼 Sosemanuk［1］是法國電信的 Berbain等人提交的面向軟件的快速流密碼，經(jīng)過為期4年的評(píng)選，已經(jīng)成為歐洲eSTREAM計(jì)劃最終獲選的7個(gè)流密碼算法之一.流密碼Sosemanuk是基于流密碼SNOW2.0和分組密碼SERPENT的加密算法，密鑰長度是可變的128bit或256 bit，具有較高的安全性，自今對(duì)128 bit密鑰還沒有比窮舉搜索更快的方法，其安全性分析已經(jīng)成為國內(nèi)外學(xué)者研究的熱點(diǎn).對(duì)其現(xiàn)有分析方法有猜測—確定攻擊［2-6］和相關(guān)攻擊［7-8］，還未發(fā)現(xiàn)有區(qū)分攻擊的分析結(jié)果.

區(qū)分攻擊是指在統(tǒng)計(jì)意義上可以將密鑰流與隨機(jī)序列區(qū)分.盡管從攻擊結(jié)果上看區(qū)分攻擊是最弱的，但區(qū)分攻擊也是最靈活的攻擊方法，面對(duì)區(qū)分攻擊流密碼設(shè)計(jì)者往往很難做到疏而不漏.許多流密碼算法都遭到區(qū)分攻擊的威脅，如 SNOW［9-11］、Shannon［12］、SN3［13］和 RC4［14］等密碼算法.

本文利用區(qū)分攻擊分析流密碼Sosemanuk的安全性，在弱化Serpent1密碼特性的前提下，利用線性掩碼技術(shù)線性逼近FSM和Serpent1;通過建立區(qū)分器，需要約2221密鑰流比特，就可以把密鑰流序列與隨機(jī)序列相區(qū)分，分析結(jié)果表明大于2221bit密鑰的密碼算法是不安全的.

1 區(qū)分攻擊基本理論

1.1 區(qū)分攻擊

2002年Coppersmith等提出“區(qū)分攻擊(distinguishing attack)”［9］，通過觀察某些輸入與輸出比特之間的關(guān)系來判別這些比特是來自真隨機(jī)源還是來自密碼，將其轉(zhuǎn)化為一個(gè)假設(shè)檢驗(yàn)問題.事實(shí)上，它并不是一種攻擊形式，而只是判定流密碼性質(zhì)好壞的一個(gè)新近提出的嚴(yán)格的安全標(biāo)準(zhǔn).區(qū)分攻擊的關(guān)鍵是尋找適當(dāng)?shù)膮^(qū)分器，更具體地說，區(qū)分器是指區(qū)分一串密鑰流和一串真正隨機(jī)序列的一種有效算法.區(qū)分器是以密鑰流的某些弱點(diǎn)為基礎(chǔ)的，這些弱點(diǎn)體現(xiàn)出給定的密鑰流具有的不隨機(jī)性，或稱為偏差.區(qū)分器正是利用這些弱點(diǎn)來設(shè)計(jì)算法的.

根據(jù)Neyman-Pearson引理給出最優(yōu)檢驗(yàn)，所需檢測的數(shù)據(jù)N由統(tǒng)計(jì)距離決定，在分布均勻的情況下，N=e－2，其中e為P0和PM1在給定有限集X上的統(tǒng)計(jì)距離，即

1.2 線性掩碼

掩碼技術(shù)的基本思想是將輸入數(shù)據(jù)和每一個(gè)中間結(jié)果都用隨機(jī)數(shù)隱藏起來;通常就是用一串2進(jìn)制對(duì)目標(biāo)字段進(jìn)行異或運(yùn)算屏蔽一些東西.本文采用異或掩碼，用“⊕”代替模加和Trans函數(shù)運(yùn)算.

記線性逼近關(guān)系Γ·F(x)=Λ·x的偏差為eF，則 εF=|cF(Λ，Γ)/2|.

1.3 Walsh變換和線性逼近

1.3.1 Walsh-Handamard 變換(WHT)

1)設(shè)有n維布爾函數(shù)f，取n維布爾向量w=(w1，w2，…，wn)，令 x·w=x1w1+x2w2+ … +xnwn.定義f的Walsh-Handamard變換F(w)∶

WHT的反變換為

1.3.2 線性逼近

記概率 p(y)=Pr［f(x)=y］，則線性逼近Γf(x)=0的相關(guān)度為

引理1(最佳逼近定理):

以Pf(x w⊕L)記函數(shù)f(x)與仿射函數(shù)x w⊕L相等的概率，則有

如果密碼函數(shù)雖然不是線性的或仿射的，但“很接近”某個(gè)線性函數(shù)或仿射函數(shù)，將對(duì)安全性構(gòu)成致命的威脅.

2 Sosemanuk密碼算法

Sosemanuk是Berbain等人設(shè)計(jì)的基于32 bit字的快速流密碼，密鑰長度是可變的128 bit或256 bit，初始化向量為 128 bit、384 bit的內(nèi)部狀態(tài).流密碼Sosemanuk是基于流密碼SNOW2.0和分組密碼SERPENT的加密算法，邏輯結(jié)構(gòu)如圖1所示，其核心部件由線性移位寄存器(LFSR)、FSM和Serpent1 3部分組成.

圖1 Sosemanuk的邏輯結(jié)構(gòu)Fig.1 The structure of Sosemanuk

2.1 線性移位寄存器

Sosemanuk的LFSR是定義在有限域GF(232)，包含10個(gè)32 bit的寄存器 si，1≤i≤10.線性遞歸序列:

對(duì)應(yīng)的特征多項(xiàng)式為

其中，a是定義在 GF(28)上多項(xiàng)式 P(x)的根，P(x)=x4+b23x3+b245x2+b48x+b239.b 是二元多項(xiàng)式 Q(x)的根，Q(x)=x8+x7+x5+x3+1.

2.2 有限狀態(tài)機(jī)(FSM)

記FSM在時(shí)刻t的狀態(tài)為(R1t，R2t)，則狀態(tài)反饋為

其中:為模232加，⊕為按比特異或;lsb(x)為x的最低位比特.

即:

2.3 Serpent1

Serpent［15］是由 Anderson 等設(shè)計(jì)的 AES 的候選密碼算法，32輪SPN結(jié)構(gòu)，其分組大小是128位，8個(gè)不同的 S-盒{S0，S1，…，S7}.Serpent1 是一輪的Serpent，沒有密鑰加法和線性變換;其S-盒為S2={8，6，7，9，3，12，10，15，13，1，14，0，11，5，2}.4 個(gè)32 bit字輸入，4個(gè)32 bit字輸出.密鑰流生成算法為

3 區(qū)分攻擊Sosemanuk

本節(jié)討論利用文獻(xiàn)［7］線性掩碼技術(shù)區(qū)分攻擊Sosemanuk.首先分別給出了FSM和Serpent1的線性逼近，然后構(gòu)建區(qū)分器，利用計(jì)算機(jī)模擬獲得線性逼近的偏差;最后獲得區(qū)分需要的密鑰流比特.

3.1 線性逼近FSM

令 at=lsb(R1t)，ai∈{0，1}，若存在 32 bit的線性掩碼，用比特異或‘⊕’代替所有的運(yùn)算(模加和Trans函數(shù)運(yùn)算)，則FSM狀態(tài)轉(zhuǎn)移函數(shù)變?yōu)?/p>

以上4式相加則有

為了提高上式線性逼近偏差的精度，采用不同的線性掩碼Φ，如圖2所示;其線性掩碼對(duì)模加和Trans函數(shù)的相關(guān)度分別為

則線性逼近式(1)的相關(guān)度為

圖2 Sosemanuk的線性掩碼Fig.2 The linear masking of Sosemanuk

3.2 線性逼近Serpent1

Serpent1是取自分組密碼Serpent的第3個(gè)S-盒，S2={8，6，7，9，3，12，10，15，13，1，14，4，0，11，5，2}，S2有最大的線性相關(guān)度1/2，則由圖2(b)得到的線性逼近關(guān)系式:

成立的相關(guān)度為(1/2)wt(Γ)，其中w(t)為漢明重量，即1的個(gè)數(shù).

由式(1)、(2)可得到下列線性逼近:

成立的相關(guān)度為

實(shí)驗(yàn)結(jié)果表明，當(dāng)T取重量為4的{25，24，14，0}時(shí)，相關(guān)度為 cΓ=2－21，41.

所以，相應(yīng)地線性逼近式(4)的偏差為eΓ=2－22，41.

因?yàn)?at∈{0，1}，則 at=0 的概率為 1/2，即atΓst+9⊕Γst+9=0成立的概率為 1/2，因此，由式(3)線性逼近:

成立的相關(guān)度為

3.3 建立區(qū)分器

結(jié)合Sosemanuk的線性遞歸序列和式(4)的線性關(guān)系，消去中間狀態(tài)，得到僅關(guān)于輸出密鑰流z的方程.建立如下區(qū)分器:

利用有限域理論，實(shí)驗(yàn)仿真結(jié)果如表1所示.

表1 線性掩碼對(duì)應(yīng)的偏差Table 1 The bais to some linear masking

依據(jù)堆積引理，區(qū)分器式(5)成立的概率為

表2 比較Sosemanuk的各種攻擊結(jié)果Table 2 Comparison of the attack results on Sosemanuk

4 結(jié)束語

流密碼Sosemanuk是最終獲選eSTREAM計(jì)劃的7個(gè)密碼算法之一，它軟硬件實(shí)現(xiàn)簡單并有較高的安全性，因此極有可能成為下一代通信加密算法.通過弱化Serpent1的密碼特性，利用線性掩碼技術(shù)線性逼近FSM和Serpent1，建立區(qū)分器，需要約2221密鑰流比特就可以區(qū)分密鑰流序列.雖然區(qū)分攻擊結(jié)果不及文獻(xiàn)［5］中猜測—確定攻擊的時(shí)間復(fù)雜度;但該文首次利用區(qū)分攻擊對(duì)流密碼Sosemanuk的安全性進(jìn)行了有益的嘗試.同時(shí)，區(qū)分攻擊不必借助于線性序列源，對(duì)基于非線性序列源的流密碼算法具有潛在的威脅，將是未來流密碼分析的重要方向之一.

［1］BERBAIN C，BILLET O，CANTEAUT A，et al.Sosemanuk，a fast software-oriented stream cipher［EB/OL］.［2005-05-26］.Cryptology ePrint Archiive，http://www.ecrypt.eu.org/2005/027.pdf.

［2］AHMADIH，EGHLIDOST，KHAZAEIS.Improved guess and determine attack on Sosemanuk［EB/OL］［2005-12-25］.http://www.ecrypt.eu.org/stream/sosemanukp3.html.

［3］TSUNOO Y，SAITO T，SHIGERIM.Evaluation of Sosemanuk with regard to guess-and-determine attacks［EB/OL］.［2006-01-02］.http://www.ecrypt.eu.org/stream/sosemanukp3.htm l.

［4］DING Lin，GUAN Jie.Guess and determine attack on Sosemanuk［C］//Fifth International Conference on Information Assurance and Security-CIAS2009.Xi＇an，China，2009:658-661.

［5］FENG Xiutao，LIU Jun，ZHOU Zhaocun，et al.A bytebased guess and determine attack on Sosemanuk［C］//Advances in Cryptology-Asiacrypt 2010.LNCS 6477.Berlin:Springer-Verlag，2010:146-157.

［6］張海霞，胡予濮，柴進(jìn).針對(duì)Sosemanuk的猜測-確定攻擊［J］.計(jì)算機(jī)工程，2011，37(4):170-171.ZHANG Haixia，HU Yupu，CHAI Jin.Guess and determine attack on Sosemanuk［J］.Computer Engineering，2011，37(4):170-171.

［7］LEE JK，LEE D H，PARK S.Cryptanalysis of sosemanuk and SNOW 2.0 using linear masks［C］//Advances in Cryptology-Asiacrypt 2008.LNCS 5350.Berlin:Springer-Verlag，2008:524-538.

［8］CHO JY，HERMELINM.Improved linear cryptanalysis of Sosemanuk［C］//Information，Security and Cryptology-ICISC 2009.LNCS 5984.Berlin:Springer-Verlag，2010:101-117.

［9］COPPERSMITH D，HALEVIS，JUTLA C.Cryptanalysis of stream ciphers with linear masking［C］//Advances in Cryptology-Crypto 2002.LNCS 2442. Berlin:Springer-Verlag，2002:515-532.

［10］WATANABED，BIRYUKOV A，CANNIERECD.A distinguishing attack of SNOW 2.0 with linearmasking method［C］//Selected Areas in Cryptography-SAC 2003，LNCS 3006.Berlin:Springer-Verlag，2004:222-233.

［11］NYBERG K，WALLEN J.Improving linear distinguishers for SNOW 2.0［C］//Fast Software Encryption-FSE 2006，LNCS 4047.Berlin:Springer-Verlag，2006:114-162.

［12］AHMADIAN Z，MOHAJERI J，SALMASIZADEH M，et al.A practical distinguisher for the Shannon cipher［J］.The Journal of Systems and Software，2010(83):543-547.

［13］KELLER N，MILLER SD.Distinguishing attack on stream ciphers based on arrays of pseudo-random words［J］.Information Processing Letters，2010，110:129-132.

［14］SEPEHRDAD P，VAUDENAY S，VUAGNOUX M.Statistical attack on RC4 distinguishing WPA［C］//Advances in Cryptology-Eurocrypt 2011， LNCS 6632. Berlin:Springer-Verlag，2011:343-363.

［15］ANDERSON R，BIHAM E，KNUDSEN L R.Serpent:A proposal for the advanced encryption standard［EB/OL］.［1998-08-21］.http://www.cl.cam.ac.uk/rja14/serpent.htm l.