"leakless" comparison of byte arrays (C vs Rust)

help
1

In git-crypt there is a function to compare char arrays that's called leakless_equals_chars which visits all elements of array before reporting back if they are the same or not:

static bool	leakless_equals_char (const unsigned char* a, const unsigned char* b, std::size_t len)
{
	volatile int	diff = 0;

	while (len > 0) {
		diff |= *a++ ^ *b++;
		--len;
	}

	return diff == 0;
}

My understanding is that they are using volatile to prevent compiler from optimizing so that while loop visits all members, this way we are not leaking any info on how different the arrays are by returning early upon first non-equal bytes.
Can the following rust snippet achieve the same goal without using ptr::read/write_volatile?

fn leakless_equals_char(a: &[u8], b: &[u8]) -> bool {
    let diff = a.iter()
        .zip(b.iter())
        .map(|(a, b)| a ^ b)
        .fold(0, |acc, x| acc | x);
    diff == 0 && a.len() == b.len()
}

How would you do this?

1 Like
2

In theory, with your snippet, there's nothing preventing the compiler from optimizing the loop to return early if any of the a ^ bs are nonzero. I'm not sure whether any current compilers actually implement such an optimization – I did some quick testing on gcc.godbolt.org and didn't find anything interesting – but a future compiler could. By contrast, the C version uses volatile to ensure the compiler treats the intermediate result as a 'black box'.

1 Like
3

Here are the relevant issues from Ring:
https://github.com/briansmith/ring/issues/95
https://github.com/briansmith/ring/issues/626

The TL;DR I think is that writing code, which is "officially" constant time is impossible, so the only way to guarantee constant-timentess is to directly verify the assembly.

1 Like
4

And even that may not be enough, as some low-level machine implementations have data-dependent timing variance of single instructions (e.g., multiply on ARM or PPC).

5 Likes
5

There is https://github.com/quininer/memsec and it uses std::ptr:::

/// Constant time `memeq`.
#[inline(never)]
pub unsafe fn memeq<T>(b1: *const T, b2: *const T, len: usize) -> bool {
    let b1 = b1 as *const u8;
    let b2 = b2 as *const u8;

    (0..len as isize)
        .map(|i| ptr::read_volatile(b1.offset(i)) ^ ptr::read_volatile(b2.offset(i)))
        .fold(0, |sum, next| sum | next)
        .eq(&0)
}

Why you need to do it without usage of std::ptr?

1 Like
6

Thanks for pointing out that crate.
I don't need to avoid std::ptr, question was more on how possibly Rust facilities could be used to avoid using C-style volatile trick to stop compiler from optimizing and getting constant time.
Additionally in the context I was doing this, avoiding that unsafe keyword would be a big bonus. However based on above answers it seems this is a problem without a 100 reliable solution.

7