EMV 應用密文的差分錯誤注入分析

彭乾，李增局，史汝輝

（國家金融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

A

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

2016-01-14；

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

國家科技重大專項基金資助項目（No.2014ZX01032401）

彭乾（1982-），男，蒙古族，內蒙赤峰人，碩士，國家金融IC卡安全檢測中心工程師，主要研究方向為金融IC卡、金融Pos機安全技術。

李增局（1982-），男，山東莘縣人，碩士，國家金融IC卡安全檢測中心工程師，主要研究方向為側信道、錯誤注入、密碼學工程實現以及借貸記交易安全性等。

史汝輝（1985-），男，山東煙臺人，碩士，國家金融IC卡安全檢測中心工程師，主要研究方向為側信道、錯誤注入、密碼學工程實現以及借貸記交易安全性等。