[Cryptography] Vulnerability of RSA vs. DLP to single-bit faults

[ianG]

On 9/11/2014 04:24 am, Jerry Leichter wrote:
> On Nov 8, 2014, at 4:49 PM, Peter Gutmann <pgut001 at cs.auckland.ac.nz> wrote:
>> Another option is to perform a pairwise consistency test each time the private 
>> key is used.  In other words every time you generate a signature you then use 
>> the public-key components to verify it (which my code does anyway just as a 
>> general precaution).  Question: Will this catch all possible problems?
> "All possible problems?"  I highly doubt it!
> 
> If we were talking ordinary code, "closing the loop" like this would certainly seem like an excellent idea whose only possible downside was cost.  But for crypto code ... one worries.  For example, are you opening up some possible side-channel attack by running two closely correlated exponentiations one after the other?  If we were talking about a *mathematical* attack, there would be no problem, as the attacker could have done the computations himself.  But he can't run this code *on you hardware*, with, for example, the caches warmed by the inverse calculation (that he can't perform).  It's not that I have any idea of a potential attack ... but the history of side-channel attacks should keep us cautious.
> 
> Another potential area of trouble is error recovery.  Does the fact that the verification failed reveal something?  Does recomputing using a very slightly different key reveal something?


I agree in theory with what you're saying above, but I'll side with
Peter on this one.

I think in practice, the issues of dodgy code and weird bugs still
outweigh by o(100) the likelihood of exotic crypto attacks.  Doing the
sign-then-verify routinely has caught a lot of bugs, whereas attacks on
keys in the wild are rare, and at this level are almost unheard of.



iang



ps; E.g., as a recent case in point:   My sign-then-verify on androids
was failing, every time on one phone.  This was eventually tracked down
to a BigInteger bug in androids <= 2.2.  The Bitcoin people had already
tracked it down, but I don't know if they were doing sign-then-verify.
Or if they were losing money on this bug...