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

[Peter Gutmann]

An attempt to summarise the discussion, both on- and off-list:

- Deliberate fault attacks are really hard, even under artificial conditions
(RSA run in a tight loop and not much else present) because the chances of
causing an appropriate fault, hitting a key bit, and getting it at exactly the
right moment are pretty remote.  From an off-list discussion, quoted with
permission from the author:

  Carrying out these sorts of attacks is actually very difficult. I used a
  microprobing station that a friend's failure analysis lab had to get an
  Am241 source right over the memory of a microcontroller (87C51, IIRC). That
  was actually tricky to do. This microcontroller just ran a loop to carry out
  RSA again and again. And even in those fairly optimal conditions, actually
  getting [bit-flip fault] that caused the right kind of error took a very,
  very long time. So although this is theoretically possible, and is
  potentially a good way to get funding to buy interesting toys for a lab, I'd
  say that it's really not even close to being practical.

- Accidental fault attacks caused by inadvertent bit-flips on data held in
memory over a period of time are scarily common, see e.g. the Bitsquatting
issue, discovered by Artem Dinaburg,
http://media.blackhat.com/bh-us-11/Dinaburg/BH_US_11_Dinaburg_Bitsquatting_WP.pdf
and investigated further by Duane Wessels
http://www.nanog.org/meetings/nanog54/presentations/Tuesday/Wessels.pdf and
Nick Freeman
http://www.security-assessment.com/files/documents/presentations/Nick_Freeman-DNS_Shenanigans-Kiwicon7_2013.pdf.

So the most appropriate defence appears to be chained/overlapping checksumming
of data to detect memory corruption:

  checksum keying data;
  perform operation;
  verify checksum on keying data to make sure post- == pre-;

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.

This should catch the likely attacks.  If an attacker can flip a bit after a
checksum computation, wait for it to be used in the next stage, and then flip
it back before the verification checksum is computed then you can evade this,
but if an attacker has that much control over your system then you've got
bigger things to worry about.

Peter.