针对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.