bcrypt is a password hashing function designed by Niels Provos
and David Mazieres, 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.
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 Mazieres 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.
The prefix "$2a$" or "$2b$" (or "$2y$") in a hash string in a
shadow password file indicates that hash string is a bcrypt hash
in modular crypt format. The rest of the hash string includes the
cost parameter, a 128-bit salt (Radix-64 encoded as 22
characters), and 184 bits of the resulting hash value (Radix-64
encoded as 31 characters). The Radix-64 encoding uses the
unix/crypt alphabet, and is not 'standard' Base-64. The cost
parameter specifies a key expansion iteration count as a power of
two, which is an input to the crypt algorithm.
For example, the shadow password record
specifies a cost parameter of 10, indicating 210 key expansion
rounds. The salt is N9qo8uLOickgx2ZMRZoMye and the resulting hash
is IjZAgcfl7p92ldGxad68LJZdL17lhWy. Per standard practice, the
user's password itself is not stored.
Many implementations of bcrypt truncate the password to the
first 72 bytes.
The mathematical algorithm itself requires initialization with
18 32-bit subkeys (equivalent to 72 octets/bytes). The original
specification of bcrypt does not mandate any one particular
method for mapping text-based passwords from userland into
numeric values for the algorithm. One brief comment in the text
mentions, but does not mandate, the possibility of simply using
the ASCII encoded value of a character string: "Finally, the key
argument is a secret encryption key, which can be a user-chosen
password of up to 56 bytes (including a terminating zero byte
when the key is an ASCII string)."
Note that the quote above mentions passwords "up to 56 bytes"
even though the algorithm itself makes use of a 72 byte initial
value. Although Provos and Mazieres do not state the reason for
the shorter restriction, they may have been motivated by the
following statement from Bruce Schneier's original specification
of Blowfish "The 448 [bit] limit on the key size ensures that the
[sic] every bit of every subkey depends on every bit of the key."
Implementations have varied in their approach of converting
passwords into initial numeric values, including sometimes
reducing the strength of passwords containing non-ASCII