密碼算法TWINE和NTRU的安全性分析.pdf

1、密碼學(xué)作為信息安全的重要基礎(chǔ)，在現(xiàn)代網(wǎng)絡(luò)社會中發(fā)揮著極其重要的作用。密碼學(xué)中的加密算法分為非對稱加密算法（又稱為公鑰加密算法）和對稱加密算法（又稱為私鑰加密算法）兩大類。本文的研究對象TWINE是對稱加密算法，NTRU是非對稱加密算法。
　　對稱密碼包括分組密碼、流密碼和哈希函數(shù)。隨著手持設(shè)備、RFID等的發(fā)展，在資源受限的環(huán)境中使用的分組密碼（即輕量級分組密碼）得到了廣泛關(guān)注并迅速發(fā)展起來。輕量級分組密碼算法TWINE即是在此背

2、景下提出的。TWINE是由Suzaki等在2011年的ECRYPT輕量級密碼會議上首次提出的，并發(fā)表在2012年的SAC會議上。它的分組長度是64比特，密鑰長度有80比特和128比特兩個版本，其采用廣義的Feistel結(jié)構(gòu)（Generalized Feistel Structure，簡稱GFS），并由36輪輪函數(shù)構(gòu)成。
　　公鑰密碼算法NTRU是由Hoffstein等在1996年的美密會上提出的。它是基于多項式環(huán)R=Z[x]/（x

3、n-1）上的運算。雖然沒有嚴格的規(guī)約證明，但是它的安全性被認為是基于求解格上困難問題的困難性，所以NTRU算法具有抵抗量子計算攻擊的能力。在計算效率方面，因為NTRU算法的簡潔設(shè)計，它的計算速度比RSA算法和橢圓曲線算法快很多。正是因為它具有高效和安全的雙重屬性，出現(xiàn)了很多針對它的安全性研究。
　　在密碼學(xué)的發(fā)展過程中，密碼設(shè)計和密碼分析是相互對立又相互促進的。密碼學(xué)家利用許多數(shù)學(xué)方法設(shè)計出好的密碼算法，然后密碼分析學(xué)者試圖找出算

4、法的缺陷并進行攻擊嘗試，之后設(shè)計者避免已知缺陷、設(shè)計出更安全高效的密碼算法。正如NIST征集美國加密標(biāo)準(zhǔn)AES，歐洲的NESSIE工程，日本的CRYPTREC工程等使得密碼的設(shè)計技術(shù)和分析技術(shù)都得到了快速發(fā)展。本論文對兩個重要的密碼算法進行安全性分析，有利于深入理解其可能的缺陷和安全強度。
　　對密碼算法的安全性分析包括對其算法層面的理論分析和對其實現(xiàn)層面的實際安全性分析。本文的工作對TWINE算法進行了理論分析，對NTRU進行了

5、實現(xiàn)算法的實際安全性分析。分組密碼算法的理論分析技術(shù)包括差分分析、線性分析、不可能差分分析、代數(shù)分析等。本文使用不可能差分分析對輕量級分組密碼算法TWINE進行了安全性評估。在密碼芯片的安全性分析方面，側(cè)信道攻擊是密碼芯片系統(tǒng)遭遇的主要威脅之一。自從Kocher在1996年的美密會上首次提出時間攻擊的概念之后，側(cè)信道攻擊得到了迅猛發(fā)展，能量攻擊是側(cè)信道攻擊中最常見和最容易實現(xiàn)的方法。能量分析攻擊包括簡單能量分析、差分能量分析、高階差分能

6、量分析和碰撞攻擊等。鑒于這些攻擊給密碼芯片系統(tǒng)帶來的實際威脅，抵抗這些攻擊的防御對策研究也隨之迅速發(fā)展。本文使用碰撞攻擊對有防御對策保護的NTRU算法進行安全性評估。
　　輕量級分組密碼TWINE的不可能差分分析
　　根據(jù)TWINE的密鑰生成算法，本工作給出輪密鑰之間的一些觀察，既有簡單的密鑰相等關(guān)系，也有較復(fù)雜的函數(shù)關(guān)系。這些密鑰關(guān)系影響了攻擊者對不可能差分路線的選取和密鑰恢復(fù)算法的具體操作。在選擇最優(yōu)的不可能差分路線時，

7、攻擊者首先尋找最長的路線，然后依據(jù)截斷差分路線中輪密鑰關(guān)系從多條最長的路線中挑選出最優(yōu)的一條不可能路線。這條最優(yōu)路線一方面要使得截斷差分路線中涉及到的不相等密鑰的個數(shù)最少，同時也要使得這些密鑰的函數(shù)關(guān)系相對更簡單，從而使過濾密鑰階段的時間復(fù)雜度能更低。
　　在已知文獻的不可能差分攻擊中，攻擊者將滿足頭部截斷差分路線和尾部截斷差分路線的子密鑰分別篩選出來，然后兩部分子密鑰的直接合并就給出了錯誤子密鑰。因為這些攻擊中涉及的不相等子密鑰

8、的比特數(shù)都沒有超過主密鑰比特數(shù)，所以假設(shè)這些子密鑰相互獨立并把兩部分子密鑰直接合并的攻擊是可行的。但是我們試圖攻擊更多的輪數(shù)，因此在我們的攻擊路線中，頭部截斷差分路線的子密鑰和尾部截斷差分路線的子密鑰之和超出了主密鑰比特數(shù)，也即這些子密鑰之間存在信息冗余。那么將兩部分子密鑰直接合并作為錯誤子密鑰的算法不再可行，我們給出了一個新的篩選錯誤子密鑰的算法。我們的算法同時考慮截斷差分路線和密鑰關(guān)系這兩個條件，逐步鏈接滿足這兩個條件的子密鑰，直至

9、所有子密鑰鏈接完成。
　　另外，我們的攻擊采用了預(yù)計算技術(shù)并對攻擊的時間復(fù)雜度和空間復(fù)雜度進行了平衡;在恢復(fù)密鑰階段優(yōu)化了密鑰關(guān)系的使用順序;根據(jù)TWINE算法s盒的差分特性給出更精確的明密文差分特征，從而加快數(shù)據(jù)收集階段正確明密文對的篩選速度。我們對23輪TWINE-80攻擊的時間復(fù)雜度是279.09次加密，數(shù)據(jù)復(fù)雜度是257.85個分組，存儲復(fù)雜度是278.04個分組長度。對24輪TWINE-128攻擊的時間復(fù)雜度是2126.

10、78次加密，數(shù)據(jù)復(fù)雜度是258.1個分組，存儲復(fù)雜度是2125.61個分組長度。
　　對受保護的NTRU體制的碰撞攻擊
　　在2010年，Lee等給出了針對NTRU的一種常見軟件實現(xiàn)的能量分析，他們的工作顯示未受保護的NTRU的一種常見軟件實現(xiàn)是不能抵抗簡單能量分析和相關(guān)能量分析攻擊的，他們因此提出了三個對策來抵抗他們提出的攻擊。他們對其對策的安全性評估結(jié)論是:只有二階能量分析才能有效的攻擊他們的第一個對策，而如果將他們的第

11、一個對策和第三個對策合并使用，組合對策保護下的NTRU算法是安全的。本論文給出了針對這些對策的有效的一階能量分析。
　　他們的第一個對策是隨機初始化寄存器f，目的是抵抗他們的簡單能量分析（Simple Power Analysis，簡稱SPA）攻擊。具體而言，在解密算法開始前令每個寄存器ti加上一個隨機數(shù)ri，在算法結(jié)束后再把ri從對應(yīng)的寄存器ti中減去。因此在這個對策下的算法中就不存在x+0的操作，從而使得SPA攻擊無效。

12、>　　他們的第二個對策是用隨機值盲化密文多項式c，目的是抵抗他們的相關(guān)能量分析(Correlation Power Analysis，簡稱CPA)攻擊。具體操作是把原始的算法輸入值ci替換成ci+r，其中r是一個隨機整數(shù)。在算法最后將每個寄存器ti的值減去增加的隨機值。
　　他們的第三個對策是隨機化數(shù)組b中元素的存儲順序，也是為了達到抵抗他們的CPA攻擊的目的。因為每次運算中第j行使用的密鑰b[j]是不固定的，所以就無法利用統(tǒng)計方

13、法得出b[j]-b[j-1]的值。
　　針對Lee等設(shè)計的保護NTRU的對策，本工作給出了漢明重量(Hamming Weight，簡稱HW)模型和漢明距離(Hamming Distance，簡稱HD)模型下的碰撞攻擊。第一個對策用隨機值初始化寄存器t。雖然消除了非零值與零值相加的操作，抵抗了SPA攻擊。但是對t的初始化操作可能會使得它成為某些攻擊的目標(biāo)。第二個對策掩蓋了ci的值，因此可以抵抗一階CPA攻擊。雖然它確實隱藏了真實的中

14、間值，但是這個對策是不能抵抗SPA攻擊的。第三個對策擾亂了密鑰b[i](i=0,…，d-1)的執(zhí)行順序，記新的密鑰序列為b'[i](i=0,…，d-1)。這個對策可以在一定程度上隱藏信息，但是它并沒有完全把信息隱藏起來，因為b'[0]=b[0]成立的概率是1/d。基于這些觀察，我們給出了碰撞攻擊。
　　針對第一個對策，理論計算表明我們的碰撞攻擊的攻擊效率比Lee等給出的二階相關(guān)能量分析提高了204.8％，AT89C51RC2微處理