Bcrypt
Encyclopedia
bcrypt is an adaptive cryptographic hash function
for password
s 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, and other languages.
EksBlowfishSetup(cost, salt, key)
state
InitState
state
ExpandKey(state, salt, key)
repeat (2cost)
state
ExpandKey(state, 0, salt)
state
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
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(j = 0..127)
ctext
Encrypt(ctext 
salt[64(n-1)..64n-1]) //as above
Si[2j]
ctext[0..31]
Si[2j+1]
ctext[32..63]
return state
Hence,
The full bcrypt algorithm utilizes these functions to compute a hash from a given input as follows:
bcrypt(cost, salt, key, input)
state
EksBlowfishSetup(cost, salt, key)
ctext
input
repeat (64)
ctext
EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode
return Concatenate(cost, salt, ctext)
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
for password
Password
A password is a secret word or string of characters that is used for authentication, to prove identity or gain access to a resource . The password should be kept secret from those not allowed access....
s designed by Niels Provos
Niels Provos
Niels Provos is a researcher in the areas of secure systems, malware and cryptography. He is currently a Principal Software Engineer at Google. He received his PhD in Computer Science from the University of Michigan....
and David Mazières, based on the Blowfish
Blowfish (cipher)
Blowfish is a keyed, symmetric block cipher, designed in 1993 by Bruce Schneier and included in a large number of cipher suites and encryption products. Blowfish provides a good encryption rate in software and no effective cryptanalysis of it has been found to date...
cipher, and presented at USENIX
USENIX
-External links:* *...
in 1999. Besides incorporating a salt
Salt (cryptography)
In cryptography, a salt consists of random bits, creating one of the inputs to a one-way function. The other input is usually a password or passphrase. The output of the one-way function can be stored rather than the password, and still be used for authenticating users. The one-way function...
to protect against rainbow table
Rainbow table
A rainbow table is a precomputed table for reversing cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering the plaintext password, up to a certain length consisting of a limited set of characters. It is a form of time-memory tradeoff, using less...
attacks, bcrypt is an adaptive hash: over time it can be made slower and slower so it remains resistant to specific brute-force search
Brute-force search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...
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
Crypt (Unix)
In Unix computing, crypt is the name of both a utility program and a C programming function. Though both are used for encrypting data, they are otherwise essentially unrelated...
in OpenBSD
OpenBSD
OpenBSD is a Unix-like computer operating system descended from Berkeley Software Distribution , a Unix derivative developed at the University of California, Berkeley. It was forked from NetBSD by project leader Theo de Raadt in late 1995...
, there are implementations of bcrypt for Java, Python, C#, Ruby, Perl, and other languages.
Algorithm
The bcrypt algorithm depends heavily on its "Eksblowfish" key setup algorithm, which runs as follows:EksBlowfishSetup(cost, salt, key)
state
InitStatestate
ExpandKey(state, salt, key)repeat (2cost)
state
ExpandKey(state, 0, salt)state
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
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 cyclicctext
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 cyclicP2n-1)
ctext[0..31]P2n
ctext[32..63]for(i = 1..4)
for(j = 0..127)
ctext
Encrypt(ctext salt[64(n-1)..64n-1]) //as aboveSi[2j]
ctext[0..31]Si[2j+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 as follows:
bcrypt(cost, salt, key, input)
state
EksBlowfishSetup(cost, salt, key)ctext
inputrepeat (64)
ctext
EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB modereturn 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#
- 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-platformPlatform (computing)A computing platform includes some sort of hardware architecture and a software framework , where the combination allows software, particularly application software, to run...
file encryptionEncryptionIn cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
utility implementing the BlowfishBlowfish (cipher)Blowfish is a keyed, symmetric block cipher, designed in 1993 by Bruce Schneier and included in a large number of cipher suites and encryption products. Blowfish provides a good encryption rate in software and no effective cryptanalysis of it has been found to date...
cipherCipherIn cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
, developed in 2002.