一种抗滑动攻击的密钥流提取改进算法

丁 杰,石 会,龚 晶,邓元庆

(解放军理工大学 通信工程学院,南京 210007)

0 概述

为推动流密码更好的发展,促进密码界开发出新的流密码设计思想与设计理念,ECRYPT项目[1]于2004年启动了eSTREAM流密码研究计划[2]。自从eSTREAM计划启动以来,国际上密码研究得到了极大发展,其中,基于分组密码思想构造流密码成为流密码设计的一个重要方向。

进入eSTREAM计划第二阶段的流密码候选算法泄露提取(Leak Extraction,LEX)[3],是基于分组密码算法高级加密标准(Advanced Encryption Standard,AES)[4]来构造的,并因其较高的密钥流生成速度以及便于硬件实现的特点倍受关注,与其他类似方式构造的流密码相比,其密钥流生成速度约是AES算法OFB模式的2.5倍[5]。

自LEX算法提出以来,出现了很多针对该算法的分析结果[6],许多针对分组密码提出的分析手段也被用来分析该流密码算法[7]。其中,文献[8]提出的针对LEX算法的滑动攻击给LEX算法的安全性带来了很大的隐患。本文研究旨在改进LEX算法的薄弱环节,增强其抗滑动攻击能力。

1 LEX算法

LEX算法采用128 bit分组密码高级加密标准AES作为密钥流产生部件,它的出现架起了分组密码与序列密码设计的桥梁,具有十分重要的意义。

1.1 LEX算法结构

与AES算法一致,LEX算法延续了128 bit的密钥与明文规模,其算法结构如图1所示[3],具体分为初始化和密钥流提取2个阶段。初始化阶段:对于给定的128 bit密钥K,以初始向量IV作为输入,运行一组AES,得到加密结果C1=AESk(IV),该组AES不输出任何密钥流;密钥流提取阶段:从第2组AES开始,每执行一组AES会有10轮轮函数迭代,从每一轮迭代后所得的128 bit中间变量提取32 bit(共4个字节),作为输出密钥流的一部分,10轮迭代后共输出320 bit密钥流。在该阶段中,每组的输入向量不断更新,具体为前一组的加密输出IVi′=Ci(i=1,2,…);加密密钥K′=K,始终为初始加密密钥,保持不变。

图1 LEX算法的结构框图

在LEX算法中最关键的部分是输出密钥流的提取位置。具体提取方式如图2所示。方框内一个bi,j代表某轮变换后的一个字节的中间变量,按行序读取共16 Byte,为一组完整的中间状态。LEX算法中奇数轮与偶数轮输出密钥流的位置不同,其中,奇数轮输出b0,0、b2,0、b0,2、b2,2共4个字节,偶数轮输出b0,1、b2,1、b0,3、b2,3共4个字节,公式表示为:

oddout32=

(t0& 0xFF00FF00)⊕((t2& 0xFF00FF00)>>8)

evenout32=

((t0& 0xFF00FF00)<<8)⊕(t2& 0xFF00FF00)

其中,ti=(bi,0,bi,1,bi,2,bi,3),i=0,1,2,3,根据i的不同取值,可代表每轮迭代后中间状态的第0,1,2,3个行向量,各由4个字节组成。

图2 奇数轮和偶数轮提取的字节位置

1.2 密钥扩展算法

LEX算法的密钥扩展运算依托其核心部件AES算法实现,通过密钥扩展将16 Byte的初始密钥K扩展为176 Byte,具体过程如下[9]:

1)将128 bit的初始密钥K按顺序划分为4个4 Byte的密钥字w0、w1、w2和w3(1个密钥字长度为4 Byte),用作AES初始阶段的轮密钥加运算。

2)10轮迭代过程所需的wi(i=4,5,…,43),共40个,由下述方法生成。

当i(mod 4)≠0时,密钥字:

wi=wi-1⊕wi-4

(1)

当i(mod 4)=0时,密钥字:

wi=ti⊕wi-4

(2)

ti为中间变量,其表达式为:

ti=Subword[RotWord(wi-1)]⊕Rconi/4

(3)

其中,RotWord函数表示将变量左移一个字节,Subword函数代表基于S盒的字节代替,Rconi/4为轮常量,由有限域GF(28)中的01循环左移定义,同样为长度是4 Byte的一个字。

1.3 针对LEX的滑动攻击

AES作为美国和欧洲分组密码加密标准,其算法本身的安全性是非常高的,可以说,至今还没有找到针对完整AES算法的有效攻击。LEX算法虽然以AES作为密钥流生成部件提高了算法的安全性能,但由于每组AES加密过程使用相同的加密密钥K,且把轮变换过程中的部分中间状态作为密钥流输出,易遭到攻击。比较典型的是针对LEX算法的滑动攻击,分析过程如图3所示[8, 10-11]。

图3 针对LEX算法的滑动攻击

(4)

(5)

2 LEX算法的改进及分析

2.1 LEX算法的改进

由前述分析可知,LEX算法无法较好地抵抗滑动攻击的根源是密钥体系不完整,每组AES都使用了相同的加密密钥K,从而导致各轮迭代的加密密钥对应相同,存在隐患。通过改进LEX算法的密钥体系,减少各组密钥的关联性,加强算法抗滑动攻击能力,具体方法如下:

1)根据初始向量IV和种子密钥K执行一次变形的AES(第10轮包含列混合操作),即算法的初始化阶段,此过程中不输出密钥流。128 bit密钥K经过密钥扩展得到44个密钥字wi(i=0,1,…,43),每轮迭代运算需要4个wi(i>3),由式(2)和式(3)可知,此过程中还需要产生10个中间变量t4i(i=1,2,…,10),t4i完全由初始密钥K和轮常量Rconi/4通过一系列复杂变化生成,t4i长度为4 Byte。

2)第2组AES的初始向量C1为上组AES的输出,加密密钥K发生改变,从第1组AES的密钥扩展过程中提取t24、t28、t32、t36共16个字节,按顺序排列,作为此组AES的初始加密密钥K1。此后每组AES的加密密钥K′=Ki(i≥1)均依托上一组AES密钥扩展中的t4i(i=6,7,8,9)组成,不仅延续了AES良好的安全性能,而且使各组加密密钥不再相同。ki(i≥2)表示第i组AES加密后输出的320 bit密钥流(第一次没有输出)。改进后的LEX算法结构如图4所示。

图4 改进的LEX算法结构

通过C++编程工具实现对算法的改进,密钥扩展部分的伪代码形式如下:

void KeyExpansion(int key_ronud[4][Nb])

{

{ int i,j,k,x,y;

int temp[4];

int key_temp[4];

int Rcon[11][4]=

{0x00,0x00,0x00,0x00,

0x01,0x00,0x00,0x00,

0x02,0x00,0x00,0x00,

0x04,0x00,0x00,0x00,

0x08,0x00,0x00,0x00,

0x10,0x00,0x00,0x00,

0x20,0x00,0x00,0x00,

0x40,0x00,0x00,0x00,

0x80,0x00,0x00,0x00,

0x1b,0x00,0x00,0x00,

0x36,0x00,0x00,0x00};

for(k=1;k<11;k++)

{

{ for(i=1;i<4;i++)

for(j=0;j<4;j++)

{temp[j]=w[k-1][(j+1)%4][3];//k=i=1,

//RotWor变换;

w[k][j][0]=temp[j];

x=w[k][j][0]/16;//除法取整

y=w[k][j][0]%16;//除法取余

w[k][j][0]=Sbox[x][y];//S变换,即Subword()

w[k][j][0]=w[k][j][0]^Rcon[k][j];//生成ti(1字节) key_temp[j]=w[k][j][0];//通过j循环提取ti(1字节)

w[k][j][0]=w[k][j][0]^w[k-1][j][0];

//i(mod 4)=0

w[k][j][i]=w[k-1][j][i]^w[k][j][i-1];

//i(mod 4)≠0

}

}

key_1[k-1][0]=key_temp[0];//将10轮ti提取出来

key_1[k-1][1]=key_temp[1];

key_1[k-1][2]=key_temp[2];

key_1[k-1][3]=key_temp[3];

}

for(int p=0;p<4;p++)

//提取6-9轮ti值赋给初始种子密钥

{

key[0][p]=key_1[5][p];

key[1][p]=key_1[6][p];

key[2][p]=key_1[7][p];

key[3][p]=key_1[8][p];

}

}

}

程序中套用3个循环,k循环表示10轮迭代,每轮迭代需要4个密钥字wi,i循环代表每轮迭代中4个wi,j循环代表每个wi中的4个字节。ti的生成与提取都是在j循环内按单个字节,分4次完成的。

2.2 安全性分析

研究表明,改进后的LEX算法可以有效地抵抗滑动攻击,具体分析如下:

分析可知,改进后的LEX算法,各AES模块加密密钥发生变化,阻断了各AES模块上的直接关联,使各组密钥不会通过对比分析而泄露出来,在根源上破解了滑动攻击的攻击点,从而使攻击者无法找到可以实施滑动攻击的碰撞对,提高算法安全性。

2.3 速度分析

改进后的LEX算法较原算法略为复杂,各组AES加密密钥均发生变化。但是,算法改进的重点是在密钥扩展阶段提取了部分中间变量t4i(i=6,7,8,9),通过两步代码存储到原初始密钥的位置,供下一组AES运行时直接调用。算法的整个改进过程中没有产生新的变量,没有增加额外的计算,两步储存所需时间与整个算法的运行时间相比可以忽略不计。因此,改进后的算法在速度上保持了原LEX快速的特点,约为OFB模式下AES的2.5倍(320/128=2.5)。

3 特性仿真实例与分析

合格的流密码算法必须要保证生成的密钥流具备良好的随机特性。根据我国随机性检测标准《随机性检测规范》[13]规定,随机性合格的序列须通过单比特频数检测、二元推导检测、近似熵检测、重叠子序列检测、块内频数检测、游程总数检测、块内最大1游程检测、扑克检测、游程分布检测、自相关检测、线性复杂度检测、矩阵秩检测、累加和检测、Maurer通用统计检测、离散傅里叶检测等15种随机性检测。

序列随机性的检测方法如下[13]:

1)用随机数发生器产生1 000个长度为105bit的0-1序列作为待检样本。

2)对待检验的1 000个样本依次进行上述15项随机性检测。

3)对于每一项随机性检测项目,统计P-value值不小于显著性水平α(建议取α=0.01),表示该样本通过该项检测。

下面以块内频数检测为例进行简要说明[13]。

块内频数检测的目的是检测待检序列的长度为

m位的子序列中1的个数是否接近m/2。对随机序列来说,其任意长度的m位子序列中1的个数都应该接近m/2。检测步骤为:

1)将待检序列ε分为N2=⎣n/m2」个长度为m2的非重叠子序列,将多余的比特舍弃。本规范取m2=100。

2)计算每个子序列中1所占的比例:

5)若P-value≥α,则认为待检序列通过该项检测。

以C++编程软件和《随机性检测规范》为依托,搭建针对LEX改进算法的随机性检测平台,对LEX改进算法产生的1 000个105bit 0-1序列进行随机性检测。如果每项检测未通过数不大于19,则通过该项检测;如果本规范所规定的15项检测全部通过,则改进后的LEX算法通过本规范检测;否则,未通过本规范检测。

改进的LEX算法随机性检测总体情况如表1所示。为便于对比分析,表1同时列出了同等条件的LEX算法的检测结果[14]。从检测结果可知,2种方案15项检测未通过数均小于19,通过随机性检测。对比来看,虽然改进后的LEX算法在15个单项检测中未通过组数较原始算法有所差别,但P-value值期望和方差分基本保持一致,除矩阵秩与离散傅里叶2项检测值略有差别,其余项目均在0.5与0.08之间上下浮动,未发生明显变化,说明改进后的算法保持了原LEX算法良好的随机特性,通过随机性检测,符合序列随机性要求。

表1 样本随机性检测结果分析

4 结束语

以分组密码AES为核心设计的流密码算法LEX是现代流密码算法设计的一种重要方法。但LEX算法的结构缺陷,引发了众多密码界学者对其进行分析和攻击,其中又以滑动攻击最为有效,只需要261个初始输入IV和2×104Byte的密钥流,就可以完全恢复出128 bit密钥[15]。本文以LEX算法为基础,对其密钥体系进行改进,使其每组AES的加密密钥均不同,具备抵抗滑动攻击的能力,提高了LEX算法的安全性,并且保持了LEX算法较高的运行速度。同时,实验仿真结果表明,改进后的算法延续了LEX算法良好的随机特性。由于算法本身的结构与运算并未做调整,因此改进后的算法在其他方面性能与LEX算法相当。

[1] ECRYPT.eSTREAM:ECRYPT Stream Cipher Project,IST-2002-507932[EB/OL].(2004-02-11).http://www.ecrypt.eu.org/stream.

[2] HASTAD J,NASLUND M.The Stream Cipher Polar Bear[EB/OL].(2005-02-10).http://www.ecrypt.eu.org /strearm/.

[3] BIRYUKOV A.A New 128-bit Key Stream Cipher LEX[EB/OL].(2005-06-13).http://www.ecrypt.eu.org/stream/ciphers/lex/lex.pdf.

[4] National Institute of Standards and Technology.Announcing the Advanced Encryption Standard(AES)[EB/OL].(2001-11-26).http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.

[5] HENRICKSEN M.Flexible Block Ciphers:Modifying LEX[C]//Proceedings of IEEE International Conference on Computer Science & Information Technology.Washington D.C.,USA:IEEE Press,2010:630-634.

[6] VELICHKOV V,RIJMEN V,PRENEEL B.Algebraic Cryptanalysis of a Small-scale Version of Stream Cipher LEX[J].Information Security,2010,4(2):49-61.

[7] 张中亚,关 杰.对流密码算法LEX的差分故障攻击[J].上海交通大学学报(自然科学版),2012,46(6):865-869.

[8] WU Hongjun,PRENEEL B.Attacking the IV Setup of Stream Cipher LEX[EB/OL].(2006-03-15).http://www.ecrypt.eu.org/stream/papersdir/059.pdf.

[9] 邓元庆,龚 晶,石 会.密码学简明教程[M].北京:清华大学出版社,2011.

[10] 李佳雨,石 会,邓元庆,等.抗滑动攻击的LEX算法改进及分析[J].通信技术,2015,48(2):203-207.

[11] 李 欣,谭晓青.抵抗滑动攻击的LEX算法改进[J].计算机工程与应用,2012,48(26):101-103.

[12] 尤加勇,李 超.针对LEX算法的截断滑动攻击[J].信息安全与通信保密,2007(9):96-98.

[13] 国家秘密管理局.随机性检测检测规范:GM/T0005-2012[M].北京:中国标准出版社,2012.

[14] 李佳雨,石 会,邓元庆,等.针对流密码LEX的差分故障攻击及算法改进分析[J].计算机科学,2015,42(11):352-356.

[15] 李佳雨.流密码算法DLEX设计与分析[D].南京:解放军理工大学,2015.