7 ms·

The author's conclusion that side channel attacks are unpreventable because x86 instructions execute in a variable amount of time does not follow. Side channel

by jstarks 12y ago

The author's conclusion that side channel attacks are unpreventable because x86 instructions execute in a variable amount of time does not follow. Side channel attacks that rely on variable instruction timing rely on _content-dependent_ timing. For example, the time spent for a mov from a memory location does not depend on the contents of the memory, but it does depend on the address of that memory. If that address is a function of the key or plain text, then the mov will leak sensitive timing information. If not, then the mov will not. None of the author's various examples have anything to do with side channel attacks. The fact that xor eax,eax is just a register operation doesn't mean it can leak sensitive information.

deleted 12y ago
[deleted]
jlebar 12y ago
> The fact that xor eax,eax is just a register operation doesn't mean it can leak sensitive information. AIUI tfa's point is that you can't assume that xor eax,eax and xor eax,ebx take the same amount of time, because "x86 is a high level language". Similarly for his other examples. This, he claims, makes it difficult to write code that resists timing attacks, if you ever want to have a branch that does nothing. Thus the discussion of cmov.
- barrkel 12y ago
  The point of the grandparent's post is that timing information is only leaked if the CPU's timing is data dependent. It's not enough to show that different instructions take unpredictable amounts of time. If the sequence of CPU instructions that get executed are the same for varying data, then the unpredictability of the individual instructions doesn't create a timing attack. xor eax,eax scans, to an x86 assembly programmer, as "eax := 0". It's idiomatic for clearing a register. There ought not be any expectation from an assembly programmer that such a frequent operation would take the same amount of time as xor eax,ebx (in particular, xor eax,eax doesn't depend on the value of eax, so it doesn't need to stall waiting for its value to be calculated). But if xor eax,eax took a different amount of time depending on whether eax was equal to 42 or not, that would be a different matter.
  - TheLoneWolfling 12y ago
    Division on some processors takes a data-dependent amount of time. See riscy's comment.
- mreiland 12y ago
  Can someone explain to me why you wouldn't just count clock ticks at a higher level than the CPU? If the operation finishes early just... wait. I understand resolution and yes you'll probably only be w/i a delta of some sort, but isn't that the point? Why wouldn't that approach work?
  - jstarks 12y ago
    Even if you could figure out the worst-case timings and how to simulate them in all cases, the performance would be unacceptable. The usual operations that are data-dependent in crypto algorithms are mov with a data-dependent address, and conditional jump with a data-dependent condition. To slow these down, you'd have to simulate the absolute worst case, which means no caches of any kind, which means possibly thousands or even millions of cycles (to simulate a page fault from disk) for every operation of unknown duration. Crypto would become infeasible. There are much better ways to achieve this, by always computing both sides of a (logical) branch or using computation instead of branching or table lookups. You likely have to write this in assembly to be sure that the compiler doesn't "optimize" any of your tricks back into branches. Some of this is hard in older crypto algorithms (AES was designed to use table lookups in software), but newer crypto algorithms are much more amenable to safe implementation.
    - mreiland 12y ago
      you misunderstand me. Where the pause happens doesn't really matter, it doesn't have to be the cryptographic function. This honestly strikes me as mental masturbation, the sort of thing that can't be worked around in theory, but the chances of an attack being able to glean something useful from it is astronomically small. And I get what you're about to tell me, "I'm a terrible human being who shouldn't ever think about security". But nothing anyone has stated so far in this thread has made any sense to me. One guy started talking about ping returning faster if your machine is sleeping instead of calculating. That literally gets swallowed up in network latency, router congestion, cache misses due to load balancing, a few extra legitimate requests, and so forth. I just don't see it in practice.
  - TheLoneWolfling 12y ago
riscy 12y ago
Something interesting to note is that at least in the Pentium 4, the number of cycles spent on integer division instructions varies depending on the values of the operands [1]. [1] https://gmplib.org/~tege/x86-timing.pdf https://gmplib.org/~tege/x86-timing.pdf (pages 4 & 6)
- pascal_cuoq 12y ago
  This same property was also advertised as an improvement in a new generation of Intel processors a few years ago. I am pretty sure it was Haswell.
  - maleadt 12y ago
    A colleague of mine mentioned how this has been the case for quite a bit longer than Haswell, see "Compiler mitigations for time attacks on modern x86 processors" (from 2012). Or Agner Fog's timings pages, where many DIV instructions list widely ranging latencies, with the comment "[l]ow values are for small results, high values for high results".
    - pascal_cuoq 12y ago
      Thanks for the reference, that is much better than my vague recollections. What I remembered having seen advertised (presented as an improvement, of course) is new early-exit paths for the easier arguments to division. The marketing brochure emphasised the novelty, so I must have wrongly inferred that division took constant time before that. Considering paragraph 2.2 in http://users.elis.ugent.be/~brdsutte/research/publications/2012TACOvancleemput.pdf http://users.elis.ugent.be/~brdsutte/research/publications/2... , I may have been remembering a new division algorithm in Nehalem. I will cite that article from now on.
bo1024 12y ago
> The author's conclusion that side channel attacks are unpreventable The author never said anything about "unpreventable". > None of the author's various examples have anything to do with side channel attacks. I think the author was trying to point more directly toward the stackoverflow post that was linked, using the examples to point out that it was based on some faulty assumptions.
- pascal_cuoq 12y ago
  I wrote the StackOverflow post, and I don't see anything in the article that points faulty assumptions. Don't get me wrong, I am glad that someone wrote that article. I was going to write a similar one myself within a few days with all the details I didn't need to expand on in the StackOverflow question because anyone who could answer didn't need them. If you see any specific assumption that the article points out as faulty, I would be delighted to know which. The article does not even specifically answer the specific question of whether memory-dependence-speculative execution is always canceled when a write occurs that goes to the location that was read, or it is can sometimes not be canceled when the written value coincides with the previous value. It's either one or the other. This is one assumption that we could make, or not, (we'll try not to make it if it's faulty!). But no help there. The article doesn't say. ____________ Something I should clarify and that may be the cause of the misunderstanding (here, or in the article if the article really points out faulty assumptions—I'm not sure it does): It is called “constant-time programming” by tradition, but it is really “secret-independent-time-programming”, which does not roll off the tongue in the same way. Certainly, the execution time of the crucial instructions that directly handle cryptographic secrets depends on the state in which the previous instructions have left the processor. This is no big deal, because we are not trying to prove that this execution time is constant! We are only trying to prove that it does not depend on the secrets. And we do this by proving * that each instruction's execution time does not depend on the secret (this is what ctgrind does, with a basic but adequate set of assumptions on what the execution time of an instruction depends on. The time taken by xor eax, eax does not depend on the previous value of eax, and it doesn't matter that it is different from the time taken by xor eax, ebx. The time taken by xor eax, ebx does not depend on the values of these registers either. And so on. The only arguable chink in the ctgrind armor is integer division, which I don't know whether Adam Langley remembered to count as having an execution time that possibly depends on the value of its arguments—as pointed out in another thread). This works super well for symmetric cryptography. Seriously, problem solved! Now we just need to replace AES with a cipher implemented according to the new rules (the rules predate AES and the reference AES implementation does not follow them. And it would apparently be very difficult to build an AES implementation that would be efficient and that would follow the rules). * that we can subdivide the code into subgroups of instructions such that each subgroup's execution time does not depend on the secret. This is obviously going to be necessary for perfect “constant-time” asymmetric cryptography. Most subgroups are only one instruction (phew! for these the problem is no harder than above) but a few subgroups need to have more than one. The StackOverflow question is about one such subgroup. Another subgroup is going to be the instructions that access tables in a secret-dependent way. These two non-unitary subgroups of instructions are already written in a very careful way by crypto implementers, who have been aware of the issues for some time. I am only doing a second check, questioning assumptions, and perhaps building an automatic tool for checking that an implementation does not leak information through timing when executed on current, relatively well-understood micro-architectures (better than future micro-architectures that haven't been imagined yet anyway). “BUT THE ARTICLE SAYS ‘EXECUTION TIME’ IS A ABSTRACTION”, I hear you scream. Yes. Define “execution time(s)” of an instruction/a group of instructions as “any observable number of cycles in the interaction between the instruction(s) and any other instructions that could be placed around it. The goal is to make all execution times independent of all secrets. It is easy, because currently, apart from memory accesses, conditional jumps, and possibly division, all the execution times of an instruction are independent of the data it handles.

by jstarks 12y ago

deleted 12y ago

[deleted]

jlebar 12y ago

> The fact that xor eax,eax is just a register operation doesn't mean it can leak sensitive information. AIUI tfa's point is that you can't assume that xor eax,eax and xor eax,ebx take the same amount of time, because "x86 is a high level language". Similarly for his other examples. This, he claims, makes it difficult to write code that resists timing attacks, if you ever want to have a branch that does nothing. Thus the discussion of cmov.

barrkel 12y ago
The point of the grandparent's post is that timing information is only leaked if the CPU's timing is data dependent. It's not enough to show that different instructions take unpredictable amounts of time. If the sequence of CPU instructions that get executed are the same for varying data, then the unpredictability of the individual instructions doesn't create a timing attack. xor eax,eax scans, to an x86 assembly programmer, as "eax := 0". It's idiomatic for clearing a register. There ought not be any expectation from an assembly programmer that such a frequent operation would take the same amount of time as xor eax,ebx (in particular, xor eax,eax doesn't depend on the value of eax, so it doesn't need to stall waiting for its value to be calculated). But if xor eax,eax took a different amount of time depending on whether eax was equal to 42 or not, that would be a different matter.
- TheLoneWolfling 12y ago
  Division on some processors takes a data-dependent amount of time. See riscy's comment.
mreiland 12y ago
Can someone explain to me why you wouldn't just count clock ticks at a higher level than the CPU? If the operation finishes early just... wait. I understand resolution and yes you'll probably only be w/i a delta of some sort, but isn't that the point? Why wouldn't that approach work?
- jstarks 12y ago
  Even if you could figure out the worst-case timings and how to simulate them in all cases, the performance would be unacceptable. The usual operations that are data-dependent in crypto algorithms are mov with a data-dependent address, and conditional jump with a data-dependent condition. To slow these down, you'd have to simulate the absolute worst case, which means no caches of any kind, which means possibly thousands or even millions of cycles (to simulate a page fault from disk) for every operation of unknown duration. Crypto would become infeasible. There are much better ways to achieve this, by always computing both sides of a (logical) branch or using computation instead of branching or table lookups. You likely have to write this in assembly to be sure that the compiler doesn't "optimize" any of your tricks back into branches. Some of this is hard in older crypto algorithms (AES was designed to use table lookups in software), but newer crypto algorithms are much more amenable to safe implementation.
  - mreiland 12y ago
    you misunderstand me. Where the pause happens doesn't really matter, it doesn't have to be the cryptographic function. This honestly strikes me as mental masturbation, the sort of thing that can't be worked around in theory, but the chances of an attack being able to glean something useful from it is astronomically small. And I get what you're about to tell me, "I'm a terrible human being who shouldn't ever think about security". But nothing anyone has stated so far in this thread has made any sense to me. One guy started talking about ping returning faster if your machine is sleeping instead of calculating. That literally gets swallowed up in network latency, router congestion, cache misses due to load balancing, a few extra legitimate requests, and so forth. I just don't see it in practice.
- TheLoneWolfling 12y ago

riscy 12y ago

Something interesting to note is that at least in the Pentium 4, the number of cycles spent on integer division instructions varies depending on the values of the operands [1]. [1] https://gmplib.org/~tege/x86-timing.pdf https://gmplib.org/~tege/x86-timing.pdf (pages 4 & 6)

pascal_cuoq 12y ago
This same property was also advertised as an improvement in a new generation of Intel processors a few years ago. I am pretty sure it was Haswell.
- maleadt 12y ago
  A colleague of mine mentioned how this has been the case for quite a bit longer than Haswell, see "Compiler mitigations for time attacks on modern x86 processors" (from 2012). Or Agner Fog's timings pages, where many DIV instructions list widely ranging latencies, with the comment "[l]ow values are for small results, high values for high results".
  - pascal_cuoq 12y ago
    Thanks for the reference, that is much better than my vague recollections. What I remembered having seen advertised (presented as an improvement, of course) is new early-exit paths for the easier arguments to division. The marketing brochure emphasised the novelty, so I must have wrongly inferred that division took constant time before that. Considering paragraph 2.2 in http://users.elis.ugent.be/~brdsutte/research/publications/2012TACOvancleemput.pdf http://users.elis.ugent.be/~brdsutte/research/publications/2... , I may have been remembering a new division algorithm in Nehalem. I will cite that article from now on.

bo1024 12y ago

> The author's conclusion that side channel attacks are unpreventable The author never said anything about "unpreventable". > None of the author's various examples have anything to do with side channel attacks. I think the author was trying to point more directly toward the stackoverflow post that was linked, using the examples to point out that it was based on some faulty assumptions.

pascal_cuoq 12y ago
I wrote the StackOverflow post, and I don't see anything in the article that points faulty assumptions. Don't get me wrong, I am glad that someone wrote that article. I was going to write a similar one myself within a few days with all the details I didn't need to expand on in the StackOverflow question because anyone who could answer didn't need them. If you see any specific assumption that the article points out as faulty, I would be delighted to know which. The article does not even specifically answer the specific question of whether memory-dependence-speculative execution is always canceled when a write occurs that goes to the location that was read, or it is can sometimes not be canceled when the written value coincides with the previous value. It's either one or the other. This is one assumption that we could make, or not, (we'll try not to make it if it's faulty!). But no help there. The article doesn't say. ____________ Something I should clarify and that may be the cause of the misunderstanding (here, or in the article if the article really points out faulty assumptions—I'm not sure it does): It is called “constant-time programming” by tradition, but it is really “secret-independent-time-programming”, which does not roll off the tongue in the same way. Certainly, the execution time of the crucial instructions that directly handle cryptographic secrets depends on the state in which the previous instructions have left the processor. This is no big deal, because we are not trying to prove that this execution time is constant! We are only trying to prove that it does not depend on the secrets. And we do this by proving * that each instruction's execution time does not depend on the secret (this is what ctgrind does, with a basic but adequate set of assumptions on what the execution time of an instruction depends on. The time taken by xor eax, eax does not depend on the previous value of eax, and it doesn't matter that it is different from the time taken by xor eax, ebx. The time taken by xor eax, ebx does not depend on the values of these registers either. And so on. The only arguable chink in the ctgrind armor is integer division, which I don't know whether Adam Langley remembered to count as having an execution time that possibly depends on the value of its arguments—as pointed out in another thread). This works super well for symmetric cryptography. Seriously, problem solved! Now we just need to replace AES with a cipher implemented according to the new rules (the rules predate AES and the reference AES implementation does not follow them. And it would apparently be very difficult to build an AES implementation that would be efficient and that would follow the rules). * that we can subdivide the code into subgroups of instructions such that each subgroup's execution time does not depend on the secret. This is obviously going to be necessary for perfect “constant-time” asymmetric cryptography. Most subgroups are only one instruction (phew! for these the problem is no harder than above) but a few subgroups need to have more than one. The StackOverflow question is about one such subgroup. Another subgroup is going to be the instructions that access tables in a secret-dependent way. These two non-unitary subgroups of instructions are already written in a very careful way by crypto implementers, who have been aware of the issues for some time. I am only doing a second check, questioning assumptions, and perhaps building an automatic tool for checking that an implementation does not leak information through timing when executed on current, relatively well-understood micro-architectures (better than future micro-architectures that haven't been imagined yet anyway). “BUT THE ARTICLE SAYS ‘EXECUTION TIME’ IS A ABSTRACTION”, I hear you scream. Yes. Define “execution time(s)” of an instruction/a group of instructions as “any observable number of cycles in the interaction between the instruction(s) and any other instructions that could be placed around it. The goal is to make all execution times independent of all secrets. It is easy, because currently, apart from memory accesses, conditional jumps, and possibly division, all the execution times of an instruction are independent of the data it handles.