分組密碼算法和流密碼算法的安全性分析.pdf

1、當今是一個網(wǎng)絡時代，人們的生活方式與過去相比發(fā)生了很大的變化，足不出戶就可以通過網(wǎng)絡解決衣食住行中的絕大多數(shù)需求，例如，用淘寶網(wǎng)購買所需、用支付寶進行日常支付、用電子銀行轉賬等等。生活變得快捷而又方便。然而，事物都有兩面性，伴隨著生活的便捷而來的是財產安全和個人隱私的保障問題。這時，密碼的使用就是在網(wǎng)絡上對進行保護的一個關鍵技術點。它是類似防火墻似的存在，是一切網(wǎng)絡活動的基石。在網(wǎng)絡傳輸時一般使用的是對稱加密算法來進行加密操作，如流密碼

2、算法和分組密碼算法。因此，對現(xiàn)有的被廣泛重視和使用的分組密碼算法和流密碼算法的安全性進行研究和分析是非常有必要的。在本文中，首先，針對分組密碼算法建立統(tǒng)計積分區(qū)分器和多結構體統(tǒng)計積分區(qū)分器新模型，并將模型應用于實際算法中;其次，基于MILP方法首次將S盒的差分特征和線性特征考慮進不可能差分路線和零相關路線的自動化搜索中，首次給出ARX算法通用的不可能差分路線和零相關路線的自動化搜索方法，并將該方法應用于實際算法中;最后，在相關密鑰場景下

3、利用不可能差分方法給出流密碼算法Lizard的安全性分析結果。具體結果如下。
　　提出分組密碼算法統(tǒng)計積分區(qū)分模型，并利用該模型理論破解Skipjack變種算法、給出CAST-256的最優(yōu)攻擊結果和IDEA的最優(yōu)積分攻擊結果:積分攻擊是對稱密碼領域最強大的分析方法之一，被廣泛的應用于分組密碼算法的安全性分析中。它是基于概率為1的平衡特性來構建區(qū)分器。攻擊者可以通過固定輸入的一部分比特而遍歷剩下的所有比特的可能取值，觀察相應的輸出值

4、在某些比特上是否為均勻分布來區(qū)分真實算法和隨機置換。為了增加積分區(qū)分器的覆蓋輪數(shù)，攻擊者通常會在整個明文空間的限制條件下以特定的結構來遍歷更多的明文比特以使得平衡特性依然成立。然而這一要求限制了積分攻擊在很多算法分析中的應用。在本文中，為降低積分分析中使用的數(shù)據(jù)復雜度，基于超幾何分布和多項分布為算法和隨機置換構造不同的概率分布來進行區(qū)分，從而構建了統(tǒng)計積分這一新模型。這個新模型所需要的數(shù)據(jù)量與傳統(tǒng)的積分區(qū)分器所需的數(shù)據(jù)量相比降低了很多。

5、利用該模型對Skipjack變種算法、CAST-256和IDEA算法進行改進分析。
　　Skipjack算法是美國NSA設計并公開的首個分組密碼算法。這個算法抵抗不可能差分攻擊的能力較弱。為了加強Skipjack抗截斷差分類攻擊的能力，Knudsen等人給出了Skipjack算法的一個變種算法Skipjack-BABABABA。本文中，利用統(tǒng)計積分區(qū)分新模型首次成功破解了Skipjack的變種算法Skipjack-BABABABA

6、。
　　CAST-256算法是由Adams等人在SAC'97上提出的一個分組密碼算法。從其提出至今，許多分析結果被陸續(xù)給出，如差分分析、線性分析、飛去來器分析和零相關線性分析等。在本文中，利用統(tǒng)計積分區(qū)分器模型來攻擊CAST-256算法。首先，給出CAST-256算法一個29輪的攻擊結果。這個攻擊需要296.8個選擇明文、2219.4次加密、273字節(jié)存儲。通過對時間復雜度和數(shù)據(jù)復雜度之間進行折中，這個攻擊也可以使用283.9個選

7、擇明文、2244.4次加密和266字節(jié)存儲進行。據(jù)所知，這是在單密鑰場景且無弱密鑰假設下CAST-256算法的最優(yōu)攻擊結果。
　　IDEA算法是由Lai和Massey在1991年提出的分組密碼算法，現(xiàn)被廣泛的用于多個安全應用中，如IPSec和PGP。在本文中，利用統(tǒng)計積分區(qū)分器模型來攻擊IDEA算法。首次給出了IDEA算法的一個2.5輪的積分區(qū)分器，這個區(qū)分器是至今為止IDEA算法最長的區(qū)分器?；谶@個區(qū)分器，成功給出了IDEA算

8、法的一個4.5輪密鑰恢復攻擊結果。這個攻擊需要258.5個已知明文、2120.9次加密和246.6字節(jié)存儲來完成。從攻擊輪數(shù)角度看，這個攻擊是目前IDEA算法最優(yōu)的積分攻擊結果。
　　提出多結構體統(tǒng)計積分區(qū)分模型，并利用該模型給出AES算法在秘密密鑰下的最優(yōu)積分區(qū)分結果和（類）AES算法的最優(yōu)已知密鑰區(qū)分攻擊結果:統(tǒng)計積分區(qū)分模型有一定的局限性，僅僅考慮了使用區(qū)分器輸出上的一個平衡特性。在一些場景下，積分區(qū)分器的輸出處同時存在多個

9、平衡特性;在另一些場景下，區(qū)分器需要同時使用多個數(shù)據(jù)結構體才能有效。針對前者，使用統(tǒng)計積分區(qū)分器模型會浪費一些積分特性;針對后者，現(xiàn)有的統(tǒng)計積分區(qū)分器不能適應于這樣的場景。為了擴展統(tǒng)計積分區(qū)分器模型以便用于更多的場景中，構造了多結構體統(tǒng)計積分區(qū)分模型。利用該模型對AES在秘密密鑰下的積分區(qū)分攻擊進行改進，給出（類）AES算法的最優(yōu)已知密鑰區(qū)分攻擊。
　　AES(Advanced Encryption Standard)是由美國國家

10、標準與技術研究所(NIST)發(fā)布的一個標準分組密碼算法，已被廣泛的應用于數(shù)據(jù)加密算法、哈希函數(shù)和認證加密方案等。研究AES的區(qū)分攻擊可以幫助算法設計者和分析者來評估相關算法的安全界限。利用多結構體統(tǒng)計積分模型，給出了一個在秘密密鑰和秘密S盒場景下5輪AES算法的選擇密文區(qū)分攻擊結果。該攻擊所需的數(shù)據(jù)、時間和存儲復雜度分別為2114.32個選擇密文、2110次加密和233.32的存儲。這個積分區(qū)分器是AES算法迄今為止在秘密密鑰和秘密S盒

11、場景下最優(yōu)的積分區(qū)分結果。除此之外，將多結構體統(tǒng)計積分模型應用于AES算法的已知密鑰區(qū)分器中。改進了Gilbert給出的原有結果。以242.61的時間復雜度完成對8輪AES的已知密鑰區(qū)分攻擊，以259.60的時間復雜度完成對全輪AES的已知密鑰區(qū)分攻擊。從時間復雜度的角度來看，給出的區(qū)分器是AES在已知密鑰場景下最優(yōu)的區(qū)分結果。
　　另外，AES算法采用的寬軌道設計思想被廣泛的用于哈希函數(shù)的設計中，如ISO標準哈希函數(shù)Whirlp

12、ool、國際重要的輕量級哈希函數(shù)PHOTON和SHA-3評選競賽最后一輪的五個候選算法之的Gr(o)stl算法等。這些算法的壓縮函數(shù)均采用類AES算法設計而成。哈希函數(shù)本身的安全性直接取決于內部置換的安全性，即類AES算法在已知密鑰場景下的安全性。與AES算法的已知密鑰區(qū)分攻擊方法類似的，可以將多結構體統(tǒng)計積分模型用于類AES算法的已知密鑰區(qū)分中。分別給出Whirlpool、Gr(o)stl-256和PHOTON的內部置換在已知密鑰場景

13、下最優(yōu)的區(qū)分結果。
　　提出基于MILP的不可能差分路線和零相關路線自動化搜索工具:不可能差分分析和零相關線性分析是對稱密碼領域有力的分析手段。現(xiàn)有多個用于搜索帶S盒算法的不可能差分路線的自動化工具，然而這些工具往往只關注于算法的線性層性質而將S盒理想化。事實上，在現(xiàn)實中理想的S盒并不存在，因而在理想S盒下搜出的差分路線有可能在實際中并不存在。在本工作中，首次將S盒的差分特征和線性特征考慮進不可能差分路線和零相關線性路線的搜索中，

14、提出基于MILP自動化搜索帶S盒算法的不可能差分路線和零相關路線的方法。除此之外，首次給出針對ARX算法的通用不可能差分路線和零相關線性路線的自動化搜索方法。作為應用實例，將該方法應用于HIGHT、SHACAL-2、LEA、LBlock、Salsa20和Chaskey中，改進了HIGHT、SHACAL-2、LEA和LBlock算法現(xiàn)有的（相關密鑰）不可能差分路線或零相關路線，首次給出Salsa20和Chaskey中使用的置換的不可能差分

15、路線。
　　相關密鑰場景下Lizard算法的安全性分析:Lizard是由Hamann等人在ToSC2016上提出的一個抗生日攻擊的流密碼算法。算法以120比特密鑰和64比特Ⅳ為輸入，內部狀態(tài)為121比特，輸出一個至多218比特的密鑰流。設計者聲明該算法抗密鑰恢復攻擊的安全性為80比特，抗區(qū)分攻擊的安全性為60比特。基于Banik等人利用碰撞對來恢復密鑰的思想，在本文中，利用猜測復合密鑰的方法在單密鑰場景下直接將密鑰恢復階段增加1輪

16、從而給出227步的攻擊結果，這在單密鑰場景下是Lizard算法的最優(yōu)密鑰恢復結果;在相關密鑰場景下將攻擊改進到233步，使得Lizard算法的安全冗余僅剩23步（共256步）。在相關密鑰場景下，首先通過選擇密鑰差分拉長不可能差分路線來進行密鑰恢復攻擊。然而，密鑰差分的引入帶來的一個問題是內部狀態(tài)的某些比特上的不確定性。為了克服這一問題，提出了“slide-collision”技術。除此之外，發(fā)現(xiàn)了一旦知道一個碰撞對，在相關密鑰場景下，無