密碼算法的高階差分分析與可證明安全性

《密碼算法的高階差分分析與可證明安全性》是依託上海交通大學，由來學嘉擔任項目負責人的面上項目。

基本介紹

• 中文名：密碼算法的高階差分分析與可證明安全性
• 項目類別：面上項目
• 項目負責人：來學嘉
• 依託單位：上海交通大學

項目摘要

在密碼算法的研究中最重要的是安全性分析。差分分析是其中最早提出同時也是最有效的分析方法。在此基礎上近年來衍生出了許多新的密碼分析方法。高階差分分析就是其中一種由差分分析方法擴展而得到的密碼分析方法。近期國際上的研究表明，高階差分能有效地分析密碼算法的安全性，但同時也揭示了其在理論和方法上的不足，特別是利用函式的代數特徵研究密碼函式的高階差分特性還有許多工作可做。.本課題將從理論基礎和實際攻擊兩方面對密碼函式的高階差分性質做深入研究，探討密碼函式高階差分的代數特性，用高階差分的方法改進最近提出一些新攻擊，從高階差分的角度研究密碼算法的可證安全性，並在此基礎上提出評價密碼函式安全性的判定準則和密碼算法的設計原理。

結題摘要

總結和分析了各種高階差分攻擊技術的理論基礎,證明了已知的高階差分類攻擊技術,如高階差分攻擊,AIDA攻擊,Cube攻擊,Cube測試和比特高階差分攻擊，本質上都是基於布爾函式高階導數的基本性質. 並挖掘出新的高階差分攻擊技術. 給出了一個基於布爾函式高階導數性質的高階差分分析框架。 高階差分攻擊基於布爾函式在高階導數後次數降低的性質。我們研究了布爾函式某些特殊差分點為快速次數下降點的充分必要條件，給出了布爾函式高階導數關於快速點性質的一個相對完整和有規律的總結。證明了一個n元的布爾函式的快速點構成一個線性子空間，並且其維數與函式的次數之和不超過變元個數n。我們還證明了非零的快速點必定存在於如下函式之中：任意n元n-1次的布爾函式、任意次數模2不同餘n的對稱布爾函式和任意奇數變元二次布爾函式。我們還詳細地給出了n元n-2次的布爾函式快速點的特殊性質並指出了其它類型布爾函式快速點的大致規律。 利用布爾函式快速點特性對分組密碼算法進行了一系列的區分攻擊，進而給出了一個新的分組密碼設計準則。具體地：我們證明了擁有最高次數不足以保證分組密碼算法能夠抵抗高階差分區分攻擊。證明了一個有最優次數n-1的n比特分組密碼算法在如下兩種情況下能夠以不可忽略的區分優勢和2^(n-1)的區分複雜度進行區分；超過一半的分量布爾函式的次數低於n-1或者超過一半的n-1次分量布爾函式的最高次單項式完全相同。 利用基於高階差分分析理論的零和區分攻擊技術對hash標準SHA-3算法進行了區分攻擊，構造關於全24輪置換Keccak-f的大小為2^1575的零和分布，優於之前的最好結果2^1590。 對分組密碼密鑰編排方案從差分、混淆的角度進行了安全性研究，利用密鑰編排方案和分組密碼輪函式之間的關係得出更好的攻擊方法。提出了實際密鑰信息（AKI），密碼泄露的概念，用於評價密碼方案的安全性。指出了AES和多個輕量級密碼構造中的問題，並提出改進方案。 提出不可能差分歸一化分析(UID)方法，自動搜尋分組密碼不可能差分鏈。將UID方法用於韓國標準ARIA及其它密碼算法，找出了比已知結果更為全面的不可能差分鏈。 研究了基於分組密碼的哈希函式的構造與安全性。