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.