Security Position Statement: EMV® and use of SHA-1 (update)

EMV-SWG-NF93r3 EMVCo Position Statement on EMV and use of SHA-1 (update) For EMVCo Advisors March 2017 Introduction and Conclusions This position statement provides an update for the EMVCo Advisors in light of the recent research that has found a collision in SHA-1 [1]. For more details about this research see https://shattered.io and https://www.theregister.co.uk/2017/02/23/google_first_sha1_collision/. Its important to note that this poses no threat to the security of EMV. The consequences for EMV of it being possible to find collisions in SHA-1 were analysed over a decade ago [2] and the conclusions remain valid. Such a collision has been anticipated for many years and builds on previous well-known work by researchers such as Professor Xiaoyun Wang and Marc Stevens [3] and [4]. However the actual demonstration of a collision in SHA-1 does represent a significant academic landmark and any legacy use of SHA-1 may be subject to public criticism. It should be noted that new EMV specifications such as 2nd Gen and 3DS 2.0 will use SHA-2 and SHA-3 rather than SHA-1.

Background

SHA-1 is a hash algorithm first standardized in 1995 in NIST FIPS 180-2 and subsequently in ISO/IEC 10118-3 and that generates from an arbitrary length input message a 160-bit hash result. The internals of SHA-1 comprise 80 iterated steps in order to ensure that it is infeasible to

• find collisions i.e. any two input strings m1, m2 with SHA-1(m1)=SHA-1(m2);
• find pre-images i.e. given a 160-bit value h, find m with SHA-1(m) = h;
• find 2nd pre-images i.e. given string m1, find m2 with SHA-1(m1)=SHA-1(m2). The attack techniques published in 2005 [3] showed that a SHA-1 collision might be found with complexity less than 269 hash operations1. This was the first theoretical attack on the full 80-step SHA-1 with complexity less than the 280 theoretical bound. This bound equals 2 raised to half the bitlength of the hash, and is governed by the length of the hash and the Birthday Paradox2. No significant progress has been made with respect to pre-image and 2nd pre-image attacks on SHA1 and these are still considered computationally infeasible problems. 1 soon thereafter reduced to 266 and subsequently to 263 2 wherein it is expected to find two balls in the same box when randomly throwing m balls into m2 boxes, or to find two people with the same birthday if 23 people gather in the same room. Business Associate Access Only: do not distribute. This document contains proprietary and confidential information of EMVCo. LLC. Copyright 2017 © EMVCo. LLC. All rights reserved Recent demonstration of a SHA-1 collision On 23rd February 2017, CWI Amsterdam and Google announced that they had performed a collision attack against SHA-1, and published two dissimilar PDF files which produce the same SHA-1 hash as proof of concept. The attack required about 263 SHA-1 evaluations which is about 100,000 times less than would be required for a 280 brute-force birthday paradox collision. This attack took the equivalent processing power of 6,500 years of single-CPU computations or 110 years of single-GPU computations. According to the authors this is similar computing power to that needed for a 768-bit factorization. See https://shattered.io/ for more information. Relevance to EMV EMV uses SHA-1 based digital signatures for public key certificates and for the offline CAM (SDA/DDA/CDA) signatures. The EMV signature algorithm is ISO/IEC 9796-2 which is a signature algorithm with message recovery. These signatures are of the form (mr || SHA(m))d || mnr, where d is the private signing key and mr and mnr are the recoverable and non-recoverable parts of the signature, respectively, so that m = mr||mnr. If an attacker could obtain sufficient computational resource to mount the recent attack, then they would be able to find two message strings m1 and m2 that collide under SHA-1: SHA-1(m1) = SHA-1(m2). Such a SHA-1 collision in two messages is of no value to a fraudster unless they are in a position to have one of those messages signed as a key by a payment system CA or issuer CA. Any fraudster in this position has much easier and more rewarding fraud opportunities without having to find the collision. Any attempt to create fake cards or become a fake issuer by finding a 2nd pre-image that matches an existing certificate remains infeasible. References [1] “The first collision for full SHA-1”, Stevens, Burzstein, Karpman, Albertini, Markov, http://marc-stevens.nl/research/papers/SBKAM17-SHAttered.pdf, February 2017 [2] “EMV and recent attacks on SHA-1” (N452r1), Security position statement for EMVCo Advisors, March 2005 [3] “Finding Collisions in the Full SHA-1”, Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, CRYPTO (Victor Shoup, ed.), Lecture Notes in Computer Science, vol. 3621, Springer, 2005, pp. 17-36. See also http://theory.lcs.mit.edu/~yiqun/. [4] Marc Stevens publications, https://marc-stevens.nl/research/. Business Associate Access Only: do not distribute. This document contains proprietary and confidential information of EMVCo. LLC. Copyright 2017 © EMVCo. LLC. All rights reserved