[Cryptography] "Physical Key Extraction Attacks on PCs"

[Jerry Leichter]

http://m.cacm.acm.org/magazines/2016/6/202646-physical-key-extraction-attacks-on-pcs/fulltext

The underlying work seems mainly to be about two years old.  The authors demonstrate a technique for determining keys (RSA, El Gamel, EC-DH - by looking at various low-frequency physical emanations (acoustic, electrical coupled through the ground plan, electromagnetic) that they can force to be correlated with key bits by using (sometimes adaptive) chosen plaintexts that will present "poisoned" values to the multiplication and exponentiation steps.

Beautiful work, but it raises two questions about actual applicability:

1.  The cause of the correlation in the multiplication routines is that there's a shortcut in the particular routines they look at that skips over "digits" that are all 0 in the bignum representation.  This seems like a completely pointless optimization in a cryptographic context, where the inputs are (except under attack!) random looking, and thus almost never actually 0 (1 in 2^32 in typical 32-bits-at-a-time representations).  Why bother with this optimization?  Is it just a side-effect of using general-purpose bignum routines - in which case that teaches us a valuable lesson right there....

2.  Much more generally:  The attacks rely on being able to send chosen ciphertexts into the public key functions.  The authors mention the use of encrypted emails, web pages, or encrypted files.  And yet ... who applies public key algorithms to presented data directly?  We've known that's hazardous for many years - but in any case, even today, it's very expensive.  The typical pattern is to apply public key functions to cryptographically secure hashes of data.  If we assume the hash is, secure, generating plaintext whose hash has particular desired properties isn't practical.

The case of DH, where the value being computed is the product of the value received and a random value computed by the recipient (which can't be known or controlled by the attacker), is a bit different, as the attack only seems to depend on being able to inject a single "poison" multiplicand.  The *particular* attacks here should be easily detectable, as the very unusual properties of some of the intermediate values stand out.  But that of course says nothing about other attacks with different characteristics.  Blinding seems like the best defense, though as the authors point out, it can be expensive.  (Also, to blind the value, you have to multiply the value you receive by the blinding value - and by hypothesis *that* leaks the information right away!)

                                                        -- Jerry