MessageDigest.isEqual function use in Java

Question

I have two question that I don't understand. Please help me take a look.Thanks.

1. What is the use of MessageDigest.isEqual function in Java?

2. Explain why, in some versions prior to Java SE 6 Update 17, it was vulnerable to a timing attack.

Answer 1

Looking at a Java SE 6 Update 10 implementation, we see :

public static boolean isEqual(byte digesta[], byte digestb[]) {

    if (digesta.length != digestb.length)
        return false;

    for (int i = 0; i < digesta.length; i++) {
        if (digesta[i] != digestb[i]) {
            return false;
        }
    }
    return true;
}

While after the fix we see :

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

    int result = 0;
    // time-constant comparison
    for (int i = 0; i < digesta.length; i++) {
        result |= digesta[i] ^ digestb[i];
    }
    return result == 0;
}

The old implementation appears to be more efficient, since it returns false when the first non-equal byte is found, but I'm assuming it was replaced because it might allow the caller to test how similar the two input byte arrays are to each other based on the running time of the method.

The new implementation always has the same running time (for same length arrays), since it iterates over the entire arrays (even if the arrays differ in their very first byte).

I searched where this method is called. One example is engineVerify(byte[] signature) in com.sun.org.apache.xml.internal.security.algorithms.implementations.IntegrityHmac class, which tests if the signature byte array passed to it is valid by comparing it to some internal byte array. Prior to the fix, by measuring the running time of that method, you could try to generate a byte array that would pass the comparison (the longer the method takes to run implies that a larger prefix of the two arrays is equal).

Answer 2

refer to the webpage link below: http://codahale.com/a-lesson-in-timing-attacks/

I can choose what message I want to be authenticated—let’s say a session cookie with a specific user ID—and then calculate 256 possible values:

0000000000000000000000000000000000000000
0100000000000000000000000000000000000000
0200000000000000000000000000000000000000
... snip 250 ...
FD00000000000000000000000000000000000000
FE00000000000000000000000000000000000000
FF00000000000000000000000000000000000000

I go through each of these values until I find one— A100000000000000000000000000000000000000—that takes a fraction of a millisecond longer than the others. I now know that the first byte of what the HMAC for that message should be is A1. Repeat the process for the remaining 19 bytes, and all of a sudden I’m logged in as you.