How to compare strings in constant time?

Question

How does one safely compare two strings with bounded length in such a way that each comparison takes the same time? Hashing unfortunately has a timing attack vulnerability.

Is there any way to compare two strings without hashing in a way that is not vulnerable to timing-attacks?

Answer 1

TL;DR: Use assembly.

---

Constant Time code is really hard to pull off. To be truly constant time you need:

• a constant time algorithm,
• a constant time implementation of said algorithm.

---

What does "constant time algorithm" mean?

The example of string comparison is great. Most of the time, you want the comparison to take as little as possible, which means bailing out at the first difference:

fn simple_compare(a: &str, b: &str) -> bool {
    if a.len() != b.len() { return false; }

    for (a, b) in a.bytes().zip(b.bytes()) {
        if a != b { return false; }
    }

    true
}

The constant time version algorithm version however should have constant time regardless of the input:

• the input should always have the same size,
• the time taken to compute the result should be identical no matter where the difference is located (if any).

The algorithm Lukas gave is almost right:

/// Prerequisite: a.len() == b.len()
fn ct_compare(a: &str, b: &str) -> bool {
    debug_assert!(a.len() == b.len());

    a.bytes().zip(b.bytes())
        .fold(0, |acc, (a, b)| acc | (a ^ b) ) == 0
}

---

What does "constant time implementation" mean?

Even if the algorithm is constant time, the implementation may not be.

If the exact same sequence of CPU instructions is not used, then on some architecture one of the instructions could be faster, while the other is slower, and the implementation would lose.

If the algorithm uses table look-up, then there could be more or less cache misses.

---

Can you write a constant time implementation of string comparison in Rust?

No.

The Rust language could potentially be suited to the task, however its toolchain is not:

• the LLVM optimizer will wreak havoc with your algorithm, short-circuiting it, eliminating unnecessary reads, now or in the future,
• the LLVM backends will wreak havoc with your implementation, picking different instructions.

The short and long is that, today, the only way to access a constant time implementation from Rust is to write said implementation in assembly.

Answer 2

To write a timing-attack-safe string comparison algorithm yourself is pretty easy in theory. There are many resources online on how to do it in other languages. The important part is to trick the optimizer in not optimizing your code in a way you don't want. Here is one example Rust implementation which uses the algorithm described here:

fn ct_compare(a: &str, b: &str) -> bool {
    if a.len() != b.len() {
        return false;
    }

    a.bytes().zip(b.bytes())
        .fold(0, |acc, (a, b)| acc | (a ^ b) ) == 0
}

(Playground)

Of course, this algorithm can be easily generalized to everything that is AsRef<[u8]>. This is left as an exercise to the reader ;-)

---

It looks like there is a crate already offering these kinds of comparisons: consistenttime. I haven't tested it, but the documentation looks quite good.