自動(dòng)化搜索ARX型密碼差分-線性特征的模型及應(yīng)用.pdf

1、ARX結(jié)構(gòu)是一類僅包含模加(Addition)、循環(huán)移位(Rotation)和異或（Exclusive-OR）運(yùn)算的密碼結(jié)構(gòu)，在分組密碼、流密碼、Hash函數(shù)以及MAC算法中都有著廣泛的應(yīng)用。ARX型密碼有著算法結(jié)構(gòu)簡(jiǎn)單、運(yùn)算效率高的特點(diǎn)，非常適合于軟件的實(shí)現(xiàn)。
　　差分-線性分析方法是在1994年的美密會(huì)上被提出的。通過(guò)將滿足一定條件的高概率截?cái)嗖罘痔卣髋c高偏差線性逼近進(jìn)行組合得到高偏差的差分-線性特征，可對(duì)部分密碼算法進(jìn)行有效

2、地攻擊。2016年的歐密會(huì)上，Leurent使用差分-線性分析方法，結(jié)合改進(jìn)的比特劃分技術(shù)，對(duì)ARX型MAC算法Chaskey進(jìn)行了攻擊，嚴(yán)重威脅了Chaskey的安全性，體現(xiàn)了差分-線性分析方法對(duì)ARX型密碼分析的有效性。
　　自動(dòng)化搜索技術(shù)在密碼學(xué)中有著廣泛的應(yīng)用。尤其在近幾年，隨著對(duì)ARX型密碼研究的深入，已形成一整套搜索該類密碼差分特征和線性逼近的自動(dòng)化方法，然而并沒(méi)有搜索差分-線性特征的自動(dòng)化工具問(wèn)世。在實(shí)際應(yīng)用中，將搜

3、索差分特征的自動(dòng)化技術(shù)與搜索線性逼近的自動(dòng)化技術(shù)進(jìn)行簡(jiǎn)單結(jié)合，以期獲得長(zhǎng)輪數(shù)的差分-線性特征的方法并不十分可行。
　　鑒于如上現(xiàn)狀，本文提出了自動(dòng)化搜索ARX型密碼差分-線性特征的模型，并給出了實(shí)現(xiàn)該模型的一種可行方法。同時(shí)，為驗(yàn)證該模型的有效性，本文將該模型應(yīng)用到對(duì)ARX型MAC算法SipHash和分組密碼SPECK的差分-線性分析中，給出了二者的差分-線性分析結(jié)果。
　　對(duì)于SipHash系列算法中使用最廣泛的SipHa

4、sh-2-4算法，本文找到了終止化階段4輪的多條較優(yōu)的差分-線性特征。其中最優(yōu)特征的絕對(duì)值僅為2-2.84，進(jìn)行區(qū)分攻擊僅需27.68個(gè)已知明文。此前公布的最好的分析結(jié)果為差分分析結(jié)果，其最優(yōu)的差分特征概率為2-35，區(qū)分需235對(duì)選擇明文。在明文消息長(zhǎng)度不大于7字節(jié)且不考慮生成MAC的四支異或運(yùn)算的情況下，本文同樣給出多條較優(yōu)的差分-線性特征。此外，在原始消息長(zhǎng)度不大于7字節(jié)情況下，本文給出了SipHash-2-4全算法的差分-線性分