簡介
今天要給大家介紹的一種加密算法叫做bcrypt, bcrypt是由Niels Provos和David Mazières設計的密碼哈希函數，他是基于Blowfish密碼而來的，并于1999年在USENIX上提出。
除了加鹽來抵禦rainbow table 攻擊之外，bcrypt的一個非常重要的特征就是自适應性，可以保證加密的速度在一個特定的範圍内，即使計算機的運算能力非常高，可以通過增加疊代次數的方式，使得加密速度變慢，進而可以抵禦暴力搜尋攻擊。
bcrypt函數是OpenBSD和其他系統包括一些Linux發行版（如SUSE Linux）的預設密碼雜湊演算法。
bcrypt的工作原理
我們先回顧一下Blowfish的加密原理。 blowfish首先需要生成用于加密使用的K數組和S-box, blowfish在生成最終的K數組和S-box需要耗費一定的時間，每個新的密鑰都需要進行大概4 KB文本的預處理，和其他分組密碼算法相比，這個會很慢。但是一旦生成完畢，或者說密鑰不變的情況下，blowfish還是很快速的一種分組加密方法。
那麼慢有沒有好處呢？
當然有，因為對于一個正常應用來說，是不會經常更換密鑰的。是以預處理隻會生成一次。在後面使用的時候就會很快了。
而對于惡意攻擊者來說，每次嘗試新的密鑰都需要進行漫長的預處理，是以對攻擊者來說要破解blowfish算法是非常不劃算的。是以blowfish是可以抵禦字典攻擊的。
Provos和Mazières利用了這一點，并将其進一步發展。他們為Blowfish開發了一種新的密鑰設定算法，将由此産生的密碼稱為 “Eksblowfish”（”expensive key schedule Blowfish”）。這是對Blowfish的改進算法，在bcrypt的初始密鑰設定中，salt 和 password 都被用來設定子密鑰。然後經過一輪輪的标準Blowfish算法，通過交替使用salt 和 password作為key，每一輪都依賴上一輪子密鑰的狀态。雖然從理論上來說，bcrypt算法的強度并不比blowfish更好，但是因為在bcrpyt中重置key的輪數是可以配置的，是以可以通過增加輪數來更好的抵禦暴力攻擊。
bcrypt算法實作
簡單點說bcrypt算法就是對字元串OrpheanBeholderScryDoubt 進行64次blowfish加密得到的結果。有朋友會問了，bcrypt不是用來對密碼進行加密的嗎？怎麼加密的是一個字元串？
别急，bcrpyt是将密碼作為對該字元串加密的因子，同樣也得到了加密的效果。我們看下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) 上述函數bcrypt 有3個輸入和1個輸出。
在輸入部分，cost 表示的是輪循的次數，這個我們可以自己指定，輪循次數多加密就慢。
salt 是加密用鹽，用來混淆密碼使用。
password 就是我們要加密的密碼了。
最後的輸出是加密後的結果hash。
有了3個輸入，我們會調用EksBlowfishSetup函數去初始化18個subkeys和4個1K大小的S-boxes，進而達到最終的P和S。
然後使用P和S對”OrpheanBeholderScryDoubt” 進行64次blowfish運算，最終得到結果。
接下來看下 EksBlowfishSetup方法的算法實作：
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 代碼很簡單，EksBlowfishSetup 接收上面我們的3個參數，傳回最終的包含18個子key的P和4個1k大小的Sbox。
首先初始化，得到最初的P和S。
然後調用ExpandKey，傳入salt和password，生成第一輪的P和S。
然後循環2的cost方次，輪流使用password和salt作為參數去生成P和S，最後傳回。
最後看一下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主要用來生成P和S，算法的生成比較複雜，大家感興趣的可以詳細研究一下。
bcrypt hash的結構
我們可以使用bcrypt來加密密碼，最終以bcrypt hash的形式儲存到系統中，一個bcrypt hash的格式如下：
$2b$[cost]$[22 character salt][31 character hash] 比如：
$2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy
\__/\/ \____________________/\_____________________________/
Alg Cost Salt Hash 上面例子中，
$2a$
表示的hash算法的唯一标志。這裡表示的是bcrypt算法。
10 表示的是代價因子，這裡是2的10次方，也就是1024輪。
N9qo8uLOickgx2ZMRZoMye 是16個位元組（128bits）的salt經過base64編碼得到的22長度的字元。
最後的IjZAgcfl7p92ldGxad68LJZdL17lhWy是24個位元組（192bits）的hash，經過bash64的編碼得到的31長度的字元。
hash的曆史
這種hash格式是遵循的是OpenBSD密碼檔案中存儲密碼時使用的Modular Crypt Format格式。最開始的時候格式定義是下面的：
-
$1$
-
$2$
-
$sha1$
-
$5$
-
$6$
但是最初的規範沒有定義如何處理非ASCII字元，也沒有定義如何處理null終止符。修訂後的規範規定，在hash字元串時：
- String 必須是UTF-8編碼
- 必須包含null終止符
因為包含了這些改動，是以bcrypt的版本号被修改成了
$2a$
。
但是在2011年6月，因為PHP對bcypt的實作 crypt_blowfish 中的一個bug，他們建議系統管理者更新他們現有的密碼資料庫，用
$2x$
代替
$2a$
，以表明這些哈希值是壞的（需要使用舊的算法）。他們還建議讓crypt_blowfish對新算法生成的哈希值使用頭
$2y$
。 當然這個改動隻限于PHP的crypt_blowfish。
然後在2014年2月，在OpenBSD的bcrypt實作中也發現了一個bug，他們将字元串的長度存儲在無符号char中（即8位Byte）。如果密碼的長度超過255個字元，就會溢出來。
因為bcrypt是為OpenBSD建立的。是以當他們的庫中出現了一個bug時, 他們決定将版本号更新到
$2b$
![TYVJ-P1035 棋盤覆寫[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)