Security Position Statement: EMV® and use of SHA-1 update: chosen-prefix collision attacks

EMV-SWG-NF93r9 EMVCo Position Statement on EMV® and use of SHA-1 update: chosen-prefix collision attacks For EMVCo Associates April 2020 Summary EMVCo has analysed a new chosen-prefix collision attack on SHA-1, see [1] and [2]. The outcome of the analysis confirms that the EMV® Chip specifications are not impacted. This is because the attacks are seeking to find collisions whereas the EMV Chip specifications rely on the much harder problem of finding 2nd pre-images. Introduction This position statement provides an update for the EMVCo Associates in light of the recent research that has found chosen-prefix collisions in SHA-1 [1]. For more details about this research see • https://sha-mbles.github.io/ • https://eprint.iacr.org/2020/014.pdf A previous EMVCo position statement addressed the SHA-1 attacks in 2017 implemented by CWI Amsterdam and Google, see: • https://shattered.io • https://www.theregister.co.uk/2017/02/23/google_first_sha1_collision/ It is important to note that these attacks pose 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 and the conclusions remain valid. Such collisions have been anticipated for many years and builds on previous well-known work by researchers such as Professor Xiaoyun Wang and Marc Stevens. However the actual demonstration of a collision and a chosen-prefix collision in SHA-1 does represent a significant landmark and any legacy use of SHA-1 may be subject to public criticism. Background on SHA-1 attacks 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 determine © 2020 EMVCo, LLC. All rights reserved. Reproduction, distribution and other use of this document is permitted only pursuant to the applicable agreement between the user and EMVCo found at www.emvco.com. EMV® is a registered trademark or trademark of EMVCo, LLC in the United States and other countries. • 1st Pre-images: Given H=SHA-1(M) for unknown M, find any M' with SHA-1(M')=H • 2nd Pre-images: Given M, find any other M' with SHA-1(M')=SHA-1(M) • Collisions: Find any M, M' with SHA-1(M')=SHA-1(M) - Chosen-prefix Collisions: Given P, P' find any M, M' with SHA-1(P||M)=SHA-1(P'||M') No significant progress has been made with respect to 1st pre-image and 2nd pre-image attacks on SHA1 and these are still considered computationally infeasible problems. SHA-1 is already known to be vulnerable to general collision attacks and has now been shown to be vulnerable to the more difficult chosen-prefix collision attacks where the attacker is forced to operate under extra constraints related to the message prefix. It can be seen that chosen-prefix collisions reduce to the simpler collision attack when prefixes P and P' are null. Overview of recent chosen-prefix collision attack The authors of the recent research [1] explained that • general ad-hoc SHA-1 collision attacks can now be computed with a complexity of 261.2 SHA-1 calculations (~11k US$) whereas chosen-prefix collisions require 263.4 (~45k US$). • their attack required 2-months computation using 900 rented GPUs (Nvidia GTX 1060) and sub-optimally cost about 75k US$. Some attack details quoted from [1] are as follows: • in order to demonstrate the practical impact of chosen-prefix collisions, we used our chosenprefix collision for a PGP/GnuPG impersonation attack. The chosen prefixes correspond to headers of two PGP identity certificates with keys of different sizes, an RSA-8192 key and an RSA-6144 key. By exploiting properties of the OpenPGP and JPEG format, we can create two public keys: key A with the victim name, and key B with the attacker name and picture, such that the identity certificate containing the attacker key and picture has the same SHA-1 hash as the identity certificate containing the victim key and name. Therefore, the attacker can request a signature of his key and picture from a third party (from the Web of Trust or from a CA) and transfer the signature to key A. The signature will still be valid because of the collision, while the attacker controls key A with the name of the victim, and signed by the third party. Therefore, he can impersonate the victim and sign any document in her name. The authors note that the attack is extremely technical, contains many details, various steps, and requires a lot of engineering work. Relevance to EMV © 2020 EMVCo, LLC. All rights reserved. Reproduction, distribution and other use of this document is permitted only pursuant to the applicable agreement between the user and EMVCo found at www.emvco.com. EMV® is a registered trademark or trademark of EMVCo, LLC in the United States and other countries. EMV uses SHA-1 based digital signatures for public key certificates and for card generated signatures during offline local card authentication (DDA/CDA). 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 signed message, respectively, so that m = mr||mnr. The relevance of chosen-prefixes to the signature algorithm used by EMV becomes apparent when one observes that the chosen prefix might be the recoverable part mr of a message m. For example to translate chosen-prefix collision attacks into EMV, an attacker may be given prefix mr = mr' and will then launch the calculation to find mnr and mnr' such that SHA-1(mr||mnr) = SHA-1(mr||mnr') and then obtain the signature S = (mr || SHA-1(mr||mnr))d on m=mr||mnr which they can then fraudulently use as a signature on m'=mr||mnr'. S = (mr || SHA-1(mr||mnr'))d 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 public key certificate 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. Note that any collision attack on a card signature to fool a terminal during DDA/CDA is precluded as the collision calculation would need to take place in real-time during the payment transaction so as to accommodate the terminal challenge UN (and would be thwarted anyway if the card incorporates its own unpredictable card dynamic number). Conclusion With collision attacks, including chosen-prefix collision attacks, the attacker first determines two messages that have the same hash and then obtains a signature on one message so as to abuse this as a signature on the other message. 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] SHA-1 is a Shambles First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust, Gaetan Laurence and Thomas Peyrin, January 2020 © 2020 EMVCo, LLC. All rights reserved. Reproduction, distribution and other use of this document is permitted only pursuant to the applicable agreement between the user and EMVCo found at www.emvco.com. EMV® is a registered trademark or trademark of EMVCo, LLC in the United States and other countries. o https://sha-mbles.github.io/ o https://eprint.iacr.org/2020/014.pdf [2] From Collisions to Chosen-Prefix Collisions Application to Full SHA-1, Gaetan Laurence and Thomas Peyrin, May 2019 o https://eprint.iacr.org/2019/459.pdf © 2020 EMVCo, LLC. All rights reserved. Reproduction, distribution and other use of this document is permitted only pursuant to the applicable agreement between the user and EMVCo found at www.emvco.com. EMV® is a registered trademark or trademark of EMVCo, LLC in the United States and other countries.