3 ms·

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 a

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.

TheLoneWolfling 12y ago
Have you checked to make sure that, for example, the kernel entry flag save / restore (i.e. PUSHFQ/POPFQ, etc.) doesn't take data-dependent time? Also, what about context switches in general? Stack memory can be zeroed to start. If you're writing zeros to the stack on a context switch I could see that being a different amount of time taken than if it's not zero. Due to the CPU not having to publish the memory write. This would be the case with any predictable value in the cache, not just zeros. It seems to me that all values that affect registers could potentially turn into a memory access. Due to context switching. Or am I missing something here?
- pascal_cuoq 12y ago
  > Have you checked to make sure that, for example, the kernel entry flag save / restore (i.e. PUSHFQ/POPFQ, etc.) doesn't take data-dependent time? One only needs to trust the timings of instructions that one actually needs to implement cryptography. I admit I had not even considered whether an interruption and a visit through the scheduler could take an amount of time that depended of secrets; on some architectures it is possible to write code on purpose to leak secrets through this channel (a flag indicates whether multimedia registers are used, and these register, which can represent large amounts of memory to read and write, are only saved if they are used). But this is something developers would have to go out of their way to use. The implementation of cryptographic primitives should not require the flags to depend on secrets, so we can simply forbid this from happening rather than having to consider the execution times of all comparatively exotic instructions that handle the flags. > If you're writing zeros to the stack on a context switch I could see that being a different amount of time taken than if it's not zero. Due to the CPU not having to publish the memory write. Is this not the same question as the one in the StackOverflow question at http://stackoverflow.com/questions/29149058/does-memory-dependence-speculation-prevent-bn-consttime-swap-from-being-constant http://stackoverflow.com/questions/29149058/does-memory-depe... ? I don't know, but someone who knows more about current micro-architectures than me thinks that instructions writing to memory takes the same execution times (see definition above) whether the value written is the same as the old value or not. > It seems to me that all values that affect registers could potentially turn into a memory access. You need to keep track of what register values depend on secrets. This is what ctgrind does. ctgrind warns when a register that has been computed from a secret is used for branching or memory access: https://www.imperialviolet.org/2010/04/01/ctgrind.html https://www.imperialviolet.org/2010/04/01/ctgrind.html I made an equivalent version for C source (if you can separately convince yourself that your C compiler translates the C to assembler naively. This is another interesting question, but sometimes C source is what you have, so C source is what you need to verify) http://blog.frama-c.com/index.php?post/2011/12/31/Do-not-use-AES-in-a-context-where-timing-attacks-are-possible http://blog.frama-c.com/index.php?post/2011/12/31/Do-not-use... I have written a ton of articles on “C source code might not be translated to assembly that does what you think” and I have the trademark on that phrase, so please do not change the discussion to that of the compilation of C, it is a separate problem. Ctgrind and Frama-C already work fine for symmetric cryptography, where they can help you check that the execution time does not depend on secrets simply by never using a secret in a branch or in the computation of an address of a memory access. - that leaves the question of whether the time taken by the memory access can depend on the value being read. This is the StackOverflow question. Don't ask me, kidnap the family dogs of executives at Intel, AMD and ARM and get them to describe the current behavior of modern processors. Get them to make a few crucial promises for future processors while you're at it. - it is not reasonable to constrain asymmetric cryptography to be implemented without memory accesses to addresses depending on secrets. The argument is going to need to be more subtle, saying that all possible secrets lead to the same instruction time. I am not sure how ctgrind could be adapted for this new challenge, but the good news is that Frama-C is very good at handling lots of possible values for variables and at computing program properties that hold for all these values.

TheLoneWolfling 12y ago

Have you checked to make sure that, for example, the kernel entry flag save / restore (i.e. PUSHFQ/POPFQ, etc.) doesn't take data-dependent time? Also, what about context switches in general? Stack memory can be zeroed to start. If you're writing zeros to the stack on a context switch I could see that being a different amount of time taken than if it's not zero. Due to the CPU not having to publish the memory write. This would be the case with any predictable value in the cache, not just zeros. It seems to me that all values that affect registers could potentially turn into a memory access. Due to context switching. Or am I missing something here?

pascal_cuoq 12y ago
> Have you checked to make sure that, for example, the kernel entry flag save / restore (i.e. PUSHFQ/POPFQ, etc.) doesn't take data-dependent time? One only needs to trust the timings of instructions that one actually needs to implement cryptography. I admit I had not even considered whether an interruption and a visit through the scheduler could take an amount of time that depended of secrets; on some architectures it is possible to write code on purpose to leak secrets through this channel (a flag indicates whether multimedia registers are used, and these register, which can represent large amounts of memory to read and write, are only saved if they are used). But this is something developers would have to go out of their way to use. The implementation of cryptographic primitives should not require the flags to depend on secrets, so we can simply forbid this from happening rather than having to consider the execution times of all comparatively exotic instructions that handle the flags. > If you're writing zeros to the stack on a context switch I could see that being a different amount of time taken than if it's not zero. Due to the CPU not having to publish the memory write. Is this not the same question as the one in the StackOverflow question at http://stackoverflow.com/questions/29149058/does-memory-dependence-speculation-prevent-bn-consttime-swap-from-being-constant http://stackoverflow.com/questions/29149058/does-memory-depe... ? I don't know, but someone who knows more about current micro-architectures than me thinks that instructions writing to memory takes the same execution times (see definition above) whether the value written is the same as the old value or not. > It seems to me that all values that affect registers could potentially turn into a memory access. You need to keep track of what register values depend on secrets. This is what ctgrind does. ctgrind warns when a register that has been computed from a secret is used for branching or memory access: https://www.imperialviolet.org/2010/04/01/ctgrind.html https://www.imperialviolet.org/2010/04/01/ctgrind.html I made an equivalent version for C source (if you can separately convince yourself that your C compiler translates the C to assembler naively. This is another interesting question, but sometimes C source is what you have, so C source is what you need to verify) http://blog.frama-c.com/index.php?post/2011/12/31/Do-not-use-AES-in-a-context-where-timing-attacks-are-possible http://blog.frama-c.com/index.php?post/2011/12/31/Do-not-use... I have written a ton of articles on “C source code might not be translated to assembly that does what you think” and I have the trademark on that phrase, so please do not change the discussion to that of the compilation of C, it is a separate problem. Ctgrind and Frama-C already work fine for symmetric cryptography, where they can help you check that the execution time does not depend on secrets simply by never using a secret in a branch or in the computation of an address of a memory access. - that leaves the question of whether the time taken by the memory access can depend on the value being read. This is the StackOverflow question. Don't ask me, kidnap the family dogs of executives at Intel, AMD and ARM and get them to describe the current behavior of modern processors. Get them to make a few crucial promises for future processors while you're at it. - it is not reasonable to constrain asymmetric cryptography to be implemented without memory accesses to addresses depending on secrets. The argument is going to need to be more subtle, saying that all possible secrets lead to the same instruction time. I am not sure how ctgrind could be adapted for this new challenge, but the good news is that Frama-C is very good at handling lots of possible values for variables and at computing program properties that hold for all these values.