基于FPGA实现AES的侧信道碰撞攻击

郭建飞，王 忠，严迎建，郭朋飞

（解放军信息工程大学，河南 郑州 450004）

0 引言

2003年Schramm等在FSE上提出碰撞攻击[1]，参考文献[2]首次将侧信道碰撞应用到AES上。随后，Bogdanov[3]对AES的侧信道碰撞攻击进行了改进，Moradi等人[4]提出对使用掩码S盒的AES进行碰撞攻击。侧信道碰撞攻击不需要依赖任何泄露模型，只需拥有识别攻击点在能量迹中位置的能力。

本文在对侧信道碰撞攻击技术研究的基础上，提出了方差检查技术，并利用基于相关系数的碰撞检测方法，对AES实施了攻击。

1 碰撞攻击流程及AES碰撞分析

1.1 碰撞攻击流程

碰撞攻击可按图1所示的步骤实施。侧信道碰撞攻击技术可分为4个阶段：碰撞分析、侧信息测量、碰撞检测和密钥恢复。其中，碰撞分析和碰撞检测为侧信道碰撞攻击的关键，本文主要对这两个阶段进行研究。

1.2 AES碰撞分析及密钥恢复

图1 侧信道碰撞攻击流程图

本文选择AES进行侧信道碰撞攻击的研究。记K={kj}1j=61，kj∈F28，(j=1，2，…，16)为初始密钥，Pi={pij}1j=61，pij∈F28，(j=1，2，…，16)为明文，其中 pij为明文的第 j个字节，i表示AES执行的序号。

如图2所示，假设在AES第一轮S盒中的第4个字节和第11个字节位置处发生一次碰撞，则：

图2 AES执行过程中发生的线性碰撞

由于S盒是双射函数，可获得一个关于密钥的线性方程：

针对第一轮第一个S盒与其他S盒的碰撞，理想情况下可得到如下方程组：

即第一轮子密钥字节 k2，…，k16均可由k1表示，然后在给定明密文对的条件下遍历 k1，就可确定 k1，根据k1和方程组(3)就可求出其他比特密钥。

2 算法实现及能量采集

2.1 算法实现

对面积和功耗有较高要求的分组密码算法在硬件实现时，会对S盒采取复用[4-6]，这为侧信道碰撞攻击的实施提供了契机。本文以如图3所示AES为攻击对象。

图中，控制模块控制寄存器组1每一个时钟周期输出输入选择模块结果的8位，最后一圈时，寄存器组1中的128比特数值为密文；寄存器组2用于寄存16个时钟周期中S盒运算的输出。

2.2 能量采集平台

采用如图4所示的能量采集平台[7]对本文的研究进行验证。其中，PC对控制模块和密码芯片进行信息配置，并对示波器采集到的波形数据进行分析；控制模块控制密码芯片的加解密运算；信号发生器提供系统时钟；密码芯片中下载待攻击密码算法；示波器采集密码芯片的电磁辐射信息。

图4 能量采集平台

3 基于相关系数的碰撞检测方法

本文提出通过计算能量迹中每一采样点的方差来识别攻击点的方差检查技术，并利用基于相关系数的碰撞检测方法对其进行了验证。

3.1 方差检查

概率论上，方差用于度量随机变量和其数学期望之间的偏离程度，随机变量X的方差如式(4)所示：

当不同算法操作处理不同输入时，对应的侧信息有差别，基于此，可利用方差来检查电磁曲线中碰撞攻击点的位置信息，具体步骤如下：

(1)针对某一攻击点，遍历所有对应明文位作为能量采集平台中算法的明文输入；

(2)利用能量采集平台采集对应明文的电磁曲线波形；

(3)对电磁曲线中每一个采样点进行方差计算。

具体地，针对AES算法，将第一轮第一个S盒视为碰撞攻击点，对其进行方差检查。

首先，遍历对应第一个S盒输入的8位明文；然后，利用能量采集平台重复采集y次对应遍历明文的电磁曲线，对每个明文对应的电磁曲线做平均，得到28条平均电磁曲线，记第i条平均电磁曲线为：

其中，Ti，j为第 j(1≤j≤m)个采样点值，m 为采样点个数；则第j个采样点的方差可用下式计算：

利用式(6)对28条平均电磁曲线计算每一个采样点的方差，就可得到对应第一个S盒的方差图。

3.2 碰撞检测方法

每条迹Ti都包含第一轮中每个S盒计算时泄露的电磁信息，当S盒计算在两个字节位置j1=a和j2=b碰撞时，可得 sia1=sib2，则pia1⊕ka=pib2⊕kb。将输入差分定义为Δa，b=pia1⊕pib2=ka⊕kb。对 于 固 定 的 密 钥 ， 差 分 Δa，b=ka⊕kb是固定的。 因此当 pa=α，pb=α⊕Δa，b时，碰撞就会发生。图 5给出了猜测 Δa，b=Δg的相关系数计算方法。 其中，T1，T2，…，Tn表示输入明文为 P1，P2，…，Pn时对应的平 均 能 量 迹 ；T1′，T2′， … ，Tn′表 示 输 入 明 文 为 P1⊕Δg，P⊕Δ ， …，P⊕Δ 时对应的平均能量迹；Ma和 Ma⊕Δg分2gngab别表示平均迹矩阵；ρ(Ma，Ma⊕Δg)表 示 对 Ma和 Ma⊕Δg在abab每一个采样点得到的相关系数。

图5 基于相关系数的碰撞检测方法示意图

对应第j个采样点的相关系数可利用下式进行计算：

遍历 Δa，b，根据式(7)对每个采样点进行相关系数计算可以得到n条相关系数曲线，对应相关系数最大的Δa，b即为正确差。

4 攻击验证

本节从实测验证、方差计算、相关系数计算三个方面对AES的实现进行攻击验证。

4.1 实测验证

按照侧信道信息采集平台的工作流程，采集AES密码芯片运行时16个S盒运算的泄露信息如图6所示。

图6 AES S盒运算时的电磁曲线

从图6可以看出示波器上的能量迹与AES的16个时钟周期的S盒运算十分吻合。因此，能量采集平台下观测到的能量迹曲线可以作为攻击的信息源。

4.2 方差计算

如3.1节的描述对个别S盒发生泄露的位置进行检测。 选择两个 S 盒为碰撞点时，固定 α∈GF(28)，遍历 Δa，b，对每个明文重复50次测量，对应每个S盒可各得50×28条迹，对两组28条平均迹分别求方差，得到图7所示两个方差图。

图7 第一轮前两个S盒的方差图

从图中可以看出，在第110个采样点附近和第160个采样点附近两图有明显差异，说明算法执行时对这两部分操作处理的数据有明显不同，这与遍历输入明文字节的位置不同相对应，印证了第一个S盒和第二个S盒作为碰撞攻击点的事实。

4.3 相关系数计算

将第一个S盒和第二个S盒作为碰撞攻击的目标。设初始密钥 K=128’h0123 4567 89AB CDEF FEDC BA98 7654 3210，固定明文 P=128’h0000 0000 0000 0000 0000 0000 0000 0000，遍历 Δa，b=Δg，对对应 P 的能量迹和对应P⊕Δg的能量迹进行相关系数计算。由于两个S盒对应电磁曲线中位置不同，在计算相关系数前，将第二个S盒的电磁曲线左移50个采样点，使得两个S盒对应位置信息对齐。固定α∈GF(28)，对每一个时间点计算相关系数ρ(Ma，Ma⊕Δa，b)。对以上采集到的电a b磁曲线进行相关系数计算，得到相关系数结果如图8所示。

从图8中可以看出， 当 Δa，b=128’h0000 0000 0000 0000 0000 0000 0000 2200 时，对应 P 和 P⊕Δa，b的 相 关系数曲线有明显的尖峰，则碰撞检测成功。

图8 相关系数结果图

5 结论

为了识别攻击点，本文提出方差检查技术，在对AES进行攻击的过程中，利用基于相关系数的碰撞检测方法对其进行了验证，结果表明方差检查技术可以有效地识别攻击点在能量迹中的位置信息。

[1]SCHRAMM K，WOLLINGER T，PAAR C.A new class of collision attacks and its application to DES[C].Johansson，T.(ed.)FSE 2003，LNCS，Springer，Heidelberg，2003：206-222.

[2]SCHRAMM K，LEANDER G，FELKE P，et al.A collisionattack on AES：combining side channel and differentialattack[C].Joye，M.，Quisquater，J.-J.(eds.)CHES 2004，LNCS，Springer，Heidelberg，2004：163-175.

[3]BOGDANOV A.Improved side-channel collision attacks on AES[C].Selected Areas in Cryptography-SAC 2007，2007：84-95.

[4]MORADI A，MISCHKE O，EISENBARTH T.Correlationenhanced power analysis collision attack[C].CHES，2010：125-139.

[5]CANRIGHT D.A very compact S-Box for AES[C].CHES 2005，volume 3659 of LNCS，Springer，2005：441-455.

[6]SATOH A，MORIOKA S，TAKANO K，et al.A compact rijndael hardware architecture with S-Box optimization[C].Advances in Cryptology-ASIACRYPT 2001，volume 2248 of LNCS，Springer，2001：239-254.

[7]段二朋，严迎建，李佩之.针对 AES密码算法FPGA实现的 CEMA攻击[J].计算机工程与设计，2012，33(8)：2926-2930.