You are looking at a specific version 20120903:124428 of this paper. See the latest version.

Paper 2012/491

On the Multiple Fault Attack on RSA Signatures with LSBs of Messages Unknown

Lidong Han and Wei Wei and Mingjie Liu

Abstract

In CHES 2009, Coron, Joux, Kizhvatov, Naccache and Paillier(CJKNP) introduced a fault attack on RSA signatures with partially unknown messages. They factored RSA modulus $N$ using a single faulty signature and increased the bound of unknown messages by multiple fault attack, however, the complexity multiple fault attack is exponential in the number of faulty signatures. At RSA 2010, it was improved which run in polynomial time in number of faults. Both previous multiple fault attacks deal with the general case that the unknown part of message is in the middle. This paper handles a special situation that some least significant bits of messages are unknown. First, we describe a sample attack by utilizing the technique of solving simultaneous diophantine approximation problem, and the bound of unknown message is $N^{\frac1{2}-\frac1{2\ell}}$ where $\ell$ is the number of faulty signatures. Our attacks are heuristic but very efficient in practice. Furthermore, the new bound can be extended up to $N^{\frac1{2}^{1+\frac1{\ell}}}$ by the Cohn-Heninger technique. Comparison between previous attacks and new attacks with LSBs of message unknown will be given by simulation test.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Fault AttacksRSA SignaturesLeast Significant Bits (LSBs)ISOIEC} 9796-2LLL Algorithm
Contact author(s)
hanlidong @ mail tsinghua edu cn
History
2012-09-03: received
Short URL
https://ia.cr/2012/491
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.