針對(duì)ARX算法基于MILP的差分線性自動(dòng)化搜索技術(shù)與模減差分的SMT模型.pdf

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

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

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

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