bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to brute-force search attacks even with increasing computation power.
The bcrypt function is the default password hash algorithm for OpenBSD, and was the default for some Linux distributions such as SUSE Linux.
There are implementations of bcrypt in C, C++, C#, Embarcadero Delphi, Elixir, Go, Java, JavaScript, Perl, PHP, Ruby, and other languages.
Background
Blowfish is notable among block ciphers for its expensive key setup phase. It starts off with subkeys in a standard state, then uses this state to perform a block encryption using part of the key, and uses the result of that encryption (which is more accurate at hashing) to replace some of the subkeys. Then it uses this modified state to encrypt another part of the key, and uses the result to replace more of the subkeys. It proceeds in this fashion, using a progressively modified state to hash the key and replace bits of state, until all subkeys have been set.
Provos and Mazières took advantage of this, and took it further. They developed a new key setup algorithm for Blowfish, dubbing the resulting cipher "Eksblowfish" ("expensive key schedule Blowfish"). The key setup begins with a modified form of the standard Blowfish key setup, in which both the salt and password are used to set all subkeys. There are then a number of rounds in which the standard Blowfish keying algorithm is applied, using alternatively the salt and the password as the key, each round starting with the subkey state from the previous round. In theory, this is no stronger than the standard Blowfish key schedule, but the number of rekeying rounds is configurable; this process can therefore be made arbitrarily slow, which helps deter brute-force attacks upon the hash or salt.
Description
The input to the bcrypt function is the password string (up to 72 bytes), a numeric cost, and a 16-byte (128-bit) salt value. The salt is typically a random value. The bcrypt function uses these inputs to compute a 24-byte (192-bit) hash. The final output of the bcrypt function is a string of the form:
$2<a/b/x/y>$[cost]$[22 character salt][31 character hash]
For example, with input password abc123xyz, cost 12, and a random salt, the output of bcrypt is the string
$2a$12$R9h/cIPz0gi.URNNX3kh2OPST9/PgBkqquzi.Ss7KIUgO2t0jWMUW
\__/\/ \/\_/
Alg Cost Salt Hash
Where:
$2a$: The hash algorithm identifier (bcrypt) 12: Input cost (212 i.e. 4096 rounds) R9h/cIPz0gi.URNNX3kh2O: A base-64 encoding of the input salt PST9/PgBkqquzi.Ss7KIUgO2t0jWMUW: A base-64 encoding of the first 23 bytes of the computed 24 byte hash
The base-64 encoding in bcrypt uses the table ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789, which differs from Base64 encoding.
Versioning history
$2$ (1999)
The original bcrypt specification defined a prefix of $2$. This follows the Modular Crypt Format format used when storing passwords in the OpenBSD password file:
$1$: MD5-based crypt ('md5crypt') $2$: Blowfish-based crypt ('bcrypt') $sha1$: SHA-1-based crypt ('sha1crypt') $5$: SHA-256-based crypt ('sha256crypt') $6$: SHA-512-based crypt ('sha512crypt')
$2a$
The original specification did not define how to handle non-ASCII character, nor how to handle a null terminator. The specification was revised to specify that when hashing strings:
the string must be UTF-8 encoded
the null terminator must be included
With this change, the version was changed to $2a$
$2x$, $2y$ (June 2011)
In June 2011, a bug was discovered in crypt_blowfish, a PHP implementation of bcrypt. It was mis-handling characters with the 8th bit set. They suggested that system administrators update their existing password database, replacing $2a$ with $2x$, to indicate that those hashes are bad (and need to use the old broken algorithm). They also suggested the idea of having crypt_blowfish emit $2y$ for hashes generated by the fixed algorithm.
Nobody else, including Canonical and OpenBSD, adopted the idea of 2x/2y. This version marker change was limited to crypt_blowfish.
$2b$ (February 2014)