generated BCrypt salts have incorrect padding

Steps to reproduce...

As reported by Johan <prinsjp@hotmail.com>, most (but not all) bcrypt hashes 
generated by Passlib (<= 1.5.2) fail to verify if passed directly into 
pybcrypt, or stored in OpenBSD's /etc/master.passwd. He contributed the 
following passlib-created hashes which fail under OpenBSD/pybcrypt...

    loppux / $2a$12$oaQbBqq8JnSM1NHRPQGXORm4GCUMqp7meTnkft4zgSnrbhoKdDV0C
    vlaflip / $2a$12$GqDY2k0khMlI69U5LN9m11tN2XCF1NH5d53SKdjfa/jmgnIN8rVb6
    Passlib11 / $2a$12$M8mKpW9a2vZ7PYhq/8eJVcUtKxpo6j0zAezu0G/HAMYgMkhPu4fLK

And the following passlib-created hashes which work...

    vlaflip / $2a$12$PL/OghAsd3QMSPQG82vLoeAWiv0eU1MyMVflfmZnth1e3H0JPEjAS

Original message is here: 
https://groups.google.com/forum/?hl=en#!topic/passlib-users/CtgkLYqM86Y

---

Diagnosis...

After some examination, the problem is caused by the padding bits at the end of 
the bcrypt salt, and how passlib generates bcrypt salts...

BCrypt uses a base64 variant to encode it's salt and digest data, encoding 6 
bits per character. Due to the 16 byte raw salt, the last character of the 
encoded salt string only encodes 2 bits of data, the other 4 bits are unused 
"padding". 

Passlib preserves these padding bits as provided, and when verifying hashes, 
compares the digest characters, not the entire string. Whereas OpenBSD 
os_crypt() and pybcrypt hashpw() both set the padding bits to 0 when they 
return a result, and use logic equivalent to ``os_crypt(password, hash) == 
hash`` when verifying passwords. Thus if they are passed a hash with the 
padding bits set, it will silently fail to verify against *anything*. 

This issue wouldn't have been revealed if it weren't for the fact that Passlib 
uses a simple getrandstr() call to generate encoded bcrypt salts, instead of 
generating raw bytes and encoding them. 15 out of 16 times, this causes Passlib 
to generate a bcrypt salt which has the padding bits set, which therefore won't 
work if passed to OpenBSD or pbcrypt. Thus causing the observed behavior of 
most (but not all) hashes failing. 

For example, the incorrect hash above should have the last salt char changed:

    wrong:  $2a$12$oaQbBqq8JnSM1NHRPQGXORm4GCUMqp7meTnkft4zgSnrbhoKdDV0C
    right:  $2a$12$oaQbBqq8JnSM1NHRPQGXOOm4GCUMqp7meTnkft4zgSnrbhoKdDV0C
                                        ^

---

Severity...

1. Affects most bcrypt hashes generated by passlib, but only an issue if 
verification done through library other than passlib.

2. Not a security risk. 

3. Should be fixed asap, don't want more of these out there mucking things up 
for people.

---

Temporary fix until issue is resolved...

The following function should clear the padding bits of existing hashes, fixing 
any hashed already created by passlib:

    BCHARS = './ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
    BCLAST = '.Oeu'

    def cleansalt(hash):
        "ensure 4 padding bits at end of bcrypt salt are always 0"
        if hash.startswith("$2") and h[28] not in BCLAST:
            hash = hash[:28] + BCHARS[BCHARS.index(hash[28]) & ~15] + hash[29:]
        return hash

The following monkeypatch should fix passlib's salt generation until issue is 
resolved....

    from passlib.hash import bcrypt
    from passlib.utils import rng, getrandstr
    BCHARS = './ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
    BCLAST = '.Oeu'

    def gensalt(salt_size=None, strict=False):
        return getrandstr(rng, BCHARS, 21) + getrandstr(rng, BCLAST, 1)
    bcrypt.generate_salt = staticmethod(gensalt)

---

(Tentative plans for a) Permanent fix...

While some of these changes are departure from Passlib's past behavior of 
preserving the padding bits, they should allow existing hashes to verify 
correctly in Passlib, while ensuring Passlib's output is *always* compatible 
with the de facto standard (OpenBSD). 

Release Passlib 1.5.3, containing the following changes:

1. Change passlib.hash.bcrypt to generate salts with padding bits set to 0. 
This should cause genconfig() and encrypt() to generate OpenBSD compatible 
hashes from this release onward.

2. Change passlib.hash.bcrypt to clear the padding bits when parsing a hash. 
This should cause genhash() to generate OpenBSD compatible hashes even if the 
config string is not compatible. 

2b. When padding bits are cleared per item 2, norm_salt() should issue a 
warning. This warning should alert users that they have an unclean hash which 
they may want to re-encrypt or clean, if they plan to verify the hash using a 
library other than passlib.

3i. add unittest to verify salts returned by genconfig() and encrypt() are 
clean.

3ii. add unittest to verify generated hashes directly using os_crypt/pbcrypt, 
just to prevent recurrence of any bugs like this one.

3iii. add the submitted test vectors, make sure genhash() outputs "cleaned" 
result per item 2, and that verify() still works against unclean hashes. 

4. make note of all this in the "deviations" in the documentation.

XXX: item 2 would also cause 
`passlib.hash.bcrypt.from_string(hash).to_string()` to "clean" existing hashes, 
need to verify such normalization should be the expected behavior from that 
operation. 

XXX: it would be nice if verify_and_update() could take care of automatically 
cleaning hashes (per item 2b), but that should wait until a major release.
Original issue reported on code.google.com by elic@astllc.org on 6 Oct 2011 at 12:45
thebaron / passlib

generated BCrypt salts have incorrect padding #25
