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

[Jerry Leichter]

On Nov 12, 2014, at 3:55 AM, Peter Gutmann <pgut001 at cs.auckland.ac.nz> wrote:

> Jerry Leichter <leichter at lrw.com> writes:
> 
>> Peter specifically asked about catching "all possible problems"
> 
> What I meant was "all posible problems within the context of the discussion",
> i.e. bit flips, memory corruption, stuck-at faults, etc.  Dealing with ebola,
> global warming, and world hunger were implicitly excluded from the problem
> space.
You mean you *don't* think we should deal with Ebola, global warming, or world hunger?  What kind of a monster are you? :-)

> So the question remains, would a pairwise consistency test detect any memory- 
> based problems, or would you still need checksumming to detect specific 
> changes in the public and private keys where the RSA/DLP operation succeeded 
> on a modified form of the key?  And as a corollary, can you modify the key 
> values so that you leak the private key but the pairwise check still succeeds 
> (in other words you don't just replace key parameters wholesale to meet the 
> "modified key" criteria).
I'm not sure what a "memory-based problem" would be.  If you allow the memory to be swapped - especially if it goes to encrypted swap, which you would presumably want to use - a disk error would result in a completely arbitrary change to any relevant value.  Measurements show that while very rare, undetected disk errors do occur.  (Note that a "memory error" could also produce arbitrary changes in the *code*.  I don't know whether any work has been done on that - obviously, you have to bound "arbitrary" or you can say nothing at all.)

The attacks I mentioned were variations of well-known side-channel attacks that tried to leverage the unusual code paths and behavior that a memory error could trigger - and which the check code could, in principle, amplify.

Complexity, as always, is the enemy of security.  Checking this way seems as if it would help - but then again, anything that uses private information has the *potential* to leak it.  If we were talking about *encryption*, doing a checksum before encryption and checking it after - to *detect faults*, *not* to do authentication - seems reasonable, though if *it* does leak information by letting an attacker know he has a valid decryption.  There's no free lunch.  (It's not clear to me how to accomplish the same thing for signatures.)

Let me be clear here:  I believe that sound engineering practices and intuition must play a big role alongside formal proofs and such.  Only formalization and proofs can get you to "all possible attacks", and I don't think you can hope for that here - nor do you need it.

We're talking exceedingly rare events.  The question becomes:  Is the cost justified?  Does the cure *possibly* introduce as much vulnerability as the (extremely tiny) vulnerability it prevents?  Are there simpler approaches that improve the situation without leaving as many open questions?

BTW, there *is* a theory of "error detecting computation" out there.  It's been years since I've seen it, and it was more oriented to traditional scientific computation.  (It probably became of interest after the Intel division issue surfaced way back when.)  Perhaps there's something to learn there.

                                                        -- Jerry