針對ARX算法基于MILP的差分線性自動化搜索技術與模減差分的SMT模型.pdf

1、隨著互聯(lián)網(wǎng)技術的快速發(fā)展，信息安全越來越受到重視。密碼學也因此逐漸成為一個熱門話題。根據(jù)研究方向的不同，密碼學主要分為對稱密鑰密碼學與公鑰密碼學。其中，分組密碼是對稱密鑰密碼的重要組成部分。分組密碼因其結構簡單，便于實現(xiàn)，被廣泛應用在各個數(shù)據(jù)加密場景。因此，分組密碼一直是密碼學界的研究熱點。
　　針對分組密碼算法，密碼學家提出許多攻擊方案。其中，差分分析與線性分析是兩種最經(jīng)典且最有效的破解手段。對于這兩種方法來說，最重要的事情莫過

2、于尋找出一條“好”的差分特征或線性逼近。因此，有關自動化搜索差分特征與線性逼近的工作是一個熱門研究方向。
　　近年來，基于混合整數(shù)線性規(guī)劃(MILP)的搜索技術越來越多的應用到分組算法的差分特征與線性逼近的自動化搜索中，且體現(xiàn)了較為顯著的優(yōu)勢，對Simon等分組密碼算法取得了較好的結果（Simon分組密碼算法是美國國家安全局NSA于2013年設計的一組輕量級加密算法，其特點是消耗硬件面積?。?。然而，目前還沒有基于MILP針對ARX

3、加密算法進行自動化搜索差分特征與線性逼近的方法。
　　在本文中，我們提出一種基于MILP自動化搜索ARX算法差分特征與線性逼近的新技術。通過研究ARX算法中模加操作的差分與線性特性，并在假設模加操作的輸入與輪與輪之間都是相互獨立的前提下，我們提出一種用線性不等式來描述模加操作差分特征與線性逼近特性的新方法。利用該方法，我們可以構建完全刻畫ARX算法差分線性特性的MILP模型，并用Gurobi（一種可公開獲得的MILP求解器）來搜索

4、ARX算法的差分特征與線性逼近。作為驗證，我們將該技術應用到Speck算法的分析中（Speck加密算法是美國國家安全局NSA于2013年設計的一組輕量級加密算法，其特點是消耗軟件資源小）。我們搜索出優(yōu)于已有結果的差分特征與線性逼近。利用新搜索出的差分特征以及guess-and-determine技術，我們改進了Speck48，Speck64，Speck96與Speck128的差分攻擊。值得注意的是，我們的攻擊目前就輪數(shù)來說是已知的最優(yōu)攻