Timing Attacks

Say I want to implement a server with a basic API key. I would probably write header_value == api_key somewhere to ensure access is only granted with the correct key. But this is not safe, as it opens the door to timing attacks. Why is that? I want to figure out why this is the case in Rust.

In this case I’m comparing two instances of &str. Writing x == y is sugar for x.eq(y) where eq is a method from the PartialEq trait. The first thing I want to check is the impl PartialEq for str:

impl const PartialEq for str {
    fn eq(&self, other: &str) -> bool {
        self.as_bytes() == other.as_bytes()
    }
}

str::as_bytes returns &[u8] so I have to keep looking. The comparison for slices is implemented like this:

impl<T, U> const PartialEq<[U]> for [T]
where
    T: [const] PartialEq<U>,
{
    fn eq(&self, other: &[U]) -> bool {
        let len = self.len();
        if len == other.len() {
            unsafe { SlicePartialEq::equal_same_length(self.as_ptr(), other.as_ptr(), len) }
        } else {
            false
        }
    }
}

Aha! Rust checks if the two slices are the same length and if not immediately returns false. Knowing this, I can already say that an attacker might be able to infer the length of my api_key, given that the function equal_same_length takes some more time. equal_same_length is defined here:

const trait SlicePartialEq<B> {
    unsafe fn equal_same_length(lhs: *const Self, rhs: *const B, len: usize) -> bool;
}

It’s a trait though. The actual implementation for types that are BytewiseEq looks like this:

impl<A, B> const SlicePartialEq<B> for A
where
    A: [const] BytewiseEq<B>,
{
    unsafe fn equal_same_length(lhs: *const Self, rhs: *const B, len: usize) -> bool {
        unsafe {
            let size = crate::intrinsics::unchecked_mul(len, Self::SIZE);
            compare_bytes(lhs as _, rhs as _, size) == 0
        }
    }
}

(A slice of u8 implements the marker trait BytewiseEq.)

equal_same_length calls the compare_bytes function that is defined like this:

pub const unsafe fn compare_bytes(left: *const u8, right: *const u8, bytes: usize) -> i32;

This function is part of the std::intrinsics module that contains functions that are built into the compiler. That’s the reason it has no body. There is no further Rust implementation and the compiler will handle this function in a special way. Fortunately, the documentation for compare_bytes tells me where to continue looking.

This underlies things like <[u8]>::cmp, and will usually lower to memcmp.

This feels like I’m getting close to the finish line. memcmp is part of libc. The man page for memcmp(3) says:

Do not use memcmp() to compare confidential data, such as cryptographic secrets, because the CPU time required for the comparison depends on the contents of the addresses compared, this function is subject to timing-based side-channel attacks.

Aha! Finally an authoritative source that confirms my initial suspicions. But… Why is it subject to timing-based attacks? I think I need to dig a little deeper.

The implementation for this function in glibc is pretty involved but the core idea that allows timing attacks is apparent: Compare bytes until a difference is found, then stop. This optimization is great for day-to-day use. There is no need to waste time comparing more bytes when you already know the strings are not equal. But an attacker might be able to see that the longer the comparison takes, the more of a secret they have correct.

Just out of curiosity, and because I found memcmp in glibc hard to read I checked out the implementation in musl:

int memcmp(const void *vl, const void *vr, size_t n)
{
	const unsigned char *l=vl, *r=vr;
	for (; n && *l == *r; n--, l++, r++);
	return n ? *l-*r : 0;
}

It’s so nice. Relatively easy to read even for a non-C programmer like me. Here it is even more apparent that it is vulnerable to timing attacks. The loop will run until a difference in the strings is detected.

I tried to write a little demo for this attack that had two parts. One program takes a secret as an argument and exits with status 0 or 1 depending on whether the secret was correct. Another program tries to attack the other one by timing its execution. Computers are plenty fast though, so I was not able to detect any runtime differences depending on whether the secret was correct or not. But someone with more know-how in statistics might!

So to be safe instead of writing header_value == api_key use a crate like subtle which provides ct_eq that compares items in constant time.

if header_value.as_bytes().ct_eq(api_key.as_bytes()).into() {
    // ok!
}