bcrypt is a key derivation function for passwords 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 BSD and many other systems.
The prefix "$2a$" 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, and the 192-bit
hash value.
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 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".
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 alternately the salt and the password as the key, each round starting with
the subkey state from the previous round.
Cryptotheoretically, 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 iteration count is a power of two, which is an input to the algorithm.
The number is encoded in the textual result.
There are implementations of bcrypt for Ruby, Python, C, C#, Perl, PHP, Java and other languages.
Algorithm The bcrypt algorithm depends heavily on its
"Eksblowfish" key setup algorithm, which runs as follows:
EksBlowfishSetup(cost, salt, key) state InitState()
state ExpandKey(state, salt, key) repeat
state ExpandKey(state, 0, key) state ExpandKey(state, 0, salt)
return state
InitState works as in the original Blowfish algorithm, populating the P-array and S-box
entries with the fractional part of in hexadecimal.
The ExpandKey function does the following:
ExpandKey(state, salt, key) for(n = 1..18)
Pn key[32(n-1)..32n-1] Pn treat the key as cyclic
ctext Encrypt(salt[0..63]) P1 ctext[0..31]
P2 ctext[32..63] for(n = 2..9)
ctext Encrypt(ctext salt[64(n-1)..64n-1]) encrypt using the current key schedule and
treat the salt as cyclic
P2n-1) ctext[0..31] P2n ctext[32..63]
for(i = 1..4) for(n = 0..127)
ctext Encrypt(ctext salt[64(n-1)..64n-1]) as above
Si[2n] ctext[0..31] Si[2n+1] ctext[32..63]
return state
Hence, ExpandKey(state, 0, key) is the same as regular Blowfish key schedule since all
XORs with the all-zero salt value are ineffectual.
ExpandKey(state, 0, salt) is similar, but uses the salt as a 128-bit key.
The full bcrypt algorithm utilizes these functions to compute a hash from a given input derived
from the password, as follows:
bcrypt(cost, salt, input) state EksBlowfishSetup(cost, salt, input)
ctext "OrpheanBeholderScryDoubt" three 64-bit blocks
repeat ctext EncryptECB(state, ctext) encrypt using
standard Blowfish in ECB mode return Concatenate(cost, salt, ctext)
User input The mathematical algorithm itself requires
initialization with 18 32-bit subkeys.
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."
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 Mazières 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 special characters.
See e.g. Feb 1, 2010 jBCrypt security advisory or Changes in CRYPT_BLOWFISH in PHP 5.3.7.
See also
crypt - password storage and verification scheme - Blowfish
scrypt Key stretching
PBKDF2 References
External links bcrypt file encryption program homepage - bcrypt
is also the name of a cross-platform file encryption utility implementing the Blowfish
cipher, developed in 2002.