轻量级认证加密算法Spook的相关能量分析

潘 力,韦永壮

(桂林电子科技大学广西密码学与信息安全重点实验室,广西 桂林 541004)

1 引言

1999年,Kocher等人[1]利用密码芯片的功耗依赖于其所处理的数据或所执行的操作关系,提出了差分能量分析(Differential Power Analysis,DPA)方法。本质上,DPA[2]利用了一个基本事实:密码设备的能量消耗依赖于算法执行过程中所处理的中间值(中间状态)。此后,各种侧信道分析被相继提出,如相关能量分析(Correlation Power Analysis,CPA)[3]、互信息分析(Mutual Information Analysis, MIA)[4]等。2015 年,王等人[5]提出了改进的相关能量分析方案 SGA-CPA。2019 年,乌等人[6]提出了针对一种基于 SM3 算法的消息验证码的CPA攻击。陈等人[7]提出了针对 SM4 的混合智能侧信道分析攻击方法。王等人[8]提出了新的改进的相关能量分析方案MS-CPA。2020年,龚等人[9]使用CPA攻击了美国国家标准与技术研究院(National Institute of Stand-ards and Technology, NIST)征集的轻量级加密算法中的第二轮候选算法WAGE。2021年,王等人[10]提出了相关能量分析中的后向检错方案,提高了相关能量分析的准确率。同年,王等[11]提出了一种基于遗传算法的高效的CPA框架。CPA与其它分析方法相比,其核心思想在于计算算法的假设功耗与真实功耗的相关性,从而恢复出敏感信息;而DPA则是根据某个中间值的某一比特将能量迹简单分组,对泄露信息的利用率较低。同其它分析方法相比,CPA分析效率更高,因此对密码算法的威胁更大,文献[12]也佐证了这一观点。

近些年来,在一些新兴领域[13](例如传感器网络、医疗保健、分布式控制系统、物联网、信息物理系统等)资源高度受限的设备[14]需要相互连接,协同完成某些工作[15]。由于当前的大多数加密算法都是为桌面/服务器环境设计的,这些算法大多不适合资源受限设备。因此,NIST于2015年面向全球启动轻量级加密算法的征集工作。2020年, 来自鲁汶大学、德国波鸿鲁尔大学及法国国家计算机科学与控制研究所的密码专家联合设计出一种新的轻量级认证加密算法Spook[16],它是NIST第二轮候选算法之一。与之前的算法不同,Spook基于双工海绵结构[17],包含Clyde-128和Shadow-512两个大部件。Spook将防泄露操作模式[18]与比特切片技术[19]相结合,以实现高效和低延迟。目前,针对Spook的传统数学分析[20]已经取得一些进展,但Spook能否抵抗侧信道攻击,特别是其抵御CPA攻击的能力还有待进一步地评估。

本文根据Spook加密算法的结构和特点,设计了针对Spook算法的CPA攻击方法。实验结果表明,Clyde-128部件对于CPA攻击具有脆弱性;Shadow-512部件具备抵抗侧信道攻击的能力,但攻击此部件仍可恢复部分敏感信息,并可进一步恢复出相应明文。实验还表明:相比S盒采用查表操作,当S盒采用切片技术时, Spook密码算法抵御CPA攻击的能力稍有提升。

2 Spook算法描述

2020年,密码学者Francesco、Gregor、Gaёtan等人基于海绵结构设计了Spook加密算法,这是一种轻量级的认证加密算法,特别适合在资源受限设备上部署使用。Spook由两个主要部件构成,分别是Clyde-128和Shadow-128,其中Shadow-512可以看作是Clyde-128的多重复用,均包含非线性替换、L盒、轮常量加。此外Shadow-512还包含混淆层。根据π部件内部状态的大小和单/多用户的不同可将其分为4种版本,分别记为:Spook128mu384、Spook128mu512、Spook128su384、Spook128su512。对于Spook128mu512和Spook128su512,密钥做了一些处理,但没有改变算法的安全强度。在算法内部,明文data和关联数据AD总长度不超过256比特,被分成i块,前i-1块长度为128比特,最后一块长度不超过128比特。密钥K长度为128比特。一次性随机变量vector长度为128比特。填充数据fill则根据实际需要确定填充长度。为方便起见,此处只讨论Spook128su384加密算法(下文简称Spook)的安全性。Spook算法结构如图1所示,加密过程如下:

1)vector、fill和主密钥K进入加密函数E,生成长度为128比特的种子密钥seed;

2)seed、vector、fill进入置换部件π更新,并吸收关联数据AD,之后进入置换部件π更新并得到更新后的中间状态state0。此时明文data未参与运算,其它参数固定不变时,state0保持不变,长度为384比特;

3)state0分块加密明文data,得到对应的密文cipher。在每次加密明文块得到密文块之后,中间状态state都会经过π被更新,这样做起到了一次一密的作用。每次运算只加密长度为128比特的明文,当data最后一块长度不足128 比特时,用0填充。

4)在加密完所有明文之后,更新后的中间状态state1与K经过E得到标签tag。tag由state1[0]与state1[1]和主密钥K经过E生成。

2.1 Clyde-128

加密函数E由Clyde-128构成,用于生成seed或tag。Clyde-128示意图如图2所示。

图2 Clyde-128示意图

2.2 Shadow-512

置换部件π由Shadow-512构成,用于更新Spook的内部中间状态,它为Spook提供了一种防泄漏操作模式。Shadow-512示意图如图3所示。

图3 Shadow-512

从图3可以看出,Shadow-512部件的内部状态state为384比特,被分成3组,每组长度为128比特。在加密明文时,state前128比特与第一块明文data[0]运算,然后state进入π更新,更新后的state中间128比特与第二块明文data[1]运算。由于明文长度不超过256比特,因此state最后一块128比特状态值不与明文做任何运算。

2.3 半字节代换

半字节代换是一个非线性变换操作,其将内部状态中的每一个半个字节替换为另一个半个字节。Spook使用4比特密码S盒,即4比特输入得到4比特输出,如表1所示。S盒的代数正规型见式(1)

表1 Spook算法S盒

y[1]=(x[0]⊗x[1])⊕x[2]

y[0]=(x[3]⊗x[0])⊕x[1]

y[3]=(y[1]⊗x[3])⊕x[0]

y[2]=(y[0]⊗y[1])⊕x[3]

(1)

式中,0表示低位,3表示高位,⊗表示与运算,⊕表示异或运算。5.2节S盒采用比特切片技术实现时需要参考式(1)。

2.4 L盒

使用L盒是为了在有限的实现成本下获得更好的分支数量,提高抵抗线性和差分攻击的能力。此L盒有16个分支,意味着S盒的位数必须是偶数。它的计算公式如式(2)所示。

(a,b)=L′(x,y)

(2)

其中,x、y表示32比特长的数,circ表示第一行用十六进制表示的循环矩阵。

2.5 混淆层

Spook算法的混淆层使用的是Midori[21]加密算法的混淆层,它基于近似MDS 4×4矩阵D,定义如(3)所示

(3)

它有4个分支,可以使用较为简单的电路实现。

2.6 轮常量

轮常量由4位线性反馈移位寄存器(Linear Feedback Shift Register, LFSR)生成,具体数值如表2所示。

表2 Spook算法L盒

3 相关能量分析与数据预处理

加密设备在运行过程中会通过侧信道泄露多种信息,如时间序列[22]、功耗[23]、电磁辐射[24]等。CPA是功耗攻击的一种常见方法,攻击的目标是设备对明文进行加密(解密)运算时泄露的功耗信息,并基于这些信息恢复出需要的敏感信息。值得注意的是,CPA攻击需要采集较多功耗数据,且数据整体需满足正态分布。下面简要介绍CPA攻击的基本思想。

3.1 相关能量分析流程

相关能量分析[3]大致可分为以下4个步骤:

1)选定算法运行过程中的某个中间值。这个中间值通常由一个函数func(p,guesskey)生成,p多为明文(密文),guesskey为猜测密钥;

2)采集加密算法在设备上运行时的真实功耗数据;

3)计算假设功耗。根据猜测密钥guesskey,计算与之对应的中间值,并将中间值通过功耗模型映射为假设功耗;

4)计算不同猜测密钥对应的假设功耗与真实功耗的相关性。相关性计算式如式(4)

(4)

图4 CPA攻击流程图

3.2 功耗模型

对于在软件平台实现的加密算法,一般选用汉明重量模型刻画动态能量消耗。原因在于微控制器采用了预充电总线,在向总线发送被操作数之前,所有总线都会被置为1[25]。设某一时刻i的功耗用T[i]表示,功耗T[i]与中间值x[i]的线性关系[26]可以表示成

T[i]=μHW(x[i])+b+noise

(5)

其中,μ表示汉明重量HW(x[i])与功耗T[i]之间的之间的常量比率,b表示电路中的静态能量消耗,noise表示随机噪声。

3.3 泄露检测

为了快速评估Spook算法是否存在可被利用的侧信息泄露及其泄露区间,引入泄露检测技术。2011年,Gilbert等人[27]将t-test用于侧信道信息的泄露评估上,并对AES算法进行了泄露检测。2013年,Becker等人[28]进一步完善了该方法,并重新命名为TVLA(Test Vector Leakage Assessment)。在实际应用中,为了减少误差,需要对对一定数量的固定明文和随机明文进行交替加密,并采集相应的功耗曲线,用获得的两组功耗曲线进行t-test。其中,t统计量计算公式如式(6)

(6)

3.4 数据预处理

在CPA中,计算相关系数尤其耗时。当单条功耗曲线的采样点数越多,相应的攻击时间越长。因此在分析功耗曲线之前,有必要压缩曲线。文献[29]通过傅里叶变换将时域信号转换为频域信号分析,但该方法的效果取决于信息泄露和噪声的频谱特征。文献[25]中提出了诸如最大值整合、原始值整合等方法处理一个时钟周期内的点,以实现压缩曲线的目的。在机器学习领域有许多降维方法,包括主成分分析(Principal Component Analysis, PCA)[30]等。将主成分分析方法引入功耗曲线的预处理阶段,用于提取功耗中的主要信息,实现曲线的压缩。

设采集到的功耗曲线组成矩阵T。其中包括n条功耗曲线,每条曲线包含m个采样点,则T为

(7)

PCA处理步骤如下:

2)计算Cov的特征值λ1,λ2,…,λm和对应的单位特征向量

(8)

P1=e1,1T1+e2,1T2+…em,1Tm

P2=e1,2T1+e2,2T2+…em,2Tm

⋮ ⋮

Pm=e1,2T1+e2,nT2+…em,nTm

(9)

使用主成分分析处理功耗曲线在于压缩曲线,预处理后的维度k(k≤m),即每条曲线的点数应尽可能少,同时包含尽可能多的信息。k可通过损失率确定,设损失率为β,则有

(10)

损失率通常限定在0.15以内。在实验中选择损失率为0.05。

4 针对Spook加密算法的相关能量分析

本节将介绍Spook算法的Clyde-128和Shadow-512部件的攻击细节。第一部分攻击Clyde-128期望恢复算法加密用的主密钥K。设计者声称Shadow-512部件为加密算法提供了防泄露操作模式[16],可以抵抗侧信道攻击。第二部分攻击Shadow-512部件,验证其是否可以抵抗CPA攻击。

4.1 攻击Clyde-128

从算法结构可以看出,在生成seed的部分,Clyde-128会用到vector、fill和主密钥K。通过固定明文,并更改vector的方式恢复出主密钥K。在Clyde-128内部,K先与vector异或得到128比特状态值,而后按图5所示生成种子密钥seed。

图5 Clyde-128攻击点

在实验过程中,攻击点选在密码S盒的输出位,将S盒输出值通过汉明重量模型映射为假设功耗,并与采集到的真实功耗求解相关性,恢复出K(具体攻击实验过程采用3.1节所述步骤)。

4.2 攻击Shadow-512

如第2节所述,当AD、K、vector固定不变时,state0始终不变。此后state0的前128比特state0[0]参与到data[0]的运算中并得到密文cipher[0]。接着state0进入部件π被更新,记为Updatestate0[1]。Updatestate0[1]与data[1]运算得到密文cipher[1]。在分析时,由于需要明文参与运算,选择在每次Shadow-512内部状态第一次过S盒时作为攻击点,如图6所示。

图6 Shadow-512攻击点

设通过混淆层前的中间状态值为:Dpre[0]、Dpre[1]、Dpre[2],通过混淆层后的中间状态值为:Dafter[0]、Dafter[1]、Dafter[2]。混淆层按如下方式更新

Dafter[0]=Dpre[0]⊕Dpre[1]⊕Dpre[2]

Dafter[1]=Dpre[0]⊕Dpre[2]

Dafter[2]=Dpre[0]⊕Dpre[1]

(11)

由于不能完全掌握通过混淆层之前的中间状态值,无法进行后续的密钥恢复操作。因此,攻击Shadow-512部件,只能恢复出与K相关的前128比特中间状态值(具体攻击实验过程采用3.1节所述步骤)。

5 测试结果与分析

实验环境如表3所示:

表3 实验环境

在实验中,为了使分析更简便,在执行加密算法时,AD为固定的256比特数据,K为固定的128比特数据,具体参数如下

K=0x000102…0d0e0f,AD=0x00…00

根据算法结构和密钥,可以计算出明文参与前的中间状态state0的前128比特为:

state0=0xC2B5BBE3E0CCF2F799CBE5C444F427EA

5.1 S盒查表

算法实现时,S盒首先采用查表方式,每个数据的高四位和低四位依次通过S盒。采集Spook功耗数据,如图7所示。

图7 Spook功耗(S盒查表)

图7中,横轴表示采样时刻,纵轴表示功耗值,每条曲线145个点。对采集到的功耗数据进行泄露评估,评估结果见图8。

图8 Spook t-test结果(S盒查表)

图8中,横轴表示采样时刻,纵轴表示t值。上图表明,加密算法大致在[0:20000]以及[850000:1450000]区间存在信息泄露。

5.1.1 Clyde-128攻击结果

由5.1节中的t-test结果可知,结合算法结构,区间[0:20000]即为Clyde-128产生的泄露。采集789条功耗曲线,经过预处理后,单条曲线的点数从20000降至29,成功恢复出Spook加密所用的密钥K。具体结果见图9:

图9 Clyde-128攻击结果(S盒查表)

可知,S盒采用查表方式时,Clyde-128部件面对CPA具有脆弱性,也即此时Spook算法面对CPA具有脆弱性。

5.1.2 Shadow-512攻击结果

由5.1节中的t-test结果可知,在区间[850000:1450000],Shadow-512部件存在侧信息泄露。在实际分析时,采集5万条功耗曲线。根据算法结构,每条能量迹截取区间[900000:1000000],即10万个点。经过预处理后,每条曲线仅有1100个点。通过分析处理后的功耗数据,得到图10。可知,对Shadow-512的攻击完全恢复了state0的前128比特敏感信息。根据恢复出的敏感信息,当明文长度不超过128比特时,可以计算出密文对应的明文,但无法得到认证用的标签。

图10 Shadow-512攻击结果(S盒查表)

5.2 S盒切片

前面的讨论中S盒均使用查表的方式,而作为对比实验,本小节采用比特切片技术实现密码S盒层,并再次检验Spook算法的安全性。设S盒输入为Sin,输入数据为in,in为16个8比特的数,S盒输出数据为Sout,具体切片过程见式(12)和(13)

Sin[0]=in[3]‖in[2]‖in[1]‖in[0]

Sin[1]=in[7]‖in[6]‖in[5]‖in[4]

Sin[2]=in[11]‖in[10]‖in[9]‖in[8]

Sin[3]=in[15]‖in[14]‖in[13]‖in[12]

(12)

经过S盒如下

Sout[0]=(Sin[0]⊗Sin[1])⊕Sin[2]

Sout[1]=(Sin[3]⊗Sin[0])⊕Sin[1]

Sout[2]=(Sout[1]⊗Sin[3])⊕Sin[0]

Sout[3]=(Sout[0]⊗Sout[1])⊕Sin[3]

(13)

式(12)、(13)中,0表示低位,3表示高位,⊗表示与运算,⊕表示异或运算。将S盒用切片技术实现后,重新采集算法的功耗信息。如图11所示。

图11 Spook功耗(S盒切片)

图11中,横轴表示采样时刻,纵轴表示功耗值,每条曲线44万个点。从图7和图11的对比中可以明确的是,使用切片技术之后,整个算法的运行速度提高。相应的t-test结果见图12。

图12 Spook t-test结果(S盒切片)

5.2.1 Clyde-128攻击结果

由5.2节中的t-test结果可知,结合算法结构,区间[0:18000]即为Clyde-128产生的泄露。采集5万条功耗曲线,经过预处理后,单条曲线的点数从18000降至96,恢复出的结果见图13。

图13 Clyde-128攻击结果(S盒切片)

根据结果可知,对Clyde-128的攻击总计恢复出44比特与密钥相关的敏感信息。

5.2.2 Shadow-512攻击结果

由5.2节中的t-test结果可知,在区间[260000: 440000]Shadow-512部件存在侧信息泄露。在实际分析时,根据算法结构,每条能量迹截取区间[250000:300000]即5万个。经过预处理后,每条曲线仅有630个点。通过分析预处理后的功耗数据,具体结果见图14。

图14中,横轴表示恢复出来的密钥,纵轴表示密钥对应的相关系数。根据结果可知,针对Shadow-512的攻击总计恢复出16比特与密钥相关的敏感信息。

5.1节和5.2节的对比实验具体情况如表4和表5。

实验表明通过使用多个S盒并行运算的比特切片技术提高了CPA攻击的难度,但并不能提供绝对的安全性。原因在于,S盒采用查找表实现时,加密数据依次输入S盒,并得到相应的输出值,每次只有半字节数据产生功耗,分析采集到的功耗时,采用经典CPA的“分而治之”思想就可以恢复出敏感信息。S盒采用切片技术实现时,算法使用32个并行运算的S盒,这32个S盒的功耗会彼此影响,当采用经典CPA分析时,效率变低。

此外,将5.1.1节与文献[9]和文献[31]中类似结构的算法在攻击复杂度方面做了一个直观的对比,具体见表6。

表6 类似算法结构攻击复杂度对比

加密算法在不同的设备上执行加密运算时,由于实现方式和设备的差异,导致侧信息的泄露的情况不完全相同,因此攻击效果也不完全一样,此处只与文献[9]和[31]做了一个横向比较。同时,通过引入PCA对功耗曲线进行预处理,较好的压缩了曲线,提高了攻击效率。

6 结束语

本文分析了Spook算法抵御CPA的能力,即主要考察了Clyde-128和Shadow-512部件对于CPA攻击的安全性。在ARM开发板上的研究结果表明:采用CPA攻击其Clyde-128部件可在很短时间内恢复出加密用的主密钥;而当攻击其Shadow-512部件则可恢复出与密钥相关的前128比特中间状态;通过利用恢复出的中间状态和密文值,可捕获到明文的前128比特信息。此外还发现:当S盒采用比特切片技术,即通过使用32个S盒并行运算,能少许提升CPA攻击的成本,但仍无法完全抵御该攻击。下一步的研究可以考虑Spook密码算法的高效的掩码防护方法。