基于碰撞模型的LED 代数旁路攻击[1]

　　引言

　　分组密码作为现代密码学的一个重要组成部分，对于保障信息安全有重要意义。随着信息技术和电子元器件的发展，密码设备逐渐轻型化，如何在RFID 标签等轻型的密码设备上实现密码算法成为分组密码研究的新热点。轻型分组密码由于其在资源受限的应用环境下的特殊性，其安全性研究不容忽视。本文以LED 轻型分组密码[1]为研究对象。

　　代数旁路攻击[2][3]将代数攻击[4]和旁路攻击[5]相结合，利用代数攻击建立密码算法明文和密钥的联立代数方程组，再将通过旁路攻击手段获取到的泄露信息代入方程组帮助求解。这种结合克服了代数攻击求解方程组复杂度高的缺陷，弥补了旁路攻击所需样本量大、旁路信息利用率低、分析轮数少、适用性较差等不足，是数学分析方法与旁路攻击发展的必然结果。代数旁路攻击可以在未知明密文的情况下恢复密钥，有时只需一个样本就能恢复密钥，对于一些加入防御措施的密码实现也能成功实现攻击，给分组密码特别是轻型分组密码造成了严重的安全威胁。如何基于代数旁路攻击进行高效的密钥恢复具有重要的理论价值及现实意义。

　　功耗碰撞信息作为旁路信息的一种用于密码分析，最早由Wiemers[6]等人在2001 年针对硬件实现的ECC 进行攻击时使用，Schramm 于2003 年首次将基于碰撞模型的功耗攻击应用于分组密码[7][8]。

　　本文以LED 轻型分组密码为攻击对象，基于碰撞模型，通过采集微控制器上LED 算法执行过程中的功耗泄露，使用Pearson 相关系数[9]方法将加密中间状态的功耗值进行匹配并转化为代数方程组，在此基础上使CryptoMinisat 可满足性解析器[10]进行密钥求解。攻击实验结果表明：LED 易遭代数旁路攻击威胁，已知明文条件下2 轮S 盒输出的碰撞信息可恢复全部初始密钥。

　　本文组织结构如下：第1 节主要给出碰撞模型和代数旁路攻击原理，第2 节进行LED 代数方程组构建，第3 节是基

　　于功耗的碰撞捕获和碰撞表示，第4 节给出实验结果，最后第5 节对文章进行总结。

　　1 基于碰撞模型的代数旁路攻击原理

　　1.1 碰撞模型

　　碰撞本义指两个或多个不同的东西在某点相遇，引申为某些性质相同。在分组密码代数旁路攻击中，如果算法运行时任意两个或多个中间状态的值相同，即为发生一次碰撞。将该碰撞信息转化为等式后可扩充算法的代数方程组，降低密钥的求解复杂度。

　　实际攻击中中间值的碰撞可以通过旁路信息的泄露表现出来，比如功耗。密码设备运行时的功耗不仅和密码设备

　　相关，和处理的数据也紧密相关。给定一条密码算法运行时的功耗曲线，通过对多轮S 盒输出的某两个中间值(LED 为半字节)对应的功耗轨迹进行相关性匹配，计算功耗轨迹之间的相关性系数，从而推断这两个中间值是否发生碰撞。图1 是碰撞模型，给出了对算法运行中的任意两个中间状态进行碰撞捕获和利用的过程，其中m 为状态矩阵， i、j 表示轮数。以相邻两轮的S 盒输出为例，对功耗曲线中的相应部分进行相关性匹配，匹配成功后可以获取碰撞信息，捕获到的碰撞信息可以转换为代数方程。

　　1.2 攻击原理

　　代数旁路攻击一般可分为3 个步骤：密码算法方程组表示、旁路泄露采集及利用、代数方程组求解。

　　(1)密码算法方程组表示：将密码算法表示为关于明文、密钥、中间变量、密文的代数方程组。在LED 算法代数方程组构造过程中，最为关键的部分是如何构造非线性部件S盒的代数方程组。

　　(2)旁路泄露采集及利用：给定一个密码算法的代数方程组，密钥恢复等价于代数方程组求解。直接进行代数方程组求解是一个N-P 难题，故需要利用旁路泄漏信息降低方程组复杂度。攻击者可以根据要攻击的密码实现平台和自身的测量能力来选取一个旁路泄漏模型M，然后采集旁路泄露信息L，根据泄漏模型M 将L 转化为加密中间状态D，最后将D 使用额外的代数方程组表示出来。本文LED 代数旁路攻击基于碰撞模型，采集的旁路泄露信息为功耗信息。

　　(3)代数方程组求解：将前面建立的密码算法方程组与旁路泄露代数方程组联立起来，再进行方程组求解。目前，典型的代数方程组求解主要包括基于可满足性问题求解、线性化以及Grŏbner 基等方法。本文基于可满足性(SAT)问题求解方法进行代数方程组求解，首先将方程组转化为SAT问题，然后利用SAT 解析器进行密钥求解。本文选用CryptoMinisat 解析器作为求解代数方程组的工具。

　　2 LED 代数方程组构建

　　2.1 算法分析

　　LED 轻型分组密码采用了SPN 结构，其实现只需966 个门电路，是同类分组密码中最少的。由于其结构特点可以导出很多类似AES 的定理，抗差分、线性、代数攻击能力极强，但在算法设计时并没有考虑抗代数旁路攻击的能力，对其进行代数旁路攻击对安全性评估及防护有重要的意义。

　　LED 算法分组长度为64 bit，支持64/128 bit 的密钥长度，加密轮数为32 轮。本文中LED 分组密码均指64 bit密钥的算法。算法第1 轮之前进行一次轮密钥加，以后每4轮进行一次，即全轮共有9 次轮密钥加操作。为了提高加密速度及减小硬件实现规模，采取无密钥生成的策略，轮密钥即为初始密钥。算法的状态矩阵为GF(24)上的4*4 的矩阵，每个元素为4 个比特。每轮有轮常量加、S 盒、行移位和列混淆4 个步骤。具体参数见文献[1], 图2 为算法的流程图。

　　1.2 攻击原理

　　代数旁路攻击一般可分为3 个步骤：密码算法方程组表示、旁路泄露采集及利用、代数方程组求解。

　　(1)密码算法方程组表示：将密码算法表示为关于明文、密钥、中间变量、密文的代数方程组。在LED 算法代数方程组构造过程中，最为关键的部分是如何构造非线性部件S盒的代数方程组。

　　(2)旁路泄露采集及利用：给定一个密码算法的代数方程组，密钥恢复等价于代数方程组求解。直接进行代数方程组求解是一个N-P 难题，故需要利用旁路泄漏信息降低方程组复杂度。攻击者可以根据要攻击的密码实现平台和自身的测量能力来选取一个旁路泄漏模型M，然后采集旁路泄露信息L，根据泄漏模型M 将L 转化为加密中间状态D，最后将D 使用额外的代数方程组表示出来。本文LED 代数旁路攻击基于碰撞模型，采集的旁路泄露信息为功耗信息。

　　(3)代数方程组求解：将前面建立的密码算法方程组与旁路泄露代数方程组联立起来，再进行方程组求解。目前，典型的代数方程组求解主要包括基于可满足性问题求解、线性化以及Grŏbner 基等方法。本文基于可满足性(SAT)问题求解方法进行代数方程组求解，首先将方程组转化为SAT问题，然后利用SAT 解析器进行密钥求解。本文选用CryptoMinisat 解析器作为求解代数方程组的工具。

　　2 LED 代数方程组构建

　　2.1 算法分析

　　LED 轻型分组密码采用了SPN 结构，其实现只需966 个门电路，是同类分组密码中最少的。由于其结构特点可以导出很多类似AES 的定理，抗差分、线性、代数攻击能力极强，但在算法设计时并没有考虑抗代数旁路攻击的能力，对其进行代数旁路攻击对安全性评估及防护有重要的意义。

　　LED 算法分组长度为64 bit，支持64/128 bit 的密钥长度，加密轮数为32 轮。本文中LED 分组密码均指64 bit密钥的算法。算法第1 轮之前进行一次轮密钥加，以后每4轮进行一次，即全轮共有9 次轮密钥加操作。为了提高加密速度及减小硬件实现规模，采取无密钥生成的策略，轮密钥即为初始密钥。算法的状态矩阵为GF(24)上的4*4 的矩阵，每个元素为4 个比特。每轮有轮常量加、S 盒、行移位和列混淆4 个步骤。具体参数见文献[1], 图2 为算法的流程图。