bcrypt

For the bcrypt file encryption utility, see Blowfish (cipher).

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.[1] 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 other systems including some Linux distributions such as SUSE Linux.[2] 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.[3] The rest of the hash string includes the cost parameter, a 128-bit salt (base-64 encoded as 22 characters), and 184 bits of the resulting hash value (base-64 encoded as 31 characters).[4] 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 $2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy 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.

There are implementations of bcrypt for Ruby, Python,[5] C, C#, Perl, PHP, Java, JavaScript, 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 accurately 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. 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.

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, key)
        state \gets 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 \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(n = 0..127)
            ctext \gets Encrypt(ctext \oplus salt[64(n-1)..64n-1]) //as above
            Si[2n] \gets ctext[0..31]
            Si[2n+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 derived from the password, as follows:

bcrypt(cost, salt, input)
    state \gets EksBlowfishSetup(cost, salt, input)
    ctext \gets "OrpheanBeholderScryDoubt" //three 64-bit blocks
    repeat (64)
        ctext \gets EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode
    return Concatenate(cost, salt, ctext)

User input

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[1] 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 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,[6] "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.[7]

See also

References

  1. 1 2 Provos, Niels; Mazières, David; Talan Jason Sutton 2012 (1999). "A Future-Adaptable Password Scheme". Proceedings of 1999 USENIX Annual Technical Conference: 81–92.
  2. ↑ "SUSE Security Announcement: (SUSE-SA:2011:035)". 23 August 2011. Retrieved 20 August 2015. SUSE's crypt() implementation supports the blowfish password hashing function (id $2a) and system logins by default also use this method.
  3. ↑ passlib. "Modular Crypt Format".
  4. ↑ passlib. "BCrypt".
  5. ↑ https://pypi.python.org/pypi/bcrypt/2.0.0
  6. ↑ Schneier, Bruce (1994). "Fast Software Encryption, Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)". Cambridge Security Workshop Proceedings (December 1993) (Springer-Verlag): 191–204.
  7. ↑ Feb 1, 2010 jBCrypt security advisory or Changes in CRYPT_BLOWFISH in PHP 5.3.7.
This article is issued from Wikipedia - version of the Friday, April 22, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.