Automated dynamic analysis for timing side-channels.
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.
Most timing side-channels are rooted in one of the following three causes:
if(key[i] == 0)
s[i] = substitution_table[key[i]]
key[i] / c
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.
This section demonstrates how TIMECOP's dynamic analysis can be applied to other projects.
Requirements:
The following fileexample.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.
| 1 | #include "poison.h" |
| 2 | |
| 3 | int 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 | |
| 20 | int 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 | |
| 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 | } |
| 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.
TIMECOP applied the described analysis to over 2,700 implementations of cryptographic algorithms. The results are sorted hierarchically, following the structure of the SUPERCOP benchmarking suite.
crypto_aead)
crypto_auth
crypto_box
crypto_core
crypto_dh)
crypto_encrypt)
crypto_hash)
crypto_hashblocks
crypto_kem)
crypto_onetimeauth
crypto_rng
crypto_scalarmult
crypto_secretbox
crypto_sign)
crypto_sort
crypto_stream)
crypto_verify
| 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 |
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.
To reproduce these results, or to generate new results for a future version of SUPERCOP, follow these instructions:
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.
path/to/supercop with the
path to your SUPERCOP installation, and
replace YYYYMMDD with the version of your
SUPERCOP installation.
path/to/supercop with the
path to your SUPERCOP installation.--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.
--track-origins=yes option, Valgrind 3.4.0
or newer is required.
valgrind.h
and memcheck.h into SUPERCOP's include
directory. These headers are provided by Valgrind.
locate might be of help:
poison.h into
SUPERCOP's include directory.
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
Finally, you can use the environment
variable SUPERCOP_SKIP_VALGRIND to skip variable-time
measurements in a patched SUPERCOP version.