典型分组密码抗差分故障攻击的安全分析*

2010-03-11李玮

电信科学 2010年2期

李玮

（东华大学计算机科学与技术学院上海 201620）

1 引言

分组密码是现代密码技术中实现数据加密、数字签名、认证及密钥管理的核心体制，在计算机通信和信息系统安全领域有着广泛的应用。随着集成电路和智能卡技术的发展以及嵌入式系统的大规模应用，单纯从分组密码算法的数学结构研究安全性能已远远不够，从算法的实现角度来考虑安全问题已成为必需。在实际应用领域中，密码算法通常使用各种芯片来实现，如智能卡、加密存储卡、加密机芯片、手机芯片和网络路由器芯片等，这些芯片在运行时有可能泄漏某些中间状态信息（出错消息、执行时间、功耗、电磁辐射等），使得攻击者有机会采集与密钥相关的关键信息，从而发现明文或密钥。故障攻击正是在这种背景下被提出的，由于其成功的攻击效果和潜在的发展前景，已经引起了国内外从事密码和微电子的研究学者的极大关注，并成为密码分析和密码工程领域发展最为迅速的方向之一。

故障攻击（fault analysis），又称故障分析，是指攻击者使用物理方法（如电磁或激光辐射）干扰密码芯片或软件的正常工作，迫使其执行某些错误的操作，从而泄漏密码系统的秘密信息。1996年，D.Boneh等人利用随机硬件故障来攻击公钥密码体制，此后故障攻击在密码分析方法中占据了重要的位置[1]。接着，E.Biham和A.Shamir于1997年针对DES密码算法提出了差分故障攻击方法[2]。然后，人们从故障诱导的长度、类型和持续度等方面对密码算法的故障攻击进行了分类，并从性能、效率、攻击难易程度等方面研究，进而给出了 AES算法[3～9]、CLEFIA 算法[10]、KHAZAD算法[8]、FOX算法[11]、SMS4算法[12]以及RC4算法[13,14]等多种密码体制的故障攻击方法[15～17]。后来，故障攻击在其自身的发展中，逐步衍生出多种攻击方法，例如差分故障攻击、无效故障攻击以及碰撞故障攻击等[2,14,18,19]，攻击对象扩展到更多的分组密码算法，例如IDEA算法[20]以及3-DES算法等[18]。与其他故障攻击技术相比较，差分故障攻击攻击范围广、能力强且计算量小，因此本文将重点研究差分故障攻击分组密码。

2 差分故障攻击

差分故障攻击是指攻击者在密码系统运行时导入故障，使其执行某些错误的操作、过程或产生错误的结果，并通过差分分析，获取密码系统的关键信息的方法。作为故障攻击的一种主要分析方法，差分故障攻击凭借其攻击范围广、能力强且计算量小等特点，已引起国内外研究学者的广泛关注。

1997年，E.Biham和A.Shamir针对DES密码提出了差分故障攻击方法[2]。接着，根据基本假设和故障模型的不同要求，研究学者对AES算法进行了深入的研究。2003年，C.Giraud首次提出了针对AES算法的差分故障攻击方法，在两种不同要求的故障模型下，分别实现了对AES算法的差分故障攻击[5]。然后，研究学者在故障模型要求较“弱”的情况下，实现了代价较小的攻击方法[7,8]。2006年，A.Moradi等人在故障模型要求更“弱”的情况下，提出并实现了差分故障攻击AES算法的新方法[3]。

从差分故障攻击分组密码的发展情况来看，差分故障攻击的成功实现需具备以下两个重要组成部分：基本假设和故障模型。

2.1 差分故障攻击的基本假设

差分故障攻击与密码算法的实现环境密切相关。因此，在分析算法之前，必须遵循以下重要的基本假设：

· 攻击者能够物理地运行包含密码运算的实体（设备、芯片、软件等）；

· 攻击者能够观察和记录实体的输出情况（具体的输出值或者输出正确与否），包括直接访问实体输出值或者在通信信道上截获信息；

· 通常要求攻击者知道实体中实现的密码算法，有时要求知道算法的具体实现方法；

· 有时要求攻击者能够选择和记录实体的输入（即选择明文攻击、密文攻击或密钥攻击）。

2.2 差分故障攻击的故障模型

由于攻击者需要在密码算法正常运行时导入故障，迫使其发生错误的输出结果。如何导入理想的故障，成为差分故障攻击能否成功实现的关键。在总结了国内外的研究成果基础上，本文讨论了故障模型的组成。通常，一个故障模型由三元组（时刻、位置、动作）构成。

故障时刻：攻击需要精确控制错误发生的时刻，例如在运算进行到某一指定的步骤时引入故障。有些攻击则不需要这样精确，引入的故障只需要在运算进行到某一个范围内，包含故障出现在算法某些部分（加密、解密、密钥编排方案）的某些轮或循环。一般地，对于迭代分组密码，根据故障轮或循环的位置可分为以下几种类型。

·单轮故障：是指每次仅在故障运算的某一轮或循环出现故障。

·最后若干轮的随机单轮故障：是指每次仅在故障运算的最后轮中的任意一轮或循环出现故障。

·随机单轮故障：是指每次仅在故障运算的任意一轮或循环出现故障。

故障位置：攻击需要精确控制错误发生的位置，例如将故障引入到某一指定的记忆单元。有些攻击对故障发生位置的要求则比较宽松，例如只将故障引入到某一指定的范围，包括某些寄存器的某些比特（或字节）、某些指令运算结果的某些比特（或字节），这些比特（或字节）包括以下情形。

·单比特故障：是指每次故障加密（或解密）中仅某一个比特出现故障。

·单字节故障：是指每次故障加密（或解密）中仅某一个字节出现故障。

·多比特故障：是指每次故障加密（或解密）中多个比特同时出现故障。

·多字节故障：是指每次故障加密（或解密）中多个字节同时出现故障。

·随机单比特故障：是指每次故障加密（或解密）中仅任意一个比特出现故障。

·随机单字节故障：是指每次故障加密（或解密）中仅任意一个字节出现故障。

·随机多比特故障：是指每次故障加密（或解密）中仅任意几个比特同时出现故障。

·随机多字节故障：是指每次故障加密（或解密）中仅任意几个字节同时出现故障。

故障动作，其包括以下类型。

·BF（bit flip）：使得故障位置的值取反。

·BSR（bit set or reset）：设定故障位置的值为预定值

（攻击者已知该值）。

·RF（random fault）：随机设定故障位置的值（攻击者未知该值）。

此外，故障导入的类型取决于故障导入方法，分为以下两种。

·瞬时故障：每次仅影响特定故障时刻、特定故障位置的特定故障动作。瞬时故障攻击的特点是故障将很快消失，不会影响到密码设备以后的正常工作。攻击者先正确地使用加密设备，得到正确的密文，然后再多次向加密设备中引入故障，得到多个故障密文。攻击者会同时利用正确密文和故障密文进行分析比较，从而发现隐藏在密码设备中的秘密信息。这类干扰的常见例子有辐射炸弹、异常高或低时钟的频率和异常电压等。

·永久故障：每次均影响所有故障时刻、特定故障位置的特定故障动作。永久故障是指向密码设备引入不可恢复的故障。故障一旦被引入，它将永久地发生在以后的加密过程中。向密码设备引入永久故障往往会直接破坏了密码设备，使密码设备丧失了正常的加解密功能。典型的永久性破坏包括冻结一个记忆单元为一固定值和切断一条数据总线等。但是如果攻击者能够在获得密钥的情况下完全复制密码设备，那么基于永久故障的攻击将很有意义。

3 典型分组密码的安全性分析

DES算法和AES算法的破译历程为其他分组密码的差分故障攻击奠定了坚实的基础。后来，KHAZAD算法[8]、FOX算法[11]、SMS4算法[12]、CLEFIA算法[10]以及IDEA算法的安全性都相继被验证具有差分故障攻击的隐患[20]，见表 1。

3.1 差分故障攻击分组密码的基本步骤

从表1得出，差分故障攻击实现环境分为两类：软件模拟和真实环境。

3.1.1 软件模拟环境下攻击的基本步骤

（1）选定一个故障模型，即需要明确给出故障的时间、位置、动作（通常，差分故障攻击的故障模型是：加密算法单轮故障、特定寄存器的随机单字节故障、RF）。

（2）在故障模型下，通过选择明文及相应的正确和故障密文对，对密码算法的执行过程进行数学分析（即差分分析），给出计算子密钥信息的步骤和数学表达式（有时同时可以根据盒的差分分布表来判定计算相应子密钥平均所需要的故障密文对的数目）。

（3）利用软件模拟该故障模型，并按照第（2）步中给出的方法和步骤编写计算机程序进行模拟试验，通过对试验数据进行数学处理和计算，求得若干子密钥，从而根据密码算法中的密钥编排方案求出原始密钥。

3.1.2 实际环境下攻击的基本步骤

（3）根据故障模型，选定特定的故障导入方法，产生特定的故障动作。

表1 典型分组密码的差分故障攻击研究

（4）任选一组明文作为输入，正常执行加密（或解密）运算，观察获得正确密文；将上述明文分别再次作为输入，异常执行加密（或解密）运算（即在加密运算或密钥编排过程中导入一次故障），分别观察获得故障密文。

（5）根据正确明文和故障密文判断哪些是符合故障模型的（即有效的）正确密文和故障密文对，并按照故障模型中的故障时刻和位置，对这些有效的正确密文和故障密文进行分类。

（6）对每一种分类数据进行数学处理和计算，求得若干子密钥的信息；根据全部分类所求得的子密钥信息和密钥编排方案求出原始密钥。

3.2 攻击评价标准

一个“好”的差分故障攻击方法需要通过以下3个方面来衡量。

· “弱”的基本假设（由弱到强排列）：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击、选择密钥攻击。

· “弱”的故障模型：容易实施、成本低。

· 攻击代价小：故障数少、计算量少、存储量少。

4 未来的研究方向

在差分故障攻击分组密码及其防御技术方面，我们认为以下内容是需要进一步研究的。

· 具体芯片平台上模拟仿真试验研究：故障攻击的实现包含有两种方式，可以在硬件上通过激光、微探针等方式实现，或者通过计算机软件模拟技术进行仿真。现阶段，国内的研究工作主要集中于计算机软件模拟仿真层面，还没有在具体的芯片平台上进行实验。

· 差分故障攻击分组密码的效率提高：国内外目前使用的故障攻击的技术均采用瞬时故障导入，攻击时要保证故障的导入精确位置，否则故障导入次数越多，攻击的代价越大。因此，未来方向是：如何通过改变故障诱导的位置，在故障诱导的实施难度相同的情况下，针对分组算法提出新的攻击方法，并降低攻击的代价。

· 其他故障攻击方法的研究：差分故障攻击是一种简单有效的密码分析方法，因此不仅成功地用于分析大量的分组密码算法，如 DES、3-DES、IDEA和AES等，还可以应用在一些广泛使用的算法结构，如SP型结构和Feistel型结构等。然而，作为故障攻击的其他方法，例如无效故障攻击和碰撞故障攻击等，目前国内外研究成果较少。因此，有必要对其他故障攻击方法的基本假设、故障模型及攻击方法展开进一步的研究。

·分组密码抗故障攻击的设计与实现方法：目前国内外抗故障攻击的技术主要有基于复用和基于码的技术。为了防御故障攻击，密码芯片须在输出结果前进行自检，但已有的做法执行效率很低或者其编码器可能会遭到破坏，因此需要研究效率更高、安全性更佳的算法故障自检技术。

5 结束语

综上，在差分故障攻击方法中，攻击者可以利用密码系统中泄漏出来的故障信息来破译密码算法的密钥，大大提高了攻击的速度，并降低了攻击的计算量。在实际应用中，随着越来越多的分组密码广泛应用于诸如智能卡、移动设备等安全性较差的环境中，系统的关键信息泄露在所难免，这些重要信息的泄露对于一个密码系统来说是一个极其危险的攻击，因为它意味着系统将彻底失去安全性保证。因此，如何利用旁路攻击技术，特别是差分故障分析分组密码的安全性，是一项非常必要且有现实意义的研究课题。未来的研究工作应围绕上述研究点开展，力求在理论和实践上有所突破，将该领域的研究工作不断推向前进。

1 Boneh D,DeMillo R A,Lipton R J.On the importance of checking cryptographic protocols for faults.Advances in Cryptology—EUROCRYPT,Berlin,Springer-Verlag,1997,1233:37～51

2 Biham E,Shamir A.Differential fault analysis of secret key cryptosystems.Advances in Cryptology-CRYPTO’97,Berlin,Springer-Verlag,1997,1294:513～525

3 Moradi A,Shalmani M T M,Salmasizadeh M.A generalized method of differential fault attack against AES cryptosystem.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2006,4249:91～100

4 Blomer J,Seifert J P.Fault based cryptanalysis of the advanced encryption standard (AES).Financial Cryptography—FC,LNCS,Berlin,Springer-Verlag,2003,2742:162～181

5 Giraud C.DFA on AES.Advanced Encryption Standard 4-AES 2004,Springer-Verlag,2005,3373:27～41

6 Chen C N,Yen S M.Differential fault analysis on AES key schedule and some countermeasures.In:Proceedings of the Australasian Conference on Information Security and Privacy-ACISP,Springer-Verlag,2003,2727:118～129

7 Dusart P,Letourneux G,Vivolo O.Differential fault analysis on AES.Applied Cryptography and Network Security,Berlin,Springer-Verlag,2003,2846:293～306

8 Gilles P,Quisquater J J.A differential fault attack technique againstSPN structures,with application to the AES and KHAZAD.Cryptographic Hardware and Embedded Systems-CHES,2003,2779:77～88

9 Amir M,Mohammad T M S,Mahmoud S.A generalized method of differential fault attack against AES cryptosystem.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2003,4249:91～100

10 Chen H,Wu W,Feng D.Differential fault analysis on CLEFIA.International Conferenceon Information and Communication Security-ICICS,Berlin,Springer-Verlag,2007,4861:284～295

11 Breveglieri L,Koren I,Maistri P.A fault attack against the FOX cipher family.Fault Diagnosis and Tolerance in Cryptography-FDTC,Berlin,Springer-Verlag,2006,4236:98～105

12 张蕾，吴文玲.SMS4密码算法的差分故障攻击.计算机学报，2006，29（9）：1594～1600

13 Hoch J J,ShamirA.Faultanalysis of stream ciphers.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2004,3156:240～253

14 Biham E,Granboulan L,Nguyên P Q.Impossible fault analysis of RC4 and differential fault analysis of RC4.Fast Software Encryption-FSE 2005,Berlin,Springer-Verlag,2005,3557:359～367

15 Biehl I,Meyer B,Müller V.Differential fault analysiss on elliptic curve cryptosystems.International Crytology Conference-CRYPTO 2000,Santa Barbara,California,USA,Berlin,Springer-Verlag,2000,1880:131～146

16 Jonathan J H,Shamir A.Fault analysis of stream ciphers.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2004,3156:240～253

17 Lin I C,Chang C C.Security enhancement for digital signature schemes with fault tolerance in RSA.Information Sciences,2007,177(19):4031～4039

18 Hemme L.A differential fault analysis against early rounds of(Triple-)DES.Cryptographic Hardware and Embedded Systems-CHES,Berlin,Springer-Verlag,2004,3156:254～267

19 Blomer J,Krummel V.Fault base on collision attack on AES.Fault Diagnosis and Tolerance in Cryptography-FDTC 2006,Berlin,Springer-Verlag,2006,4236:106～120

20 Clavier C,Gierlichs B,Verbauwhede I.Fault analysis study of IDEA.Topics in Cryptology-CT-RSA,2008,4964:274～287