dude, is my code constant time?
Non-constant time crypto code is dangerous. Exactly 20 years ago Kocher presented the first timing attack on a cryptographic implementation. Since then, a long list of implementations have been broken by timing attacks.
Naturally, there are countermeasures in place, even in popular open source crypto libraries. However, those countermeasures are rarely publicly tested for effectiveness. Some timing countermeasures are just baked into the code, without a test harness that could provide some degree of confidence that the countermeasure is sound. In many cases, however, shit happens and things can go wrong (for example, your compiler may get in your way).
How do we test if a piece of code runs in constant time or not? Not easy. (Otherwise every crypto library would be using it.) It turns out that, in general, it is not enough to look at the C code, or even at the assembly output.
There are already several tools available out there:
- ctgrind. This is a patch to valgrind by Langley. Essentially ctgrind monitors secret-dependent memory accesses and program flow jumps. (There is an updated patch by Aumasson, but similar things can be achieved just by running stock valgrind with uninitialized secret data.)
- ctverif. This tool by Almedia, Barbosa, Barthe and Dupressoir is based on formal methods and static analysis.
- Flow-tracker. This tool by Rodrigues Silva “finds one or more static traces of instructions” that lead to timing variabilities.
I released dudect
:
a small tool to assess whether a piece of code runs in constant time or not.
The approach is easy and fundamentally different from previous approaches:
run the piece of code under test with different inputs, measure its execution time and apply statistics
(leakage detection).
This method is very simple and effective in nature.
We rely on actual measurements and not on any hardware model.
This is an important difference wrt previous approaches.
The resulting tool is fairly small (around 350 source code lines of C) and can run in a wide range of platforms (from high-end servers to embedded processors.)
The source code for dudect is available in github (public domain.)
Showcase: AES on x64 #
Let’s test the timing variability of two AES128 implementations in my laptop
(Haswell architecture).
The first implementation is the classic
Rijmen–Bosselaers–Barreto rijndael-alg-fst.c
(T-tables implementation for 32-bit processors).
I used clang
to compile dudect
and link it against rijndael-alg-fst.o.
The procedure starts by measuring the execution time for two input classes corresponding to two different input values. (The code calls the RDTSC instruction to get accurate cycle-level timing measurements.) We take roughly a million measurements (taking a few minutes) corresponding to both input values.
In the next figure I plotted two cumulative distribution functions (cdfs) for both distributions in orange and blue. We can see that a single AES execution takes under 250 cycles. More importantly, we see that the distributions for the two classes are clearly different, that is, we suspect there is timing leakage about the input data.
To check our hypothesis a bit more rigorously we can apply a statistical test. A natural match here is the Kolmogorov-Smirnov test, but a simpler test will do also. I applied a t-test to the previous dataset. The next figure shows the evolution of the t-statistic:
The t-statistic reaches huge values (>100). This is bananas and means that the two distributions are different, that is, there is information leakage on the execution time.
Now let’s switch to the bitsliced implementation. I took a bitsliced AES from the libsodium library (which comes from Schwabe porting Kasper’s code). The resulting cdfs are very similar –they are actually indistinguishable from naked eye in the following figure:
However, looking at a cdf alone may not be enough to determine that both distributions are equivalent (that is, there is no timing leakage). The next figure shows the results of several t-tests. The statistic value never crosses the 4.5 value, which indicates that we did not detected leakage, up to several million measurements.
Thus, as expected, the table implementation leaks timing information whereas the bitsliced doesn’t.
Other examples #
I’ve used dudect to test for constant-time some other implementations:
- a vector-permutation AES implementation by Hamburg.
- a curve25519-donna implementation running on an embedded 32-bit ARM7TDMI with an early-abort multiplier. In this case we split dudect: some parts run in the target platform and the statistics in a host computer.
Dependencies #
The source code is available from github. No exotic tools are needed to build this, just a C compiler. This code includes the AES examples below.
How it works #
The internals are described in our paper
Oscar Reparaz, Josep Balasch and Ingrid Verbauwhede
dude, is my code constant time?
DATE 2017
I leverage tools typically used in hardware side-channel evaluations, such as leakage detection tests, first published in a wonderful paper by Coron, Naccache and Kocher in 2000. Leakage detection is now bread and butter in hardware side-channel analysis.