Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures

Jean-Sebastien Coron; David Naccache; Mehdi Tibouchi; Ralf-Philipp Weinmann

Paper 2009/203

Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures

Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi, and Ralf-Philipp Weinmann

Abstract

In 1999, Coron, Naccache and Stern discovered an existential signature forgery for two popular RSA signature standards, ISO/IEC 9796-1 and 2. Following this attack ISO/IEC 9796-1 was withdrawn. ISO/IEC 9796-2 was amended by increasing the message digest to at least 160 bits. Attacking this amended version required at least 2^61 operations. In this paper, we exhibit algorithmic refinements allowing to attack the amended (currently valid) version of ISO/IEC 9796-2 for all modulus sizes. A practical forgery was computed in only two days using 19 servers on the Amazon EC2 grid for a total cost of roughly 45,000), the acceleration also extends to EMV signatures. EMV is an ISO/IEC 9796-2-compliant format with extra redundancy. Luckily, this attack does not threaten any of the 730 million EMV payment cards in circulation for operational reasons. Costs are per modulus: after a first forgery for a given modulus, obtaining more forgeries is virtually immediate.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. An extended abstract will appear at CRYPTO 2009. This is the full version.
Keywords: digital signatures forgery RSA public-key cryptanalysis ISO IEC 9796-2
Contact author(s): jscoron @ gmail com
History: 2009-05-20: received
Short URL: https://ia.cr/2009/203
License: CC BY

BibTeX

@misc{cryptoeprint:2009/203,
      author = {Jean-Sebastien Coron and David Naccache and Mehdi Tibouchi and Ralf-Philipp Weinmann},
      title = {Practical Cryptanalysis of {ISO}/{IEC} 9796-2 and {EMV} Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/203},
      year = {2009},
      url = {https://eprint.iacr.org/2009/203}
}