DJB vs. AES
Thomas Ptacek | April 17th, 2005 | Filed Under: Uncategorized
Side-channel AES attack. “Embarassingly simple”. Basic idea: software AES uses key values to look entries up in a table. The speed difference between two adjacent words in memory can vary by orders of magnitude, depending on whether the value is cached. For each byte of the AES key, generate thousands of random inputs: the inputs that maximize the compute time reveal likely key values.
Linked to the sci.crypt thread instead of the paper because the thread is amusing. My thoughts:
- Bernstein demonstrated this against OpenSSL, so, pretty much game over for the argument that this is theoretical.
- It is exceedingly difficult to create a resistant AES implementation in software. Your encryption subsystem would basically have to forego cache, running at the lowest common denominator of memory speed. Even after taking that speed hit, you’d still have to be extraordinarily careful to keep things running in constant time. Easier to use a constant-time (non-S-box) AES. Unfortunately, non-S-box AES is very slow. Nobody is going to do either of these things when it is so much easier to pretend the problem doesn’t really exist. Note that remote timing against OpenSSL (for other reasons) has been a practical attack for 2 years.
- There’s an argument that this doesn’t apply to many secure hosts because network variance will obscure the timings. From experience doing side-channel sniffer detection, this is overblown, but it’s also irrelevant: if you can get *topologically close* to a secured server, and it’s using naive AES software (read: virtually all AES software), you can get the key.
I think OpenSSL AES key-timing predictors will be this generation’s Crack/John-the-Ripper. Read page 11 of the paper for 7 of Dan’s suggestions on how to streamline the attack. Someone should write this and demo it at DefCon CTF.
