分組密碼算法幾種分析模型的研究.pdf

1、分組密碼算法是保證當(dāng)今網(wǎng)絡(luò)空間中信息私密性的一類重要的密碼算法，密碼設(shè)計(jì)與密碼分析是研究分組密碼算法的兩個(gè)主要方面，兩者相輔相成，不斷推動(dòng)對(duì)稱密碼算法體系的發(fā)展。
　　本文主要研究分組密碼算法的安全性分析方法，對(duì)幾類重要的分析模型的攻擊過程或者是攻擊使用的區(qū)分器進(jìn)行改進(jìn)。具體研究的分析模型包括線性分析、多維線性分析、多維零相關(guān)線性分析、不可能差分分析、零相關(guān)分析以及積分分析，相關(guān)工作為(1)改進(jìn)了卡方法多維線性分析模型以及多維零相

2、關(guān)線性分析模型的攻擊過程;(2)將動(dòng)態(tài)密鑰猜測(cè)技術(shù)引入到面向比特的分組密碼算法的線性分析模型中并對(duì)Simon進(jìn)行了改進(jìn)的線性分析，有效的降低了攻擊的時(shí)間復(fù)雜度;(3)對(duì)不可能差分區(qū)分器、零相關(guān)區(qū)分器、積分區(qū)分器之間的關(guān)系進(jìn)行了進(jìn)一步研究，提出了零相關(guān)區(qū)分器向積分區(qū)分器轉(zhuǎn)化的一般方法，并建立了Feistel-type算法不可能差分區(qū)分器與零相關(guān)區(qū)分器之間更有效的等價(jià)條件。
　　改進(jìn)卡方法多維線性分析以及多維零相關(guān)分析模型:多維線性分

3、析和多維零相關(guān)線性分析是攻擊分組密碼算法的兩種重要的分析模型，在使用卡方法的多維線性分析模型中（或者多維零相關(guān)線性分析模型），用來區(qū)分正確密鑰和錯(cuò)誤密鑰的統(tǒng)計(jì)數(shù)是從多維區(qū)分器的概率分布情況計(jì)算得出。而在本文中，我們提出了一種計(jì)算統(tǒng)計(jì)數(shù)更簡(jiǎn)單的方法:在隨機(jī)的明文空間下，從多維（零相關(guān)）線性路線的試驗(yàn)的相關(guān)系數(shù)出發(fā)，計(jì)算最終的統(tǒng)計(jì)數(shù)。這樣，可以省掉計(jì)算概率分布的過程，如果在計(jì)算每條路線相關(guān)系數(shù)的時(shí)候，將FFT技術(shù)引入的話，可以降低disti

4、llation階段的時(shí)間復(fù)雜度。
　　為了說明我們新模型的有效性，我們使用多維零相關(guān)線性分析方法對(duì)具有雙射輪函數(shù)且模加（或異或）輪密鑰的Feistel結(jié)構(gòu)進(jìn)行了一般性攻擊，對(duì)于模加密鑰的情況，我們的結(jié)構(gòu)攻擊在輪數(shù)上是最優(yōu)的;我們還分析了CAST-256，將其多維零相關(guān)分析結(jié)果從28輪擴(kuò)展到了29輪，改進(jìn)了一輪攻擊，雖然與已有的29輪多重零相關(guān)分析結(jié)果具有相近的復(fù)雜度，但是我們的攻擊對(duì)區(qū)分器沒有獨(dú)立假設(shè)，是在無假設(shè)條件下最優(yōu)的攻擊結(jié)

5、果。
　　利用動(dòng)態(tài)密鑰猜測(cè)技術(shù)改進(jìn)對(duì)Simon的線性分析:Simon是美國(guó)國(guó)家安全局(NSA)在2013年提出的輕量級(jí)分組密碼算法，自出現(xiàn)起就吸引了廣大密碼學(xué)者的注意力，至今已存在許多的分析結(jié)果，包括差分分析、線性分析、不可能差分分析、積分分析等。在本文中，我們將動(dòng)態(tài)密鑰猜測(cè)技術(shù)（該思想提出時(shí)是與差分分析結(jié)合，有效的改進(jìn)了對(duì)Simon的差分分析結(jié)果）引入到面向比特的分組密碼算法的線性分析模型中并對(duì)Simon進(jìn)行了改進(jìn)的線性分析，有

6、效的降低了攻擊的時(shí)間復(fù)雜度。
　　基本思路是:首先建立線性區(qū)分器的活性比特向兩邊擴(kuò)展幾輪后的布爾函數(shù)，發(fā)現(xiàn)其中存在許多“與”運(yùn)算，通過猜測(cè)“與”一邊的密鑰來簡(jiǎn)化布爾函數(shù)，進(jìn)而使得針對(duì)不同的情況，猜測(cè)不同的密鑰值，可以有效的降低密鑰的平均猜測(cè)量，從而降低時(shí)間復(fù)雜度。我們改進(jìn)了Simon算法所有10個(gè)版本的線性分析結(jié)果，具體為可以攻擊23輪SIMON32/64,24輪SIMON48/72,25輪SIMON48/96,30輪SIMON6

7、4/96,31輪SIMON64/128，37輪SIMON96/96，38輪SIMON96/144，49輪SIMON128/128，51輪SIMON128/192以及53輪SIMON128/256。對(duì)大多數(shù)版本來說，我們的攻擊在輪數(shù)上是最優(yōu)的。
　　零相關(guān)、不可能差分、積分區(qū)分器的新關(guān)系:零相關(guān)(ZC)、不可能(ID)以及積分(IG)分析方法也是分析分組密碼算法的三種重要模型，最近幾年，三種分析模型攻擊使用的區(qū)分器之間的關(guān)系成為密碼

8、學(xué)者關(guān)注的焦點(diǎn)之一。在ASIACRYPT'12上， Bogdanov等人給出了零相關(guān)路線與積分路線的一個(gè)基本關(guān)系，可以從輸入掩碼與輸出掩碼相互獨(dú)立的零相關(guān)路線推導(dǎo)出一條積分路線。在ACNS'14上，Blondeau等人使用矩陣表示法，給出了幾類結(jié)構(gòu)的不可能差分路線與零相關(guān)路線的等價(jià)條件。在CRYPTO'15上，Sun等人也給出了針對(duì)這幾個(gè)分析方法區(qū)分器等價(jià)關(guān)系的結(jié)論。
　　在本文中，我們(1)針對(duì)具有非獨(dú)立的輸入輸出掩碼的零相關(guān)路

9、線轉(zhuǎn)化為積分路線的方法進(jìn)行了深入研究，并給出了將零相關(guān)路線轉(zhuǎn)化為積分路線的更容易的方法，并給出了TEA、XTEA和HIGHT的新的積分路線;(2)使用可逆的矩陣構(gòu)造Feistel-type結(jié)構(gòu)不可能差分路線與零相關(guān)路線等價(jià)性條件，與之前的置換矩陣相比，可以覆蓋更多算法。利用此方法，成功利用算法自身的特點(diǎn)解釋了SMS4-like、MARS-like、Skipjack算法Rule-A結(jié)構(gòu)和Rule-B結(jié)構(gòu)中不可能差分路線與零相關(guān)路線的等價(jià)性