AES Attacks Possible?

In another brain-drowning math-fest, Daniel J. Bernstein (djb for you geeks out there), has a paper on cache-timing attacks against AES (pdf link). It's a scary trip into cryptography math, cpu internals, complex timing side-attacks, and somewhat frightening conclusions.

His attack centers on the OpenSSL implementation of AES. As OpenSSL's implementation is the AES backbone of numerous SSH products, and SSH is the backbone of a modern system administrator's security toolkit, this paper presents some disconcerting information.

I'm no math genius, and I'm not qualified to speak to the validity of this paper's contents, but a read-through shows methodical, well-argued processes for determining secret keys from external observation. The math is complex, and maybe djb's assumptions break down at some point, I couldn't say. But it is definitely something to keep looking for in crypto news.

His attack does seem to be able to recover a single AES key in a four to five hours of Pentium III compute cycles. Given multiple faster processors, the time to extract a single AES key could be greatly reduced. The real question is, how often do people using OpenSSL rekey their AES encryption. The SSH protocol allows for re-keying on the fly, and some SSH products allow control of how often a server re-keys. So what is a paranoid/safe value for re-keying maximums? Even if set "reasonably" low, how can you prevent a distributed observation/compute attack from dipping below the re-key timing. Once they have the first key, all is lost for that SSH connection, and possibly your server.

If you are a sysadmin, keep an ear to the ground on this one; particularly if you are one who has chosen AES over other encryption methods since it is FIPS approved.