孔德謙，李曉林，高薇，王學(xué)偉，王心靈

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

1 代數(shù)分析簡介

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

1.1 代數(shù)方程的構(gòu)建

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

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

1.2 代數(shù)方程的求解

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

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

2 LBlock介紹

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

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

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

2.1 加密過程

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

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

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

(1)輪函數(shù)F:

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

(2)混淆函數(shù)S:

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

(3)擴散函數(shù)P:

輪函數(shù)的總體結(jié)構(gòu)見圖2。

2.2 解密過程

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

2.3 密鑰計劃

圖2 輪函數(shù)的總體結(jié)構(gòu)圖Fig.2 Total structure diagram of a round function

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

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

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

2.4 S 盒定義

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

表1 S盒的設(shè)置Table 1 Setting of the S－box

2.5 LBlock的方程系統(tǒng)

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

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

3 LBlock方程系統(tǒng)求解

3.1 實驗條件

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

實驗機器配置:

CPU:Intel Core2 Duo T6570@2.10 GHz 2.10 GHz

內(nèi)存:DDR28003072 Mbytes

3.2 實驗過程及結(jié)果

3.2.1 隨機明文攻擊

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

3.2.2 選擇明文攻擊

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

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

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

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

3.2.3 高輪次LBlock實驗結(jié)果

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

3.3 實驗結(jié)果與分析

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

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

表4 7輪實驗結(jié)果Table 4 Attack results of 7－round encryption

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

4 結(jié)論

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

［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.