針對LBlock的代數攻擊的研究

孔德謙，李曉林，高薇，王學偉，王心靈

(山東省科學院新材料研究所，山東 濟南 250014)

1 代數分析簡介

代數分析［1－5］是破解許多密碼算法的一種框架方法，不同于傳統的基于統計的分析方法，代數分析是從代數角度來分析一個密碼系統的安全性。代數攻擊源于Shannon提出的一個基本命題:對于一個完善的密碼算法而言，攻破該算法所需的計算量不應亞于解決一個復雜的、規模未知的聯立方程組的計算量。換句話說，如果將一個密碼算法的計算過程表示成一組代數方程，通過求解這組方程中的未知元可獲取該密碼算法中的密鑰信息，就攻破了該算法，而其中使用的分析方法則稱為代數分析法。針對加密算法的代數分析大致分為構建加密過程中的方程組和求解該方程組兩步。代數分析中，求解方程組需要的時間代價最高。二元域(GF(2))上的多元二次方程組的求解問題已被證明是一個NP困難問題［6］。如何構建有效的、適合求解的方程組是難點之一。

1.1 代數方程的構建

原則上，任何一個密碼系統都可以被有限域上的一組方程來描述。事實上，經常有同一個密碼系統可以由許多不同的方程系統來描述。因此，破解密碼系統的復雜程度就與解方程系統的復雜度緊密相關。構建更加容易解的方程系統也就成為了代數分析的目標。構建加密過程中的代數方程，是利用加密算法中S盒或其他非線性組件的代數特性，尋找一組以密鑰和加密過程中的中間變元為未知量的方程。在方程系統建立過程中最關鍵的是S盒的方程表達，其直接決定方程系統的質量，即解方程難度。S盒的輸出向量中的任意bit可以表示成輸入bit的表達式，表達式中僅包含異或運算和與運算［7－8］。S盒的代數方程表示方法有許多種，最直接的是插值法。插值法的優點是解唯一，即給定S盒的輸入向量，能解出唯一的輸出向量，但插值法的缺點也是非常明顯，用插值法列出的方程次數過高，其次數最高為輸入向量的維數，使得解方程比較困難。

由于密碼系統自身并不確保具有明文、密鑰和密文的一一對應關系，經常會出現多個密鑰對應同一對明密文對的情況，因此需要多對明密文對來確保解的唯一性［9］。保持密鑰不變，每一組明密文對可以產生一組代數方程。由隨機的兩組明文出發產生的兩組方程，這兩組方程中相互對應的中間變量相互獨立。每當引入新的明密文對時，方程數和變量數都會增加。新方程的引入在一定程度上能夠增加限制條件，縮小滿足方程系統的解的范圍，有可能加快解方程的速度;但新引入的變元也使得代數系統規模不斷變大，方程組的求解復雜度增加。

1.2 代數方程的求解

已有學者在求解多元高次方程組方面做了大量的研究［10－12］。Buchberger［13］最早提出了利用Groebner基求解多元高次方程組的方法。這是一種指數復雜度的算法，其本質是從多項式環中任意理想的生成元出發，計算出一組具有特殊性質的Groebner基，進而研究理想的結構并進行運算求解方程組的所有解。其中計算Groebner基的復雜度為指數級別，所以整個算法也是指數級的。盡管多位學者對計算 Groebner基［14－15］的算法進行了優化，但是其復雜度仍然是指數級的。

此外，還有一些方法嘗試將求解方程組問題轉換成其他問題進行求解，如將方程組的求解問題轉換成可滿足性問題(SAT)的求解［16］。目前對于可滿足問題已經有了不少的研究，一些求解工具如MiniSAT可以求解一定規模的SAT問題。轉換成可滿足問題求解是一種相對簡單的方法，便于進行實驗。采用該方法，研究者可以更加容易地發現一些隱蔽的代數結構弱點。此外使用這種方法，攻擊者可以有更多的精力去關注密碼算法結構中的一些弱點.

2 LBlock介紹

隨著電子和通訊技術的發展，越來越多的地方用到了射頻識別(RFID)技術。這種技術依賴于許多小型的設備作為終端，這些設備計算能力弱、體積小、供電功率小。因此，傳統的分組密碼，例如AES，并不適合應用在這些設備上。輕量級分組密碼成為了一個研究熱點。

LBlock［17］是一個輕量級的分組密碼，它的分組規模是64 bit，密鑰長度為80 bit。LBlock可以被高效的通過軟件或硬件的方式實現。

圖1 加密過程示意圖Fig.1 Illustration of the encryption process

2.1 加密過程

記64 bit的明文 M=X1|X2，Ki為第 i輪輪密鑰(i=1，…，32)，Xi為中間結果(i=0，…，33)，F是輪函數。加密過程見圖1。

Step 1:對于 i=2，3，…，33，

Step 2:輸出64 bit密文 C=X32|X33。

(1)輪函數F:

其中S和P分別是非線性的混淆函數和線性的擴散函數。

(2)混淆函數S:

這里Zi=Si(Yi)，i=0，…，7是8個4 bit S盒，定義見后。

(3)擴散函數P:

輪函數的總體結構見圖2。

2.2 解密過程

記64 bit密文C=X32|X33，則解密過程如下:

2.3 密鑰計劃

圖2 輪函數的總體結構圖Fig.2 Total structure diagram of a round function

LBlock的80 bit主密鑰K最初存儲在一個寄存器中。記K=k79k78…k0。把當前寄存器最左邊的32 bit作為第一輪輪密鑰K1輸出，然后每一輪按照如下規則操作:

對于 i=1，2，…，31，更新寄存器 K:

(d)把當前寄存器K最左邊的32 bit作為輪密鑰Ki+1輸出。

2.4 S 盒定義

加密、解密和密鑰計劃中用到的10個S盒的定義見表1。

表1 S盒的設置Table 1 Setting of the S－box

2.5 LBlock的方程系統

針對LBlock各個部分的結構，我們可以分別列出方程，然后組成一個完整的方程系統。使用SAGE(目前流行的基于python的數學軟件)，直接根據LBlock的加密過程列出方程。

使用SAGE提供的庫函數，可以非常方便地給定S盒的輸入輸出，列出指定次數的方程。對于擴散層等非線性部分，方程可以直接列出。再與密鑰計劃的方程合并，就可以完整地建立出LBlock的方程系統。這里要注意的是，為了降低方程的次數，S盒方程可能存在多組解，必須要使用多組明密文對才能獲得唯一的正確密鑰。

3 LBlock方程系統求解

3.1 實驗條件

我們使用MiniSat206［18］進行實驗，MiniSat是目前比較流行易用的求解SAT問題的軟件，求解速度快、占用內存小，在同類軟件中表現相當出色。

實驗機器配置:

CPU:Intel Core2 Duo T6570@2.10 GHz 2.10 GHz

內存:DDR28003072 Mbytes

3.2 實驗過程及結果

3.2.1 隨機明文攻擊

實驗最初我們采用一對隨機的明文和一個隨機的主密鑰生成一對密文，并以此生成方程系統進行實驗，多次試驗后發現6輪可以在1 h內得到結果，而7輪的LBlock就無法在24 h內獲得結果。

3.2.2 選擇明文攻擊

為了進一步提高破解的輪數，我們使用選擇明文攻擊。以這種明密文對為基礎生成的方程系統由于滿足一定的差分關系，解方程的速度可以快于隨機明文［19］。選擇明文攻擊中，明文的選擇方法就變得至關重要，并且由于明密文對的個數對方程系統的破解難度也有很大影響，增加明密文對的個數，變量個數和方程個數都會隨之增加，一方面使得方程系統的限制增多，易于求解，一方面又會使得方程系統的復雜性增加，增加求解時間。因此尋找兩者之間的平衡點是關鍵，必須要嘗試不同的明密文對個數進行多次試驗，以找到最適宜的明密文對個數。

實驗中我們選擇了比較特殊的以零向量為中心構造明文的方法，在6輪的實驗中，為保證方程解的唯一性，最少要使用2個明密文對。我們對2，3，4，5個明密文對分別進行了實驗，結果發現3個明密文對在求解6輪LBlock時速度是最快的。結果見表2。

3個明密文對，一個為全0，另2個分別只有一位為1，其求解速度明顯高于4，5個明密文對。我們推測繼續增加明密文個數只會使得方程系統變得更加復雜而無法加快解方程速度。

表2 不同明文對的攻擊結果Table 2 Attack results of different plaintext pairs

3.2.3 高輪次LBlock實驗結果

在求解7，8輪LBlock時均以3個明密文對為主要方法。在使用了上文所述的選擇明文攻擊方法后，原本無法有效破解的7輪LBlock可以在短時間內破解。我們使用與破解6輪LBlock相同的明文，每次使用不同的隨機密鑰進行多次實驗，結果破解時間為15 min～1 h不等，因此，我們認為，7輪LBlock的破解，在90min內是可以達到的。使用同上文相同的方法，變換不同的明文對，經過多次實驗仍無法在24 h內破解8輪的LBlock。

3.3 實驗結果與分析

6輪與7輪選擇明文攻擊的實驗結果分別見表3、表4。

表3 使用隨機密鑰的6輪實驗結果Table 3 Attack results of 6－round encryption with a random key

表4 7輪實驗結果Table 4 Attack results of 7－round encryption

對比表2、3后兩列可知，選定明文比隨機明文更容易求解。對比同一輪的3個密鑰的求解結果可知，不同的密鑰對于求解速度影響不大。

4 結論

在本文中我們使用代數攻擊的方法對輕量級機密算法LBlock進行分析，使用SAGE可以方便地列出加密方程，之后使用MiniSat進行方程求解。實驗結果表明，我們可以在僅有極少量明密文對的情況下有效破解7輪LBlock。由于LBlock結構簡單，高輪次加密易于硬件實現，本文認為LBlock的一般實現在代數攻擊下是安全的。

［1］ALBRECHT M.Alorithmic algebraic techniques and their application to block cipher cryptanalysis［D］.Royal Holloway:University of London，2010.

［2］ALBRECHT M，CID C.Algebraic techniques in differential cryptanalysis［C］//Fast Software Encryption.Springer Berlin，2009:193－208.

［3］COURTOIS N T.Fast algebraic attacks on stream ciphers with linear feedback［M］//Advances in Cryptology－CRYPTO 2003.Berlin:Springer，2003:176 －194.

［4］COURTOIS N T，BARD G V.Algebraic cryptanalysis of the data encryption standard［M］//Cryptography and Coding.Berlin:Springer，2007:152 －169.

［5］COURTOIS N T，MEIER W.Algebraic attacks on stream ciphers with linear feedback［M］//Advances in Cryptology－EUROCRYPT 2003.Berlin:Springer，2003:345 －359.

［6］BARD G V，COURTOIS N T，JEFFERSON C.Efficient methods for conversion and solution of sparse systems of low－degree multivariate polynomials over GF(2)via SAT－solvers［EB/OL］.［2013 －07 －01］.http://eprint.iacr.org/2007/024.pdf.

［7］COURTOIS N T.Higher order correlation attacks，XL algorithm and cryptanalysis of Toyocrypt［M］//Information security and cryptology－ICISC 2002.Berlin:Springer，2003:182 －199.

［8］COURTOIS N T，PIEPRZYK J.Cryptanalysis of block ciphers with overdefined systems of equations［M］//Advances in Cryptology－ASIACRYPT 2002.Berlin:Springer，2002:267 －287.

［9］MATSUI M.Linear cryptanalysis method for DES cipher［M］//Advances in Cryptology－EUROCRYPT’93.Berlin:Springer，1994:386－397.

［10］GERALD C F，WHEATLEY O P.Numerical analysis［M］.Boston:Addison－Wesley，2003.

［11］COURTOIS N，KLIMOV A，PATARIN J，et al.Efficient algorithms for solving overdefined systems of multivariate polynomial equations［EB/OL］.［2013 －07 －01］.http://www.iacr.org/archive/eurocrypt 2000/1807/18070398－new.pdf.

［12］PAN V.Solving a polynomial equation:some history and recent progress［J］.SIAM review，1997，39(2):187 － 220.

［13］BUCHBERGER B.An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal［J］.Journal of symbolic computation，2006，41(3):475 －511.

［14］FAUGERE J C.A new efficient algorithm for computing Gr?bner bases［J］.Journal of pure and applied algebra，1999，139(1):61－88.

［15］HOSTEN S，STURMFELS B.GRIN:An implementation of Gr?bner bases for integer programming［M］∥Integer programming and combinatorial optimization.Berlin:Springer 1995:267 －276.

［16］BARD G V.Algorithms for solving linear and polynomial systems of equations over finite fields with applications to cryptanalysis［D］.College Park:University of Maryland，2007.

［17］WU W，ZHANG L.LBlock:A lightweight block cipher［M］//Applied Cryptography and Network Security.Berlin:Springer，2011:327－344.

［18］S?RENSSON N，EEN N.MiniSat V1.13－A SAT solver with conflict－clause minimization［EB/OL］.［2013 － 07 － 01］.http://minisat.se/down wads/minisat－v1.13－short.pdf.

［19］BIHAM E，SHAMIR A.Differential cryptanalysis of DES－like cryptosystems［J］.Journal of Cryptology，1991，4(1):3 －72.