幾個(gè)重要對稱密碼和通用密碼結(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)證加密算法等。對稱密碼具有運(yùn)算速度快、易于標(biāo)準(zhǔn)化、便于軟硬件實(shí)現(xiàn)等特點(diǎn)，已成為信息與網(wǎng)絡(luò)空間安全中實(shí)現(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劃分為兩個(gè)n比特，記為(L0，R0)，然后按照如下方式迭代r輪，對于第i=1，2，…，r，令{Li=Ri-1Ri=Li-1⊕ F(Ri-1，ki).2013年亞密會(huì)上，日本密碼學(xué)者Isobe和Shibutan

4、i將Feistel結(jié)構(gòu)進(jìn)一步劃分為三類，記為Feistel-1/2/3.
　　分組密碼和哈希函數(shù)是很多密碼協(xié)議的基礎(chǔ)部件。隨著傳感器、智能卡等的廣泛使用，輕量級(jí)的密碼受到工業(yè)界和密碼學(xué)界的高度重視。很多輕量級(jí)的應(yīng)用環(huán)境中，完整性認(rèn)證和保密兩個(gè)功能同時(shí)被需要，采用分組密碼構(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在亞密會(huì)首先提出對分組密碼的已知密鑰攻擊模型，并給出由7輪Feistel-2類分組密碼構(gòu)造的MMO、MP類哈希函數(shù)的半碰撞(half-collision)攻擊。2009年，Biyukov等在美密

6、會(huì)上提出選擇密鑰攻擊模型，并給出了由全輪AES-256分組密碼構(gòu)造的DM類哈希函數(shù)的q維差分多碰撞，將AES-256與理想算法進(jìn)行區(qū)分。2011年，Sasaki和Yasuda在2011年FSE會(huì)議上提出Feistel-SP類分組密碼的11輪已知密鑰區(qū)分攻擊，并給出了由Feistel-SP類分組密碼構(gòu)造的MMO、MP類哈希函數(shù)的9輪碰撞(full-collision)攻擊。
　　本文中，我們進(jìn)一步探索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ù)類時(shí)，我們采用兩消息塊構(gòu)造碰撞的攻擊技術(shù)，第一個(gè)消息塊用來提供密鑰自由度，在第二個(gè)消息塊中，我們

8、構(gòu)造了11輪反彈攻擊路線，最終給出了11輪實(shí)際碰撞攻擊，復(fù)雜度為248.6，將之前由著名密碼學(xué)家Sasaki和Yasuda共同提出的9輪碰撞攻擊提高了2輪，進(jìn)而證明在采用Feistel-SP結(jié)構(gòu)設(shè)計(jì)分組密碼時(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)定性強(qiáng)的認(rèn)證加密算法，國際密碼學(xué)界啟動(dòng)了CAESAR競賽。由于認(rèn)證加密標(biāo)準(zhǔn)的重要性，自2014年競賽啟動(dòng)開始，共57個(gè)算法被密碼學(xué)家提出并分析，經(jīng)過兩輪的篩選，目前只有16個(gè)候選算法進(jìn)入第三輪的評估。新的設(shè)計(jì)滿足新環(huán)境的應(yīng)用需要，但是同樣帶來未知的安全威脅。探索新的攻擊方法對提出安全可靠的認(rèn)證加密新標(biāo)準(zhǔn)至關(guān)重要。在2015年歐密會(huì)上，Dinur等首

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

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

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

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

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