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

1、雖然早在1949年Shannon就提出了現(xiàn)代分組密碼算法設(shè)計(jì)所遵循的兩大安全性準(zhǔn)則——混淆（Confusion）與擴(kuò)散(Diffusion)，但是現(xiàn)代分組密碼算法的研究卻真正開始于20世紀(jì)70年代中期，以數(shù)據(jù)加密標(biāo)準(zhǔn)DES的頒布為標(biāo)志。20世紀(jì)90年代差分分析、線性分析等分析方法的出現(xiàn)以及計(jì)算能力的突飛猛進(jìn)，促使美國(guó)和歐洲分別開始了AES以及NESSIE工程。這些征集工作極大地推動(dòng)了分組密碼算法的設(shè)計(jì)與分析理論的發(fā)展。由于差分分析與線性

2、分析的有效性，種種基于這兩種分析方法的新的分析模型被逐漸引入到分組密碼算法分析領(lǐng)域。差分分析關(guān)注密碼算法中出現(xiàn)的差分值的高概率傳播現(xiàn)象并圍繞此特性構(gòu)建模型進(jìn)行密鑰恢復(fù)攻擊。作為差分分析的衍生方法，不可能差分從另一個(gè)角度關(guān)注算法結(jié)構(gòu):利用算法中不可能出現(xiàn)的差分（概率為0）來(lái)排除錯(cuò)誤的密鑰猜測(cè)（正確密鑰下不可能出現(xiàn)的差分）。由于不可能差分在對(duì)諸多算法的分析中取得的顯著成果，以及線性分析與差分分析的相似性（都是基于算法結(jié)構(gòu)中出現(xiàn)的高概率事件進(jìn)

3、行密鑰恢復(fù)），線性領(lǐng)域中類似于不可能差分這樣強(qiáng)有力的分析工具的存在性成為值得考量的問題。
　　2012年，Bogdanov與Rijmen提出的零相關(guān)線性分析的概念（Zero-CorrelationLinear Cryptanalysis）開啟了這個(gè)方向的研究。線性分析依賴于分組密碼算法中存在的具有高概率偏差的線性逼近（或者線性殼），而零相關(guān)線性分析則從另一個(gè)角度入手，依賴于分組密碼算法中存在的相關(guān)度為零（偏差為零）的線性逼近。 B

4、ogdanov和Rijmen展示了如何利用算法中存在零相關(guān)線性逼近進(jìn)行密鑰恢復(fù)攻擊。然而對(duì)于高數(shù)據(jù)復(fù)雜度的需求極大的限制了零相關(guān)線性分析的應(yīng)用。借鑒多重線性分析的思想，F(xiàn)SE2012上Bogdanov和Wang利用大量零相關(guān)線性逼近，提出用區(qū)分統(tǒng)計(jì)分布的形式進(jìn)行密鑰恢復(fù)的新模型——多重零相關(guān)線性分析。新模型能夠利用l條零相關(guān)線性逼近，將攻擊所需的數(shù)據(jù)復(fù)雜度降為(6)(2n/√l)（n為目標(biāo)算法的分組長(zhǎng)度）。新模型的數(shù)學(xué)建模過程中，依賴的

5、強(qiáng)假設(shè)條件通常并不能滿足，零相關(guān)線性分析模型仍待完善。同年的ASIACRYPT上，Bogdanov等人提出多維零相關(guān)線性分析新模型在維持基本相同的數(shù)據(jù)復(fù)雜度的情況下，消除了對(duì)強(qiáng)假設(shè)條件的依賴，這一模型的提出標(biāo)志著零相關(guān)線性分析模型的成熟。
　　快速傅里葉變換(FFT)技術(shù)最初是由Collard等人在ICISC2007上引入到分組密碼分析領(lǐng)域。Collard等人指出在特定條件下部分算法的線性分析的時(shí)間復(fù)雜度可以通過FFT技術(shù)進(jìn)行改進(jìn)

6、。由于基于線性分析與基于多重零相關(guān)線性分析的密鑰恢復(fù)攻擊過程之間的相似性，F(xiàn)FT技術(shù)同樣可以用來(lái)改進(jìn)多重零相關(guān)線性分析的時(shí)間復(fù)雜度。FFT技術(shù)已經(jīng)被整合到線性分析、多重零相關(guān)線性分析以及及積分攻擊的攻擊過程中。雖然FFT技術(shù)獲得了廣泛應(yīng)用，但是FFT的現(xiàn)有理論要求密鑰恢復(fù)攻擊過程中的部分加解密階段僅有子密鑰異或操作和至多一個(gè)子密鑰模加操作。這一要求限制了FFT技術(shù)在ARX算法分析領(lǐng)域的應(yīng)用。擴(kuò)展的FFT技術(shù)以及對(duì)29輪CAST-256算

7、法的多重零相關(guān)線性分析本文中通過對(duì)FFT技術(shù)的理論基礎(chǔ)——循環(huán)矩陣（Circulant Matrix）理論的考察，發(fā)現(xiàn)即使在部分加解密階段存在多個(gè)子密鑰模加的情形，F(xiàn)FT技術(shù)仍然可以用來(lái)改進(jìn)這一階段的時(shí)間復(fù)雜度。這一發(fā)現(xiàn)拓展了FFT技術(shù)在密碼分析領(lǐng)域的應(yīng)用。在此基礎(chǔ)之上，我們重新考察了CAST-256在零相關(guān)線性分析模型下的安全性。通過將FFT技術(shù)整合到多重零相關(guān)線性分析技術(shù)，本文中給出了29輪CAST-256的多重零相關(guān)線性分析結(jié)果，

8、這一結(jié)果在是無(wú)弱密鑰假設(shè)條件下CAST-256的最好分析結(jié)果。
　　HIGHT的多維零相關(guān)線性分析HIGHT是韓國(guó)信息安全局參與設(shè)計(jì)的輕量級(jí)分組密碼算法并發(fā)表在CHES2006并且隨后被采納為ISO標(biāo)準(zhǔn)算法之一。HIGHT是采用8分支的Type-Ⅱ廣義Feistel結(jié)構(gòu)的32輪分組密碼算法，并且在第一輪之前以及最后一輪之后都有白化密鑰層。通過跟蹤線性掩碼在HIGHT算法內(nèi)的傳播，本文構(gòu)造了16輪HIGHT上的零相關(guān)線性逼近。在16

9、輪零相關(guān)線性逼近的基礎(chǔ)之上，通過優(yōu)化的密鑰猜測(cè)順序以及逐比特的部分和(Partial Sum)技術(shù)，我們首次給出了26輪HIGHT（包含全部白化密鑰，第4輪到第29輪）的密鑰恢復(fù)攻擊。另外，本文給出了27輪HIGHT（包含全部白化密鑰，第4輪到第30輪）的密鑰恢復(fù)攻擊。相比于已經(jīng)公開發(fā)表的對(duì)HIGHT的最好分析結(jié)果（不考慮Biclique等攻擊方法）——Chen等人在AFRICACRYPT2012上利用不可能差分分析技術(shù)對(duì)27輪HIGH

10、T（包含全部白化密鑰，第4輪到第30輪）的密鑰恢復(fù)攻擊，本文中給出的對(duì)27輪HIGHT的攻擊結(jié)果在存儲(chǔ)復(fù)雜度方面有著顯著的改進(jìn)。
　　E2的多維零相關(guān)線性分析E2是由日本NTT公司設(shè)計(jì)的128比特分組長(zhǎng)度的分組密碼算法，是AES征集過程中首輪的15個(gè)候選算法之一，而其設(shè)計(jì)理念被應(yīng)用到ISO標(biāo)準(zhǔn)算法Camellia算法的設(shè)計(jì)之中，因此E2的安全性得到了密碼分析學(xué)者的關(guān)注。E2的主密鑰可以為128、192、256比特，分別用E2-12

11、8，E2-192，E2-256來(lái)指代這三個(gè)版本的E2算法，其輪數(shù)都為12輪。在E2的安全性分析方面，本文構(gòu)建了6輪E2算法上的零相關(guān)線性逼近。在此基礎(chǔ)之上，本文給出了不考慮初始變換IT和最終變換FT的8輪的E2-128以及9輪的E2-256算法的密鑰恢復(fù)攻擊。與已有的針對(duì)E2的不可能差分分析結(jié)果相比，本文的分析結(jié)果能夠多攻擊一輪。而與之前的截?cái)嗖罘址治鼋Y(jié)果相比，本文中對(duì)8輪E2-128的攻擊在時(shí)間復(fù)雜度方面更具優(yōu)勢(shì)。另外，本文中也給出了

12、考慮初始變換IT和最終變換FT時(shí)對(duì)6輪E2-128以及7輪E2-256算法密鑰恢復(fù)攻擊，這也是針對(duì)E2的首個(gè)考慮初始變換IT和最終變換FT的攻擊結(jié)果。
　　由于零相關(guān)線性分析的有效性，零相關(guān)線性區(qū)分器與其它區(qū)分器之間的內(nèi)在聯(lián)系受到關(guān)注。Bogdanov等人在ASIACRYPT2012上指出在一定條件下零相關(guān)線性區(qū)分器等價(jià)于積分區(qū)分器并據(jù)此提出積分零相關(guān)攻擊的概念。與FFT技術(shù)的應(yīng)用相似，ARX算法上的零相關(guān)線性逼近通常不符合ASI

13、ACRYPT2012中的模式，無(wú)法從相應(yīng)結(jié)果中獲益。ARX算法中零相關(guān)線性區(qū)分器與積分區(qū)分器之間的聯(lián)系以及改進(jìn)的SHACAL-2分析結(jié)果本文中詳細(xì)考察了ARX算法的通用零相關(guān)線性逼近的模式以及其與積分區(qū)分器之間的聯(lián)系并指出在該模式下零相關(guān)線性區(qū)分器仍然可以轉(zhuǎn)化為積分區(qū)分器。據(jù)此，本文中構(gòu)造的12輪SHACAL-2算法上零相關(guān)線性逼近被轉(zhuǎn)化成為積分區(qū)分器。在該積分區(qū)分器的基礎(chǔ)之上，本文對(duì)30輪和32輪的SHACAL-2算法進(jìn)行了密鑰恢復(fù)攻

14、擊。
　　相關(guān)密鑰條件下對(duì)23輪LBlock算法的不可能差分分析本文最后一部分的工作關(guān)注LBlock算法在相關(guān)密鑰條件下安全性分析，采用的具體的分析模型是經(jīng)典的相關(guān)密鑰不可能差分分析。LBlock算法Wu和Zhang在ACNS2011上發(fā)表的輕量級(jí)分組密碼算法。該算法采用64比特的分組長(zhǎng)度以及80比特的主密鑰，并且是基于改造過的Feistel結(jié)構(gòu)設(shè)計(jì)而成，總輪數(shù)共32輪。更長(zhǎng)的相關(guān)密鑰不可能差分路徑通常意味著攻擊者能夠攻擊更多的輪