*15:17*[Pub][ePrint] On the Multiple Fault Attack on RSA Signatures with LSBs of Messages Unknown, by Lidong Han and Wei Wei and Mingjie Liu

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.