bcrypt

bcrypt is an adaptive cryptographic hash 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 hash: over time it can be made slower and slower so it remains resistant to specific brute-force search attacks against the hash and the salt.

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 (really, a 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. Then there are 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. This is not cryptographically significantly stronger than the standard Blowfish key schedule, but the number of rekeying rounds is configurable; the hashing process can therefore be made arbitrarily slow, which helps deter brute-force attacks upon the hash or salt.

The number of rounds of keying is a power of two, which is an input to the algorithm. The number is encoded in the textual hash.

Besides the original implementation for crypt in OpenBSD, there are implementations of bcrypt for Java, Python, C#, Ruby, Perl, PHP 5.3+ and other languages.

Algorithm

The bcrypt algorithm depends heavily on its "Eksblowfish" key setup algorithm, which runs as follows:

EksBlowfishSetup(cost, salt, key)
    state $\gets$ InitState()
    state $\gets$ ExpandKey(state, salt, key)
    repeat (2cost)
        state $\gets$ ExpandKey(state, 0, salt)
        state $\gets$ ExpandKey(state, 0, key)
    return state

InitState works as in the original Blowfish algorithm, populating the P-array and S-box entries with the fractional part of $\pi$ in hexadecimal.

The ExpandKey function does the following:

ExpandKey(state, salt, key)
    for(n = 1..18)
        Pn $\gets$ key[32(n-1)..32n-1] $\oplus$ Pn //treat the key as cyclic
    ctext $\gets$ Encrypt(salt[0..63])
    P1 $\gets$ ctext[0..31]
    P2 $\gets$ ctext[32..63]
    for(n = 2..9)
        ctext $\gets$ Encrypt(ctext $\oplus$ salt[64(n-1)..64n-1]) //encrypt using the current key schedule and treat the salt as cyclic
        P2n-1) $\gets$ ctext[0..31]
        P2n $\gets$ ctext[32..63]
    for(i = 1..4)
        for(j = 0..127)
            ctext $\gets$ Encrypt(ctext $\oplus$ salt[64(n-1)..64n-1]) //as above
            Si[2j] $\gets$ ctext[0..31]
            Si[2j+1] $\gets$ 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 as follows:

bcrypt(cost, salt, key, input)
    state $\gets$ EksBlowfishSetup(cost, salt, key)
    ctext $\gets$ input
    repeat (64)
        ctext $\gets$ EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode
    return Concatenate(cost, salt, ctext)

See also

• crypt - password storage and verification scheme - Blowfish
• jBCrypt - bcrypt implementation for Java
• py-bcrypt - bcrypt implementation for Python
• pbcryptnet - bcrypt implementation for C#
• JFBCrypt - bcrypt implementation for Objective C
• bcrypt-ruby - bcrypt implementation for Ruby
• Crypt::Eksblowfish::Bcrypt - bcrypt implementation for Perl
• bcrypt file encryption program homepage - bcrypt is also the name of a cross-platform file encryption utility implementing the Blowfish cipher, developed in 2002.