分组密码故障攻击效率分析方法研究*

朱仁杰，杨 鹏，郑 辉，陈保亮

（1.海军工程大学 信息安全系，湖北 武汉 430000；2.中国人民解放军31677部队，河北 保定 071000；

3.海军工程大学 电子工程学院，湖北 武汉 430000）

0 引 言

故障攻击可以被攻击者主动实施，根据需要对密码算法注入故障，获取故障泄露信息，提高了分析算法密钥的可能性，降低了计算复杂度，对密码应用造成了严重的安全威胁[1-6]。故障的安全威胁是密码应用领域需要长期面对的问题[7-10]。文献[11]主要以信息论的角度对故障攻击的能力进行研究。本文通过研究分析故障攻击能力评估方法，进而揭示密码芯片面临故障攻击威胁程度。

本文深入分析了分组密码算法故障攻击特点，提出了一种描述故障攻击的一般方法。确定故障攻击中的关键要素，并通过对比故障攻击中的关键要素实现对故障攻击的评估。通过分析将不同的故障攻击纳入到统一的框架体系内，实现通用工具分析处理不同的故障攻击。

1 故障攻击特点分析

1.1 AES算法简介

本文以高级加密标准（Advanced Encryption Standard，AES[12]）为对象，研究故障攻击能力的评估方法。在本文中，明文记为P，密文记为C，密钥记为K。

AES密码算法是由美国国家标准与技术研究所（National Institute of Standards and Technology，NIST）制定的分组密码算法加密标准。本文中以128位密钥版本的AES算法为研究对象。

Kr是第r轮的轮密钥。加密操作首先将128位的明文分组转换为2维的16字节状态矩阵，与轮密钥K0进行异或运算后，进行 10轮函数加密操作。每一轮的加密操作包括以下步骤：

字节替换（SubBytes，SB），非线性变换，由16个S盒组成，每一个S盒独立进行替换操作，记为SB。

行移为（ShiftRows，SR），状态矩阵每行单独进行字节移位操作，记为SR。

列混合（MixColums，MC），状态矩阵每一列进行线性混合操作，记为MC。

轮密钥加（AddRoundKey，ARK），状态矩阵与轮密钥Kr,r∈[0,10]进行按位的⊕操作。

1.2 故障攻击特点分析

故障攻击通过干扰电路，改变算法的正确加密操作，使其输出错误的密文。故障的注入方法有很多，例如：激光、时钟故障、电源尖峰或电磁扰动等。

故障攻击的目标是密码算法的密钥K，通过反推算法中间状态，与故障模型进行匹配获取秘密信息。现有的故障攻击方法主要有差分故障攻击（Different Fault Attack，DFA[13-16]）、故障敏感度分析（Fault Sensitive Analyze，FSA[17]）、差分故障强度分析（Different Fault Intensity Analyze，DFIA[18]）等。对分组密码的故障攻击可描述为以下三步。

第一步：故障泄露信息获取。

在密码芯片有未知密钥K对随机明文P进行加密操作过程中，进行故障注入，获取观测信息O和故障特征T。典型的观测信息O有：明文、正确密文、故障密文、故障注入强度等。故障特征T则由故障模型所确定。对于不同的故障攻击方法，需要获取的观测信息不同，故障特征也不同。

例如，DFA中观测信息为

其中，C为任意明文P经未知密钥K加密得到的正确密文，C´是在明文和密钥相同的情况下，故障干扰的密文输出结果。

攻击者需要找到一条攻击路径。攻击路径是观测信息O，故障特征T与算法密钥K之间的连接关系，记为R。输入是O和K，输出是故障特征T。

其中，gi是分组密码算法中的加密函数。以AES为例，gi∈{SB-1,SR-1,MC-1,ARK-1}。f由攻击方式确定。

第二步：故障特征推测。

利用第一步中获取的信息，结合密码算法结构和故障注入模型，以及候选密钥，反推中间状态数据，推测故障特征。

式中，Kg是猜测密钥，Tp是由观测信息O、Kg根据攻击路径R推测出的故障特征。其中，Kg与R是未知的。为了推测中间故障特征，攻击者在所有可能密钥范围内选取猜测密钥Kg。攻击必需采用分而治之的策略，保证攻击目标K足够短，确保可以测试所有可能的猜测密钥。

例如在对AES开展的攻击中，攻击目标是轮密钥Kr的一个字节，则K=[0,255]，可能的猜测密钥有256个。

第三步：关联度匹配。

在上一步中，所有的猜测密钥经过故障特征推测，会得到一个Tp值，只有在猜测密钥正确，关系R正确的情况下，推测出来的中间故障状态Tp符合第一步中的故障特征T。

关联度匹配目的是将正确密钥和错误密钥区分开，将第一步中获取的故障模型与第二步中反推得到的中间秘密数据进行比较，区分出正确的密钥。

以上三步过程是所有故障攻击所遵循的基本过程。有些故障攻击首先恢复出部分信息，不能一次直接恢复出全部的密钥信息，在这种情况下，需要重复进行上述三步过程。在重复的过程中可能需要不同的观测信息和故障特征等。

2 故障攻击效率分析研究

目前，已发布的故障攻击分析方法有很多种，然而绝大部分的故障攻击方法都是从经典的攻击方法中衍变而来。在本节的内容中，我们主要介绍并分析差分故障分析（DFA）、故障敏感度分析（FSA）和差分故障强度分析（DFIA）三种故障攻击分析方法。并分析比较三种故障攻击分析方法在不同情况下的攻击效率。

2.1 差分故障分析（DFA）

1997年，Biham和Sharmir首次提出了针对DES分组密码算法的差分故障攻击概念。随后，差分故障分析方法又经过了不断的发展衍变。

在此例中，攻击的目标是第十轮密钥的四个字节，k=k10。k10存在256个可能值。攻击者在第8轮字节代换（SB）操作之间注入单字节故障，故障特征T为下图红色标注状态矩阵。

第一步：获取信息是密文对O=(C,C´)。

第二步：反推得到中间状态。R=R1⊕R2，其中R1=SB-1○SR-1○⊕，R2=SB-1○SR-1○⊕。

则中间故障状态为Tp=R(O)=R1(C)⊕R2(C´)。

第三步：故障状态匹配。不满足式mat(Tp,T)的候选密钥Kg为错误密钥。

攻击者探索最后一轮密钥k1,k8,k11,k14四个字节时，T为：

由Kg反推得到的Tp若不满足上式T，Kg即为错误密钥。

单次故障的计算复杂度为216，剩余密钥空间为232。Michael Tunstall提出了利用第9轮密钥与第10轮密钥之间的关系，再进行复杂度为216的计算，可将剩余密钥空间降为212。

已公布的DFA分析方法有很多种，从第6轮到第10轮都存在DFA的故障攻击方法。各种攻击方法所需的故障注入数量和计算复杂度各有不同。

2.2 故障敏感度分析（FSA）

故障敏感度分析（FSA）攻击由Yang Li等人在2010年的Cryptographic Hardware and Embedded Systems上提出。该分析方法主要依赖于密码芯片故障敏感度的数据依赖性。注入故障能引起密码状态产生故障与密码状态的汉明重量有关系。

第一步：获取信息为若干明文和错误密文对，O=(P,C)。通过逐渐增强故障注入强度，直到加密出现故障，记录此时的故障敏感度FC。根据故障敏感度的数据依赖性，得到中间状态的汉明重量，记为故障特征T。

第二步：反推中间故障状态。

R=HW○SB-1○SR-1○⊕，Tp=R(O)=HW○SB-1○SR-1○ (C⊕Kg)利用密文C和候选密钥计算出中间状态值I的汉明重量Tp=HW(I)。

第 三 步：mat(Tp,T)。Cor(Kg)=ρ(T,Tp)，计 算Tp和T之间的皮尔逊相关系数，相关系数最大的Tp对应的候选密钥为正确密钥。

当攻击者可以在第10轮输入状态选取字节进行故障注入时，需要对50组明文进行故障注入可以恢复全部密钥信息。计算复杂度为212。

2.3 差分故障强度分析（DFIA）

差分故障强度分析是由Ghalaty提出的。当故障注入强度调整较小时，中间故障状态也会随之产生较小的改变，DFIA就是根据这种特性对密码芯片进行攻击。该攻击的方法步骤如下：

第一步：在AES第9轮输出位置注入逐渐增加强度的故障，观测信息为O=(q,C´q)。q为故障注入强度和C´q为相应的故障密文。

第二步：利用故障密文和候选密钥反推第9轮输出状态矩阵。S´q=SB-1○SR-1○(C´q⊕Kg)

第三步：对所有的猜测密钥Kg，计算下式结果。

值最小的ρKg对应的密钥即为正确密钥。

DFIA攻击的成功实施，主要依赖于随着故障强度逐渐增加，中间状态的故障比特位随之增加。因此在攻击开始前，需要掌握故障注入强度与产生故障类型的对应关系。

在最理想的条件下，攻击者可以精确的故障注入，通过控制故障注入强度，使第10轮的输入状态的单字节分别产生1、2、3位比特故障。在这种情况下，48次故障注入可恢复完整的第10轮密钥，计算复杂度为212。

当攻击者无法精确控制注入故障位数时，通过逐渐增加故障注入强度，目标状态在故障强度达到故障敏感点时产生故障。在这种情况下，平均需要对90组明文进行90次故障注入可恢复完整的第10轮密钥，计算复杂度约为214.5。

当攻击者不能控制故障注入的字节时，需要进行约2000次故障注入可恢复完整的第10轮密钥，计算复杂度约为240。

2.4 攻击效率分析

在本节中，分析对比上述三种故障分析攻击方法的效率。在所有的故障攻击方法中，单次故障攻击计算复杂度相差不大，因此故障攻击所需的次数决定了攻击效率。对于每一种类型的故障攻击，记录所需明文数量以及每一个明文所需的故障注入数量。在本文中，故障攻击效率定义为：

其中，E，Pn，Fn分别代表故障攻击效率、所需明文数量、单个明文所需注入故障数量。

本节主要在三种情况下比较各故障分析攻击的效率。第一种情况，攻击者可以精确的故障注入，可以使状态矩阵的单一字节分别产生1、2、3字节比特故障。第二种情况，攻击者可以在状态矩阵的确定字节注入故障。第三种情况，攻击者可以在状态矩阵注入随机字节故障。第四种情况，攻击者在状态矩阵若干个字节注入故障。

如表1所示，在相同的情况下DFA攻击相对于其他两种攻击方法比起来效率更高。DFA发展到目前已有很多不同类型的分析方法，这些方法都依赖于较为严格的故障模型，当攻击者没有能力注入确定的故障模型，DFA攻击将不再适用。与DFA相比，FSA和DFIA攻击效率较低，但不需要严格的故障模型。在注入故障不确定的情况下，仍然可以恢复出密钥信息。

表1 不同情况下的攻击效率

3 结 语

本文提出了一种对分组密码故障攻击过程的形式化描述方法。不同的故障攻击方法，虽然故障注入位置可能相同，但由于其分析机制不同、依赖的特性不同，在攻击能力上会产生很大的差异。将所有分组密码的故障攻击方法纳入到一个框架体系内，为评估并比较各种故障攻击方法提供了基础。为密码安全防护工作提供指导。