分組密碼的密鑰編排方案研究及單密鑰攻擊研究.pdf

1、作為最重要的對稱密碼算法之一，分組密碼算法由于運行速度快，軟硬件實現(xiàn)方便，適用于加密大數(shù)據(jù)量等特點，在實際安全領(lǐng)域中應(yīng)用廣泛。作為這些領(lǐng)域中的核心算法，分組密碼的設(shè)計和安全性評估近幾十年來一直是密碼學(xué)者研究的熱點。安全而高效的分組密碼是研究的重中之重。
　　分組密碼的實際安全性基于其抵抗密碼攻擊的能力。多數(shù)密碼攻擊技術(shù)利用密碼結(jié)構(gòu)和輪函數(shù)本身的弱點，如線性攻擊，差分攻擊等。而作為分組密碼中不可或缺的獨立模塊，近年來密鑰編排方案在攻

2、擊中所起的作用逐漸被重視，涌現(xiàn)了一些新興的利用密鑰編排方案弱點的攻擊，如中間相遇攻擊及其變體。盡管如此，和密碼結(jié)構(gòu)和輪函數(shù)相比，針對密鑰編排方案設(shè)計的研究相對較少。當(dāng)前多數(shù)的設(shè)計準(zhǔn)則都是針對密碼結(jié)構(gòu)和輪函數(shù)提出的，對密鑰編排方案缺乏具有實際指導(dǎo)意義的設(shè)計準(zhǔn)則。
　　本文的研究對象為分組密碼，重點研究密鑰編排方案對密碼安全性的影響，同時也研究不考慮密鑰編排方案影響的單密鑰攻擊技術(shù)。研究貢獻主要分為兩大塊。
　　第一塊貢獻是研究

3、受密鑰編排方案影響的攻擊和避免這些攻擊的設(shè)計準(zhǔn)則，包括如何利用密鑰編排方案的弱點獲得更好的攻擊結(jié)果、如何設(shè)計安全高效的密鑰編排方案，以及給出具體的設(shè)計實例。這部分研究成果為密鑰編排方案的設(shè)計提供了新的指導(dǎo)思想。具體研究成果及創(chuàng)新性如下：
　　1.探討密鑰編排方案在密碼攻擊技術(shù)中所處的地位。首先，定義實際密鑰信息(actual key information, AKI)，用于精確刻畫密鑰編排方案的弱點導(dǎo)致實際攻擊的一般規(guī)律。我們發(fā)現(xiàn)

4、，多數(shù)和密鑰編排方案相關(guān)的攻擊均利用了計算路徑上實際密鑰信息AKI不足這一弱點。而AKI不足的一個重要原因是密鑰編排方案的擴散層和算法輪函數(shù)的擴散層存在相互作用，從而導(dǎo)致了計算路徑上密鑰比特信息的泄露。在此基礎(chǔ)上，本文提出一個密鑰編排方案設(shè)計準(zhǔn)則以避免密鑰比特泄漏現(xiàn)象，為分組密碼輪函數(shù)和密鑰編排方案擴散層的設(shè)計提供科學(xué)依據(jù)。同時，本文開發(fā)出一個高效的密鑰編排方案檢測工具來自動搜索密鑰編排方案的弱點。對攻擊者而言，該工具可以用于檢測現(xiàn)有密

5、碼的安全漏洞，從而進行攻擊。對設(shè)計者而言，該工具可以用于檢測設(shè)計中的密鑰編排方案，為構(gòu)造安全有效的密鑰編排方案提供實際保障。
　　2.基于上述研究成果給出實際的攻擊范例，利用AKI不足的計算路徑獲得了對多個分組密碼的新的攻擊結(jié)果。包括，優(yōu)化了Serpent中間相遇攻擊的時間復(fù)雜度，優(yōu)化了AES-256中間相遇攻擊的內(nèi)存復(fù)雜度，延伸了一輪對Safer++256的積分攻擊，給出了TWINE-80的首個具有極低數(shù)據(jù)復(fù)雜度的攻擊；發(fā)現(xiàn)了對

6、XTEA的一個新的中間相遇攻擊，該攻擊結(jié)果和XTEA現(xiàn)有最好的攻擊結(jié)果相當(dāng)，但攻擊過程更簡單。
　　3.給出AES的一個新的密鑰編排方案設(shè)計，該設(shè)計提高了AES在單密鑰和相關(guān)密鑰攻擊模型下的安全性。由于該設(shè)計沒有額外引入非線性模塊(如S盒)，也沒有額外引入其它增加擴散程度的操作(如模加、異或等)，其執(zhí)行效率和AES原有的密鑰編排方案幾乎相當(dāng)，遠遠快于其它的AES密鑰編排方案變體。
　　第二塊貢獻是研究不考慮密鑰編排方案影響的

7、單密鑰模型下的密碼攻擊技術(shù)，如線性攻擊及其變體。此類攻擊的研究成果能幫助更好地理解分組密碼輪函數(shù)和結(jié)構(gòu)的設(shè)計和安全性。具體研究成果如下：
　　1.對降低輪數(shù)的Serpent分組密碼考查了線性攻擊的選擇明文變體。通過合理地固定部分明文輸入比特，對10輪Serpent，使用單個逼近式的線性攻擊的數(shù)據(jù)復(fù)雜度可以降低222個數(shù)量級。本文還給出目前為止最好的攻擊10輪Serpent的數(shù)據(jù)復(fù)雜度，即，280個明密文對。同時，本文將固定明文技術(shù)

8、擴展到多維線性攻擊，并在不同的攻擊場景下改進了時間和/或數(shù)據(jù)復(fù)雜度。最后，對5輪Serpent進行了實驗攻擊以驗證該固定明文技術(shù)的正確性。
　　2.對19輪的MIBS輕量級分組密碼給出了一個多維線性攻擊。該攻擊在數(shù)據(jù)復(fù)雜度和攻擊輪數(shù)上都是目前最優(yōu)的。在前人的工作基礎(chǔ)上，進一步發(fā)現(xiàn)了594個線性逼近式，利用這一發(fā)現(xiàn)，降低了攻擊的數(shù)據(jù)復(fù)雜度。同時，本文改進了Nguyen等對多維線性攻擊計數(shù)階段時間復(fù)雜度的優(yōu)化技術(shù)，使該技術(shù)不局限用于掩

9、碼相同的線性逼近式，也可用于掩碼不同的逼近式。利用新發(fā)現(xiàn)的逼近式和改進的優(yōu)化技術(shù)，對MIBS的攻擊時間復(fù)雜度得以降低。
　　3.本文提出一個適用于任意實際分組密碼的中間相遇攻擊。該攻擊的成功率逼近于1，數(shù)據(jù)復(fù)雜度極低，時間復(fù)雜度可表示為2k(1??)，其中?>0。先前，普遍認為主密鑰長度為k的分組密碼的安全界為k比特，本文的攻擊結(jié)果表明這一安全界被高估了。由于實際分組密碼存在不可避免的密鑰比特損失，其實際的安全界無法達到k比特。本