Cache-timing attacks on AES

AES  [via: Schneier on Security]
                Daniel J. Bernstein published a profound paper on AES Timing attack. There is very little new in the article from cryptology or cyptography point of view. The side-channel timing attacks of this nature are well known for decades. Moreover, the attacks are not against AES algorithm as such, but against a specific software implementation (OpenSSL on Pentium III).

However it's clear that it is applicable to any other modern CPU, and to any software implementation of any cryptographic algorithm which uses S-boxes. This and other things that I will point out later, led me to conclude that the article and its implications are truly profound. But first of all a quote from the article:

Was there some careless mistake in the OpenSSL implementation of AES? No. The problem lies in AES itself: it is extremely difficult to write constant-time high-speed AES software for common general-purpose CPUs. The underlying problem is that it is extremely difficult to load an array entry in time that does not depend on the entry's index. I chose to focus on OpenSSL because OpenSSL is one of today's most popular cryptographic toolkits. (Constant time low-speed AES software is fairly easy to write but is also unacceptable for many applications. Rijndael would obviously not have survived the fist round of AES competition if it had been implemented in this way.) Is AES the only cryptographic function vulnerable to this type of attack? No. The relevant feature of AES software, namely its heavy reliance upon S-boxes, is shared by cryptographic software for many other functions.

Emphasis is mine. If you don't know the particulars of clock-resolution performance of modern CPUs, just take his word for it. If you do, most likely you don't know half of it. Read the article for all the gory details. The bad news is that an attacker doesn't even need to understand any of the detils. He just need to know that time depends on index, and simply measure it.

Any software algorithm on any modern CPU which involves a table lookup, like S-boxes, for example, is subject to timing attacks. Since many algorithms, including AES, can be implemented without table lookups, it wouldn't be a terribly big deal, if it weren't for one fact: apparently cryptographers participating in AES standardization were completely unaware of the fact that table lookups are a vulnerability. Again quoting from the article: (note that [19] refers to "Report on the Development of the Advanced Encryption Standard (AES)" and [9] refers to "Resistance Against Implementation Attacks: A Comparative Study of the AES Proposals")