Schneier on Security
A blog covering security and security technology.
May 17, 2005
AES Timing Attack
Nice timing attack against AES.
For those of you who don't know, timing attacks are an example of side-channel cryptanalysis: cryptanalysis using additional information about the inner workings of the cryptographic algorithm. I wrote about them here.
What's the big idea here?
There are two ways to look at a cryptographic primitive: block cipher, digital signature function, whatever. The first is as a chunk of math. The second is a physical (or software) implementation of that math.
Traditionally, cryptanalysis has been directed solely against the math. Differential and linear cryptanalysis are good examples of this: high-powered mathematical tools that can be used to break different block ciphers.
On the other hand, timing attacks, power analysis, and fault analysis all makes assumptions about implementation, and uses additional information garnered from attacking those implementations. Failure analysis assumes a one-bit feedback from the implementation -- was the message successfully decrypted -- in order to break the underlying cryptographic primitive. Timing attacks assumes that an attacker knows how long a particular encryption operation takes.
Doesn't look complicated to me.....
I wonder why wasn't it discovered before, say during the AES process?
Posted by: Anonymous at May 17, 2005 10:50 AM
The author suggests that the algorithm is at fault for making it difficult for implementors to make fast-but-constant-time implementations, then they list a few algorithms that don't have this limitation. They mention Helix, but not Blowfish, so how good/bad is Blowfish in this area? (Blowfish was Mr. Schneier's entry into the AES competition wasn't it?)
Posted by: Andrew at May 17, 2005 10:55 AM
Bruce Schneier's AES candidate was Twofish, not Blowfish; Blowfish was an earlier Schneier cipher.
Posted by: g at May 17, 2005 11:06 AM
One of the author's opening statements is "This attack should be blamed on the AES design, not on the particular AES library used by the server;..." This seems like a somewhat harsh statement: is AES a poor design because it is susceptible to this attack? As a previous poster asked, how do other ciphers such as the AES finalists (Twofish, Serpent, MARS, RC6) fare in this area?
In addition, the author makes comparisons between AES and Helix. Since Helix is a stream cipher, is this an 'apples & oranges' situation? The original Helix paper remarked that AES vs. Helix is a somewhat unfair comparison.
Twofish uses S-boxes; higher-performance implementations use larger S-boxes (which I suspect, though I haven't thought about it hard) are more vulnerable to the sort of attacks Bernstein describes. I don't think Twofish would have done any better than Rijndael against attacks like this.
Posted by: g at May 17, 2005 11:12 AM
The paper does mention that all 15 AES candidates could be vulnerable to this attack.
Maybe we need to have crypto co-processors as standard (as floating point co-pros are, though now built into the CPU). As part of the CPU would be ideal. Give the crypto co-pro dedicated cache, and let the hardware designers learn from crypto co-processors in the smart card world.
Crypto co-processors in the smart card world work in a potentially very hostile environment where the attacker can control power, timing signal ...
Posted by: hamish at May 17, 2005 11:16 AM
Can anyone explain why a table lookup T[i] leaks information about the index i ?! Isn't it constant? Ok, it may not be constant for values fetched from the main memory, but in that case the time should be one of either quick (cache) or slow (memory) ?!
Posted by: Andy at May 17, 2005 11:33 AM
And hasn't it been found that many such coprocessors *are* in fact vulnerable to timing and power attacks? :-) Perhaps I'm out of date and this is no longer true.
Posted by: g at May 17, 2005 11:34 AM
Andy: Because T[i]'s quick or slow leaks information about the cache state, which is based on the history of previous accesses.
MARS is a nightmare and should not have made it into the final round for implementation reasons. And it would possibly be vulnerable because of the large S-box.
Serpent is probably vulnerable because a fast software imprementation ends up using several significant S-boxes.
Twofish is probably vulnerable, because it uses large, key dependant S-boxes.
RC6 is probably NOT vulnerable: Most multipliers are constant-time in current CPUs, and shift as well. (although << 0 might be shortcutted on some arch, eg P4 has a 4 cycle shift operation, so shortucting ROT/SHIFT 0 would be a performance win).
Posted by: Nicholas weaver at May 17, 2005 11:58 AM
Timing attacks are a just one of the TEMPEST tricks that have been known about for many years....
The first Timing attack that I know of was against a UK One Time