Security Position Statement: ROCA: Return of the Coppersmith Attack

EMV-SWG-NG53r3 EMVCo Position Statement on ROCA: Return of the Coppersmith Attack For EMVCo Advisors 11 January 2018 Background and Overview EMV reliance on RSA EMV specifies the use of RSA cryptography for local authentication of a card to a terminal. If a fraudster could obtain an EMV card’s private RSA key then the fraudster could create clones of that card and commit fraudulent offline (low-value) transactions. The fraudster would not be able to commit fraudulent online transactions as these transactions are secured using symmetric cryptographic keys (Triple DES or AES) unaffected by the broken RSA key. Recent attack on RSA keys Researchers have recently published a paper [1] that describes an attack that breaks RSA public keys (i.e. reveals the corresponding RSA private keys) if the RSA keys were generated by a certain Infineon chip software library1. The researchers believe that their attack affects around one-quarter of all current TPM (Trusted Platform Modules) and many millions of smartcards that generate their own RSA keys. Consequences for EMV The researchers tested a small number of EMV smartcards but none had RSA keys that were vulnerable to the attack. This is probably because the EMV card RSA key pairs would not have been generated by the card but by an HSM under the control of the issuer or a delegated bureau. Indeed the EMV Card Personalisation Specification provides no support for on-card key generation and consequently the Issuer Security Guidelines do not mention it either. The RSA key pair and certificate, along with the derived Triple DES or AES symmetric keys are normally generated off-card and transferred securely with all the other necessary data to the card. Brief Description of the Attack Primes generated by the Infineon chip software are generated using a specially crafted non-standard algorithm dubbed “fast prime” which is indeed faster than standard RSA key generation but unfortunately results in RSA public keys that can be easily recognized (once you know the structural characteristics to look for) and then broken. The authors of [1] discovered statistical anomalies in the RSA public keys generated by this Infineon chip and were able to design rules for quickly determining whether or not an RSA public key was 1 See https://crocs.fi.muni.cz/public/papers/rsa_ccs17 This document contains proprietary and confidential information of EMVCo. LLC. Copyright 2018 © EMVCo. LLC. All rights reserved generated by the Infineon chip. More crucially they then proceeded to develop and optimize an attack using a well-known method by Coppersmith [3] to determine the secret primes p and q whose product is the public key modulus. This method was also used a few years ago by researchers to break RSA keys generated in Taiwan identity cards [2]. The paper [1] presents the following table of products tested by them. EMV Security Evaluation Although the authors of [1] note that the Infineon RSA software library “was approved for use in EMV cards by EMVCo”, EMV transactions involve RSA signatures using RSA keys personalised as described above, but not RSA key generation. References [1] “The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli”, Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, Vashek Matyas, ACM CSS 2017. [2] “Factoring RSA Keys from Certified Smart Cards: Coppersmith in the Wild”, Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, and Nicko van Someren. 2013. In Advances in Cryptology - ASIACRYPT 2013. Springer-Verlag, 341–360. [3] “Finding a Small Root of a Univariate Modular Equation”, Don Coppersmith, In Advances in Cryptology — EUROCRYPT ’96. Springer-Verlag, 155–165. This document contains proprietary and confidential information of EMVCo. LLC. Copyright 2018 © EMVCo. LLC. All rights reserved