Jacques Mattheij seems floored by the idea that you could look at something as obscure as cache timings in a hyperthreading-enabled processor and use it to deduce crypto keys. He's right: it's a clever attack. But if it surprises you, please count it as another reason you should never implement your own crypto.
For the past 10 years or so, crypto researchers have been pawing through the x86 microarchitecture (microarchitecture: the part of the processor that isn't directly exposed in the instruction set; best example: cache) looking for side channels. They've found a lot of scary stuff.
For instance, every time your processor takes a branch, it's caching the computed branch target; it does that so that it can predict branches, so that when it snorfles instructions into its pipeline, it doesn't have to chuck them when a branch goes the "wrong" way. But the branch cache (the BTB) is finite. You can write a process that continuously profiles branch timing to deduce the state of the branch caches, and if that code runs alongside crypto code, it can make predictions about key bits (that's Aciicmez's paper).
There's every reason to believe that there are areas of the microarchitecture that aren't documented that have even worse effects.
There is actually a practical point to pull out of this (and here I've buried a lede): it is very probably unsafe to run "secure" code (SSL credit card processing, etc) on shared hosting of any sort. A motivated attacker can probably get their code running on the same physical hardware, and the odds right now say that attacker can pull key bits out of your processes.
An acquaintance of mine implemented a solution to this problem: it's an implementation of AES that used no tables and no branches; it used the shuffle instruction (pshufb) in a very creative way combined with a different interpretation of the AES algorithm to make it possible. It should be invulnerable to (at least standard) timing and cache attacks. For bonus points, it was also far faster than most standard implementations.
All mainstream modern crypto libraries are hardened in one way or another against timing attacks (Nate Lawson can probably be counted on to jump in here and correct us on this), but to my mind the bigger concern is that we simply don't know what trails our code is leaving inside the processor. Processor microarchitecture is vast, undocumented, complicated, and intricate.
I just took a quick look at 0.9.8h and this is still the case. The C code (aes_core.c) is the standard "alg-fst" version. The asm code in the subdirectory is faster but has no masking.
In short, if you want timing attack resistance, you can't just expect it in standard libraries.
Essentially you'd have to audit the entire cpu design to be sure that you didn't leave any fat fingerprints all over the place. Any flip-flop that had changed state in a recoverable way would be a potential security leak.
Good luck getting that kind of access to a cpu design though, and even better luck trying to figure out all the angles of attack, miss one and someone else has a vector, silicon is hard to change after the fact.
What is interesting here to me about this whole subject is that it has apparently long ago gone from 'theoretical' to 'practical', and you'd be hard pressed to prove that you didn't lose a key or two (or all of them) to an attacker sophisticated enough to do his snooping and then disappear quietly.
After all, any hack or hacker that you read about or hear about wasn't as good as they could have been, the ones you never hear about are the ones to worry about.
For me this whole idea of having someone plant a piece of software on a machine that I own without me detecting it was a prime reason in choosing not to do my own card processing (even though in the dark ages I wrote 'webpay', which later became the foundation for a major IPSP).
I realized that by simply having a page hosted that accepts credit cards on a https connection I would basically be putting up an open 'hack me' invite.
You want to google "Remote Timing Attacks Are Practical", which is the landmark paper in this subfield and also the one crypto people use to scare their children around campfires with.
What you're really observing is the flip side of the "covert channel problem", which has been a well-known Hard Problem driving systems research since the '70s (it's part of Saltzer/Schroeder). Systems security people generally concede that the covert channel problem is impractical to solve in theory, and have resigned themselves to occasional fire drills as theory becomes practice.
And even better, the Crosby article on optimizing timing attacks. He gets to the level of measuring differences as small as 15-100 microseconds over the Internet and 100 nanoseconds over the LAN.
Maybe I'm thinking about this too simply, but wouldn't fugding the timing on any cryptographic operation in a random fashion make it (much) harder to deduce the keys ?
No. This is basic signal processing. Increase the noise, and all you do is increase the number of measurements needed to recover the signal.
This is a really common misconception about defeating timing attacks.
A more pernicious problem is that many of these microarch side channel attacks don't rely on direct timing of crypto code, so much as on microarch artifacts.
(For what it's worth, the specifics beyond this get to a place where I'm out of my depth and Colin and Nate are still in theirs.)
Right, I get that, increase the noise by a factor of two and you'd need more samples, increasing the chance of detection but ultimately not making the problem much harder.
But every factor of two that you make it harder is effectively one bit extra on the key that you're trying to find right ?
Assuming that's true (going out on a limb here) the more you are willing to waste time the harder it will get for an attacker to recover the keys, so ultimately it is a measure of efficiency vs security.
As for micro architecture, I don't know much about that other than reading up on the 68K when it came out and how it functioned at the block level, but one way to side-step that issue completely if you want to write bullet proof crypto code (if that is even possible) would be to write it for a controller on a separate plug in card (pci, possibly usb) that would be permitted to allow exactly one crypto operation per fixed interval of time to be performed.
That way you could effectively 'hide' the key and all its side-effects from view from both local and remote attackers.
It would then take at a minimum physical access to the card to monitor its buses in order to recover they keys.
That's a nice paper. Bitsliced implementations, for those who don't know, use sequential instructions to perform parallel computation. They compute the logic function for the S-boxes instead of a lookup table.
Excellent points, as always, but the tone of the opening sentence could have been a little muted; addressing a generic reader, "you", instead of a personal name.
For the past 10 years or so, crypto researchers have been pawing through the x86 microarchitecture (microarchitecture: the part of the processor that isn't directly exposed in the instruction set; best example: cache) looking for side channels. They've found a lot of scary stuff.
For instance, every time your processor takes a branch, it's caching the computed branch target; it does that so that it can predict branches, so that when it snorfles instructions into its pipeline, it doesn't have to chuck them when a branch goes the "wrong" way. But the branch cache (the BTB) is finite. You can write a process that continuously profiles branch timing to deduce the state of the branch caches, and if that code runs alongside crypto code, it can make predictions about key bits (that's Aciicmez's paper).
There's every reason to believe that there are areas of the microarchitecture that aren't documented that have even worse effects.
There is actually a practical point to pull out of this (and here I've buried a lede): it is very probably unsafe to run "secure" code (SSL credit card processing, etc) on shared hosting of any sort. A motivated attacker can probably get their code running on the same physical hardware, and the odds right now say that attacker can pull key bits out of your processes.