14
\$\begingroup\$

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();
        }
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Side question: if you're trying to prevent timing attacks then why you say no need to keep length secret? To determine exact string length Isn't it the very first step an attacker performs? Then he will go on timing response for each character... \$\endgroup\$ – Adriano Repetti Jun 16 '16 at 9:18
  • 2
    \$\begingroup\$ @AdrianoRepetti I don't care about the length. Keeping it secret would be slightly better, but the secret is a case-sensitive alphanumeric string of length 37, giving 52**37 = 2e66 possibilities. Gaining or losing a factor of 10 (or a million) just doesn't count. \$\endgroup\$ – maaartinus Jun 16 '16 at 21:11
  • \$\begingroup\$ intern()? :-D \$\endgroup\$ – Grim Jun 22 '16 at 19:48
4
+50
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. - I'm not sure, but isn't communication with other threads equally demanding as communication with HW? Quite a few Java concurrent data structures rely on volatile as it's way faster than other synchronization primitives. +++ My only reason for SecureRandom was not to provide any additional clue to the attacker as they might see the delay cause by the assignment dummy = new SecureRandom().nextLong() and learn about n if the previously assigned value was predictable. \$\endgroup\$ – maaartinus Jun 23 '16 at 2:41
  • \$\begingroup\$ @maaartinus JLS §8.3.1.4: "A field may be declared volatile, in which case the Java Memory Model ensures that all threads see a consistent value for the variable". This is weaker than the "as-if" rule for C/C++ because if no thread observes the variable, it is in practice allowed to omit the stores to it. \$\endgroup\$ – Emily L. Jun 23 '16 at 10:57
  • \$\begingroup\$ Interesting point. So e.g. when the JVM runs a single thread, it could ignore all volatiles and synchronized and whatever. Funny! \$\endgroup\$ – maaartinus Jun 23 '16 at 21:52
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I disagree with you concerning adding NEQ test. There's no place for it as I'm computing delta += input.charAt(i) ^ secret.charAt(i). At this point, the characters being equals or not just can't matter as a sum is to be computed. The sum gets used in two ways later: Once in a blackhole, hopefully in a way that can't be eliminated. Because of this, there's no reason to use a short-circuit for the boolean as after having computed int result, the simplest and fastest way is to return delta == 0. \$\endgroup\$ – maaartinus Jun 23 '16 at 2:34
  • \$\begingroup\$ Sure there is. if(char1 != char2) delta += char1 ^ char2 yields equivalent result to plain delta += char1 ^ char2. Except that the former avoids an unconditional memory write, so it is a legit optimization to happen. You won't see this happening with current Oracle JVMs, I think, but likely with ones optimizing more aggressively. \$\endgroup\$ – Ext3h Jun 23 '16 at 6:45
  • \$\begingroup\$ But there's no memory write as delta is in a register... most probably not in any CPU for which avoiding memory writes would be a win. Maybe x86 in 32 bit mode could ran out of registers, but even then this optimization would cause a slowdown due to conditional branching.... but you might be right: See my update. \$\endgroup\$ – maaartinus Sep 28 '16 at 19:25
  • \$\begingroup\$ "Adding a random wait on authentication failures as suggested by others is a good start" - sadly not unless you can directly use HPET and interrupts. Artificial delays on almost any platform are subject to the whims of the thread scheduler and timer limitations of the operating system; common sleep functions usually have a granularity of at least 16ms and any random delays produced with them can be low-passed out of a sufficiently large timing sample, or counteracted using cluster analysis. \$\endgroup\$ – Polynomial Aug 17 '17 at 13:42
3
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Are you sure that the JIT is not allowed to remove the instantiation of SecureRandom? Sure it has side effects, but they are not observable in the sense that you cannot tell from the execution of the program whether or not a SecureRandom object was created or not. I would find it unlikely that the JIT would do this, but I cannot rule it. \$\endgroup\$ – Emily L. Jun 16 '16 at 10:47
  • \$\begingroup\$ @Emily compiler can't arbitrarily remove an object instantiation for a non primitive type. First of all because it has always an important side effect (even for an empty object): run-time memory allocation. Any function call without an used return value (let's say you create you create a file) won't have an observable effect from the execution of the program but obviously compiler won't remove it... \$\endgroup\$ – Adriano Repetti Jun 16 '16 at 10:58
  • 1
    \$\begingroup\$ Can you point me to a reference that says the JIT isn't allowed to remove an instantiation of an object? In your example the created file is an observable effect. The run-time memory allocation isn't observable if it is not used. It doesn't change the result of the program. \$\endgroup\$ – Emily L. Jun 16 '16 at 11:01
  • 1
    \$\begingroup\$ @Polynomial I disagree with adding random delays being worthless. The noise doesn't make the signal impossible to recover, but it may make it much harder. You may need a thousand tries to recover a character, but after one hundred you get kicked out. A much better idea would be to add unpredictable input-dependent delays which are independent of the secret to all failed attempts like sleep(hmac(anotherSecret, input)). \$\endgroup\$ – maaartinus Aug 1 '17 at 17:34
  • 1
    \$\begingroup\$ @maaartinus I took the liberty of posting this as a new answer. \$\endgroup\$ – Polynomial Aug 17 '17 at 13:43
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The only thing I'm missing is a pointer supporting your claim about the intrinsication of MessageDigest.isEqual. \$\endgroup\$ – maaartinus Aug 17 '17 at 13:51
  • \$\begingroup\$ See the updates at the bottom of this article: codahale.com/a-lesson-in-timing-attacks \$\endgroup\$ – Polynomial Aug 17 '17 at 14:24
  • \$\begingroup\$ MessageDigest.isEqual was and still is implemented in pure Java. Unfortunately. It baffles me that Java doesn’t provide a _standard, guaranteed_constant-time comparison method. They did change it from a short-circuit algorithm to a seems-constant-time-in-source-code one, but not to C, and you’ll notice the OP of this question already knew this at the time of asking if you follow the link in the question. \$\endgroup\$ – Chortos-2 Sep 17 '19 at 16:36
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ No, this will break constant time check. In theory when state variable changes to a non-zero value compiler may short-circuit loop and return immediately (an optimization to do not execute full loop, it may even be done by javac but without PGO it's a blind-guess, JIT compiler has much more context). \$\endgroup\$ – Adriano Repetti Jun 30 '16 at 10:37
  • \$\begingroup\$ @AdrianoRepetti Surely the compiler can't implement such aggressive optimisation? For example, how does it infer that the charAt call can't throw an exception or produce some other side effect at a later call than when it decides to early-out? If it were capable of such an optimisation then all bets are off; even returning the value of state would not resolve the issue as the calling conditional would surely be identified and the optimisation would remain. If this is the case, I'd argue that Java as a language is incapable of constant-time operations entirely. \$\endgroup\$ – Polynomial Jun 30 '16 at 10:51
  • \$\begingroup\$ It has been a strong debate in chat! Someone has even more radical ideas about what a compiler may (in theory) do. I think it won't go too far because its knowledge is fairly limited (and it's not a theorem prover) but for internal methods it has a lot of knowledge. It may even do bounds checking just once. I don't mean it does it NOW (and especially for this code snippet) but it's surely free to do it in future (code is still correct, just...faster) \$\endgroup\$ – Adriano Repetti Jun 30 '16 at 10:56
  • \$\begingroup\$ @AdrianoRepetti It seems that this is an intractable problem with Java's JIT compiler, then. I've edited to suggest moving the algorithm out to a native DLL, since in C or a similar language this can be controlled, analysed, and instrumented once by the developer to ensure security. \$\endgroup\$ – Polynomial Jun 30 '16 at 11:01
  • \$\begingroup\$ Java compiler is in theory allowed to do almost what it wants. There are however limits (unknown native code and I/O) it can't touch. I agree, with a native DLL you have a finer control and it's probably a better choice for this kind of tasks. \$\endgroup\$ – Adriano Repetti Jun 30 '16 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.