[Cryptography] "Flip Feng Shui: Hammering a Needle in the Software Stack"

Jerry Leichter leichter at lrw.com
Fri Sep 2 10:56:10 EDT 2016


> Why bother with patching public keys, making them amenable to
> factorization, if you can patch executable code instead?
> 
> If you can target executable code (and I see why not, it's all the
> same to KSM), it is very clear that there cannot be a software-only
> defense....
The technique cannot be aimed exactly:  You can flip some unpredictable, uncontrollable subset of the bits in a word.  (The vulnerability of particular bits is dependent on physical variations in the memory cells.)

If you try this against executable code, you stand a good chance of breaking something with a visible effect - a much better chance than of producing a useful code change.  The neat observation in the paper is that RSA moduli are particularly vulnerable:  *Any* bit flip is highly likely to make the modulus easily factorable.  Yes, the change in the modulus will be detectable since messages either won't decrypt or signatures won't verify - but that happens on other systems, not the one under attack, and it may take a while for anyone to notice.  (E.g., if you break an ssh key, no one will notice until the legitimate user tries, and fails, to log in - and even than, many users will just assume the system has been reconfigured and generate a new key.)

Attacks against the executable code are certainly the worst case, and you might be able to find security-sensitive but very rarely executed code to attack.  But this is likely much harder to pull off than the attack outlined here.

BTW, this is yet another in a long, long line of attacks against RSA that are based on its exquisite sensitivity.  Leak the bottom bit of messages? Leak the top log n (or something like that) bits of messages?  Make very rare errors in the arithmetic operations?  Flip a bit in the moduli?  All of these lead to full breaks.

Contrast this with, say, AES.  Flip an unknown bit in the sender's key?  The resulting message is just as secure - in fact, more so:  Now, *no one* can decrypt it!  (Well, if you know the key you can try all keys with close Hamming distances.)  At best, an attacker might be able to generate related key attacks this way.

RSA is like a beautiful piece of blown glass:  Admire it, but treat it with great care.

(One thing I don't recall seeing, BTW, is analyses of the sensitivity of ECC to things like leaked bits.  My guess would be that it's also sensitive, though perhaps less so than RSA.)

Anyway, coming back around:  Yes, this attack does show that hardware that's vulnerable to this attack simply cannot be trusted to run the software you think it's supposed to be running.  An attack would be difficult, but as with some other things, cryptography has the property that it concentrates vulnerabilities.  (Leaking a 1MB document through a slow channel will take a long time; leaking the AES-256 key that protects the "black", encrypted version that anyone can get hold of is pretty quick.)

                                                        -- Jerry



More information about the cryptography mailing list