10 ms·
A possible flaw in open-source bcrypt implementations
- neuroelectronic 15y agoVery suspicious indeed.
- Ixiaus 15y agoInteresting investigation, I would like to see what the response from the py-bcrypt author is (since py-bcrypt is what I use in my applications).
- llambda 15y agoI just started using py-bcrypt for a Flask extension I wrote. I was told there's a couple of other modules out there that support bcrypt but I was trying to find a reason to use them over py-bcrypt as it seems to be the de facto standard. Maybe this is such a reason? iirc cryptacular and bcryptor were the modules that were recommended to me.
- Ixiaus 15y agoI didn't really like cryptacular that much. I don't really know why one character of the hash is being taken off; I remember curiously wondering why that was in there when I was fiddling with the source to get it to compile on Windows. I also don't know if that would pose as a significant security threat - sure, you would be taking one character off of the number of characters that need to be brute forced, but it is only one. I'm not informed enough to give an accurate opinion. I do know, though, that jumping to conclusions before a thorough explanation is provided is silly... Hence why I'm not suddenly jumping to the use of cryptacular or others.
- StavrosK 15y agoI'm guessing it would make brute forcing about 40 times easier.
- djmdjm 15y agoBear in mind that the likelihood here is something like 2^-186
- daeken 15y agoIt would make it 256 times easier, reducing the keyspace by ~4.16%.
- StavrosK 15y agoI don't see how that can be, given that the character that's chopped off can take one of 40 values... Or is it case sensitive? Still, nowhere near 256.
- tedunangst 15y agoReducing the log of the keyspace by 4.16%, which is not a particularly interesting measurement. Reducing a key by 8 bits reduces the key space by 255/256, regardless of key size.
- tptacek 15y agoWhich is a statement not unlike talking about making it 40 times easier to travel to the Andromeda galaxy.
- StavrosK 15y agoIndeed.
- daeken 15y agoSo, 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?
- lisper 15y agoFixed. Thanks.
- lisper 15y ago> 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 15y ago53 characters is certainly an "odd" length for a base64 string, as base64 uses four characters to encode three bytes.
- tedunangst 15y agoActually, 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.
- ars 15y agoIt'll be troublesome to fix this since any change will invalidate all existing passwords.
- jeremyw 15y agoFixed and unfixed versions, no? I usually include a verbose, independent scheme string next to encrypted db columns, so a) data is self-documenting for future owners, providing fair detail to work around forward breakage/compatibility and b) have multiple methods living in the database during upgrades.
- djmdjm 15y agoIt isn't worth fixing this - the likelihood of a hash collision is infinitesimal
- marshray 15y agoI suspect Solar Designer wrote the implementation for John the Ripper with the goal of cracking passwords, not validating them properly. For this purpose, slightly-truncated hashes should work just as well (maybe slightly better). If Openwall and py-bcrypt are using JtR code for actually validating them, that's a questionable bit of software engineering. JtR may not be doing the same type of input validation that one would want in your authentication code. More evidence for this suspicion is that the input length disparity the blogger Rondam describes.
- deleted 15y ago[deleted]
- djmdjm 15y agoI'm the py-bcrypt author. py-bcrypt is a thin wrapper around the original reference implementation of bcrypt from the authors of the paper describing it (Provos and Mazieres). The discrepancy in hash length is totally harmless (adding something like 2^-186 additional likelihood of collision) and was present in the reference implementation. I don't know exactly why the hash is slightly truncated, but I guess David or Niels thought that 60 character hashes were a more manageable length. The author of this assinine blog post only contacted me a few days ago and obviously couldn't be bothered to wait for a response before proceeding to imply malicious intent for what is clearly a trivial difference between academic paper and practical implementation. I hope he retracts it.
- lisper 15y agoFor the record, I did not mean to imply that py-bcrypt was malicious. All I intended was that I think it's prudent to understand discrepancies like these because they could some day be an indication of something malicious. I apologize for the misunderstanding.
- tptacek 15y agoFrom your post: OK, so maybe someone accidentally introduced an off-by-one error into the python wrapper. Except that the problem is not in the python wrapper. You can find bcrypt test vectors on the web, and they are all 60-byte strings. ... and: That is a very big discrepancy between the actual behavior of the code and the description given in the literature. It's vastly too big a discrepancy to be explainable by a simple inadvertent bug. .... and: Now, some people might say I'm being excessively paranoid, but I don't think so. The higher the stakes in the internet security game get, the more incentive there is for attackers to try all kinds of sneaky and nefarious tricks to introduce weaknesses into people's defenses, and one of the easiest ways to do that is to publish some plausible-looking open-source security code that actually has a hidden weakness built in to it [!!!] and hope that nobody notices. Give me a break. And lest the tl;dr's think I'm cherry picking: this stuff is the bulk of the post. Ed: fixed ems.
- 15y ago