brief introduction
One of the cryptographic algorithms that we will introduce today is bcrypt, a cryptographic hash function designed by Niels Provos and David Mazi res, which was based on the Blowfish password and was introduced at USENIX in 1999.
In addition to adding salt to protect against rainbow table attacks, one of the most important features of bcrypt is its adaptability, which ensures that the encryption speed is within a certain range. Even if the computer has a very high computing power, the encryption speed can be slowed down by increasing the number of iterations so that it can resist violent search attacks.
The bcrypt function is the default password hashing algorithm for OpenBSD and other systems, including some Linux distributions such as SUSE Linux.
How bcrypt works
Let's first review Blowfish's encryption principles. Blowfish first needs to generate K arrays and S-boxes for encryption.Blowfish takes some time to generate the final K array and S-box, and each new key needs to be preprocessed with approximately 4 KB of text, which is slower than other block cipher algorithms. However, once the generation is complete, or the key remains unchanged, blowfish is a fast method of group encryption.
Is it good to be slow?
Of course, because for a normal application, the key will not be changed frequently. Therefore, the preprocessing will only be generated once. It will be fast to use later.
For a malicious attacker, each attempt at a new key requires a lengthy preprocessing, so it is very inexpensive for the attacker to crack the blowfish algorithm. So blowfish is resistant to dictionary attacks.
Provos and Mazi res take advantage of this and further develop it. They have developed a new key-setting algorithm for Blowfish, which calls the resulting password "Eksblowfish" ("expensive key schedule Blowfish")This is an improved algorithm for Blowfish. In the initial key setting of bcrypt, both salt and password are used to set the subkey. After a round of standard Blowfish algorithms, salt and password are used alternatelyPassword is the key, and each round depends on the state of the previous key. Although in theory, the bcrypt algorithm is not as strong as blowfish, because the number of rounds to reset the key in bcrpyt is configurable, it is better to resist violent attacks by increasing the number of rounds.
bcrypt algorithm implementation
Simply put, the bcrypt algorithm is the result of 64 blowfish encryptions of the string OrpheanBeholderScryDoubt. A friend will ask, is bcrypt not used to encrypt passwords? How is a string encrypted?
Don't worry, bcrpyt uses the password as a factor to encrypt the string, and it also encrypts the string. Let's look at the basic algorithm implementation of bcrypt:
Function bcrypt
Input:
cost: Number (4..31) log2(Iterations). e.g. 12 ==> 212 = 4,096 iterations
salt: array of Bytes (16 bytes) random salt
password: array of Bytes (1..72 bytes) UTF-8 encoded password
Output:
hash: array of Bytes (24 bytes)
//Initialize Blowfish state with expensive key setup algorithm
//P: array of 18 subkeys (UInt32[18])
//S: Four substitution boxes (S-boxes), S0...S3. Each S-box is 1,024 bytes (UInt32[256])
P, S <- EksBlowfishSetup(cost, salt, password)
//Repeatedly encrypt the text "OrpheanBeholderScryDoubt" 64 times
ctext <- "OrpheanBeholderScryDoubt" //24 bytes ==> three 64-bit blocks
repeat (64)
ctext <- EncryptECB(P, S, ctext) //encrypt using standard Blowfish in ECB mode
//24-byte ctext is resulting password hash
return Concatenate(cost, salt, ctext)
The above function bcrypt has three inputs and one output.
In the input section, cost denotes the number of turns, which we can specify by ourselves. Encrypting more turns is slower.
Salt is an encrypted salt used to confuse password use.
The password is the password we want to encrypt.
The final output is the encrypted result hash.
With three inputs, we will call the EksBlowfishSetup function to initialize 18 subkeys and 4 1-K S-boxes to reach the final P and S.
Then the OrpheanBeholderScryDoubt is blowfish 64 times using P and S, and the result is obtained.
Next, look at the algorithm implementation of the EksBlowfishSetup method:
Function EksBlowfishSetup
Input:
password: array of Bytes (1..72 bytes) UTF-8 encoded password
salt: array of Bytes (16 bytes) random salt
cost: Number (4..31) log2(Iterations). e.g. 12 ==> 212 = 4,096 iterations
Output:
P: array of UInt32 array of 18 per-round subkeys
S1..S4: array of UInt32 array of four SBoxes; each SBox is 256 UInt32 (i.e. 1024 KB)
//Initialize P (Subkeys), and S (Substitution boxes) with the hex digits of pi
P, S <- InitialState()
//Permutate P and S based on the password and salt
P, S <- ExpandKey(P, S, salt, password)
//This is the "Expensive" part of the "Expensive Key Setup".
//Otherwise the key setup is identical to Blowfish.
repeat (2cost)
P, S <- ExpandKey(P, S, 0, password)
P, S <- ExpandKey(P, S, 0, salt)
return P, S
The code is simple, and EksBlowfishSetup takes our three parameters above and returns the final P with 18 sub key s and 4 Sbox sizes of 1k.
Initialize first to get the initial P and S.
ExpandKey is then called, salt and password are passed in, and the first round of P and S is generated.
It then loops 2 cost squares, alternately uses password and salt as parameters to generate P and S, and returns.
Finally, take a look at the implementation of ExpandKey:
Function ExpandKey
Input:
password: array of Bytes (1..72 bytes) UTF-8 encoded password
salt: Byte[16] random salt
P: array of UInt32 Array of 18 subkeys
S1..S4: UInt32[1024] Four 1 KB SBoxes
Output:
P: array of UInt32 Array of 18 per-round subkeys
S1..S4: UInt32[1024] Four 1 KB SBoxes
//Mix password into the P subkeys array
for n <- 1 to 18 do
Pn <- Pn xor password[32(n-1)..32n-1] //treat the password as cyclic
//Treat the 128-bit salt as two 64-bit halves (the Blowfish block size).
saltHalf[0] <- salt[0..63] //Lower 64-bits of salt
saltHalf[1] <- salt[64..127] //Upper 64-bits of salt
//Initialize an 8-byte (64-bit) buffer with all zeros.
block <- 0
//Mix internal state into P-boxes
for n <- 1 to 9 do
//xor 64-bit block with a 64-bit salt half
block <- block xor saltHalf[(n-1) mod 2] //each iteration alternating between saltHalf[0], and saltHalf[1]
//encrypt block using current key schedule
block <- Encrypt(P, S, block)
P2n <- block[0..31] //lower 32-bits of block
P2n+1 <- block[32..63] //upper 32-bits block
//Mix encrypted state into the internal S-boxes of state
for i <- 1 to 4 do
for n <- 0 to 127 do
block <- Encrypt(state, block xor salt[64(n-1)..64n-1]) //as above
Si[2n] <- block[0..31] //lower 32-bits
Si[2n+1] <- block[32..63] //upper 32-bits
return state
ExpandKey is mainly used to generate P and S. Algorithms are very complex to generate, so you can study them in detail if you are interested.
Structure of bcrypt hash
We can use bcrypt to encrypt the password and eventually save it to the system as bcrypt hash in the following format:
$2b$[cost]$[22 character salt][31 character hash]
For example:
$2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy \__/\/ \____________________/\_____________________________/ Alg Cost Salt Hash
In the example above, $2a$represents the unique flag of the hash algorithm. This represents the bcrypt algorithm.
10 represents the cost factor, which is the tenth power of 2, or 1024 rounds.
N9qo8uLOickgx2ZMRZoMye is a base64-encoded 22-length character with 16 bytes (128bits) of salt.
The final IjZAgcfl7p92ldGxad68LJZdL17lhWy is a hash of 24 bytes (192bits), encoded by bash64 and 31 characters long.
History of hash
This hash format follows the Modular Crypt Format format used when storing passwords in OpenBSD password files. The format definitions initially are as follows:
- $1$: MD5-based crypt ('md5crypt')
- $2$: Blowfish-based crypt ('bcrypt')
- $sha1$: SHA-1-based crypt ('sha1crypt')
- $5$: SHA-256-based crypt ('sha256crypt')
- $6$: SHA-512-based crypt ('sha512crypt')
However, the original specification did not define how to handle non-ASCII characters, nor did it define how to handle null terminators.
- String must be UTF-8 encoding
- Must contain null Terminator
Since these changes were included, the version number of bcrypt was changed to $2a$.
However, in June 2011, due to a bug in PHP's crypt_blowfish implementation of bcypt, they recommended that system administrators update their existing password database and replace $2a$with $2x$to indicate that these hashes are bad (requiring the old algorithm)They also recommend that crypt_blowfish use the first $2y$for the hash value generated by the new algorithm. Of course, this change is limited to crypt_blowfish for PHP only.
Then in February 2014, a bug was found in OpenBSD's bcrypt implementation that stored the length of the string in an unsigned char (that is, 8-bit Byte). If the password was longer than 255 characters, it would overflow.
Because bcrypt was created for OpenBSD, when a bug appears in their library, they decide to upgrade the version number to $2b$.
This article is included in http://www.flydean.com/37-bcrypt/
The most popular interpretations, the deepest dry goods, the most concise tutorials, and many little tricks you don't know are all yours to discover!
Welcome to my Public Number:'What's happening in the program', know the technology, know you better!