On: A possible flaw in open-source bcrypt implementations

[daeken]

So, he's right in that there seems to be a flaw with respect to the base64 encoding, but he's wrong about how much. It's one byte of hash that's lost when you add the padding back (it decodes to 184 bits), which is explained by the following code:

        encode_base64((u_int8_t *) encrypted + strlen(encrypted), ciphertext,
            4 * BCRYPT_BLOCKS - 1);

It does indeed look like it's cutting a byte off the ciphertext when it's encoded.

Edit: I think I know what's going on with the key length, too. It just so happens that len(base64.decodestring('x'72)) == 54 -- just below the key size limit. But I don't see where the key is getting base64 decoded in the code. Digging...

Edit #2: The b64d('x'72) == 4 behavior I saw was coincidental. What happens is that subkeys can be up to 72 bytes long but will not affect all bits of ciphertext. This is valid and by design:

    /* Schneier specifies a maximum key length of 56 bytes.
	 * This ensures that every key bit affects every cipher
	 * bit.  However, the subkeys can hold up to 72 bytes.
	 * Warning: For normal blowfish encryption only 56 bytes
	 * of the key affect all cipherbits.
	 */

Edit #3: The hash truncation occurs in the reference implementation as well. This is in disagreement with the paper, and reduces the keyspace by ~4.16% -- that's ungood. Wonder why that was?

[tedunangst → daeken]

Actually, it reduces the keyspace by 99.6%.

As to why, I've never encountered a software implementation that precisely matched its design paper. Usually has a lot to do with publication deadlines. Papers don't change, software does.

[daeken → tedunangst]

Sorry, my math was initially off -- the keyspace is reduced to ~99.6%, or a drop of ~0.4%.

[tedunangst → daeken]

No, the upper byte of key should have 256 possible values. It now has one (all zeroes, essentially). Keyspace is reduced to 1/256 of original, a reduction of 255/256.

[daeken → tedunangst]

Only for that byte -- the overall keyspace is 184 bits instead of 192 bits.

[esrauch → daeken]

I think his point is that 2 raised to 192 is 256 times larger than 2 raised to 184, meaning that you are getting 1/256 as many possible keys by reducing the key length by 8 bits.

[daeken → esrauch]

Ahh, that's a good point. Thanks for clarifying.

[lisper → daeken]

> len(base64.decodestring('x'72)) == 54

Yeah, I thought about that. But I tested it and that wasn't it:

>>> hashpw('x',s) '$2a$05$YTnGVPqoxIgfmWrHAxHqhegbOHvVmK8y9bvOwNlOUVEruX9NjPBJy'

>>> hashpw(chr(ord('x')+128), s) '$2a$05$YTnGVPqoxIgfmWrHAxHqhesvRgqg0bHauZJ3SrAc2oRwZ3XF46hE2'

> subkeys can be up to 72 bytes long

That makes a lot more sense.

[marshray → daeken]

53 characters is certainly an "odd" length for a base64 string, as base64 uses four characters to encode three bytes.

[lisper → daeken]

Fixed. Thanks.