分組密碼算法的Linear Hull的研究.pdf

1、分組密碼是一個最基本的對稱密碼體制，廣泛應用于其它密碼領域。目前攻擊分組密碼最常用和實用的方法主要有差分分析和線性分析，而且抵抗差分分析和線性分析已經成為現代分組密碼設計的安全要求。
　　 線性分析本質上是一種已知明文攻擊方法，最早由Matsui在1993年提出，它的基本思想是通過尋找一個給定密碼算法的有效的線性近似表達式來恢復部分密鑰比特。線性近似表達式與算法的部分輸入比特(即輸入掩碼)、部分輸出比特(即輸出掩碼)和部分密鑰比

2、特(即密鑰掩碼)有關，“有效”是要求線性近似表達式成立的概率p≠1/2。此后相繼演化出了一系列的線性分析方法的變種：密鑰掩碼相同的多線性分析、多線性分析、基于LinearHull的線性分析等等。
　　 密鑰掩碼相同的多線性分析是Kaliski等人在1994年提出的，多個線性近似表達式的使用降低了給定成功率下攻擊算法所需的已知明文量，但是該方法要求所用線性近似表達式的密鑰掩碼相同，這無彤中限制了可用線性近似表達式的個數。Linea

3、r Hull則是一個所有輸入掩碼和輸出掩碼相同而密鑰掩碼不同的線性近似表達式(這里我們稱為線性路釋)的集合，由KNyherg在1994年首先提出。Nyberg指出Linear Hull總體偏差的平方等于所有線性路徑偏差的平方和，基于Linear Hull的線性分析比先前的方法更為有效，并稱之為Linear Hull Effect。然而，2009年Murphy否定了Nyberg的理論，認為Linear Hull的總體偏差是由算法的擴展密鑰

4、和每條線性路徑的偏差共同決定的，線性分析中不存在Lineal Hull Effeet。同年，K.Ohkuma卻指出在PRESENT算法中存在32％的弱密鑰仍可利用Linear Hull進行攻擊，即存在基于弱密鑰的攻擊。此結論是在線性路徑相互獨立的條件下得到的。一股來說線性路徑間是相關的，因此，現有的獨立性假設下的模型是不準確的。
　　 那么，如何建立一個更為準確的弱密鑰下的線性分析模型呢?
　　 本文的主要工作就是在線性

5、路徑相關的條件下，建立弱密鑰下基于Linear Hull的線性分析模型，重點完成以下工作：
　　 1.給出線性路徑相關時Linear Hull總體偏差的計算方法；
　　 2.給出線性路徑相關時計算Linear Hull的弱密鑰比例的新方法；
　　 3.以PRESENT算法為例，用新方法計算7-13輪Linear Hull的弱密鑰比例，并與Ohkuma的模型下的計算結果進行比較。此外，還將7輪的結果與對實際算法隨機

6、檢測的結果進行了對比。
　　 對Linear Hull而言，線性路徑的相關也就是等價密鑰比特的相關。本文中我們采用將無關的等價密鑰比特分類的思想來得Linear Hull的偏差和弱密鑰比例的計算方法。主要思想如下：
　　 1.我們找出所有相互獨立的等價密鑰比特(稱為無關項)，其它的與無關項存在依賴關系的等價密鑰比特稱為相關項。
　　 2.分類研究R個無關項在L-R個相關項中的分布情況。我們將無關項按其取值為0還是

7、1分成兩組，設取值為0的無關項個數為s(1≤s≤R)個，那么當且僅當相關項中出現這s個無關項中的奇數個時，該相關項的取值為0。設相關項的表達式中含有j(0≤j≤s)個0值無關項，為了得到統(tǒng)一的計算公式，我們再根據j值的不同將所有相關項分組。
　　 3.實際上我們是將等價密鑰取值按偏差做了分類，再根據弱密鑰的定義即可快速計算出弱密鑰比例。
　　 本文中的模型的計算量會隨著線性路徑個數的增加而增大，為了降低計算復雜度，本文在

8、整個等價密鑰空間中采用隨機檢測方法來計算弱密鑰比例，并用此法計算了PRESENT算法7-13輪Linear Hull的弱密鑰比例。其中，7輪Linear Hu1l存在72條線件路徑，且無關項個數為45，Ohkuma的模型下的弱密鑰比例為28.88％，由真實的相關路徑(也就是我們的模型)計算得到的弱密鑰比例為28.13％，則弱密鑰比例的下降率為0.28880.2813/0.2888≈2.60％。13輪Linear Hull存在24255條

9、線性路徑，無關項個數為153，Ohkuma的模型下的弱密鑰比例為29.60％，我們的模型下的弱密鑰比例為25.15％，此時弱密鑰比例的下降率為0.2960－0.2515/0.2960≈15.03％。詳細結果見表5.2。
　　 我們的模型目前只能用于分析較低輪的分組密碼算法。當Linear Hull的輪數較高時，線性路徑的個數會非常多，由于計算量的限制使分析變得困難。
　　 但是，我們仍然可以通過對低輪算法的分析，得出規(guī)律