Benchmarking memcmp() for timing attacks

We were interested in timing attacks against memcmp() for various reasons (CVE-2017-2624) and decided to explore the topic a bit further.

Timing attacks against memcmp() have been successful in the past against light bulbs or even the Xbox 360.

The basic idea behind these kinds of attacks is, that memcmp() takes longer if the bytes of the memory areas match, since an additional byte will be compared. If this difference could be measured, an attacker could brute force secrets much more efficient by testing all values for the first byte, taking the one which took the longest to compare and then go on with testing all values for the second byte. The difference in timing is pretty small since only a few instructions differ in contrast to other widely abused timing attacks, like the timing attack against OpenSSH which allowed to enumerate the users. In the OpenSSH case, the password send to the daemon was only verified against the locally stored hash, if the user exists, if the user did not exists, there was no hash to compare against and the login attempt was rejected instantly. In order to exploit this issue efficiently a very long password used, which takes a long time to hash. This increased the time between rejection of a existing user and a non existing one enough to be easily measurable over the network.

In order to protect against this, especially in cryptographically relevant code, there are several implementations of a timing constant memory comparisons.

How big is the timing difference when comparing "AA" to "BA"? This highly depends on the implementation of memcmp(). Some implementations use a block size compare to speed things up, others use modern instructions like SSE for faster comparisons. Take a look at the glibc implementation which is quite lengthy to achieve the best speed for all use cases. We decided to do a quick benchmark.

This of course highly depends on the system and the load on the machine. In order to reduce side influences we used nice to give the process the highest priority and pinned it to a single CPU using taskset. Furthermore you want to disable powersaving during the test to make sure that the CPU speed is not changing.

Lets take a look of two runs, one comparing two and the other comparing 64 bytes. We run each comparison a 10000000 times and add the timings. To reduce the impact of other tasks even further, we interleave the tests:

for (i = 0; i < count; i++) {
    a = get_ticks();
    comp(cookiegood, cookie, comparesize);
    b = get_ticks();
    totalg += (b - a);

    a = get_ticks();
    comp(cookiebad, cookie, comparesize);
    b = get_ticks();
    totalb += (b - a);
}    

How to measure the timing? We have opted to use rdtsc, which returns the processors time stamp counter, which is usually considered a high-resolution timer with low overhead. This is another reason why we bind the program to a single CPU using taskset, since the counters on various CPUs could differ.

Disclaimer: In our benchmark, not all functions have the exactly the same behaviour, some just return that there is a difference, others return the difference between the first non-matching bytes.

What are the results of a run when only two bytes are compared? Note: our source can be found here

Version Equal Unequal Difference Faster Version
glibc 001395356192 001394972053 000000384139 b
naiive 001450446420 001399492504 000050953916 b
blockbased 001477100272 001407210544 000069889728 b
builtin 001393116852 001393273220 000000156368 g
fastmemeq 001517470488 001447338372 000070132116 b
consttime 001803111820 001803071588 000000040232 b
timingsafe 001783485212 001783893148 000000407936 g
crypto 001524643216 001524825004 000000181788 g
openssl 001382549144 001382676276 000000127132 g
sse2 001579218680 001583962136 000004743456 g

How does this differ for 64 bytes?

Version Equal Unequal Difference Faster Version
glibc 001459868600 001449436793 000010431807 b
naiive 006893595988 001406745332 005486850656 b
blockbased 002008822664 001523502340 000485320324 b
builtin 001453912568 001443792076 000010120492 b
fastmemeq 002505249908 001411098452 001094151456 b
consttime 015470300784 015470952360 000000651576 g
timingsafe 013019553596 012996265528 000023288068 b
crypto 006730822580 006727159920 000003662660 b
openssl 002673272920 002692763332 000019490412 g
sse2 002487218616 001835804324 000651414292 b

What we can easily see, even for the naiive implementation, we do not get a time that is 32 times longer when comparing equal strings. This means there is a high calling/setup overhead.

The second view reveals, that for some implementations, the equal memory areas are compared faster than the differing ones. This is for example the case for the consttime and openssl implementation in the 64 Byte run. The other timing safe implementations flicker. If several runs are performed sometimes the equal and sometimes the unequal cases take longer, depending on context switches and other load happening on the box. Furthermore it is clearly visible, that it is possible to perform timing attacks against memcmp() if the implementation is not fully optimised but not on all systems.

In conclusion, it highly depends on the circumstances if a memcmp() is subject to a timing attack.

Update: We were asked by @PaulM, if we did disable hyperthreading. In our experiments, HT did not make a difference, we assume because we bound the process to a single CPU.

Author: Eric Sesterhenn
Date: 2017-04-20 00:00:00 +0200