How do I implement a string comparison in Java that takes the same amount of time no matter whether they match or where a mismatch (if any) occurs?

Question

I want to implement a String comparison function that doesn't take a different amount of time depending on the number of characters that match or the position of the first mismatch. I assume there must be a library out there somewhere that provides this, but I was unable to find it via a quick search.

So far, the best idea I've got is to sum the XOR of each character and return whether or not the sum is 0. However, I'm pretty sure this wouldn't work so well with Unicode. I also have a vague concern that HotSpot would do some optimizations that would change my constant-time property, but I can't think of a specific optimization that would do this off the top of my head.

Thanks.

UPDATE: Sorry, I don't believe I was clear. I'm not looking for O(1), I'm looking for something that won't leak timing information. This would be used to compare hashed password values, and if the time it took to compare was different based on where the first mismatch occurred, that would be leaking information to an attacker.

Answer 1

I want to implement a String comparison function that doesn't take a different amount of time depending on the number of characters that match or the position of the first mismatch. I assume there must be a library out there somewhere that provides this, but I was unable to find it via a quick search.

So far, the best idea I've got is to sum the XOR of each character

Do you see the contradiction?

update:

To the updated, and therefore different question:

Can you gain information once, how much time is spent for comparing 2 Strings, in terms of constant amount and time, depending on the length of the two strings?

a + b*s(1).length + c*s(2).length + d*f(s(1), s(2))? 

Is there an upper bound of characters for String 1 and 2?

If the time is, depending on a factor for the machine, for example for the longest strings you expect 0.01ms. You measure the time to encode the string, and stay idle until you reach that time, maybe + a factor of rand(10%) of the time.

If the length of the input is not limited, you could calculate the timing in a way, that will fit for 99%, 99.9% or 99.99% of typical input, depending on your security needs, and the speed of the machine. If the program is interacting with the user, a delay up to 0.2s is normally experienced as instant reaction, so it wouldn't annoy the user, if your code sleeps for 0.19994s, while doing real calculations for 0.00006s.

Answer 2

The following code is one common way to do a constant-time byte[] comparison in Java and avoid leaking password info via the time taken:

public static boolean isEqual(byte[] a, byte[] b) {
    if (a.length != b.length) {
        return false;
    }

    int result = 0;
    for (int i = 0; i < a.length; i++) {
      result |= a[i] ^ b[i];
    }
    return result == 0;
}

See http://codahale.com/a-lesson-in-timing-attacks/ for more discussion of this issue.

Current implementation in openjdk as an inspiration is available in isEqual method.

(This assumes that the length of the secret is not sensitive, for example if it is a hash. You should pad both sides to the same length if that is not true.)

This is essentially the same as your first suggestion:

So far, the best idea I've got is to sum the XOR of each character and return whether or not the sum is 0.

You asked:

However, I'm pretty sure this wouldn't work so well with Unicode.

This is a valid concern, but you need to clarify what you will accept as "equal" for a solution to be proposed. Luckily, you also say "This would be used to compare hashed password values", so I don't think that any of the unicode concerns will be in play.

I also have a vague concern that HotSpot would do some optimizations that would change my constant-time property,

Hopefully that's not true. I expect that the literature on how to avoid timing attacks in Java would address this if it were true, but I can't offer you any citations to back this up :-)

Answer 3

I see two immediate possibilities for not leaking password-related information in timing:

1/ Pad both the password string and candidate string out to 1K, with a known, fixed character (like A). Then run the following (pseudo-code):

match = true
for i = 0 to 1023:
    if password[i] != candidate[i]:
        match = false

That way, you're always taking the same amount of loops to do the comparison regardless of where it matches.

There's no need to muck about with xor since you can still do a simple comparison, but without exiting the loop early.

Just set the match flag to false if a mismatch is found and keep going. Once the loop exits (taking the same time regardless of size or content of password and candidate), then check whether it matched.

2/ Just add a large (relative to the normal comparison time) but slightly random delay at the end of the comparison. For example, a random value between 0.9 and 1.1 seconds. The time taken for the comparison should be swamped by the delay and the randomness should fully mask any information leakage (unless your randomness algorithm leaks information, of course).

That also has the added advantage of preventing brute force attacks since a password check takes at least about a second.

Answer 4

This should take approximately the same time for any matching length Strings. It's constant-time with a big constant.

public static boolean areEqualConstantTime(String a, String b) {
    if ( a.length != b.length ) {
        return false;
    }

    boolean equal = true;
    for ( long i = 0; i < (Long)Integer.MAX_INT; i++ ) {
        if ( a.charAt((int)(i % aChars.length)) != b.charAt((int)(i % bChars.length))) {
            equal = false;
        }
    }
    return equal;
}

Edit

Wow, if you're just trying to avoid leaking timing information this facetious answer got pretty close to the mark! We can start with a naive approach like this:

public static boolean arePasswordsEqual(String a, String b) {
    boolean equal = true;
    if ( a.length != b.length ) {
       equal = false;
    }

    for ( int i = 0; i < MAX_PASSWORD_LENGTH; i++ ) {
        if ( a.charAt(i%a.length()) != b.charAt(i%b.length()) ) {
            equal = false;
        }
    }
    return equal;
 }

We need the MAX_PASSWORD_LENGTH constant because we can't simply use either the max or the min of the two input lengths as that would also leak timing information. An attacker could start with a very small guess and see how long the function takes. When the function time plateaus, he would know his password has the right length which eliminates much of the range of values he needs to try.

Answer 5

You can do constant time string comparisons if you intern your strings. Then you can compare them with == operator resulting in a constant time equality check.

Read this for further detials

Answer 6

The usual solution is to set a timer, and not return the result until the timer has expired.

The time taken to compare strings or hashes is not important, just set the time-out value sufficiently large.