5 ms·

> 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 ea

by 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
  Your operating system hits memory pressure and pages your RAM page to disk. Some time later it restores it. Hey, look, you've suddenly had an arbitrarily long delay. So you can't always finish early. Also, even assuming you can always finish early, that plan won't prevent, for example, measuring the delay of other responses. (As your process sleeping will have an impact on how fast other responses are sent. Due to cache pressure, in particular. But also due to CPU throttling, scheduling, etc, etc.

by jlebar 12y ago

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
Your operating system hits memory pressure and pages your RAM page to disk. Some time later it restores it. Hey, look, you've suddenly had an arbitrarily long delay. So you can't always finish early. Also, even assuming you can always finish early, that plan won't prevent, for example, measuring the delay of other responses. (As your process sleeping will have an impact on how fast other responses are sent. Due to cache pressure, in particular. But also due to CPU throttling, scheduling, etc, etc.