Constant-time string equality check

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  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();
        }
    }

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.

StackExchange Code Review Q#131921, answer score: 4