一個混沌分組密碼算法的分析

摘 要:研究了一個基于混沌設計的分組密碼算法的安全性，發現該算法所產生的混沌序列具有前幾個值對混沌初態和參數的低位比特變化不夠敏感的性質，在選擇明文攻擊條件下，提出了攻擊加密算法等效密鑰的分割攻擊方法。分組密碼算法的密鑰長度為106 bit，分割攻擊方法的計算復雜性約為260，存儲復雜性約為250，成功率為0.928 4。

關鍵詞:混沌密碼; 分組密碼; 密碼分析; 分割攻擊; 等效密鑰

中圖分類號:TN918.1; TP309.7文獻標志碼:A

文章編號:1001-3695(2010)06-2294-03

doi:10.3969/j.issn.10013695.2010.06.085

Cryptanalysis of chaotic block cipher

ZHANG Tao

(Institute of Electronic Technology， PLA Information Engineering University， Zhengzhou 450004， China)

Abstract:This paper investigated the security of a chaotic block cipher. Found that the firstly several chaotic states generated by this cipher were not sensitive to the initial state and parameter. Under the chosen plaintexts condition， proposed a divideandconquer attack on the equivalent key. The length of key is 106 bit， and the computing and memory complexity of the attack are about 260 and 250 respectively. The success rate is 0.928 4.

Key words:chaotic cipher; block cipher; cryptanalysis; divideandconquer attack; equivalent key

由于混沌所具有的許多類似隨機的性質與密碼學中的混亂和擴散等性質相似，很多學者利用混沌來設計密碼算法。到目前為止，已經出現了很多混沌密碼算法。按照加密方式來分，混沌密碼算法主要有兩大類:a)基于同步調制技術設計的模擬加密算法[1]; b)基于混沌映射設計的數字加密算法[2~6]。其中，數字式混沌密碼又可分為混沌序列密碼[2]、混沌分組密碼[3]及混沌公鑰密碼[4]。按照應用對象來分，混沌密碼算法主要包括數據加密算法[2]、圖像加密算法[5]和數字水印算法[6]。另一方面，混沌密碼的分析理論研究也取得了一定的進展，對模擬混沌算法的分析方法主要包括參數重構攻擊方法[7]、回歸映射分析方法[8]和錯誤函數攻擊方法[9]，對數字式混沌算法的攻擊方法主要包括多分辨率攻擊方法[10]、分割攻擊方法[11，12]以及特定條件下的分割攻擊方法[13，14]。

本文分析了一個基于混沌設計的分組密碼算法[3]的安全性，發現該算法所產生的混沌序列具有前幾個值對混沌初態的低位比特變化不夠敏感的性質。

1 混沌分組密碼算法介紹

文獻[3]中使用的混沌映射是設計數字式混沌密碼算法最常用的Logistic映射:

fμ(x)=μx(1-x)(1)

其中:μ∈(3.5699，4]，x∈[0，1]。

由于實數在計算機中均是以有限精度實現，不妨設將混沌映射定義域[0，1]中的實數x=∑∞i=0xi2-i用x(n)=∑n-1i=0xi2-i來實現。在下面的討論中均用x(n)來表示x的n精度數。

混沌分組密碼算法[3]的分組長度是64 bit，密鑰是混沌初態x0和參數μ，在PC機中雙精度實數的十進制精度為16，故混沌分組密碼密鑰空間的大小為102×16≈2106。該加密算法包括三步:

a)初始化。以混沌初態x(53)0∈[0，1]和參數μ(53)∈(3.5699，4]為密鑰，對于1≤i≤250，由x(53)i=fμ(x(53)i-1)產生當前混沌狀態x(53)250。

b)對于第j(j≥1)個64 bit分組的明文mj經過以下操作被加密為密文:

(a)產生混沌序列。以當前混沌狀態x(53)t為起點，對于1≤i≤70，由x(53)t+i=fμ(x(53)t+i-1)產生混沌序列{x(53)t+i}70i=1。

(b)量化混沌序列。由混沌序列{x(53)t+i}70i=1產生量化序列{bi}70i=1，量化函數為

bi=g(x(53)t+i)=(floor(23x(53)t+i))mod 2(2)

其中:floor(x)表示不大于x的最大整數。

(c)加密明文分組。令Aj=(b1，b2，…，b64)為64 bit分組，Dj=∑5i=025-ib65+i，明文mj對應的密文分組cj=(mj<<

c)如果所有的明文分組均經過加密，算法終止;否則，再迭代混沌映射Dj次從而更新當前混沌狀態x(53)t，即x(53)t:=fμ70+Dj(x(53)t)，返回步驟b)加密下一個明文分組。

2 混沌分組密碼算法分析

加密算法的步驟a)實質上是為了掩蓋混沌初態x(53)0從而增強密碼算法的安全強度。由于混沌序列的前250個狀態均被丟棄并且Logistic映射在其定義域上是多對一映射，從信息論上講，即使攻擊者得到x(53)250和參數μ(53)也無法惟一確定x(53)0的值。這似乎說明加密算法的步驟a)增強了密碼算法的安全強度。但是，從另一方面說，如果以x(53)250和μ(53)分別為混沌初態和參數不經過初始化過程而直接產生混沌序列用于加密明文分組，則加密結果與以x(53)0和μ(53)分別為混沌初態和參數時加密算法的加密結果完全一致。這樣可以將x(53)250看做是x(53)0的等效密鑰，只要完成對{x(53)250，μ(53)}的攻擊實際上就完成了對該加密算法的攻擊。因此，加密算法的初始化過程對于增強該密碼算法的安全性沒有作用。下面就給出對算法等效密鑰的選擇明文攻擊方法。

在選擇明文攻擊條件下，選取第一個64 bit明文分組為全零分組，即m1=(0，0，…，0)，記c1為m1對應的密文分組，則由c1=(m1<<

下面分析如何由{bi}64i=1恢復等效密鑰x(53)250和參數μ(53)。

定理1 設函數fμ(x)=μx(1-x)。其中μ∈(3.5699，4]，x∈[0，1]，則有xfμ(x)<4 和μfμ(x)<14。

證明 由于xfμ(x)=μ(1-2x)，μfμ(x)=x(1-x)，故μ(1-2x)≤4，故xfμ(x)<4和μfμ(x)<14。

定理2 設函數f(x)=μx(1-x)，μ，μ+δ∈(3.5699，4]，x，x+ε∈[0，1]，則fμ(x)-fμ+δ(x+ε)≤4|ε|+14|δ|。

證明 由拉格朗日中值定理知，存在ξμ∈[x，x+ε]和ηx+ε∈[μ，μ+δ]，使得fμ(x)-fμ(x+ε)=xfμ(x)x=ξμ#8226;|ε|和fμ(x+ε)-fμ+δ(x+ε)=μfμ(x+ε)μ=ηx+ε#8226;|δ|，再由定理1知，fμ(x)-fμ+δ(x+ε)≤fμ(x)-fμ(x+ε)+fμ(x+ε)-fμ+δ(x+ε)≤4|ε|+14|δ|。

定理2說明，Logistic混沌映射具有如下性質:輸入的低位變化對輸出的高位影響不大。由于混沌序列是由混沌映射反復迭代產生的，這就導致了混沌序列具有前幾個值對混沌初態和參數的低位比特變化不夠敏感的性質。需要指出的是，混沌現象所具有的蝴蝶效應是指初態或參數的微小變化經過足夠多的迭代最終將導致混沌序列發生不可預測的變化，但蝴蝶效應并不能保證混沌序列的前幾個值與混沌初態和參數的低位比特不相關。

定理3 設g(x)=[floor(23x)]mod 2，x∈(0，1)，若2-3floor(23x)-x≤ε<2-3+2-3floor(23x)-x，則g(x+ε)=g(x)。

定理3的證明比較簡單，這里不再給出。

定理3說明量化函數g(x)同樣具有輸入發生微小變化時輸出不發生變化的性質，結合上述混沌序列的性質可知，量化序列仍然具有前幾個比特對混沌初態和參數的低位比特變化不夠敏感的性質。為了定量刻畫這種性質，本文引入吻合度的概念。

定義1[12] 設k和k′分別是某密碼算法的正確密鑰和試驗密鑰，{bi}∞i=1和{b′i}∞i=1分別是它們產生的量化序列，則稱max{t:i:1≤i≤t，有bi=b′i}為k′的吻合度。

令x(m)250表示等效密鑰x(53)250的m精度數，μ(m)表示參數μ(53)的m精度數，將{x(m)250，μ(m)}的吻合度記為tm。要從理論上精確分析tm的分布規律是困難的。因此，本文利用模擬實驗方法獲取tm的分布規律。具體方法為:隨機選取一萬組雙精度實數{x(53)250，μ(53)}，針對m=8，16，24，32，40，48六種情形，得到的吻合度tm的分布律如表1~6所示。

表1 t8的分布律

t801234567891011121314151617≥18

個數76218395607866113710851075896818572501390307240157140115405

表2 t16的分布律

t16≤8910111213141516171819202122232425≥26

個數98721161933143984595595896265835985695174903983493012771

表3 t24的分布律

t24≤181920212223242526272829303132333435≥36

個數107751321852642843683944023583963723574003543333503014568

表4 t32的分布律

t32≤282930313233343536373839404142434445≥46

個數2001101481962222242843092772442702992492842512882382435664

表5 t40的分布律

t40≤3637383940414243444546474849505152≥53

個數117781051351751682052112232021972052072182112151836945

表6 t48的分布律

t48≤4546474849505152535455565758596061≥62

個數140921061171351371691651921781811751521661771631817374

因此，p(t8≥1)=0.9924，p(t16≥9)=0.9902，p(t24≥19)=0.9893，p(t32≥29)=0.9800，p(t40≥37)=0.9883，p(t48≥46)=0.9860。

設{x(53)250，μ(53)}是正確密鑰，若同時窮舉密鑰中兩個數的高m bit，則吻合度≥t的試驗密鑰的個數期望為22m-t，且吻合度≥t的試驗密鑰中包含{x(m)250，μ(m)}的概率為p(tm≥t)。

當試驗密鑰{x(m)，μ′(m)}與{x(m)250，μ(m)}不相等時，可認為由{x(m)，μ′(m)}產生的序列與亂數序列相互獨立，因而{x(m)，μ′(m)}產生的序列的吻合度≥t的概率近似為2-t，而由模擬實驗知，{x(m)250，μ(m)}的吻合度≥t的概率相對于2-t要大得多。據此就可將隨機的試驗密鑰{x(m)，μ′(m)}與{x(m)250，μ(m)}區分開。這就是對該算法進行分割攻擊的理論依據。

下面給出對混沌分組密碼算法[3]的分割攻擊算法，將53 bit x(53)250和μ(53)從左到右依次分割為六個8 bit塊和一個5 bit塊，記為

x(53)250=(x250，8，x250，16，x250，24，x250，32，x250，40，x250，48，x250，53)μ(53)=(μ8，μ16，μ24，μ32，μ40，μ48，μ53)

記正確密鑰和試驗密鑰產生的量化序列分別為{bi}64i=1和{b′i}64i=1:

a)令

x250，8=x250，16=x250，24=x250，32=x250，40=x250，48=x250，53=0μ8=μ16=μ24=μ32=μ40=μ48=μ53=0

b)攻擊{x(8)250，μ(8)}。以{x250，8，μ8}的每個可能值為密鑰產生量化序列{b′i}64i=1，將吻合度≥1的所有{x250，8，μ8}存入文件1中。

c)攻擊{x(16)250，μ(16)}。如果文件1中的值均已讀取完，則執行d);否則從文件1中讀取{x250，8，μ8}的下一個值，依次窮舉{x250，16，μ16}的所有可能值，以(x250，8，x250，16)和(μ8，μ16)為密鑰產生量化序列{b′i}64i=1，如果吻合度≥9，則將該(x250，8，x250，16)和(μ8，μ16)存入文件2中。當{x250，16，μ16}的所有可能值窮舉完畢，則返回c)。

d)攻擊{x(24)250，μ(24)}。如果文件2中的值均已讀取完，則執行e);否則從文件2中讀取(x250，8，x250，16)和(μ8，μ16)的下一個值，依次窮舉{x250，24，μ24}的所有可能值，以(x250，8，x250，16，x250，24)和(μ8，μ16，μ24)為密鑰產生量化序列{b′i}64i=1，如果吻合度≥19，則將該(x250，8，x250，16，x250，24)和(μ8，μ16，μ24)存入文件3中。當{x250，24，μ24}的所有可能值窮舉完畢，則返回d)。

e)攻擊{x(32)250，μ(32)}。如果文件3中的值均已讀取完，則執行f);否則從文件2中讀取(x250，8，x250，16，x250，24)和(μ8，μ16，μ24)的下一個值，依次窮舉{x250，32，μ32}的所有可能值，以(x250，8，x250，16，x250，24，x250，32)和(μ8，μ16，μ24，μ32)為密鑰產生量化序列{b′i}64i=1，如果吻合度≥29，則將該(x250，8，x250，16，x250，24，x250，32)和(μ8，μ16，μ24，μ32)存入文件4中。當{x250，32，μ32}的所有可能值窮舉完畢，則返回e)。

f)攻擊{x(40)250，μ(40)}。如果文件4中的值均已讀取完，則執行g);否則從文件4中讀取(x250，8，x250，16，x250，24，x250，32)和(μ8，μ16，μ24，μ32)的下一個值，依次窮舉{x250，40，μ40}的所有可能值，以(x250，8，x250，16，x250，24，x250，32，x250，40)和(μ8，μ16，μ24，μ32，μ40)為密鑰產生量化序列{b′i}64i=1，如果吻合度≥37，則將該(x250，8，x250，16，x250，24，x250，32，x250，40)和(μ8，μ16，μ24，μ32，μ40)存入文件5中。當{x250，40，μ40}的所有可能值窮舉完畢，則返回f)。

g)攻擊{x(48)250，μ(48)}。如果文件5中的值均已讀取完，則執行h);否則從文件5中讀取(x250，8，x250，16，x250，24，x250，32，x250，40)和(μ8，μ16，μ24，μ32，μ40)的下一個值，依次窮舉{x250，48，μ48}的所有可能值，以(x250，8，x250，16，x250，24，x250，32，x250，40，x250，48)和(μ8，μ16，μ24，μ32，μ40，μ48)為密鑰產生量化序列{b′i}64i=1，如果吻合度≥46，則將該(x250，8，x250，16，x250，24，x250，32，x250，40，x250，48)和(μ8，μ16，μ24，μ32，μ40，μ48)存入文件6中。當{x250，48，μ48}的所有可能值窮舉完畢，則返回g)。

h)攻擊{x(53)250，μ(53)}。如果文件6中的值均已讀取完仍未找到正確密鑰，則報告算法失敗，算法終止;否則從文件6中讀取(x250，8，x250，16，x250，24，x250，32，x250，40，x250，48)和(μ8，μ16，μ24，μ32，μ40，μ48)的下一個值，依次窮舉{x250，53，μ53}的所有可能值，以(x250，8，x250，16，x250，24，x250，32，x250，40，x250，48，x250，53)和(μ8，μ16，μ24，μ32，μ40，μ48，μ53)為密鑰產生量化序列{b′i}64i=1，如果吻合度≥64，則利用第二個明密對檢驗該試驗密鑰，輸出通過檢驗的試驗密鑰，算法終止，如果未通過檢驗，返回h);否則返回h)窮舉{x250，53，μ53}的下一個可能值。當{x250，53，μ53}的所有可能值窮舉完畢，則返回h)。

定理4 分割攻擊算法的成功率為0.928 4，計算復雜性約為260，存儲復雜性約為250。

證明 攻擊算法不漏掉正確密鑰等價于對各比特塊的攻擊都不會漏掉正確值。由模擬實驗知，該算法中各步不漏掉正確值的概率分別為0.9924，0.9902，0.9893，0.9800，0.9883，0.9860，故算法的成功率為

p=p(t8≥1)p(t16≥9)p(t24≥19)p(t32≥29)p(t40≥37)p(t48≥46)=0.9924×0.9902×0.9893×0.9800×0.9883×0.9860≈0.9284

下面分析算法的平均計算復雜性。

如果將試驗密鑰產生的序列與正確密鑰產生的序列看做相互獨立，則試驗密鑰的吻合度≥t的概率約為2-t。因此，吻合度≥t的試驗密鑰的個數的期望為22m-t。其中m為試驗密鑰的精度。步驟b)窮舉了{x250，8，μ8}的所有可能值，共16 bit，故步驟b)的計算復雜性為216，而步驟b)僅保留吻合度≥1的{x250，8，μ8}的候選值，故約有216-1=215個候選值被保留。

對于步驟c)~g)，每步均在上一步的基礎上窮舉16 bit，如果上一步保留的候選值的個數為N，則此步的計算復雜性為216N且保留下來的個數約為22m-t，而步驟c)~g)中試驗密鑰的精度依次取16，24，32，40，48，吻合度t依次取9，19，29，37，46。因此步驟c)~g)的計算復雜性依次約為231，239，245，251，259。步驟g)中保留下來的個數約為250，步驟h)在g)的基礎上共窮舉10 bit，故步驟h)的計算復雜性至多為260。綜上所述，算法的計算復雜性約為216+231+239+245+251+259+260≈260。算法的存儲復雜性約為215+223+229+235+243+250≈250。

由定理4知，本文提出的分割攻擊算法將密鑰熵由106 bit降至60 bit，降低了46 bit。

3 結束語

本文分析了一個基于混沌設計的分組密碼算法的安全性，發現該算法所產生的混沌序列具有前幾個值對混沌初態的低位比特變化不夠敏感的性質，在選擇明文攻擊條件下，提出了攻擊加密算法等效密鑰的分割攻擊方法。分割攻擊算法將密鑰熵由106 bit降至60 bit，存儲復雜性約為250，成功率為0.928 4。

參考文獻:

[1]KLEIN E， MISLOVATY R， KANTER I， et al. Publicchannel cryptography using chaos synchronization[J]. Physical Review E， 2005， 72(1): 016214.

[2]羅啟彬，張健. 一種新的混沌偽隨機序列生成方式[J]. 電子與信息學報， 2006， 28(7): 1262-1265.

[3]XIANG Tao， LIAO Xiaofeng， TANG Guoping， et al. A novel block cryptosystem based on iterating a chaotic map[J]. Physics Letters A， 2006:349:109-115.

[4]TENNY R， TSIMRING L S. Additive mixing modulation for public key encryption based on distributed dynamics[J]. IEEE Trans on Circuits and Systems， 2005， 52(3):672-679.

[5]YEN Juicheng， GUO Jiunin. A new chaotic keybased design for image encryption and decryption[C]//Proc IEEE International Symposium Circuits and Systems. 2000: 49-52.

[6]紀震，李慧慧，肖薇薇，等. 基于混沌序列的數字水印信號研究[J]. 電子學報， 2004， 32(7):1131-1134.

[7]SHORT K M. Signal extraction from chaotic communications[J]. Int J Bifurcation and Chaos， 1997， 7(7):1579-1597.

[8]LI Shujun， CHEN Guanrong， ALVAREZ G， et al. Returnmap cryptanalysis revisited[EB/OL]. http://arxiv.org/nlin.CD/0501018.

[9]WANG Xingang， ZHAN Meng， LAI C H， et al. Error function attack of chaos synchronization based encryption schemes[EB/OL]. http://arxiv.org/nlin.CD/0305015.

[10]李樹鈞，牟軒沁，紀震，等. 一類混沌流密碼的分析[J]. 電子與信息學報， 2003， 25(4): 473-479.

[11]金晨輝. 一個基于混沌的分組密碼算法的分析[J]. 中國工程科學， 2001， 3(6): 75-80.

[12]金晨輝，高海英. 對兩個基于混沌的序列密碼算法的分析[J]. 電子學報， 2004， 32(7):1066-1070.

[13]金晨輝，楊陽，祁傳達. 對混沌序列密碼的相關密鑰攻擊[J]. 電子與信息學報， 2006， 28(3):410-414.

[14]金晨輝，楊陽. 對自同步混沌密碼的分割攻擊方法[J]. 電子學報， 2006， 34(7):1337-1341.