Posted by Scott Laird
Tue, 17 May 2005 20:13:57 GMT
Bruce Schneier posted a link to an AES timing attack from Dan Bernstein.
This is similar to last week’s hyperthreading vulnerability, in that it exploits cache timing variances to extract sensitive information, but DJB’s attack is demonstrated working over a network–it doesn’t require that the attack code run on the same physical CPU as the encryption code. Instead, it exploits the fact that AES implementations need to do data-dependent lookups from tables, and the tables don’t fit entirely into the CPU’s fastest cache. Therefore, by closely watching the time it takes for a server to encrypt a packet and return a result, you can learn something about the key itself. By feeding the server millions of carefully-crafted packets and examining the timing results produced, he was able to narrow the keyspace substantially.
In this case, he was able to recover all 128 bits of a randomly-generated AES key in around a day. Most likely, the process could be optimized substantially by testing high-probablility keys against a known plaintext in parallel with the AES. I wouldn’t be surprised if an hour’s worth of traffic was enough to narrow the keyspace enough to make a brute-force attack possible. His notes also suggest a number of other optimizations that may lower the amount of work even further.
In general, any data-dependent timings anywhere in a crypto system will subject the system to this sort of problem. Unfortunately, it’s nearly impossible to eliminate all of the data-dependent timing issues on any modern computer–between cache issues, hidden optimizations in certain instructions, measurable delays when switching between cache banks, and an utter lack of comprehensive performance documentation, there’s really no easy way to avoid this class of problems on modern CPUs. The best you can do is minimize the amount of variance and force the attacker to use larger and larger amounts of traffic.
All in all, this probably isn’t just a theoretical attack. It isn’t something that random hackers will use, but it’s fast enough to be usable by a determined attacker with relatively low-latency network access to the victim’s system.
Posted in Computer Security | Tags aes, cryptography, djb, security, timingattack | no comments
Posted by Scott Laird
Fri, 13 May 2005 00:27:44 GMT
KernelTrap is reporting that a SFU grad student has found some sort of hyperthreading vulnerability. Details are slim, but he’s claiming some sort of information leakage between threads on a HT CPU, saying that this could lead to the disclosure of things like RSA private keys.
If I had to guess, I’d say that this is some sort of timing attack. Most likely, the leak occurs when one HT thread runs a predictable chunk of code with secret data while the other HT thread runs some sort of monitoring code, watching for things like cache misses or utilization of the various shared resources. Or maybe, Intel shares the CPU performance counters between the two threads so the attacking thread can simply extract detailed timing information from the other thread’s work, and then use the timing information to reconstruct details on what the attacked thread was doing. There’s a decent body of work on attacking smart cards using similar techniques.
Update: After doing a bit of research, it looks like Intel does share performance counter data between threads, and some of the data shared is really interesting, like branch prediction data–if you’re attacking a known body of code, you may actually be able to extract enough data from this to get a decent peak at the private key.
Update 2: The paper is online. If I’m reading this correctly, the basic attack uses timing measurements against the L1 and L2 caches to see when the RSA thread moves on to a new cache line worth of data. The attack doesn’t need access to anything more advanced then the CPU’s cycle-counter clock to be able to recover roughly 310 bits from a 512 bit key.
Personally, I find this to be fascinating from an academic standpoint but not terrifically useful in the real world. I don’t generally want untrusted users to have any access to systems with valuable keys. Historically, it hasn’t taken most attackers very long to turn untrusted shell access into a root exploit. In almost any case, a root exploit is more worrying then the loss of 310 bits from a 512 bit key–if the attacker had root, odds are they could recover the entire key directly.
This is clearly a problem that needs to be fixed by Intel, but I’m not planning on running around disabling Hypertheading on all of my systems today. It’s just not that dangerous of an exploit for most users.
Posted in Computer Security | Tags cryptography, security, timingattack | no comments
