Duplicated code (seen with constant time comparison)

[LoupVaillant]

Hi,

BouncyCastle recently fixed a vulnerability in OpenBSDBCrypt. The culprit was faulty constant time comparison. The details of the error aren't very interesting. BouncyCastle is a big project, and sometimes our attention just slips. This error however hints at a deeper problem: code duplication.

OpenBSDBCrypt re-implemented constant time comparison inline instead of calling a common utility function. It still does. Constant time comparison is a bit trickier than it lets on. I submit that it should be implemented in one place, and used everywhere. Not only will it make the code base a little tighter and smaller, it will eliminate an entire class of bugs.

While we're at it, it might be a good idea to check whether other common functions are duplicated. Some of them may have to be inline for performance reasons, but those who don't should probably be factored out as well.

[dghgit]

I agree about adding the utility function (mind you, that could have easily been wrong instead...), although we want to leave it as is for one more release. One thing, would you point out where else the comparison is being done? Thanks.

[LoupVaillant]

I agree about adding the utility function

Thanks. 👍

(mind you, that could have easily been wrong instead...)

That has crossed my mind. I believe that had it been a common function from the beginning, it would have received more attention, and any bug would have been uncovered sooner. Here, special attention will be needed when moving this function to a common utility, to make sure no further bug is introduced.

(While we're at it, you may want to question the use of the == equality operator. It may be fine in Java, but I've heard C compilers tends to generate variable time for those — which is why I personally use XOR instead.)

we want to leave it as is for one more release.

No rush. I see you have a lot on your plate, I understand this issue is not high priority.

would you point out where else the comparison is being done?

Well… I don't know BouncyCastle's code base, so I haven't checked beyond OpenBSDBcrypt. I just acted on a strong suspicion that other primitives & constructions may be affected. Sorry.

You most probably know the following, but in case someone else wants to pick it up: my first reflex would be to check anything that has "check" or "verify" in its name, or any function that returns a boolean. Those functions are most likely found in the following:

• Authenticated encryption.
• MAC (Such as GHASH, Poly1305, HMAC…)
• Hashes, maybe
• Password hashes
• Signature verification

[dbaxa]

Consider using MessageDigest.isEqual (https://github.com/AdoptOpenJDK/openjdk-jdk11u/blob/712f3de16fd2c4e31d60bd105aac864e2929abaf/jdk/src/java.base/share/classes/java/security/MessageDigest.java#L455).

[LoupVaillant]

Seconded, with some reservation about the preliminary checks:

• Don't test whether the two buffers are one and the same. It's redundant with the main loop, and in practice always returns false.
• If one of the buffers is null, that's a programming error. Throw an exception.
• If the buffers have different lengths, that's a programming error. Throw an exception.

Also, OpenBSDBCrypt compares strings. What @dbaxa proposes compares byte arrays. Some adjustment will be needed. Either we decide that comparing strings is not a good idea, and we replace them all with proper byte arrays… or we modify the function so it compares strings. I'm personally not competent enough to have an opinion.

[dbaxa]

On a related note, Spring security converts strings to byte arrays for their bcrypt password checking code
https://github.com/spring-projects/spring-security/blob/master/crypto/src/main/java/org/springframework/security/crypto/bcrypt/BCrypt.java#L758

[dghgit]

By way of further information we have some constant time functions in our Arrays class already, not all JVMs actually have the MessageDigest API (probably a lot less true now than 20 years ago) and calling something like Arrays.constantTimeAreEqual() doesn't leave any doubt in the mind of a reader. OpenBSDBCrypt appears to be the only place a String comparison is done like this at the moment, but at this stage I'm leaning towards adding a Strings.constantTimeAreEqual().

[rzwitserloot]

It may be fine in Java, but I've heard C compilers tends to generate variable time for those — which is why I personally use XOR instead.)

It is guaranteed in java. As in, both a.charAt(i) == b.charAt(i) is as constant as anything you're going to write, as is flag &= condition - that is as constant as flag = flag & condition is going to be. I don't see how you can use XOR for that last operation; you'd be toggling the flag, very much not what you wanted. Theoretically you can translate each of the 60 comparisons to a bit on a long, and then test if the end result is 0 to indicate no differences - now you still don't really need XOR, you might as well use bitwise OR - same result. I don't think this would make the code and more constant-time than the much simpler flag &= condition used now.

[LoupVaillant]

I don't see how you can use XOR for that last operation

I don't. XOR replaces equality:

isDifferent |= a[i] ^ b[i];

Then I use an arithmetic trick to implement the isDifferent == 0 test. Here's my code in C.

Of course, those precautions aren't needed in languages that guarantee a == b is constant time.

[dghgit]

Actually I have a feeling the guarantee breaks down for longs... I'd have to check though. I've added Strings.constantTimeAreEqual() so there's something in place if the need to do this, by us or others, comes up again.

Thank you to everyone for contributing to the discussion.