Schneier on Security: AES Timing Attack

success fail Jan MAY Oct 17 2007 2008 2010 90 captures 18 May 2005 - 26 Jan 2018 About this capture COLLECTED BY Collection: Common Crawl Web crawl data from Common Crawl. TIMESTAMPS

Bruce Schneier

Home

Blog

Crypto-Gram Newsletter

Books

Essays and Op Eds

Computer Security Articles

News and Interviews

Audio and Video

Speaking Schedule

Password Safe

Cryptography and Computer Security Resources

Contact Information

Schneier on Security

A blog covering security and security technology.

« Surveillance Cameras in U.S. Cities | Main | Fearmongering About Bot Networks »

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.

Posted on May 17, 2005 at 10:05 AM40 CommentsView Blog Reactions

To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.

Comments

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.

Any thoughts?

Posted by: Simmoril at May 17, 2005 11:08 AM


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