BCrypt says long, similar passwords are equivalent - problem with me, the gem, or the field of cryptography?

Question

I've been experimenting with BCrypt, and found the following. If it matters, I'm running ruby 1.9.2dev (2010-04-30 trunk 27557) [i686-linux]

require 'bcrypt' # bcrypt-ruby gem, version 2.1.2

@long_string_1 = 'f287ed6548e91475d06688b481ae8612fa060b2d402fdde8f79b7d0181d6a27d8feede46b833ecd9633b10824259ebac13b077efb7c24563fce0000670834215'
@long_string_2 = 'f6ebeea9b99bcae4340670360674482773a12fd5ef5e94c7db0a42800813d2587063b70660294736fded10217d80ce7d3b27c568a1237e2ca1fecbf40be5eab8'

def salted(string)
  @long_string_1 + string + @long_string_2
end

encrypted_password = BCrypt::Password.create(salted('password'), :cost => 10)
puts encrypted_password #=> $2a$10$kNMF/ku6VEAfLFEZKJ.ZC.zcMYUzvOQ6Dzi6ZX1UIVPUh5zr53yEu

password = BCrypt::Password.new(encrypted_password)

puts password.is_password?(salted('password')) #=> true
puts password.is_password?(salted('passward')) #=> true
puts password.is_password?(salted('75747373')) #=> true
puts password.is_password?(salted('passwor')) #=> false

At first I thought that once the passwords got to a certain length, the dissimilarities would just be lost in all the hashing, and only if they were very dissimilar (i.e. a different length) would they be recognized as different. That didn't seem very plausible to me, from what I know of hash functions, but I didn't see a better explanation.

Then, I tried shortening each of the long_strings to see where BCrypt would start being able to tell them apart, and I found that if I shortened each of the long strings to 100 characters or so, the final attempt ('passwor') would start returning true as well. So now I don't know what to think.

What's the explanation for this?

Memphis

Answer 1

The good news is, the mathematical foundations of encryption haven't been dissolved. :)

The bad news is that there's an 8-bit key length limit in bcrypt.c which is silently failing:

uint8_t key_len, salt_len, logr, minor;

Then later:

key_len = strlen(key) + (minor >= 'a' ? 1 : 0);

What you're passing in for encryption is 263 characters, but it winds up thinking it's only 8. So you're getting comparisons on only the very first part of the strings.

However, it works fine for me when I pare down the length of the long_strings, so if you actually do get a problem in the sub-255-total range that may be related to something else.

Mosby

I imagine the fix will probably be to make bcrypt() return NULL when there's a key that's too long. Also, since there's already a salt in the password structure and bcrypt is ostensibly for solving the security problem you're concerned about, I'd not bother with my own salting here. – Mosby

There doesn't seem to be a good reason why key_len is such a short type at all. – Goodly

@Goodly - I see a lot of lines of code on the web. And an unfortunately large percentage of those lines don't seem to be motivated by good reasons. :) – Mosby

Answer 2

Blowfish's P-array is 18 4-byte integers long. BCrypt XORs this array by the password + null, then repeats the procedure until it gets to the end. Say my password was 12345, it would XOR the P-array by 12345(null)12345(null)12345(null), etc...

A full description of EksBlowfish is here. The short version is, BCrypt only uses the first 72 bytes.

Coquet