Constant-time string equality check

Question

This is my attempt to answer my own equally named question on SO. In this case, I need a method comparing two strings so that the running time is input independent.

// Not private in order to prevent optimizations.
static class Blackhole {
    private static void eat(long n) {
        dummy += n;
    }

    // Not private in order to prevent optimizations.
    static volatile long dummy;
}

public boolean areEqual(String input, String secret) {
    final int length = secret.length();
    // No need to keep the length secret.
    if (input.length() != length) {
        return false;
    }
    long delta = 0;
    for (int i = 0; i < length; ++i) {
        // Any char is interpreted as a non-negative number.
        // Xoring such numbers preserves non-negativity.
        // The result depends on every input bit, so no short-circuit is possible.
        // Overflow is impossible, therefore diff is zero <=> all chars are the same.
        delta += input.charAt(i) ^ secret.charAt(i);
    }
    Blackhole.eat(delta);
    return delta == 0;
}

It's a really short snippet and I'm mainly interested in ensuring that it really works in constant time. In particular, I'm afraid that the loop could indeed get optimized to something like

int i = 0
for (; ; ++i) {
    if (input.charAt(i) != secret.charAt(i)) break;
}
for (; i < length; ++i) {
    delta += input.charAt(i) ^ secret.charAt(i);
}

where the first loop could be faster on some architectures, as -- after unrolling -- it translates to load, xor with memory, and a conditional jump. Assuming some future architecture capable of executing 6 instructions per cycle when there are no data dependencies and no mispredictions, it could be a win. Or the JIT could believe, it makes sense...

Concerning the Blackhole, I wonder if volatile is necessary. I didn't want to depend on JMH nor copy this monster.

---

In the meantime I've got an idea avoiding volatile writes nearly perfectly

    private static void eat(long n) {
        if (n == dummy) {
            dummy = new SecureRandom().nextLong();
        }
    }

Answer 1

Firstly, we cannot rely on arguments that the "compiler isn't smart enough to do that" because that may change tomorrow. We need to base our assessment of the code on what the compiler is and isn't allowed to do.

Given two input strings and a yes/no return if the string match, any program performing the function can be transformed into the trivial short-circuited for-loop. Provided that there isn't anything prohibiting the compiler from doing the transform.

Will writing the sum of xor differences to a volatile prevent the transform? Maybe, it depends on the execution model and guarantees of volatile in Java. In C++ under the as-if rule all writes and reads to/from volatile memory regions must occur in the same order as-if the program was executed according to the wording in the standard (somewhat simplified but that's the gist of it). So for C++ this would work; However I'm unsure if Java has the same guarantee. For C++ this limitation is natural because it must be able to interface with device drivers and bus addresses where writes and reads cannot be re-ordered or omitted. But Java does none of the kind and as such I wouldn't be terribly surprised if volatile has a more lax meaning in Java.

What about SecureRandom? Well it is really just volatile reads from /dev/urand in disguise to get the seed, the rest is deterministic which the compiler that compiled the JVM isn't allowed to reorder or remove, but what the JIT is allowed to do in this context is beyond me. It is conceivable that the JIT can deduce that the read from /dev/urand will not affect the program in an observable way and it will remove the code all together.

If the volatile keyword doesn't have the same meaning in Java as in C++ I believe that doing this kind of processing in Java in a reliable and guaranteed way is difficult. I would consider a hand written loop in assembler in a JNI library, this is guaranteed by your C/C++/assembler to not be fudged in any way.

I'm sorry this isn't an authoritative yes/no answer on correctness, but I hope that it is of some help any way.

Answer 2

I'm sorry to burst the bubble, but achieving "constant time" in any environment where the compiler, a bytecode interpreter, or even the processor might optimize your code, is delusional.

This only works on very simple architectures where you control both the machine code, and know the precise hardware characteristics. With a Java compiler + Java VM + unknown hardware arch, you are far off from these requirements.

I'm serious about the hardware. Worst case would e.g. be the JVM inserting a NEQ test around the character XOR and addition, which could trigger the branch prediction in the processor to go onto the "fast path" as soon as it encounters the first 2-3 equal characters. That's not even in the code you've written, but it's a sensible optimization to be added by the JVM.

This is not even just about the "Blackhole" potentially being eliminated by the compiler, but being unable to assume even constant time for the actual comparison.

If you want constant time, there is only a single legit solution: Use a clock and then wait to enforce a constant execution time. Beware that in concurrent systems, getting the system into a state of starvation on CPU time will still allow an attacker to estimate the effective cost based on raw throughput.

Adding a random wait on authentication failures as suggested by others is a good start, but also suffers from the aforementioned issue. This is only reliable as long as the authentication is additionally rate limited to avoid the possibility of being CPU limited.

Answer 3

To avoid clever compiler optimizations simply instruct it that you want to count differences instead of matches:

int differences = 0, matches = 0;
for (int i = 0; i < length; ++i) {
    if ((input.charAt(i) ^ secret.charAt(i)) != 0)
        ++differences;
    else
        ++matches;
}

Then let's use differences value to call a function which side effect cannot be ignored (idea stolen from your updated question about Blackhole), this is just an example but something smarter may be done for sure:

try
{
    new SecureRandom().nextLong(differences);
}
catch (IllegalArgumentException) {
    // If argument is 0 (what we want for an exact match)
    // then nextLong() throws this exception
    return true;
}

return false;

In chat it has been widely discussed if/when compiler is allowed to perform some optimizations. I won't repeat that discussion here but also note that you may simply use loop counter outside the loop to stop any compliant compiler to apply any short-circuit:

int differences = 0, i= 0;
for (i = 0; i < length; ++i) {
    // ...
}

if (i != length - 1)
    throw new Exception("..."); // Is it better Error here?

I'm using if/else instead of differences += ... ? 1 : 0 to avoid JIT compiler to possibly generate CMOV instruction (or equivalent on your target architecture). Use matches somewhere to avoid compiler to optimize it away. You can ^ it with input.length() and add it to differences, for example.

---

Note that to determine exact string length is the very first step of a timing attack, only after that the attacker will start to work character by character. Your first check about string length matching will vanish 1/3rd of your work, let's work around it. Comparison time is always dictated by input string, this won't give any hint to an attacker about secret length.

int differences = 0, matches = 0;
for (int i = 0; i <= input.length(); ++i) {
    char secretChar = input.charAt(Math.min(input.length() - 1, i));
    if ((input.charAt(i) ^ secretChar) != 0)
        ++differences;
    else
        ++matches;
}

Now we have to change our final check to be sure length matched (otherwise a partial match or an empty string will be compared as equal). We can simply add input.length() ^ secret.length() to difference count, we just want it's zero:

    new SecureRandom().nextLong(differences + (input.length() ^ secret.length()));

---

Side note about Unicode: this code (as well as original one) is not really Unicode-friendly. A grapheme isn't equivalent to char and string comparison should be performed with normalized inputs but let's keep it simple, for now.

---

If timing attack is really a common problem to address you may consider to add a random delay for failed attempts. In this case you may drop this constant time string comparison and simply make timing useless. Note that delay has to be short enough to don't make DoS easier but sufficiently long to confuse attacker when performing exact time measurement. 3-4 milliseconds may be a good starting point for further investigations. See also https://security.stackexchange.com/a/30785/80859.

---

Note that redesigning your code you can take a different approach. First pre-compute a good hash function for secret password.

int secretPasswordHash = Hash(secret);

Now your function may be:

public boolean areEqual(String input, String secret) {
    if (secretPasswordHash != Hash(input))
        return false;

    if (input.length() != secret.length())
        return false;

    // With a good hash you really do not need constant-time comparison...
    for (int i = 0; i < input.length(); ++i)
        if (input.charAt(i) != secret.charAt(i))
            return false;

    return true;
}

Answer 4

After looking into this further, I have what seems to be the most sensible solution for the case where you need portable (i.e. cross-platform and cross-architecture) code.

First, check System.getProperty("java.version") returns "1.6.0_17" or later and that System.getProperty("java.vendor") returns "Oracle Corporation". This ensures that you're running code on Oracle Java with a version number after the constant-time patch was applied to MessageDigest.isEqual.

After this check has been completed, you are safe to use MessageDigest.isEqual. If the check fails, exit the program with a fatal error and do not perform the check. The implementation within Oracle Java SE 6 Update 17 and later is written as a constant-time check which is not implemented in Java bytecode, but rather in C. This is as close as you're going to get to a constant-time check in Java without sacrificing portability.

The only other semi-sane way to go with this is to wrap libsodium via JNI and do all of your crypto in there, utilising the constant time helpers for equality checks, although this largely restricts you to x86_32, x86_64, and ARM architectures.

Answer 5

One thing that people seem to have neglected is the issue of branches within the loop body. Taking a branch may invalidate the instruction pipeline, leading to timing differences based on the contents of data. While these differences are subtle, they're important if you're looking to build a hardened constant-time comparison algorithm.

A pseudocode implementation is as follows:

int compareLength = min(a.length(), b.length());

if (compareLength == 0)
{
    // at least one string is empty (zero length)
    // so if they're both the same length, both are empty (equal)
    return a.length() == b.length();
}

int state = 0;
for (int i = 0; i < compareLength; i++)
{
    state |= a.charAt(i) ^ b.charAt(i);
}

return state == 0;

Apologies for any syntax issues, my Java is rusty.

The benefits of this approach are:

• Loop contains only linear fixed-time operations (OR, XOR) which removes data-conditional branches.
• The use of linear operations prevents aggressive compiler optimisation (e.g. early-out once inner equality check results cannot affect the function's returned value).
• Looping over the shortest string length makes it more difficult to discern the exact length of both strings.
• On very large strings, this algorithm is faster than using if inside the loop, as no cache invalidation occurs (branch predictor should always be correct for the loop bound condition).

That said, if the strings are particularly sensitive, you should consider whether they should be string objects in the first place. My understanding is that Java strings are immutable managed objects which have no disposal guarantee. This means that you end up with various copies and fragments of the string in the managed heap without any guarantee of when they'll be cleaned up, if ever. For sensitive values you should consider storing them raw, in the unmanaged heap, and ensuring that all code paths correctly wipe the associated memory (e.g. via a finally block).

In fact, Java is a pretty horrible language to do this kind of thing in, because the JIT compiler is free to do whatever it likes to your code with all sorts of horrible abominations of optimisation. I would suggest moving this function to a native DLL with optimisation disabled.