[openssl-dev] curve25519

[Pascal Cuoq]

Dmitry Belyavsky <beldmit at gmail.com> wrote:

> BTW, is there any tool for checking C code whether it is constant-time?

Short answer:

No tools that are useful for usable implementations of asymmetric cryptography, that I know of, but useful tools for confirming that symmetric cryptography designed for constant-time implementation was correctly implemented.

Long answer:

The C standards says nothing about execution time;  the 600+ pages of the latest (C11) one only describe the functional effects of defined C programs. But if you are willing to assume that your knowledge about the time taken by assembly instructions is correct, you can check that the execution time of a piece of assembly code does not depend on secrets (at least the dependencies of instructions' outputs with respects to their inputs is well documented and understood, so it is possible to know which of the inputs of the sequence an intermediate value depends on; what isn't documented is what inputs of an instruction can influence the execution time of that instruction). If you are willing to add the assumption that the C compiler translates a program line by line to the straightforward corresponding assembly, it is theoretically possible to check the same property for C code.

Following this line of reasoning gives you two tools that you can use:

- ctgrind, by agl, based on Valgrind.
https://github.com/agl/ctgrind
https://www.imperialviolet.org/2010/04/01/ctgrind.html
 Valgrind works at the binary level but you just assumed that compilation from C to binary was straightforward. ctgrind checks that the secrets are not used in the computation of addresses or in conditionals along one execution path. The property that it provides is more general than it looks, because since it checks that execution does not depend on the secrets in this way, you can infer that if the secrets had been different, the same property would have held. However, using ctgrind once only provides a guarantee for the particular values of non-secret inputs that were used. In this context, key length and message length are non-secret inputs, so if you checked with ctgrind that execution time did not depend on secrets for key length=512, that doesn't mean it's also the case for key length=1024, and if you check that a message of length 64 is encoded in “constant time” by a symmetric cipher, that does not prove that a message of length 65 is.

- experimental options of the existing Frama-C dependency plug-in:
http://blog.frama-c.com/index.php?post/2011/12/31/Do-not-use-AES-in-a-context-where-timing-attacks-are-possible
I wrote these (the full story is in the blog post, no point in repeating it here). This works on C, which in this case is a drawback (it means that you have no choice but to assume that the C compiler translates a program line by line to the straightforward corresponding assembly, which is not true of existing compilers and will only become more untrue as time passes.

There are two problems with both these approaches:

- the assumption about knowledge about the time taken by assembly instructions. Both Frama-C and, to the best of my knowledge, ctgrind, ignore intermediate values computed from secrets and passed as arguments to the division instruction. On a modern processor the execution time of division reveals information about its inputs:
http://users.elis.ugent.be/~brdsutte/research/publications/2012TACOvancleemput.pdf (“Compiler Mitigations for Time Attacks on Modern x86 Processors”). There is no theoretical difficulty in adding division as an instruction that both tools watch for, but currently, they don't watch for it.
Another example: shift is usually constant-time nowadays, but its execution time used to depend on its second input, and this could still be the case on a processor designed for low consumption
Another example: cmov takes constant time on current processors, but in the next generation of Intel processors, cmovcc mem, reg will be faster when the condition is false (joke: I do not actually know that, but there is no official commitment on the part of Intel that would disprove it, either).
Another example: it is possible to conceive a memory dependence speculation system in which reading at address A after a secret-dependent value has been written at address A is faster if the value that was written turned out to be identical to the value that was previously at address A:
http://stackoverflow.com/a/29949891/139746
So to summarize the first problem, there are a lot of assumptions. That doesn't prevent going forward, and taking any new discovery of an information leak through timing as a bug and fixing them as flaws are discovered in our assumptions, but you won't be “checking” that C code is “constant-time” in the sense that you might check the proof of a theorem. But even more serious is the second problem:

- no current implementation of asymmetric cryptography primitives for a general-purpose processor without special support would be fast enough to be used if it was written to be constant-time according to the above criteria.
The above methods work fine to check that the implementor did not mess up the implementation of a symmetric cipher that was designed to be implemented as “constant-time”. But implementations of asymmetric cryptography intended for real use, in OpenSSL or elsewhere, when they try to be “constant-time”, do not absolutely avoid dereferencing addresses computed from secrets. Instead they lay out the data to access so that, with low-level assumptions about cache line sizes and the internals of modern processors, the time taken to access a group of addresses computed from secrets take the same time for all values of the secrets. You could call it a false positive of the tools ctgrind and Frama-C, but the end result is that you cannot use these tools to check that your usable asymmetric cryptography implementation is constant-time, because they will tell you that it's not. Also you should bear in mind that when implementing cache-aware constant-time look-up tables, you are really assuming a lot of things about the behavior of the processor.
By the same token, ctgrind and Frama-C will tell you that the third solution in the blog post below, “[AES implemented with] a single 256-bytes S-box”, has execution time that depends on secrets, because it fails their criterion although it was designed so that the amount of information was so low as to be (probably) impossible to exploit.
https://securityblog.redhat.com/2014/07/02/its-all-a-question-of-time-aes-timing-attacks-on-openssl/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150621/0642c5f7/attachment-0001.html>