Paper 2009/309

Fault Attacks on RSA Signatures with Partially Unknown Messages

Jean-Sebastien Coron, Antoine Joux, Ilya Kizhvatov, David Naccache, and Pascal Paillier

Abstract

Fault attacks exploit hardware malfunctions to recover secrets from embedded electronic devices. In the late 90's, Boneh, DeMillo and Lipton introduced fault-based attacks on {\sc crt-rsa}. These attacks factor the signer's modulus when the message padding function is deterministic. However, the attack does not apply when the message is partially unknown, for example when messages contain some randomness which is recovered only when verifying a {\sl correct} signature. In this paper we successfully extends RSA fault attacks to a large class of partially known message configurations. The new attacks rely on Coppersmith's algorithm for finding small roots of multivariate polynomial equations. We illustrate the approach by successfully attacking several randomized versions of the ISO 9796-2 encoding standard. Practical experiments show that a $2048$-bit modulus can be factored in less than a minute given one faulty signature containing $160$ random bits and an unknown $160$-bit message digest.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. An extended abstract of this paper will appear at CHES 2009. This is the full version.
Keywords
Fault attacksdigital signaturesRSACoppersmith's theoremISO 9796-2
Contact author(s)
jscoron @ gmail com
History
2009-07-01: received
Short URL
https://ia.cr/2009/309
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/309,
      author = {Jean-Sebastien Coron and Antoine Joux and Ilya Kizhvatov and David Naccache and Pascal Paillier},
      title = {Fault Attacks on RSA Signatures with Partially Unknown Messages},
      howpublished = {Cryptology ePrint Archive, Paper 2009/309},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/309}},
      url = {https://eprint.iacr.org/2009/309}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.