TIMECOP

Automated dynamic analysis for timing side-channels.

What it is

Even though modern CPUs and operating systems have various methods to separate processes from one another, some side-channels can remain that allow attackers to extract information across process, CPU [5], or even network boundaries [3].

One such side-channel can open up when the execution time of a piece of code depends on secret data. This class of vulnerabilities has been used succesfully in the past to extract encryption keys from AES, private keys from RSA, and other kinds of attacks.

Timing side-channels can be hard to spot in the wild, but they can be detected automatically to some degree with dynamic analysis. TIMECOP applies this analysis to the SUPERCOP benchmarking suite, covering over 2,700 implementations of cryptographic algorithms. The results are presented on this website.

How it works

Most timing side-channels are rooted in one of the following three causes:

  • Conditional jumps based on secret data [1]
    e.g. if(key[i] == 0)
  • Table lookups at secret indices [2], [3], [4], [5]
    e.g. s[i] = substitution_table[key[i]]
  • Variable-time CPU instructions operating on secret data [6],
    e.g. key[i] / c
    On Intel Pentium 4, the number of cycles for a division instruction depends on the arguments (as measured here and mentioned here)

Adam Langley described in 2010 how the first two types can be detected automatically using Valgrind.

Valgrind is a framework for dynamic code analysis that comes with a large range of tools for specific analysis tasks. One of those tools checks memory usage to identify memory leaks, use of uninitialized memory, read after free, and other common problems related to memory management.

When Valgrind checks for the use of uninitialized memory, it performs exactly the checks necessary to spot timing side-channels. By flagging secret data as uninitialized for Valgrind, it will report any cases where conditional jumps or table lookups are based on secret data.

TIMECOP takes Langley's idea and applies it to the numerous implementations of cryptographic algorithms collected in the SUPERCOP benchmarking suite.

Limitations
  • Valgrind cannot spot cases where variable-time code is caused by variable-time CPU instructions.
  • The analysis has only been tested on C and C++ code, and might not produce meaningful or correct output for other languages.
  • Some implementations mix public and secret data for various reasons. For example, in some implementations, the secret key also contains a copy of the public key. This can cause TIMECOP to flag an implementation as variable-time, even though the timing variances depend on public data. Refer to the page on each operation to see exactly what data is flagged as secret.
save_alt Download

Example

This section demonstrates how TIMECOP's dynamic analysis can be applied to other projects.

Requirements:

The following file example.c shows a variable-time implementation of modular exponentiation. Modular exponentiation is used in a number of cryptogragphic primitives, and most prominently in Diffie-Hellman. We are going to check this implementation for timing side-channels.
cat <<EOF >example.c
1#include "poison.h"
2
3int modular_pow(int base, int exponent, int modulus) {
4 if(modulus == 1) {
5 return 0;
6 }
7
8 int result = 1;
9 base = base % modulus;
10 while(exponent > 0) {
11 if (exponent % 2 == 1) {
12 result = (result * base) % modulus;
13 }
14 exponent = exponent >> 1;
15 base = (base * base) % modulus;
16 }
17 return result;
18}
19
20int main(int nargs, char** args) {
21 int modulus = 65535;
22 int base = 123;
23 int exponent = 981357566;
24 // mark the exponent as secret

Let us assume that the exponent is secret. For this, we poison the variable containing the exponent. This function is provided by poison.h which we included on line 1.

25 poison(&exponent, sizeof(int));
26 // Note that it's not necessary to pass the secret value
27 // as a reference.
28 int result = modular_pow(base, exponent, modulus);
29
30 return result;
31}
EOF
We then compile the code
$ clang -O0 -g -Wall -o example example.c
and run it through Valgrind
$ valgrind --track-origins=yes ./example
yielding this output:
1==9133== Memcheck, a memory error detector
2==9133== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
3==9133== Using Valgrind-3.15.0.GIT and LibVEX; rerun with -h for copyright info
4==9133== Command: ./example
5==9133==
6==9133== Conditional jump or move depends on uninitialised value(s)
7==9133== at 0x4004F8: modular_pow (example.c:10)
8==9133== by 0x4005DF: main (example.c:28)
9==9133== Uninitialised value was created by a client request
10==9133== at 0x4005C6: main (example.c:25)
11==9133==
12==9133== Conditional jump or move depends on uninitialised value(s)
13==9133== at 0x400514: modular_pow (example.c:11)
14==9133== by 0x4005DF: main (example.c:28)
15==9133== Uninitialised value was created by a client request
16==9133== at 0x4005C6: main (example.c:25)
17==9133==
18==9133==
19==9133== HEAP SUMMARY:
20==9133== in use at exit: 0 bytes in 0 blocks
21==9133== total heap usage: 0 allocs, 0 frees, 0 bytes allocated
22==9133==
23==9133== All heap blocks were freed -- no leaks are possible
24==9133==
25==9133== For lists of detected and suppressed errors, rerun with: -s
26==9133== ERROR SUMMARY: 61 errors from 2 contexts (suppressed: 0 from 0)

As expected, Valgrind discovered the two lines which depend on the value of the exponent: In example.c:10, the exponent is used as the exit condition of the while loop. The value of the exponent will influence the number of loop iterations. In example.c:11, the exponent is used in an if-condition, and its value will determine whether or not the if-branch is taken.

Finally, Valgrind also reports that these findings are explicitly rooted in the poisoning we did in example.c:25.

Using TIMECOP

To run this analysis on your own code, all you need is a fairly recent version of Valgrind, as well as the following header file:
cat <<EOF >poison.h
1// this code is released into the public domain
2#ifndef POISON_H
3#define POISON_H
4
5#include "memcheck.h"
6
7/**
8 Poisons a memory region of len bytes, starting at addr, indicating that
9 execution time must not depend on the content of this memory region.
10
11 Use this function to mark any memory regions containing secret data.
12 */
13#define poison(addr, len) VALGRIND_MAKE_MEM_UNDEFINED(addr, len)
14
15/**
16 Use this function to indicate that the specified memory region does no longer
17 contain data that must not affect execution time.
18 */
19#define unpoison(addr, len) VALGRIND_MAKE_MEM_DEFINED(addr, len)
20
21
22/**
23 Checks whether the memory region of len bytes, starting at addr,
24 contains any poisoned bits.
25
26 Returns 0 if the code is running natively, rather than within valgrind.
27 If valgrind is running, it returns the first address containing poisoned
28 data, or 0 if there is no poisoned data in the specified memory region.
29
30 You can use RUNNING_ON_VALGRIND from valgrind.h to check whether the code
31 is being executed within valgrind.
32
33 */
34#define is_poisoned(addr, len) VALGRIND_CHECK_MEM_IS_DEFINED(addr, len)
35
36#endif // POISON_H
EOF

The included memcheck.h is provided by Valgrind.

As you can see, the defined functions are simply wrappers around Valgrind's client request functions. Calling VALGRIND_MAKE_MEM_UNDEFINED(addr, len) instead of poison(addr, len) works just as well.

How to reproduce these results

To reproduce these results, or to generate new results for a future version of SUPERCOP, follow these instructions:

Preparation

  1. Get SUPERCOP
    Follow the instructions here to download and unpack SUPERCOP.
  2. Patch SUPERCOP
    Patches for SUPERCOP are readily available for the following versions:

    These patches are released into the public domain.

    How you proceed depends on whether there is a patch available for the version of your SUPERCOP installation.

    • If you are using one of the versions above, then you can simply download and apply that patch:
      $ SUPERCOP_VERSION=YYYYMMDD $ wget https://post-apocalyptic-crypto.org/timecop/supercop-${SUPERCOP_VERSION}.diff $ patch -p1 -d path/to/supercop < supercop-${SUPERCOP_VERSION}.diff
      Note: Replace path/to/supercop with the path to your SUPERCOP installation, and replace YYYYMMDD with the version of your SUPERCOP installation.
    • If you are using a newer version of SUPERCOP, run these commands instead:
      $ SUPERCOP_VERSION=20190816 $ wget https://post-apocalyptic-crypto.org/timecop/supercop-${SUPERCOP_VERSION}.diff $ patch --dry-run -p1 -d path/to/supercop < supercop-${SUPERCOP_VERSION}.diff
      Note: Replace path/to/supercop with the path to your SUPERCOP installation.
      By passing the --dry-run option in the last command, patch checks whether the latest patch can be applied without issues, but does not actually changes anything about your SUPERCOP installation in case of errors.
      If the last command exited without errors, run the following command to apply the latest patch:
      $ patch -p1 -d path/to/supercop < supercop-${SUPERCOP_VERSION}.diff
      However, if there were errors, and you cannot resolve them yourself, feel free to contact moritz@post-apocalyptic-crypto.org for help. Please include the version of SUPERCOP you are using, as well as the output of the commands above.
      Versions of SUPERCOP prior to 2018-11-13 are not officially supported.
  3. Install Valgrind
    Follow the instructions here to download and install Valgrind. TIMECOP was tested with Valgrind 3.15.0. To use the --track-origins=yes option, Valgrind 3.4.0 or newer is required.
  4. Copy the header files valgrind.h and memcheck.h into SUPERCOP's include directory. These headers are provided by Valgrind.
    If you cannot find the header files, locate might be of help:
    $ locate -b '\memcheck.h' '\valgrind.h'
  5. Copy TIMECOP's header file poison.h into SUPERCOP's include directory.

Measurements

With the above preparation, TIMECOP will automatically run variable-time analysis within a regular SUPERCOP run. Incremental benchmarks are currently not supported.

Note that you can set the environment variable SUPERCOP_SKIP_MEASUREMENTS to skip benchmarking measurements, in case you are only interested in the TIMECOP measurements.

So, to measure all implementations available in SUPERCOP, run

$ SUPERCOP_SKIP_MEASUREMENTS=true path/to/supercop/do-part all
Furthermore, you can follow these tips to measure a specific primitive, or to reduce measurements to specific compiler options.

Finally, you can use the environment variable SUPERCOP_SKIP_VALGRIND to skip variable-time measurements in a patched SUPERCOP version.

References

[1]
Onur Acıiçmez, Çetin Kaya Koç, Jean-Pierre Seifert, Predicting secret keys via branch prediction. In Proceedings of the 7th Cryptographers' Track at the RSA Conference on Topics in Cryptology
[2]
Yuval Yarom, Katrina Falkner, FLUSH+RELOAD: a High Resolution, Low Noise, L3 Cache Side-Channel Attack.
[3]
Daniel J. Bernstein, Cache-timing attacks on AES.
[4]
Paul C. Kocher, Timing Attacks in Implementations of Diffie-Hellman, RSA, DSS, and Other Systems.
[5]
Mehmet Sinan İnci, Berk Gülmezoğlu, Gorka Irazoqui, Thomas Eisenbarth, Berk Sunar, Seriously, get off my cloud! Cross-VM RSA Key Recovery in a Public Cloud.
[6]
Thierry Kaufmann, Hervé Pelletier, Serge Vaudenay, and Karine Villegas When Constant-time Source Yields Variable-time Binary: Exploiting Curve25519-donna Built with MSVC 2015.
Logo Font: Edge Racer by Daniel Zadorozny (Iconian Fonts)