Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I read the paper Cache-timing attacks on AES (by Daniel J. Bernstein), but I don't seem to understand everything. The author dedicates a long section on how to prevent the OS to interrupt an AES computation. But how does this leak any information? Yes, the calculation takes more time than usual, but it is not dependent on the input?

(This is a follow-up to AES timing attacks.)

share|improve this question

2 Answers 2

up vote 9 down vote accepted

The paper explains why. Preventing the OS from interrupting the AES computation is part of Bernstein's proposed method of defense against cache-based timing attacks. Let me sketch the argument for you:

  • The early part of the paper explains that if the time is variable, then it introduces a risk of timing attacks. Sections 3-6 demonstrate that such an attack is practically feasible.

  • This raises the question of how to provide high assurance that we have stopped these attacks -- and not just the ones we know about, but the entire class of timing attacks. Bernstein argues that the best defense against this class of attacks is to ensure that the running time for the AES computation is constant, and independent of the inputs. See Section 8.

  • So, this raises the question of what we need to do to ensure that the AES computation is timing-independent. The remaining sections identify some challenges, and outline solutions.

  • In particular, Sections 10-11 point out that cache effects can cause timing variability. And, it is easy to see how this could affect security: cache effects mean that the time taken depends upon the address you look up, and the design of AES means that (if you use table lookups in the obvious way) the address you look up depends upon the key. Indeed, this is almost certainly exactly the effect that enabled the attack in Sections 3-6.

  • So the next question is, how do we ensure that cache effects don't introduce timing variability? The natural solution is: load the entire table into L1 cache, lock it into L1 cache, and make sure it doesn't get kicked out at any point during the AES computation. However, this natural solution has a problem, on time-sharing operating systems: the OS might preempt us at any point and run some other task. If that happens, it screws up our defense, by evicting our pre-loaded values from the L1 cache.

    In particular, if our pre-loaded values get evicted from the L1 cache, we're back to the vulnerable situation where we started. Now the total time taken depends upon the sequence of addresses looked up. For instance, if you look up the same index in the table twice, it'll be faster than looking up two separate indices -- so we might leak information about whether table lookups use the same indices or different indices. However, in (a natural implementation of) AES, those indices are key-dependent. Thus, this timing leak might leak information about key-dependent values: it'll leak whether two intermediate values are equal, where both intermediate values depend upon some key material. This leaked information can plausibly be used to learn some partial information about the key material, thus creating exactly the sort of side-channel attack we're trying to stop.

  • To prevent this, we need to have some way to be sure that this sort of bad outcome won't happen. The obvious way to be sure is to somehow introduce some mechanism to ensure the AES computation cannot be interrupted. If the AES computation cannot be interrupted, then we eliminate the risk of attacks based upon such interruptions. So, that's what Bernstein proposes.

  • Bernstein goes on to argue that this is the only solution he is aware of, that meets the requirements. In particular, the key requirement here is "we need a way to be confident (with high assurance) that there are no attacks".

    Does this mean I can tell you with certainty that there is no other defense? Of course not. It just means that someone smart studied this and came to the conclusion that, at the moment, the highest-assurance solution appears to be preventing interruptions by the OS. If someone else wants to argue that this is unnecessary, the burden is on them to show that their alternative is guaranteed to be free of attacks.

Please understand that an important principle of cryptography is: just because you can't think of any attacks, doesn't mean no attacks are possible. In cryptography, there's a big difference "no evidence that an attack is possible" vs "evidence that no attack is possible". It's not uncommon for cryptographic schemes that are justified on the basis that the designer couldn't think of an attack (in other words, couldn't find any evidence that an attack is possible) to get broken. For that reason, cautious cryptographers often aim for the goal of demonstrable evidence that the system is secure (finding positive evidence that no attack is possible). This is harder, but a more solid foundation for security.


That said, it's important to understand that this paper represents Bernstein's recommendations, which are somewhat at odds with the conventional wisdom of the rest of the community. Most of the cryptographic community doesn't bother with preventing the OS from interrupting the AES computation, on the theory that they don't know of any attack that's practical enough to pose a significant risk to their system as deployed in the wild. Basically, they judge that the risk of such an attack is low enough that they are willing to accept the risk. They may be right. Or they may not. Either way, my answer above is predicated on the assumption that you want to understand Bernstein's argument, so you can form your opinion about whether you are convinced or not. I'm not trying to take a position on whether Bernstein is right or whether the conventional wisdom is right, just trying to respond for your request for help understanding the paper.

share|improve this answer
    
Great explanation. Have an upvote! –  Stephen Touset Nov 30 '12 at 20:43

If I recall correctly the idea is to deduce key bits via the uneven S_BOX lookup timings. Since the time for a lookup varies widly depending wether or not a given variable is in cache or not a solution might be to make sure to have all S_BOXes in cache for the entire computation. Unfortunately even if that was possible an interrupt could cause the cache to be emptied and we're right back where we started

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.