针对LBlock算法踪迹驱动Cache攻击S盒特性分析

于　茜,蔡红柳，陈财森

(装甲兵工程学院　a.信息工程系； b.科研部，北京　100072)



针对LBlock算法踪迹驱动Cache攻击S盒特性分析

于茜a,蔡红柳a，陈财森b

(装甲兵工程学院a.信息工程系； b.科研部，北京100072)

针对轻量级密码LBlock算法的Cache计时研究，着重分析密码算法中S盒的非线性结构特征。基于其结构特征推导出S盒的真值表，求解得出S盒输入输出关系的代数表达式；再结合LBlock算法的加密过程和轮函数F的结构，推导出每个轮运算的表达式以及S盒查找索引的代数表达式；结合踪迹驱动Cache计时攻击的攻击原理与模型，总结得出针对LBlock算法Cache攻击中密钥分析的核心表达式，结果表明LBlock算法存在遭受Cache计时攻击的可能性。

LBlock算法；Cache计时攻击；代数表达式；S盒；特性分析

本文引用格式：于茜,蔡红柳，陈财森.针对LBlock算法踪迹驱动Cache攻击S盒特性分析[J].兵器装备工程学报，2016(8):146-150.

随着信息安全的地位日益重要，轻量级密码算法在RFID电子标签、无线传感器网络、移动智能终端等资源受限设备的应用越来越广，是目前密码安全研究的一个热点领域。LBlock算法[1]是吴文玲和张蕾2011年提出的一种基于32轮类Feistel结构的轻量级分组密码，采用与传统分组密码类似的迭代结构，即将明文用简单的轮函数在密钥的作用下进行多次迭代最终得到密文，轮密钥则通过密钥调度算法由主密钥生成，其密钥和分组长度分别为80和64比特。

轻量级密码算法[2]具有处理数据规模小、数据吞吐量低、实现占用内存空间小等特点，在保证安全性的前提下，为提高实现效率，目前主要采用利用现有算法结构的健壮性和安全性改进现有的密码算法，如改善算法的布尔函数，使算法的S盒相同，以降低算法实现的资源需求等。基于分组密码的迭代结构特性，传统的安全性分析方法主要有基于统计方法的线性分析[3]、差分分析[4]、立方攻击[5]和基于解方程组的代数攻击[6]等。近年来，随着旁路攻击在密码分析领域的研究进展，攻击者可通过获取密码算法在执行过程中泄露的功耗、电磁、时间等旁路信息，利用这些旁路信息与密钥的相关性分析获取密钥，是密码分析研究领域的热点[7]。将旁路攻击与传统密码分析方法相结合，提出了代数旁路攻击、立方攻击与侧信道相结合的攻击方法。Shamir等[8]提出的侧信道立方攻击，其思想是假设攻击者通过侧信道获取密码算法中间状态的某个比特，将该比特信息与立方攻击相结合从而获取密钥信息，2009年Yang等[9]对PRESENT算法进行了侧信道立方攻击的验证。自Kocher[10]和Kelsey[11]等人提出将高速存储器Cache的行为信息作为旁路泄露信息的思想以来，Cache攻击成为旁路攻击的新热点，其主要思想是通过获取密码算法在执行过程中对Cache的访问行为，以及Cache计时信息与密钥信息的相关性分析获取密钥信息，对基于S盒查找的分组密码算法构成了安全性威胁，如DES、AES、ARIA算法，同时也可基于滑动窗口算法实现的RSA公钥密码算法进行攻击。

在Cache计时攻击过程中，如何准确获取Cache访问行为信息和S盒查找索引与子密钥的相关性分析是密钥分析的关键因素。本文在踪迹驱动Cache计时攻击原理的基础上，结合LBlock算法实现过程的代数性质分析，给出LBlock算法的非线性组件S盒的代数表达式，结合算法的加密过程和轮函数F的结果，推导出每个轮运算的表达式以及S盒查找索引的代数表达式，由轮子密钥的代数表达式，给出通过Cache访问信息与S盒查找索引推导出子密钥信息的核心表达式，从理论上论证了LBlock存在遭受Cache计时攻击的可能性。

1　LBlock密码算法实现分析

1.1算法概述

LBlock算法的加密过程主要是一个32位的类Feistel结构迭代。设M=X1‖X0表示64比特明文，其加密过程如下：

1) 对于i=2,3,…,33，执行：

2) 输出64比特密文C=X32‖X33。LBlock加密结构如图1所示。

图1　LBlock加密结构

其中，每轮加密运算的轮函数F及其涉及的混淆函数S和扩散函数P定义如下。

1) 轮函数F：

2) 混淆函数S：

S:{0,1}32→{0,1}32

Y=Y7‖Y6‖Y5‖Y4‖Y3‖Y2‖Y1‖Y0→

Z=Z7‖Z6‖Z5‖Z4‖Z3‖Z2‖Z1‖Z0

Z7=s7(Y7),Z6=s6(Y6)

Z5=s5(Y5),Z4=s4(Y4)

Z3=s3(Y3),Z2=s2(Y2)

Z1=s1(Y1),Z0=s0(Y0)

混淆函数中S盒的具体变换规律如表1所示。

表1　LBlock的S盒

3) 扩散函数P：

P:{0,1}32→{0,1}32

Z=Z7‖Z6‖Z5‖Z4‖Z3‖Z2‖Z1‖Z0→

U=U7‖U6‖U5‖U4‖U3‖U2‖U1‖U0

Z7=U6,Z6=U4,Z5=U7,Z4=U5

Z3=U2,Z2=U0,Z1=U3,Z0=U1

轮函数F的具体结构如图2所示。

图2　LBlock轮函数F的结构

根据LBlock轮函数F的结构图，对应8个S盒，将每轮参与轮函数F的左32比特Xi按4比特一组，从左到右依次记为ai,7,ai,6,ai,5,ai,4,ai,3,ai,2,ai,1,ai,0；相应地，轮密钥Ki也按4比特一组，从左到右依次记为Ki,7,Ki,6,Ki,5,Ki,4,Ki,3,Ki,2,Ki,1,Ki,0。

假设第一轮右32比特X0为全0，那么以S7为例，则可知第一轮的查找索引为a1,7⨁K1,7；第二轮的查找索引为a2,7⨁K2,7。

由LBlock算法加密过程，每轮左32位的数学表达为

则有：

由轮函数F的结构图可知，第一轮S6盒的输出对应于第二轮S7盒的索引，即a2,7=S6(a1,6⨁K1,6)。

那么可得出，第二轮S7盒的查找索引为S6(a1,6⨁K1,6)⨁K2,7。

因此通过以上分析得出如下结论：

假设LBlock算法第一轮右32比特X0为全0，由算法加密结构可得第一轮查找S7盒的索引为a1,7⨁K1,7；第二轮查找S7盒的索引为S6(a1,6⨁K1,6)⨁K2,7。

该结论也是通过获取S盒索引值分析推导相关密钥位的关键因素。

1.2子密钥生成算法

LBlock算法的子密钥生成，主要用于如何从80比特的主密钥中依次生成32个32位的轮子密钥。假设初始时80比特的主密钥存储于密钥寄存器K中，记为

其中，k0表示最低位。

算法步骤具体如下：

1) 输出K的最左边32比特作为轮子密钥K1；

2) 对于i=1,2,…,31，执行：

a) K<<<29；

b) [k79k78k77k76]=s9[k79k78k77k76]，

[k75k74k73k72]=s8[k75k74k73k72]；

c) [k50k49k48k47]=[k50k49k48k47]⨁[i]2；

d) 输出当前最左边32位最为轮子密钥Ki+1。

利用同样的方法依次生成各个轮子密钥，用于轮计算。

2　LBlock算法中非线性S盒的特性分析

2.1S盒的真值表推导

LBlock算法的S盒输入、输出均为4位二进制数。假设输入X=x3x2x1x0，其中x3为最高位，x0为最低位，输出Y=y3y2y1y0，其中y3为最高位，y0为最低位。根据表1中LBlockS盒的变换规律，以S0为例：当输入X(x3x2x1x0)=0000时，输出Y(y3y2y1y0)=1110，依次可得S0的真值表，如表2所示。

表2　S0的真值表

由表2 S0的真值表可分别得到LBlock算法中S0盒4个对应于x3x2x1x0(从0000到1111)的输出y0，y1，y2，y3的真值表，如表3所示。

表3　LBlock S盒(S0)中输出y0，y1，y2，y3的真值表

假设LBlock算法中S盒的输出Y(y3y2y1y0)与输入X(x3x2x1x0)的布尔函数关系为

yi=fi(x3,x2,x1,x0)

其中，i=0,1,2,3，以S0盒为例，根据4个输出y0，y1，y2，y3的真值表求解其布尔函数表达式，以y0为例，真值表中共有8项为1，可表示成：

展开后得：

m0001=x3x2x1x0⨁x3x2x0⨁x3x1x0⨁x2x1x0⨁

x3x0⨁x2x0⨁x1x0⨁x0

同理可得：

m0010=x3x2x1x0⨁x3x2x1⨁x3x1x0⨁

x2x1x0⨁x3x1⨁x2x1⨁x1x0⨁x1

m0100=x3x2x1x0⨁x3x2x1⨁x3x2x0⨁

x2x1x0⨁x3x2⨁x2x1⨁x2x0⨁x2

m0111=x3x2x1x0⨁x2x1x0m1000=

x3x2x1x0⨁x3x2x1⨁x3x2x0⨁x3x1x0⨁

x3x2⨁x3x1⨁x3x0⨁x3

m1011=x3x2x1x0⨁x3x1x0

m1100=x3x2x1x0⨁x3x2x1⨁x3x2x0⨁x3x2

m1111=x3x2x1x0

全部相加并约去0项即可得到y0，同理可得其他3个输出y1，y2，y3关于输入的表达式。

即可得出如下结论：

设X=x3x2x1x0为S盒的输入，Y=y3y2y1y0为S盒的输出，利用LBlock算法中S0的真值表，可计算出：

其他S盒(S1到S9)的4个输出的代数表达式都可用类似方法求得，这里不再赘述。

2.2轮子密钥的代数表达式

根据上述章1.2中描述的子密钥生成算法和章2.1中推导的S盒输入输出代数表达式可以得到LBlock算法的每一轮子密钥的代数表达式。

设主密钥

则第二轮子密钥为

K2={1⨁k47⨁k49⨁k47k49⨁k48k49⨁k50,

k47⨁k48⨁k49⨁k50⨁k49k50,

1⨁k47⨁k47k49⨁k48k49⨁k50⨁k47k50⨁

k49k50⨁k47k49k50⨁k48k49k50,

1⨁k47k48⨁k47k49⨁k50⨁k48k50⨁k47k49k50,

1⨁k43⨁k43k45⨁k44k45⨁k43k46⨁k45k46k43k45k46⨁

k44k45k46⨁k43⨁k44⨁k43k44k45⨁k43k45⨁k44k46⨁

k45k46⨁k43k45k46,k43⨁k44⨁k45⨁k46⨁k45k46,

k43⨁k45⨁k43k45⨁k44k45⨁k46,k42,k41,k40,k39,

k38,k37,k36,k35,k34,k33,k32,k31,k30,k29,k28,

k27,k26,k25,k24,k23,k22,k21,k29,k19}

同理可得第三轮的子密钥K3，以此类推。

3　基于S盒索引特性的踪迹驱动Cache攻击密钥分析

3.1踪迹驱动Cache攻击原理与S盒索引特性

踪迹驱动Cache 攻击是一种非常有效的旁路分析技术[13]，其原理是：在执行密码算法的过程中，常常多次查表访问同一个S盒，利用多次查表产生的Cache命中和失效情况推测密钥。其中，查找所需元素在Cache中的情况称为Cache命中，查找所需元素不在Cache中的情况称之为Cache失效，此时处理器会把所需元素所在内存块的所有对应元素加载到某一Cache行。

实验中，先对Cache进行清空，则第一次查表通常会发生Cache失效；第二次查表时，Cache可能产生Cache命中也可能产生Cache失效，若命中，说明所需元素一定在第一次查表后加载元素的Cache行中。而每次查表需要一个查表索引值，该索引值的高两位对应Cache行，低两位对应行内地址，即两次查表索引值的高两位相等。

由此得出结论：

设Y为查找S盒的索引值，其高两位表示为〈Y〉，若两次查找同一S盒的索引值分别为Y1，Y2，且二次查找发生Cache命中，则有

3.2LBlock密钥与S盒索引值相关性分析

通过构造LBlock算法加密过程中的S盒查找命中，利用上述得出的3个结论理论上对LBlock密钥与S盒索引值相关性进行分析[14]。

假设第一轮右32比特X0为全0，随机选择第一轮加密的高四位明文ai,7和次高四位明文ai,6，使得第二轮查找S7发生Cache命中。则由节1.1与3.1得出的结论可推导出：

(1)

将明文比特和密钥比特分别代入式(1)，可得：

此时S7索引的高两位比特只与10位密钥k79，k78，k75，k74，k73，k72，k50，k49，k48，k47有关，其中最高位只与9位密钥k79，k75，k74，k73，k72，k50，k49，k48，k47有关，次高位只与9位密钥k78，k75，k74，k73，k72，k50，k49，k48，k47有关。对此，选出发生命中的12组明文，由这12组等式可以确定唯一解，可以恢复与高两位比特相关的10位密钥。综上可知，至多进行12×29+12×29=12×210次判别运算可恢复上述10位密钥k79，k78，k75，k74，k73，k72，k50，k49，k48，k47。

同理，分析第一轮第二轮S6盒查表索引的高两位比特，可唯一确定8位密钥，即k67，k66，k65，k64，k46，k45，k44，k43。

进一步分析其他S盒查表索引的高两位，最终可恢复49位密钥，具体每次S盒查表索引的高两位对应密钥位和密钥个数如表4所示。

表4　第二轮命中时S盒查表索引的高两位

如果每次选择的明文的组数都比每次S盒索引所涉及的密钥数多2，则从表4中易知此时共需12+10+8+6+10+5+8+6 = 65 个选择明文，大约12 × 210+10 × 28+8 ×26+6×24+10×28+5×23+8×26+6×24≈214.18次判别操作。

因为LBlock 算法有32 轮，每一轮都有8个S盒参与运算，同时每一次判别操作至多有2 个S盒参与运算，所以1 次判别运算可视为2/(32×8)=1/128 次LBlock 加密运算。综上所述，共需约27.18次LBlock 加密运算，可恢复表1中的49 bit密钥。

同理，对S盒进行第三轮第四轮分析，可获得更多的相关密钥位，如表5所示。

表5　第四轮命中时S盒查表索引的

同样假设每次选择的明文的组数都比每一次索引所涉及的密钥数多2，则分析第3 轮只需5+8+4+6+6+4+4+4=41 个选择明文，判别时间可忽略，最后剩余的6 bit 密钥可以用穷举的方法来得到，至多需要26次LBlock 运算。

综上所述，整个攻击一共需要106 个选择明文，约27.18+26≈27.71次加密运算可恢复LBlock 的全部密钥。

因此，LBlock算法存在Cache计时攻击的可行性。

4　结论

本文通过深入分析LBlock算法的实现过程及算法函数结构，依据踪迹驱动Cache计时攻击原理，针对LBlock算法的S盒特性展开研究，首先分析得出其非线性S盒的代数表达式，依据加密过程和轮函数F的结构，推导出每个轮运算的表达式以及S盒查找索引的代数表达式；然后基于S盒索引特性分析，提出了针对LBlock算法Cache攻击中密钥分析的核心表达式，从而论证了LBlock算法Cache计时攻击的可行性，为其他轻量级密码算法的实现安全性分析提供有价值的参考借鉴。

[1]WU W L,ZHANG L.LBlock:A Lightweight Block Cipher[C]//Proceedings of the 9th International Conference on Applied Cryptography and Network Security.Berlin,Germany:Springer-Verlag,2011:327-344.

[2]吴文玲,范伟杰,张蕾.轻量级分组密码研究进展[J].中国密码学发展报告,2010,140:159.

[3]MATSUI M.Linear cryptanalysis method for DES cipher[C]//Advances in Cryptology-EUROCRYPT’ 93.Springer Berlin Heidelberg,1994:386-397.

[4]BIHAM E,SHAMIR A.Differential cryptanalysis of the data encryption standard[C]//Advances in Cryptology-CRYPTO 1990,LNCS 537,1991: 2-21.

[5]DINUR I,SHAMIR A.Cube attacks on tweakable black box polynomials[C]//Advances.in Cryptology-EUROCRYPT 2009.Springer Berlin Heidelberg,2009:278-299.

[6]ALBRECHT M.Alorithmic algebraic techniques and their application to block cipher cryptanalysis[D].Royal Holloway:University of London,2010.

[7]郭世泽,王韬,赵新杰.密码旁路分析原理与方法[M].北京:科学出版社,2014.

[8]LI Z Q,ZHANG B,YAO Y,et al.Cube Cryptanalysis of LBlock with Noisy Leakage[C]//Proceedings of the 15th International Conference on Information Security and Cryptology.Berlin,Germany:Springer-Verlag,2012:141-155.

[9]BOGDAOV A,KUNDSEN L R,LEANDER G,et al.PRESENT:An Ultra-lightweight Block Cipher[C]//Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems.Berlin,Germany:Springer-Verlag,2007:450-466.

[10]KOCHER P.Timing attacks on implementations of Diffie-Hellman,RSA,DSS,and other systems[C]//Advances in Cryptology-CRYPTO 1996,LNCS 1109,1996:104-113.

[11]KELSEY J,SCHNEIER B,WAGNER D,et al.Side channel cryptanalysis of product ciphers[C]//Peoceeding of the 5th European Symposium on Research in Computer Security-ESORICS 1998,LNCS 1485,1998:97-110.

[12]温巧燕,钮心忻,杨义先.现代密码学中的布尔函数[M].北京:科学出版社,2000.

[13]谷晓辰，丁文霞. 基于混沌Lorenz系统的S盒设计[J]．重庆理工大学学报(自然科学)，2013(3)：97-103.

[14]朱嘉良,韦永壮.针对LBlock算法的踪迹驱动Cache攻击[J].计算机工程,2015,47(5):153-158.

[15]彭昌勇,祝跃飞,顾纯祥,等.1～5轮LBlock的多项式表示及完全性分析[J].计算机工程,2012,38(9):155-157.

(责任编辑杨继森)

Completeness Analysis onS-Box of Trace Driven Cache Timing Attack against LBlock Algorithm

YU Xia, CAI Hong-liua, CHEN Cai-senb

(a.Department of Information and Communication Engineering;b.Department of Science Research, Academy of Armored Forces Engineering, Beijing 100072, China)

Aiming at the study of the cache timing attack for lightweight block cipher called LBlock, we focused on the analysis of the nonlinear structure characteristics ofSbox in cryptographic algorithms. Firstly, we derived the truth-table ofSbox based on its structure feature to obtain the relation algebra expression between inputs and outputs ofSbox. Secondly, with reference of encryption process of the LBlock algorithm and the structure of round functionF, the operation expression of each round and the algebra expressions of look-up index forSbox were deduced. Finally, we summarized the core expression of the analysis of the key in the cache attack for LBlock algorithm on the basis of the principle and model of the trace-driven cache timing attack. The final conclusion shows that the LBlock algorithm has the possibility of the cache timing attack.

LBlock algorithm; Cache timing attack; algebra expression; S box; characteristic analysis

2016-02-17；

2016-04-10

于茜(1992—)，女，硕士研究生，主要从事网络安全与对抗研究。

10.11809/scbgxb2016.08.033

format:YU Xi, CAI Hong-liu, CHEN Cai-sen.Completeness Analysis on S-Box of Trace Driven Cache Timing Attack against LBlock Algorithm[J].Journal of Ordnance Equipment Engineering,2016(8):146-150.

TP391

A

2096-2304(2016)08-0146-06

【信息科学与控制工程】