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

[Jerry Leichter]

On Nov 10, 2014, at 7:01 AM, ianG <iang at iang.org> 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....
> 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.
Actually, I suspect all three of us are in violent agreement here.  Peter specifically asked about catching "all possible problems" - something only a theory we aren't even close to having could answer.  I answered along the lines of what such a theory would have to account for.

As a practical matter, I'd consider the closed loop check myself - though in fact such checks are pretty rare, in any kind of code.  If we're talking about RSA, you could, of course, use its multiplicative property to blind the data, so that you would be checking the signature not on the original data but on some random multiple of it - which would presumably make attacks that much more difficult, for little cost.  Though that raises the interesting question of whether you could come up with a check that's much more efficient - something along the lines of "casting out nines" to check additions.  Probably.  Or you could say that machines today are fast enough that it's not worth the trouble.

                                                        -- Jerry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141110/69accdae/attachment.bin>