A few thoughts on the BCBCBC vulnerability. Original report. There’s a few things not explicitly stated in the report, which I thought may be interesting.

vuln

To recap, the bug is that password hashes are compared by looking at the position of each character value, instead of comparing the character values at each position. This leads to a great many false positives, effectively a password bypass.

Here’s a few hashes to review. As a reminder, hashes are structured as algorithm identifier, log round count, then a base64 encoding of the salt followed by the encrypted password. (Password: password)

$2b$08$EVUJdN.PNZbjUOi9D3nsJecEYZE2jN0dr1/3CEvawNH.d5lp9Nt9G
$2b$08$TMwmj0nJfvO6eXGRTNoeaOGbivW1wvSAklXatjMo7tRwoo5FCxCTu
$2b$08$p31golX/c.Lz3mh0drcoU.O5Z/6NwzfWR6v7W5RbXKZnOGveumEja

The comparison function looks at the index for the first 60 characters. For many of these characters, they will never appear in a password hash. Consulting the ascii table we can see that the first 32 are control characters, definitely not in a hash (which is mostly base64 encoded). Then comes some punctuation and the numbers. The entire alphabet, upper and lower, come after 60, and so the comparison function never looks for them.

So we can immediately see that for most hashes, the majority of the hash will not be looked at. We can also see that the ’$’ character will always match, as will ‘2’, ‘0’ and ‘8’. (In these examples. Other examples with e.g. 12 log rounds will match ‘1’ and ‘2’.) Even if a ‘0’ appears later in the hash, as in the first two hashes above, they will compare equal because the first ‘0’ is in the same position.

This leaves only a very limited set of characters to match on. I’ll rewrite the first hash with ‘X’ for unmatched characters. And again, with repeated letters removed as well, since we only compare index of the first occurrence.

$2b$08$EVUJdN.PNZbjUOi9D3nsJecEYZE2jN0dr1/3CEvawNH.d5lp9Nt9G
$2b$08$XXXXXX.XXXXXXXX9X3XXXXXXXXX2XX0XX1/3XXXXXXX.X5XX9XX9X
$2b$08$XXXXXX.XXXXXXXX9X3XXXXXXXXXXXXXXX1/XXXXXXXXXX5XXXXXXX

I don’t know what password generates those hashes, but they do exist. As we can see, there are only six significant characters to match. Not many. We could brute force guess our way to logging in quite easily.

Here’s two more hashes with custom salts.

$2b$08$./0123456789XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
$2b$08$XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX./0123456789

Any and every possible password will auth against the first hash. No matter what password is entered by an attacker, the salt will “absorb” all the possible comparisons. So this is the worst possible case. Neither the attacker nor user has control over the salt, it’s blind luck, but some users will be very unlucky. The second hash is the reverse. If the salt only contains uncompared characters, then it’s possible they appear in the password half of the hash. The second user here got lucky, it will take at least a few more guesses to find another password that matches. This is the best, but also unlikely, case, and it’s still not great.

impact

I don’t know enough about the java ecosystem to know who uses bcrypt from bouncy castle. I kinda thought most people used jBCrypt, but that’s guesswork.

cause

The commit introducing this was a switch to constant time comparison functions. The irony is that this isn’t needed for password hashes. There’s no useful information leakage that comes from comparing a password hash letter by letter.

That said, people fuss about such comparisons, and it can be easier to simply use a constant time function instead of analyzing each case (and then endlessly repeating that justification to people who haven’t done the analysis). So the change is reasonable, if unnecessary.

I think the lesson is to use a constant time comparison function that is known to work instead of coding from scratch.

discovery

I’m not sure, but I’d guess this bug was found by inspection. That seems the best way to find this bug.

It may be possible to create a test case for this bug, but I’m not surprised it doesn’t exist. Most of the time, a different password will still correctly compare unequal. You’d need to test many, many passwords against a single hash, all to find a bug which you probably didn’t consider could exist.