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

[Michael Kjörling]

On 8 Nov 2014 02:27 +1300, from pgut001 at cs.auckland.ac.nz (Peter Gutmann):
> For private keys this requires multiple levels of chaining.  Assuming a
> conventional process of read of a private key from backing store that decrypts
> it and loads it from its now-decrypted but marshalled form into some internal
> bignum format ready for use, there are three stages, encrypted data, decrypted
> data, and data loaded into bignums (and, obviously, another check on the
> bignum when it's actually used for crypto):
> 
>   checksum1 = check( encrypted key data );
>   MAC-verify encrypted key data;
>   decrypt encrypted key data;
>   checksum2 = check( decrypted key data );
>   load decrypted key data;
>   checksum3 = check( loaded key data );
>   if( checksum3 != check( re-load of decrypted key data ) )
>     error; // Decrypted vs. bignum data differs
>   if( checksum2 != check( decrypted key data ) )
>     error; // Decrypted data was changed
>   if( checksum1 != check( encrypted key data ) )
>     error; // Encrypted data was changed
> 
> In other words if the key data is corrupted after the MAC check then checksum1
> will detect it, if it's corrupted between decryption and load then checksum2
> will detect it (with a very slight race condition between decrypt and check()
> that would require storing a second MAC of the plaintext alongside the MAC of
> the ciphertext), and finally if it's corrupted after it's loaded then the
> second load attempt will detect it since the loaded values will differ from
> the first load attempt.

I agree that if the attacker has enough access that they can flip bits
back and forth at will in step with code execution then you have a
much more serious problem. However, I think the above sequence
potentially misses one failure case, namely the stuck bits case which
I mentioned in my previous email in this thread.

Thankfully, stuck bits is fairly easy to protect against, since (and
especially with the above) you can likely assume non-intelligence. A
trivial way of checking this might be to on key storage normalize the
actual key data to some known format (this could be as simple as an
ASCII base-10 digits representation of the parameters in a fixed
order), compute a checksum over that data, and store that checksum
along with the stored (encrypted, marshalled, whatever strikes your
fancy) key material. As a final step before using the loaded key
material for crypto, normalize the key material that is about to be
used into the same format, compute the checksum over that, and compare
it to the stored checksum. In other words, true _end to end_
verification that the key material is what was originally generated or
at least stored. If they differ, then bail out with a prominent error
message.

-- 
Michael Kjörling • https://michael.kjorling.se • michael at kjorling.se
OpenPGP B501AC6429EF4514 https://michael.kjorling.se/public-keys/pgp
                 “People who think they know everything really annoy
                 those of us who know we don’t.” (Bjarne Stroustrup)