PCI Watch

Tracking changes across the Payment Card Industry

Security Position Statement: EMV® Use of 2-key Triple DES

Security Advisories

EMV-SWG-NF05r3 EMV use of 2-key Triple DES Updated Position Statement September 2016 This note provides an EMVCo position statement on 2-key Triple DES that updates EMVSWG-N552r3 (May 2006). The primary updates relate to an impact assessment of recent cryptanalyses of 2-key Triple DES, the security of the ANSI Retail MAC and side-channel attacks. Introduction and background 2-key Triple DES is an 8-byte block cipher using a 16-byte key (K1,K2) C = EK1[DK2[EK1[P]]] Which due to DES parity bits has a nominal strength of 112 bits. N552r3 focused on the key recovery attack of van Oorschot and Wiener [vOW] which describes how, with T=2t plaintext ciphertext pairs encrypted using the 2-key Triple DES block cipher under a single key, an attacker can recover the key with effort 2(120-t). Thus if an attacker would obtain 240 plaintext ciphertext pairs then the effective strength of the cipher is reduced from 112 bits to 80 bits. The headline of N552r3 was that with EMV payments an attacker would not be able to obtain such a quantity of plaintext-ciphertext pairs because either the plaintext is simply not available in such quantities (e.g. PINs) or the use of session keys prevents it. Recent paper by Mitchell A recent paper by Mitchell [Mi] showed that the vOW attack can operate across multiple keys to find one of the keys with the only mitigation of using session keys being that the broken key is a session key not a long-life key. The adapted attack works as follows: For plaintext-ciphertext pairs (P,C), define A=EK1[P] and B= DK1[C] So that P A B C EK1 DK2 EK1 Suppose the attacker has precisely one plaintext-ciphertext pair (P, C) and they guess an arbitrary value for A. The correctness of this guess can be checked by decrypting A under all 256 bit keys K1 and seeing if any key yields P and if it does then using K1 to decrypt C to obtain B and then doing another exhaustive key search to determine K2. This effort is 256 + 256 but reduces to 256 when the DES complementation property is exploited. Although the chances of guessing the correct A is only 2-64, this increases to T*2-64 = 2(t-64) if the attacker has T=2t pairs (P,C) and this is irrespective of whether the same key is used. Hence the attacker will expect to try only 2(64-t) values of A before succeeding in finding a

2016

http://www.emvco.com/.

EMV-SWG-NF05r3 single A that is valid for one of the 2t pairs. Thus the overall effort is expected to be 256 * 2(64-t) = 2(120-t). Note that the essential thing here is checking whether guessed values for A are valid. This checking may still be feasible if only a partial plaintext is known (e.g. ISO-0 PIN blocks) or if rather than a plaintext block the input is known data that will be MAC’d according to the ANSI Retail MAC. Consequences for EMV:

  • The EMV PIN Change command uses a dedicated secure messaging session key and even if an attacker could gather together sufficient known plaintext-ciphertext pairs for the attack to work the attacker would only get the key that encrypted a PIN that was already known to them and not used for anything else.
  • For online PIN encryption the consequences are potentially more of a concern. But again the attacker has the challenge of gathering sufficient encrypted PIN blocks and finding a system that does not use unique keys per transaction.
  • EMV Application Cryptograms use 2-Key Triple DES but the classical attacks on the ANSI Retail MAC are more relevant (see next). ANSI Retail MAC attacks EMV Triple DES Application Cryptograms use the ANSI Retail MAC (ARM) which is a 2-key Triple DES hybrid MAC. ARM calculates a MAC by processing data in DESCBC mode under K1 and then applies 2-key Triple DES to the final block (see Figure 1). It has been known for many years (see [BP]) that due to the ARM structure and because DES and 2-key Triple DES are only 64-bit block ciphers, that a key recovery attack is expected to be possible given roughly 232 message-MAC pairs generated using the same key and only 257 effort. This is a stronger result than vOW even after it has been adapted by Mitchell. For example, if an attacker would have 232 message-MAC pairs generated using different keys so that the classical ARM attack is not possible then the Mitchell attack would require 288 bits of effort and this is not feasible. If an attacker would have 260 message-MAC pairs generated using different keys then the Mitchell attack would require 260 bits of effort, but whilst this effort is more feasible, gathering the 260 message-MAC pairs is not feasible and a broken session key could not be used by the attacker anyway so long as the issuing bank checks that the card’s Application Transaction Counter is not old. Consequences:
  • EMV Application Cryptograms use ARM but because they use session keys they are not vulnerable to ARM attacks.
  • The use of session keys means that the vOW attack as extended by Mitchell only breaks old MAC keys (but the attack is anyway infeasible). Combined Side-Channel and Brute-Force attacks (an implementation attack) 2016 http://www.emvco.com/. EMV-SWG-NF05r3 In [FeTh14], Feix and Thiebeauld show that a non-invasive key recovery attack on the ARM structure is possible. In order for the attack to work, it requires that ARM uses a static key pair (K1,K2) where K1 is used in the DESCBC part and K2 in the final 2-key Triple DES block The attack requires physical access (few hours) to the card in order to perform a sidechannel attack to expose an intermediate DES output value. Next, an exhaustive search will recover first key K1 and next K2. During normal operation, the intermediate DES values (C1, C2, …) are not outputted, only the final TDES calculation (MAC) and the input values (P1, P2, …). In the EMV Application Cryptogram, the input is 40 bytes of which 29 bytes are controlled by terminal/attacker and 11 bytes controlled by card (known by terminal/attacker). The attack set P1 to a constant value, while P2(i) is chosen randomly in each step i. The sidechannel will target the first ciphertext (C1) which is XORed with P2(i), The attack retrieves the value C1 XOR P2(i) via a side-channel attack. This step requires a few hours. Once C1 is recovered a brute-force attack is used to recover K1, and a second brute-force to recover K2. A single DES key can be obtained by brute-force with modern computers, dedicated hardware or cloud services as has been demonstrated by recent publications. The cost is now less than 10 thousand dollars and keys can be found in less than a day. Consequences:
  • An implementation attack requires physical access to the card and can be performed in less than a day.
  • EMV Application Cryptograms use ARM and should use session keys in order not to be vulnerable to this attack.
  • It is part of normal security evaluation to ensure defence against these attacks. Figure 1 ANSI Retail MAC 2016 http://www.emvco.com/. EMV-SWG-NF05r3 Combined Downgrade and Brute-Force attacks an (implementation attack) Note that a straightforward semi-invasive fault injection is also possible. The first part of the attack is on the final TDES calculation to downgrade it to a single DES computation with K1. Next, a brute-force attack is used to recover K1, and a second brute-force to recover K2. Consequences:
  • An implementation attack requires physical access to the card and is semi-invasive. The attack works for each instance of (K1,K2).
  • It is part of normal security evaluation to check defence against these attacks. Conclusions
  • A semi-invasive attack requires the use of a Lost & Stolen card and this limits the exploitation time to the period between being lost or stolen and reporting it.
  • HSMs should not be susceptible to these kinds of attacks.
  • The Mitchell paper shows that the vOW attack applies irrespective of key change however the consequences of the attack are limited to a single session key if session keys are used.

References

BvO B. Preneel and P. C. van Oorschot, A key recovery attack on the ANSI X9.19 retail MAC. Electronics Letters, 32:1568-1569, 1996. FeTh14 B. Feix and H. Thiebeauld, Defeating ISO9797-1 MAC Algo 3 by Combining Side-Channel and Brute Force Techniques,, IACR Cryptology ePrint Archive 2014/702. Mi C. Mitchell, On the security of 2-key Triple DES arXiv:1602.06229v1 [cs.CR], vOW P. C. van Oorschot and M. J. Wiener, A known plaintext attack on two-key triple encryption. In Advances in Cryptology: EUROCRYPT '90, number 473 in Lecture Notes in Computer Science, pages 318-325. Springer-Verlag, Berlin, 1991.

2016

http://www.emvco.com/.