This paper says that if you can touch a simple bare wire to the chassis of a desktop computer, or even to the metal on an Ethernet, VGA, or USB cable connected to that computer, and then trigger RSA operations, you can extract RSA private keys from the computer, even against software that puts some effort into not leaking information in its computations.
This is an extremely cool paper (I'm not qualified to say how novel it is, though I can say that Eran Tromer is an important name in side channel cryptanalyis; the acoustic side channel against GPG builds in some ways off his earlier work).
Some things to look at:
* How the paper builds up from distinguishing a test case using electrical side channels, to distinguishing between different keys using those side channels, to attacking a single key operation, to attacking a single key adaptively.
* The (not particularly complicated) math involved in selecting chosen RSA ciphertexts to target GPG's multiplication code and amplify the side channel.
* The way the adaptive attack (where you bounce repeated and different ciphertexts off the target and learn from each "experiment" to select the next one) builds from the simpler attack.
If the electrical mechanics of how they actually captured the signal are interesting to you, something like the last third of the paper goes into detail, including the part numbers of the equipment they used to capture and process the signals.
I'd like to get someone on my team working on reproducing some of this work. Which is usually the sign of a well-written paper. :)
It appears that this algorithm specifically targets RSA and El-Gamel by crafting inputs that would produce different numbers of multiplications (among other ops) depending on the input.
This should be a wake-up call for the move to elliptic curves, as GPG and OpenSSH allegedly support them. Windows support is lacking for remoting into Linux hosts with elliptic curve based ciphers. I found that while PuTTY does not support this directly, evidently the Gpg4win agent can work with putty, and that might allow ECDSH/ECDSA. I haven't tested this, however. And another terminal client, Tera Term, purports to support elliptic curve algorithms.
Unfortunately for GnuPG, it looks like the only supported curves are those defined in NSA Suite B (the NIST recommended curves). That set is considered tainted by some community members. There's some discussion of GnuPG supporting Curve25519/Ed25519, of implementing it, but I can't tell if it's implemented or not.
Edit: I've played with Tera Term and can confirm that it works with Ed25519 along with OpenSSL 1.0.1f. I'm pleased with the result.
RSA is difficult to make constant time, but there are plenty of constant-time elliptic curve implementations out there. Curve25519/Ed25519 is one of them, and this paper suggests that they will be strongly resistant to these sort of attacks.
RSA is actually one of the easiest algorithm to protect from side-channel attacks (though nothing gives you 100% protection), thanks to the various kinds of blindings you can immediately apply.
Blinding techniques are not constant-time, but what you really want in the end is to reduce the Signal-to-Noise ratio on the radiated energy.
For ECC it is more difficult, and it becomes very hard for most symmetric ciphers.
Blinding ECC is as easy as RSA, if not easier. Coron's classic paper has 3 easy measures to blind a scalar multiplication, and more have appeared since then:
The problem with GnuPG is not that it's using RSA/ElGamal instead of ECC; it's that it's using a general-purpose large integer arithmetic package, MPI, whose purpose is to optimize speed for a wide range of input arguments.
On the specific case of RSA (or rather, CRT-RSA), I've mostly studied fault-injection attacks, which can be considered a kind of side-channel attack. And I agree with you that it is possible to protect RSA (see my most recent paper [1] on that subject, which will be published at FDTC 2014, the day just before CHES 2014, where the paper being discussed in this HN thread will appear).
I also agree with you on the fact that ECC is not immune to side-channel attacks at all: for proof this cool paper [2] by Barthe, Dupressoir, Fouque, Grégoire, and Zapalowicz, which will appear at CCS 2014 which shows working fault-injection attacks on both RSA and ECDSA.
Curve25519 was designed specifically to be leak-resistant, by one of the world's foremost experts in leak-resistant cryptography. Most elliptic curve software is not. Like RSA, elliptic curve also involves exponentiation and modular reduction.
This isn't a very novel technique; I didn't see any reference to TEMPEST, which has been known for a long time - no physical contact required, it can be done at a distance:
The most interesting part is that adding noise won't help to mask the signal, even if the signal is much weaker than the noise, since it can still be recovered through processing.
Tempest deals with extracting signals at a distance, from things that are already directly broadcasting them in some form or another.
There's no such thing in this case. There is no USB port or VGA cable that is directly carrying the internal state of one of dozens of different processes/applications being run on the target PC.
This work is quite completely different. Using special knowledge of how specific software has been written and compiled, and also with the ability to throw carefully crafted inputs at the software in question, they're able to use some fun statistical methods to guess what the internal state must be.
The paper and this type of work generally is very interesting because software developers are used to thinking of CPUs as "black boxes" which do their thing invisibly and effortlessly.
This kind of work is just as awesome as all the papers on CPU side-channel attacks (cache, branch prediction, etc) which really seemed to take off around 2005.
>> This kind of work is just as awesome as all the papers on CPU side-channel attacks (cache, branch prediction, etc) which really seemed to take off around 2005.
Maybe you meant late 90ies, when Kocher (and others) published results on side-channel attacks.
No, that's not what he meant. He was referring to the x86 microarchitectural side channel trend that started in 2005, with stuff like Aciicmez's BTB timing paper, or Osvik and Tromer's local cache timing.
So this is incredibly cool. Like, I could interpret this as scary I guess, but it's outright amazing that you can do something like this to a laptop and distinguish instruction being executed in a CPU from such data.
I am in awe of the people that have the skillset to dream up stuff like this. I never thought the interference of the processor would travel down the line of a UTP cable.
This is an extremely cool paper (I'm not qualified to say how novel it is, though I can say that Eran Tromer is an important name in side channel cryptanalyis; the acoustic side channel against GPG builds in some ways off his earlier work).
Some things to look at:
* How the paper builds up from distinguishing a test case using electrical side channels, to distinguishing between different keys using those side channels, to attacking a single key operation, to attacking a single key adaptively.
* The (not particularly complicated) math involved in selecting chosen RSA ciphertexts to target GPG's multiplication code and amplify the side channel.
* The way the adaptive attack (where you bounce repeated and different ciphertexts off the target and learn from each "experiment" to select the next one) builds from the simpler attack.
If the electrical mechanics of how they actually captured the signal are interesting to you, something like the last third of the paper goes into detail, including the part numbers of the equipment they used to capture and process the signals.
I'd like to get someone on my team working on reproducing some of this work. Which is usually the sign of a well-written paper. :)