Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures
CORON, Jean-Sébastien; Naccache, David; TIBOUCHI, Mehdi et al.
2009In Proceedings of CRYPTO 2009
Peer reviewed
 

Files


Full Text
203.pdf
Publisher postprint (342.32 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
digital signatures; forgery; RSA; public-key cryptanalysis; ISO/IEC 9796-2; EMV
Abstract :
[en] 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 $\simeq$ US$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.’s technique but significantly accelerate it for parameter values previously considered beyond reach. While less efficient (US$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.
Disciplines :
Computer science
Identifiers :
UNILU:UL-CONFERENCE-2010-083
Author, co-author :
CORON, Jean-Sébastien ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Naccache, David;  École Normale Supérieure
TIBOUCHI, Mehdi;  École Normale Supérieure
WEINMANN, Ralf-Philipp ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Language :
English
Title :
Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures
Publication date :
2009
Event name :
CRYPTO
Event place :
Santa Barbara, United States - California
Event date :
August 16-20, 2009
Main work title :
Proceedings of CRYPTO 2009
Publisher :
Springer
ISBN/EAN :
978-3-642-03355-1
Pages :
428-444
Peer reviewed :
Peer reviewed
Commentary :
5677 <br />Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference
Available on ORBilu :
since 04 December 2013

Statistics


Number of views
167 (10 by Unilu)
Number of downloads
308 (0 by Unilu)

Scopus citations®
 
10
Scopus citations®
without self-citations
8
OpenCitations
 
11
WoS citations
 
6

Bibliography


Similar publications



Contact ORBilu