幾個重要對稱密碼和通用密碼結(jié)構(gòu)的分析.pdf

1、隨著互聯(lián)網(wǎng)等技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)空間安全成為關(guān)系到國家安全戰(zhàn)略的重要課題。密碼學(xué)作為網(wǎng)絡(luò)空間安全的基礎(chǔ)學(xué)科，在我國網(wǎng)絡(luò)空間安全建設(shè)中發(fā)揮著重要的作用。密碼學(xué)中將密碼算法分為對稱密碼算法和非對稱密碼算法兩大類。對稱密碼算法包括分組密碼、流密碼、哈希函數(shù)以及認(rèn)證加密算法等。對稱密碼具有運算速度快、易于標(biāo)準(zhǔn)化、便于軟硬件實現(xiàn)等特點，已成為信息與網(wǎng)絡(luò)空間安全中實現(xiàn)數(shù)據(jù)加密、消息認(rèn)證和密鑰管理等關(guān)鍵領(lǐng)域的核心部件，被廣泛應(yīng)用。本文研究對象包括國際

2、通用分組密碼結(jié)構(gòu)Feistel-SP以及通用哈希模式(MMO、Miyaguchi-Preneel modes)的安全性分析，認(rèn)證加密競賽CAESAR第三輪候選算法KETJE的安全性分析，國際ISO/IEC標(biāo)準(zhǔn)算法Camellia的安全性分析。在研究中發(fā)現(xiàn)了一些有意義的密碼學(xué)性質(zhì)，并構(gòu)造了新的分析模型，得到了一些較好的研究成果。
　　國際通用密碼結(jié)構(gòu)的安全性分析
　　目前通用的分組密碼結(jié)構(gòu)都采用了迭代結(jié)構(gòu)，主要包括Feiste

3、l結(jié)構(gòu)、SPN結(jié)構(gòu)和Lai-Massey結(jié)構(gòu)等。Feistel結(jié)構(gòu)是20世紀(jì)60年代末IBM公司的Feistel等提出的，著名的數(shù)據(jù)加密標(biāo)準(zhǔn)DES即采用該結(jié)構(gòu)。對于分組長度為2n的r輪Feistel結(jié)構(gòu)的密碼，首先將2n比特的明文P劃分為兩個n比特，記為(L0，R0)，然后按照如下方式迭代r輪，對于第i=1，2，…，r，令{Li=Ri-1Ri=Li-1⊕ F(Ri-1，ki).2013年亞密會上，日本密碼學(xué)者Isobe和Shibutan

4、i將Feistel結(jié)構(gòu)進一步劃分為三類，記為Feistel-1/2/3.
　　分組密碼和哈希函數(shù)是很多密碼協(xié)議的基礎(chǔ)部件。隨著傳感器、智能卡等的廣泛使用，輕量級的密碼受到工業(yè)界和密碼學(xué)界的高度重視。很多輕量級的應(yīng)用環(huán)境中，完整性認(rèn)證和保密兩個功能同時被需要，采用分組密碼構(gòu)造哈希函數(shù)的技術(shù)使這種要求成為可能。著名密碼學(xué)家Bart Preneel等提出或分析了幾種采用分組密碼構(gòu)造哈希函數(shù)的工作模式，即著名的PGV模式，包括著名的Dav

5、ies-Meyer(DM)模式、Matyas-Meyer-Oseas(MMO)模式和Miyaguchi-Preneel(MP)模式等。因此分析由通用分組密碼和以上重要哈希模式構(gòu)造的哈希函數(shù)的安全性尤為重要。2007年，Knudsen和Rijmen在亞密會首先提出對分組密碼的已知密鑰攻擊模型，并給出由7輪Feistel-2類分組密碼構(gòu)造的MMO、MP類哈希函數(shù)的半碰撞(half-collision)攻擊。2009年，Biyukov等在美密

6、會上提出選擇密鑰攻擊模型，并給出了由全輪AES-256分組密碼構(gòu)造的DM類哈希函數(shù)的q維差分多碰撞，將AES-256與理想算法進行區(qū)分。2011年，Sasaki和Yasuda在2011年FSE會議上提出Feistel-SP類分組密碼的11輪已知密鑰區(qū)分攻擊，并給出了由Feistel-SP類分組密碼構(gòu)造的MMO、MP類哈希函數(shù)的9輪碰撞(full-collision)攻擊。
　　本文中，我們進一步探索Feistel-SP類分組密碼的

7、區(qū)分攻擊，以及采用該類分組密碼構(gòu)造的MMO、MP類哈希函數(shù)的碰撞攻擊。我們構(gòu)造了7輪反彈攻擊內(nèi)部對接路線，將Sasaki和Yasuda提出的5輪路線提高了兩輪，并利用密鑰自由度篩選出正確的7輪對接數(shù)據(jù)對，給出了12輪選擇密鑰區(qū)分攻擊，將之前的11輪區(qū)分攻擊提高了1輪。在分析通過Feistel-SP類分組密碼和MMO、MP哈希模式構(gòu)造的哈希函數(shù)類時，我們采用兩消息塊構(gòu)造碰撞的攻擊技術(shù)，第一個消息塊用來提供密鑰自由度，在第二個消息塊中，我們

8、構(gòu)造了11輪反彈攻擊路線，最終給出了11輪實際碰撞攻擊，復(fù)雜度為248.6，將之前由著名密碼學(xué)家Sasaki和Yasuda共同提出的9輪碰撞攻擊提高了2輪，進而證明在采用Feistel-SP結(jié)構(gòu)設(shè)計分組密碼時，輪數(shù)必須大于11輪，否則其對應(yīng)的MMO、MP類哈希函數(shù)將存在碰撞攻擊。
　　認(rèn)證加密競賽CAESAR第三輪候選算法Ketje的安全性分析
　　認(rèn)證加密算法屬于對稱密碼算法中的一種，它不僅支持?jǐn)?shù)據(jù)的保密功能，也支持?jǐn)?shù)據(jù)完

9、整性認(rèn)證功能。目前被廣泛使用的認(rèn)證加密算法為AES-GCM，為獲得安全性高、適用環(huán)境廣和穩(wěn)定性強的認(rèn)證加密算法，國際密碼學(xué)界啟動了CAESAR競賽。由于認(rèn)證加密標(biāo)準(zhǔn)的重要性，自2014年競賽啟動開始，共57個算法被密碼學(xué)家提出并分析，經(jīng)過兩輪的篩選，目前只有16個候選算法進入第三輪的評估。新的設(shè)計滿足新環(huán)境的應(yīng)用需要，但是同樣帶來未知的安全威脅。探索新的攻擊方法對提出安全可靠的認(rèn)證加密新標(biāo)準(zhǔn)至關(guān)重要。在2015年歐密會上，Dinur等首

10、先提出對KEYAK的立方攻擊，將流密碼的攻擊方法立方攻擊應(yīng)用到KEYAK當(dāng)中，給出了一些縮減輪的密鑰恢復(fù)攻擊和偽造攻擊。隨后在CT-RSA2015會議上，該方法被應(yīng)用到對縮減輪ASCON的分析中。2017年歐密會上，黃森洋等提出帶條件立方攻擊，改進了Dinur等的結(jié)果。在FSE2017會議上，李錚等將帶條件的立方攻擊模型化，并結(jié)合密鑰劃分技術(shù)將之前ASCON的分析結(jié)果提高了1輪，提出7輪的密鑰恢復(fù)攻擊，并給出6輪ASCON的實際攻擊（復(fù)

11、雜度240）。
　　本論文我們給出了KETJE的立方攻擊。KETJE是CAESAR第三輪16個候選算法之一，由KECCAK團隊（SHA-3設(shè)計者）設(shè)計，軟硬件效率高。我們利用立方攻擊技術(shù)給出了KETJE主算法的6/7輪密鑰恢復(fù)攻擊，并討論了其他KETJE族算法的安全性。首先我們將線性結(jié)構(gòu)技術(shù)應(yīng)用到尋找稀疏的立方變量集合中，并找到32維和64維立方變量集合，滿足第一輪中立方變量之間不相乘。然后我們引入新的動態(tài)變量，達到同時降低密鑰和

12、立方變量擴散的目的。這使得只有少量的密鑰影響6輪、7輪后的立方變量加和，從而將立方攻擊的分治法應(yīng)用到6輪、7輪KETJE SR的密鑰恢復(fù)攻擊中，復(fù)雜度較窮搜分別降低263.4和215倍。另外，我們還討論上述方法在其他KETJE族算法中的應(yīng)用，以及當(dāng)初始向量長度縮減為128比特時攻擊的效果，并給出了系列密鑰恢復(fù)攻擊。
　　國際ISO/IEC標(biāo)準(zhǔn)算法Camellia的安全性分析
　　Camellia是由日本電報電話公共公司NTT

13、和三菱電子公司聯(lián)合設(shè)計的一個分組密碼，最早在2000年SAC會議上提出。Camellia分組長度為128比特，密鑰長度包括128比特、192比特和256比特三個版本。該算法由國際標(biāo)準(zhǔn)化組織(ISO)選定為國際標(biāo)準(zhǔn)ISO/IEC18033-3，也被日本的CRYPTREC計劃推薦為日本e-government算法，被歐洲NESSIE競賽的列為獲勝算法之一。鑒于該算法的重要性，其安全性引起世界范圍內(nèi)密碼學(xué)家的關(guān)注，已有的分析包括不可能差分、中

14、間相遇攻擊、零相關(guān)等。
　　本文研究Camellia算法的多差分分析。結(jié)合Camellia-128組件差分?jǐn)U散性質(zhì)，采用搜索算法找到很多概率優(yōu)勢相對較弱的差分路線，并基于此構(gòu)造多差分路線。根據(jù)不同的多差分路線，將整個密鑰空間劃分為224+1個子集合，這些密鑰使得不同的差分在通過FL-1層時擴散最低?？傊覀儤?gòu)造出了224種8輪多差分路線，對于每個多差分路線，有243個概率較低的差分路線?；谠?輪多差分路線，我們對每個密鑰子集攻