針對(duì)LBlock的代數(shù)攻擊的研究

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

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

1 代數(shù)分析簡(jiǎn)介

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

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

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

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

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

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

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

2 LBlock介紹

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

LBlock［17］是一個(gè)輕量級(jí)的分組密碼，它的分組規(guī)模是64 bit，密鑰長(zhǎng)度為80 bit。LBlock可以被高效的通過軟件或硬件的方式實(shí)現(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:對(duì)于 i=2，3，…，33，

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

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

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

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

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

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

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

2.2 解密過程

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

2.3 密鑰計(jì)劃

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

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

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

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

2.4 S 盒定義

加密、解密和密鑰計(jì)劃中用到的10個(gè)S盒的定義見表1。

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

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

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

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

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

3.1 實(shí)驗(yàn)條件

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

實(shí)驗(yàn)機(jī)器配置:

CPU:Intel Core2 Duo T6570@2.10 GHz 2.10 GHz

內(nèi)存:DDR28003072 Mbytes

3.2 實(shí)驗(yàn)過程及結(jié)果

3.2.1 隨機(jī)明文攻擊

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

3.2.2 選擇明文攻擊

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

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

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

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

3.2.3 高輪次LBlock實(shí)驗(yàn)結(jié)果

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

3.3 實(shí)驗(yàn)結(jié)果與分析

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

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

表4 7輪實(shí)驗(yàn)結(jié)果Table 4 Attack results of 7－round encryption

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

4 結(jié)論

在本文中我們使用代數(shù)攻擊的方法對(duì)輕量級(jí)機(jī)密算法LBlock進(jìn)行分析，使用SAGE可以方便地列出加密方程，之后使用MiniSat進(jìn)行方程求解。實(shí)驗(yàn)結(jié)果表明，我們可以在僅有極少量明密文對(duì)的情況下有效破解7輪LBlock。由于LBlock結(jié)構(gòu)簡(jiǎn)單，高輪次加密易于硬件實(shí)現(xiàn)，本文認(rèn)為L(zhǎng)Block的一般實(shí)現(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.