IACR News item: 03 September 2012
Lidong Han, Wei Wei, Mingjie Liu
ePrint ReportPaillier(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.
Additional news items may be found on the IACR news page.