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