A hole in crypt_blowfish

A longstanding bug that was recently found in the crypt_blowfish password hashing library highlights the problems that can occur when a bug is found in a widely used low-level library. Because crypt_blowfish has been around for so long (this bug is said to go back to 1998 or possibly 1997), it has been used by various other packages (PHP for example) as well as some Linux distributions. The security impact is not likely to be huge, because it only affects passwords with somewhat uncommon characteristics, but the impact on those who have stored hashed passwords generated using the library may be a bit more painful.

Password hashing is a standard technique that is used by authentication mechanisms (for logging into a system or web application for example), so that the plaintext password does not need to be stored. Instead, something derived from the plaintext password is stored. Typically, one-way cryptographic hash functions like SHA-1 or the Blowfish cipher are used for that purpose. When the user presents the password, the same function is applied to that input and compared to what is stored. The idea is that even if an attacker gets access to the password database, they would need to "crack" the hashed values stored there. As its name implies, crypt_blowfish implements password hashing based on Blowfish.

The bug itself is quite simple, and the change to fix it will likely make the problem obvious to C programmers:

    tmp |= *ptr;

    tmp |= (unsigned char)*ptr;

The problem was actually discovered in the John the Ripper (JtR) password cracking program. As part of creating a test suite, "magnum" was attempting to crack a password that consisted of a single non-ASCII character (£ or 0xa3), which was hashed using a library other than crypt_blowfish. Because JtR and crypt_blowfish share their implementation of the Blowfish encryption algorithm, tests using both would pass, but independent implementations would generate the correct hash, thus failing to match what was generated by JtR.

JtR and crypt_blowfish developer Alexander Peslyak (aka Solar Designer) analyzed the effects of the bug and found that some password pairs would hash to the same value with only minimal differences (e.g. "ab£" hashed to the same value as "£"), which would make password cracking easier. A further analysis shows that some characters appearing just before one with the high bit set may be effectively ignored when calculating the hash. That would mean that a simpler password than that given by the user could be used and would still be considered valid—a significant weakening of the user's password.

It should be noted that Solar Designer has been very forthcoming with details of the problem and its effects. His CVE request is quite detailed, and he takes full responsibility for the error. Other projects who find security holes in their code would do well to follow his lead here.

There is no real problem for JtR, as it can get the updated code so that it can crack passwords with high-bit-set characters in them. In addition, it could continue to use the broken code to crack passwords that were hashed incorrectly. But for applications that use crypt_blowfish, it's a different story. Passwords with the high bit set may be fairly uncommon—at least for sites with typically ASCII-only users—but there is no easy way to determine whether stored hashes are invalid or not.

The safest solution for administrators with potentially bad password hashes (which could include those running Openwall Linux (Owl), SUSE, and ALT Linux which can use crypt_blowfish for hashing the password database) is to invalidate all passwords and have their users input new ones. That could prove to be a logistical nightmare, however, depending on how easily, and securely, users can set new passwords without authenticating with their existing password. Requiring that users change their existing passwords after logging in is an alternative, but one that might give attackers a window in which to operate. It also leaves passwords unchanged for any users that do not log in.

The risks of attackers using this flaw to log in to a site are likely to be fairly small, but they do exist. If a site's login process is susceptible to brute force attacks, this bug makes it somewhat easier to do so, at least for specific password types. On the other hand, if the password database has been exposed, and some passwords were not crackable (at least for attackers using cracking programs other than JtR), this information would give them the means to crack those passwords. In the end analysis, it is an exploitable hole, but not the kind to send administrators into panic mode.

It is somewhat amazing that this bug has existed for 13+ years in a fairly widely used library. Up until now, no one has tested it in this way, at least publicly, which should serve as something of a warning to those who are using well-established software, both free and proprietary. With free software (crypt_blowfish has been placed into the public domain which may be a bit legally murky but is in keeping with free software ideals) there are more and easier opportunities to examine and test the code, but that's only effective if the testing is actually done.

There are, without doubt, bugs still lurking in various security-oriented libraries that we depend on every day, so testing those libraries (as well as code that is not being used for security purposes) regularly and systematically can only help find them. While it took more than a decade for this bug to come to light, it's worth pointing out that it certainly could have been discovered by others in the interim. Attackers clearly do their own testing, and are generally not inclined to release their results. That may not be the case here, but one should always recognize that public disclosure of a vulnerability is not necessarily tied to its discovery.