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 $800. The forgery was implemented for e=2 but attacking odd exponents will not take longer. The forgery was computed for the RSA-2048 challenge modulus, whose factorization is still unknown. The new attack blends several theoretical tools. These do not change the asymptotic complexity of Coron et al. technique but significantly accelerate it for parameter values previously considered beyond reach. While less efficient ($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 signaturesforgeryRSApublic-key cryptanalysisISOIEC 9796-2
Contact author(s)
jscoron @ gmail com
History
2009-05-20: received
Short URL
https://ia.cr/2009/203
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2009/203}},
      url = {https://eprint.iacr.org/2009/203}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.