EMV 应用密文的差分错误注入分析

2016-09-23彭乾李增局史汝辉

网络与信息安全学报 2016年4期

关键词：密文字节密钥

彭乾，李增局，史汝辉

（国家金融IC卡安全检测中心，北京 100070）

EMV 应用密文的差分错误注入分析

彭乾，李增局，史汝辉

（国家金融IC卡安全检测中心，北京 100070）

研究了EMV规范中应用密文的生成过程，发现过程密钥存在部分冗余位，结合DES算法S盒的压缩特性，利用基于碰撞的safe-error攻击实现对EMV规范中应用密文主密钥的破解。提出了针对应用密文生成的差分错误注入的物理模型和实施步骤，深入分析了影响攻击效果的2个关键因素（密钥错误产生概率和碰撞概率），尤其是对不同错误模型进行了理论数据分析。实验分析表明，实际攻击中，只要不同密钥的碰撞概率差大于0.003 5即可区分，结果表明，过程密钥的冗余位提高了碰撞概率，有利于对正确密钥的区分。最后，针对该攻击方法，提出了几种防御方案。

EMV；应用密文；碰撞攻击；safe-error

1　引言

EMV规范是由国际三大信用卡组织Europay、MasterCard、Visa联合制定的，其中，金融集成电路卡支付标准是目前国际上绝大多数银行卡使用的标准。我国的PBOC3.0规范也是基于EMV规范建立的，并根据特定需求，在EMV规范框架上进行了细微的调整。

在EMV规范中，标识金融IC卡不可抵赖性有对称密钥体系和非对称密钥体系。对称密钥体系主要是完成金融IC卡的联机交易，基于该对称密钥的应用密文和MAC等机制保证了IC卡交易的不可抵赖性和可信性。非对称密钥体系主要是基于三级密钥证书体系保证金融 IC卡在脱机交易中的可信性和不可抵赖性。如果能破解金融IC卡的对称密钥，则完成了卡片复制，甚至进行部分发卡行数据的改写，完成伪卡交易。

目前，EMV规范［1］中主要用对称密码算法3DES，密钥长度为128位，实际有效长度为112位。3DES的差分错误注入分析在1997年已经被提出。经过多年的发展，有很多关于3DES的差分错误注入分析模型［2～5］。随着错误注入的发展，针对EMV规范中RSA签名算法的攻击方式成果也很多。Coron等［6］提出了针对EMV规范签名机制的攻击。但是，到目前为止，还没有针对EMV规范中3DES的分析，主要原因是在EMV规范中使用的加密算法协议，明密文不断变化，无法对同一明密文进行差分错误注入分析。因此，本文首先提出了针对EMV规范中3DES的差分错误注入的分析。

2　背景知识

2.1EMV应用密文

EMV规范中对应用密文［1］的定义为：在交易过程中，由IC卡将相关交易数据（如交易金额、交易货币代码、终端国家代码、终端验证结果、交易日期、交易类型、随机数、卡片应用交互特征以及卡片验证结果等）经3DES（CBC模式、双倍长密钥）加密生成的密文。终端收到卡片应用密文，直接送到后台，后台可以将应用密文的有效性返回给终端，终端发送给卡片，确定该应用密文是否有效。

应用密文生成时使用的3DES加密密钥为过程密钥，由IC卡使用应用密文主密钥对交易计数器（ATC）进行3DES加密生成。ATC为2个字节长度，初始为1，每笔交易后自动加1，上限为65 535，因此过程密钥为一次一密，每笔交易都不同。应用密文的过程密钥产生过程如下。

算法1过程密钥生成算法

如果用双长度DES密钥生成，步骤如下。

1）生成过程密钥的卡片密钥为：数据加密3DES密钥A和B（ENC UDK）。

2）将两字节的ATC右对齐，前面补6个字节00，使用数据加密3DES密钥A和B加密生成过程密钥KA。

3）将两字节的ATC取反后右对齐，前面补6个字节00，使用数据加密3DES密钥A和B加密生成过程密钥KB。

上述1）中使用的DES密钥A和B是每张卡片唯一的应用密文主密钥。

应用密文产生过程如下。

算法2应用密文生成算法

1）将交易数据块分成8字节一组：D1、D2、D3…。

2）如果最后一块数据块的长度为8个字节，后面补8个字节数据块：80 00 00 00 00 00 00 00。

如果最后一块数据块的长度小于8个字节，后面补一个字节80，如果仍然不够8个字节，补00直到8个字节。

3）使用算法 1产生的过程密钥用对称密钥算法生成应用密文。

图1是使用过程密钥KA和KB生成应用密文的流程。其中，I=输入；D=数据块；DEA（a）=数据加密算法（加密模式）；KA=密钥A；DEA（d）=数据加密算法（加密模式）；KB=密钥B；O=输出；+=异或。

2.2碰撞攻击

碰撞攻击算法最早是出现在散列算法中［7］。碰撞攻击要求算法的映射函数是多对一映射，只有满足该条件才有可能产生碰撞。而 DES算法Sbox映射是64输入对应16输出，因此，它具有碰撞攻击的可行性。随着功耗分析、差分错误分析的提出，研究者逐渐关注DES的碰撞性质，并利用碰撞性质得到密钥［3，4］。在功耗分析技术中，攻击者主要利用碰撞性质及其功耗特征来确定碰撞行为是否发生。如果发生了碰撞，则可以通过建立方程或增加密钥约束条件的方法缩小 DES密钥的搜索空间。

碰撞攻击比差分功耗分析或相关性功耗分析等方法普适性要差一些，主要原因有3点：1）较难建立合适的碰撞模型；2）由于噪声的存在，使通过功耗分析确定碰撞发生有一定难度，而差分错误分析、错误注入发生概率的问题，使碰撞分析难度加大；3）通过碰撞直接得到密钥的难度很大。

2.3Safe-error

Safe-error攻击是差分错误分析发展过程中最简便易行的一种攻击手段。Safe-error攻击可以分为操作性safe-error［8］和数据性safe-error［9］。最初，RSA算法为了防御简单功耗分析和时间分析，会在实现过程中插入冗余运算。Safe-error不需要关注错误的结果，而只是通过判断最终的结果正确与否来获得信息。如果冗余操作与密钥位有关系，比如密钥位为 1，则不加入冗余操作；而密钥位为 0，则加入冗余操作，通过对操作注入错误，比较最终结果，如果最终结果出现错误，则操作不是冗余的，得到的密钥位为 1；反之，则操作是冗余的，得到密钥位为 0。通过结果的正确与否，即可以判断密钥信息。这种攻击过程属于操作性的safe-error。

在DES运算过程中，有一种错误模型，无论其原始值是多少，能将DES任意密钥比特置为1。因此，针对某个DES密钥比特进行操作，如果加密结果正确，说明DES原始密钥比特为1，反之，则说明DES该比特为0。依次对不同密钥进行这种实验，就可以逐个比特得到DES密钥。这种方法就是属于数据性safe-error。

3　攻击原理

3.1错误模型及碰撞位置

根据错误注入发生错误的模型分类，可分为固定值错误、固定翻转错误、随机翻转错误、部分比特固定错误等类型。本文研究3种错误模型：目标数据只发生0-＞1翻转错误、目标数据只发生1-＞0翻转错误、目标数据发生随机翻转错误。

本文假设目标数据的比特位之间是相互独立的，且每个比特产生错误的概率是相同的。目标数据的多个比特的错误概率可以使用二项分布的模型来计算。

本文采用碰撞攻击的方法，DES运算中的Sbox变换为6进4出的非线性运算，因此，存在碰撞的可能性。Sbox变换式为

本文研究对象为式（1）中的k，对k注入错误得到k’。因此，对于明文输入datain，从0～63遍历，计算每一个明文分别对应k和k’的Sboxout的值，如果两者相等，则存在碰撞。

攻击的目标操作为DES或3DES运算的最后一轮的Sbox运算，3.2节会详细分析选择最后一轮作为攻击目标的原因。

图1　用双长度DES密钥生成应用密文

3.2攻击模型

在生成应用密文过程密钥的过程中，如果应用密文主密钥加密ATC生成的密文结果（即应用密文过程密钥）每个字节的最低位（奇偶校验位）产生错误，卡片仍然能生成正确的应用密文，因为对应的这些奇偶校验位作为密钥时不参与DES加密运算，不会影响3DES的结果，定义为冗余位。因此，根据银行后台对应用密文校验的结果，可以判断应用密文是否正确，从而形成safe-error攻击。本节将详细分析过程密钥的8个冗余位带来的碰撞和 Sbox自身碰撞的性质是否有利于破解卡片的应用密文主密钥。

DES/3DES最后一轮的运算如图2所示。其中，L和R分别是DES的左寄存器和右寄存器，F是DES和S盒置换，P是32位置换表，IP-1是DES的最后置换。

图2　DES/3DES最后两轮运算流程

根据DES运算的流程可知，主密钥加密结果中有 8位冗余位，即应用密文过程密钥的 8位校验位，分别为第8、16、24、32、40、48、56、64位，这些比特不参与应用密文的加密运算。DES的末尾逆置如图3所示，该置换是一个一一映射的置换，通过数据变化增强了数据的混淆程序。

图3　IP-1置换

根据图2的算法流程可知，第16轮的L||R经过了IP-1置换得到最终结果，因此，密钥的8为校验位在IP-1置换前分别为第32、31、30、29、28、27、26、25位，即为第16轮L寄存器结果的最后一个字节。图4是DES每轮中使用的置换，通过置换和Sbox的非线性效应，达到了混淆和置乱的目的，使密码算法具有雪崩效应。

图4　P置换

根据图2的算法流程可知，第16轮的L寄存器结果是由Sbox输出经P置换得到，因此，L寄存器的最后一个字节分别对应 Sbox输出的第19、13、30、6、22、11、4、25位，即Sbox5的第3位、Sbox4的第1位、Sbox8的第2位、Sbox2的第2位、Sbox6的第2位、Sbox3的第3位、Sbox1的第4位、Sbox7的第1位。

3.1节中的模型对一般的碰撞定义为

在增加了8位冗余位之后，碰撞的定义需要将冗余位考虑进去，对于 Sbox1，冗余位为第 4位，因此只需要考虑前3位，新的碰撞定义为

对比式（2）、式（3）可知，式（3）的解包含了式（2）的解。因此，使用3.1节的攻击模型，同时引入8位冗余位的信息，理论上可以提高Sbox碰撞的概率，增加密钥的区分度。其他Sbox的碰撞方程变化原理与Sbox1类似。

考虑到应用过程密钥产生时使用 ATC，对3DES进行加密，攻击3DES第48轮时，可以认为每个Sbox的输入明文具有充分的统计随机性，因此，对于DES Sbox的2个密钥k和k'的碰撞概率，本文定义为数据datain从0～63遍历，然后观察式（3）成立的个数。如果个数越多，说明碰撞概率越大。

由于应用密文过程生成过程为双倍长密钥的3DES加密，使用3.1节中的攻击模型只能对3DES的最后一轮进行攻击，因此只能攻击3DES的第一个密钥，第二个密钥需要暴力破解。对单个DES密钥的破解不在本文的讨论范围内。

由于应用密文的产生过程是受ATC控制的，正常交易ATC是2个字节长度，即最大值为65 536。由2.1节描述可知，应用密文产生过程中两部分过程密钥存在联系，一次交易过程中产生两次应用密文和一次外部认证，其中一次应用密文和一次外部认证的DES运算结果是否正确可以得知。综上，使用应用密文主密钥进行的有效DES运算约130 000（65 536×2）次，并且这些运算的结果是否正确都可得知。考虑到实际中错误注入会存在概率，在有限执行次数中需要一定概率差值才能区分不同的密钥。

3.3影响攻击的关键因素

在有限次运算中，如果在对Sbox子密钥进行错误注入后，不同的Sbox子密钥产生碰撞概率的差异足够大，那么就可以通过密文的正确率来区分不同的子密钥。设为错误注入导致子密钥产生错误的概率，为因子密钥发生错误而产生碰撞的概率，则密文的正确率为

因此，影响应用密文正确率的因素有2个：一是密钥错误产生概率二是碰撞概率

3.3.1密钥错误产生概率

对于错误发生概率，假设单比特错误发生概率为P，在0-＞1翻转错误模型下，设6比特Sbox子密钥中0的比特个数为m，则二阶近似模型的错误发生概率为

以子密钥数据为0x1为例，m=5，则2个比特发生错误概率为，不发生错误的概率为发生一个比特错误概率为

实际中错误发生概率较小时，如 P=0.2，在0-＞1翻转模型下，若m＜3，不可能发生3比特以上错误；若m=3，发生3比特错误概率比发生2个比特错误概率小很多；若m=4，发生3比特以上错误概率（0.027）比发生2比特错误概率小很多；若m=5，发生3比特以上错误概率（0.062 1）比发生2个比特错误概率（0.205）小很多；若m=6，则发生3个比特以上错误概率（0.1）比发生2个比特错误概率（0.246）小很多。并且随着P减小，2比特错误概率要高于3比特以上错误发生概率。

对于0-＞1的错误模型和1-＞0的错误模型，不同密钥数据的错误概率是不同的，而对于随机错误模型来说，密钥数据的错误概率是相同的。例如b000001和b111110对于0-＞1和1-＞0的错误模型的错误概率是完全不同的，但是对于随机错误模型则是相同的。

3.3.2碰撞概率

计算Sbox1的碰撞概率，根据式（3），其他Sbox的碰撞概率表都参考实现。这里，首先计算Sbox1的不同密钥碰撞概率表。碰撞概率计算方式根据式（3）进行，使用算法是算法3。

根据算法3计算Sbox1的碰撞概率表，错误模型采用2.1节中描述的3种模型。

假设Sbox1密钥每个比特独立同分布，将错误模型细分为一阶碰撞、二阶碰撞和高阶碰撞。一阶碰撞为密钥key翻转任意1比特产生的碰撞。二阶碰撞为翻转任意2比特产生的碰撞。高阶碰撞则为翻转任意3比特以上的碰撞。

由于DES Sbox具有良好的非线性性质，输入改变任1比特，输出至少改变2个比特，因此，由式（3）可知，不存在一阶碰撞的可能性。而由3.3.1节分析可知，高阶碰撞的错误概率要远小于二阶碰撞的错误概率，因此只研究二阶碰撞。

由于随机错误模型包含 0-＞1错误模型和1-＞0的错误模型，因此将二阶随机模型重新定义为：翻转的2比特中0-＞1和1-＞0同时发生。

表1为Sbox1的二阶碰撞概率。由表1可知，0-＞1错误模型和 1-＞0的错误模型对于互补的数据碰撞概率是相同的；随机翻转的碰撞概率较其他模型变化较小，这主要是由于随机模型的二阶翻转变化较少。

表1　Sbox1二阶碰撞概率

4　仿真实验

4.1仿真环境

本仿真实验平台为PC一台，配置如下。

操作系统Windows XP Professional

CPUIntel Pentium（双核2.7 G）

内存2 GB

仿真工具Microsoft Visual Studio 2005

编程语言C

4.2实验步骤

参数说明：N为DES随机密钥（K）的个数，K_R16为DES第16轮的子密钥，DES_15（）为DES的前15轮运算，Sbox（）为DES的Sbox置换运算。

1）i=0；

2）判断i是否小于N，若是，执行3），否则执行12）；

3）ATC=1，生成DES算法64 bit随机密钥K；

4）使用KEY生成DES16轮子密钥K_R16；

5）以P1、P2、P3、P4、P5的概率对K_R16进行错误注入（采用 A、B、C 3种模型）得到K_R16'；

6）判断ATC是否小于65 536，若是执行7），否则执行11）；

7）计算R_15=DES_15（K，ATC），

Sboxout_16=Sbox（R_15，K_R16），

Sboxout_16'=Sbox（R_15，K_R16'）；

8）分别在考虑冗余位和不考虑冗余位的情况下，判断Sboxout_16和Sboxout_16'是否碰撞，若是，执行9），否则执行10）；

9）将发生碰撞所对应 Sbox子密钥计数器加1；

10）ATC加1，执行6）；

11）将KEY_R16对应的8个Sbox的密钥计数器加1，i加1，执行2）；

12）计算碰撞发生的概率。

4.3仿真结果分析

图 7为 Sbox1在 0-＞1模型下的正确率对比，虚线为考虑冗余位的概率曲线，实线为未考虑冗余位，即仅 Sbox自身性质导致的。由图可知，虚实线在相同的P的情况下，趋势一致。但是随着P的增大，虚线与实线的差距越来越大，说明随着P的增大，冗余位导致的影响越来越大。

图5　0-＞1翻转模型下不同错误概率的Sbox1正确率

图6　随机翻转模型下不同错误概率的Sbox1正确率

图7　0-＞1模型下的Sbox1正确率对比

5　防御方案

1）反向校验

根据应用密文攻击原理分析，本文提出了一种简单有效的防御策略：应用密文过程密钥生成后，进行反向运算（3DES解密运算），然后比较验证加密的输入与解密的输出是否一致，如果一致，说明未受到错误注入，输出结果；否则，触发警报，停止运算，清除敏感数据。使用反向校验措施，可以校验8个冗余比特是否正确，从而降低碰撞概率。

2）使用替代算法

由2.1节的分析可知，冗余位是应用密文生成过程中的弱点，提高了碰撞的概率，因此可以考虑让冗余位参与到实际的运算中，冗余位的改变会使最后的应用密文改变，那么也可以避免该漏洞。从现行 EMV规范看，使用 AES或者SMS4（PBOC 3.0）算法，可以避免类似的碰撞攻击。

3）数据校验算法

在数字电路设计中，可以使用CRC等算法对数据过程结果进行实时保护计算，保证数据运算正确性，这样冗余的比特可以通过类似校验算法进行保护，因此可以抵抗本文提出的攻击方法。

6　结束语

本文通过研究发现，在EMV规范中3DES算法产生应用密文的过程中，存在部分过程密钥的冗余。攻击者可以利用这种冗余产生碰撞性攻击，并利用safe-error方法判断碰撞攻击是否存在。通过统计结果的正确性，可以获取很多比特的密钥信息，从而对卡片的密钥信息造成损害。基于这种攻击方法的原理，本文给出了几种建议的防御方案，以提高卡片防御类似攻击手段的能力。

［1］EMV. Integrated circuit card specifications for payment systems，book 2： security and key management，version4.2［EB/OL］. http：//www.emvco.com.

［2］BIHAM E，SHAMIR A. Differential fault analysis of secret key cryptosystems［J］. Lncs，1999，1294：513-525.

［3］SCHRAMM K，WOLLINGER T，PAAR C. A new class of collision attacks and its application to DES［C］//International Conference Fast Software Encryption（FSE）. c2003： 206-222.

［4］RIVAIN M. Differential fault analysis on DES middle rounds［J］. Lecture Notes in Computer Science，2009，5747： 457-469.

［5］LEE C. A new approach of differential fault analysis on block ciphers with S-box［J］. International Journal on Information，2013（16）： 1915-1928.

［6］CORON J S，NACCACHE D，TIBOUCHI M. Fault attacks against EMV signatures［C］//International Conference Topics in Cryptology. c2010： 208-220.

［7］CONTINI S，YIN Y L. Forgery and partial key-recovery attacks on HMAC and NMAC using hash collisions［M］//Advances in Cryptology. Berlin Heidelberg： Springer，2006：37-53.

［8］YEN S M，KIM S，LIM S，et al. A countermeasure against one physical cryptanalysis may benefit another attack［C］//International Conference Information Security and Cryptology. c2002： 414-427.

［9］YEN S M，JOYE M. Checking before output may not be enough against fault-based cryptanalysis［J］. IEEE Transactions on Computers，2002，49（9）： 967-97.

Differential fault analysis on EMV application cryptogram

PENG Qian，LI Zeng-ju，SHI Ru-hui

（National Financial IC Card Test Center，Beijing 100070，China）

The process of application cryptogram in EMV was researched and dummy bits in session key were found. Based on the session key's dummy bits and compressive property of DES's Sbox，much information of the application cryptogram master key was got by using safe-error attack. The differential fault attack model and steps to implement the attack were proposed，two key factors（the probability of generating wrong key and the probability of collision happening）affecting an attacking result were analyzed. The theoretical result and simulation of the attack were given. The experiment results show that the two keys could be distinguished in a real attacking when the difference of two key's collision probability was bigger than 0.003 5. The dummy bits in the key will increase the difference and make distinguishing easier. Finally，several countermeasures against the attack were proposed.

EMV，application cryptogram，collision attack，safe-error

National Science and Technology Major Project（No.2014ZX01032401）

TP309.7

10.11959/j.issn.2096-109x.2016.00044

2016-01-14；

2016-03-27。通信作者：李增局，liecas@sina.com

国家科技重大专项基金资助项目（No.2014ZX01032401）