簡介

今天要給大家介紹的一種加密算法叫做bcrypt, bcrypt是由Niels Provos和David Mazières設計的密碼哈希函數(shù)掀亥，他是基于Blowfish密碼而來的，并于1999年在USENIX上提出托享。

除了加鹽來抵御rainbow table 攻擊之外舶得，bcrypt的一個非常重要的特征就是自適應性，可以保證加密的速度在一個特定的范圍內(nèi)痒钝，即使計算機的運算能力非常高婉支，可以通過增加迭代次數(shù)的方式鸯隅，使得加密速度變慢，從而可以抵御暴力搜索攻擊向挖。

bcrypt函數(shù)是OpenBSD和其他系統(tǒng)包括一些Linux發(fā)行版（如SUSE Linux）的默認密碼哈希算法蝌以。

bcrypt的工作原理

我們先回顧一下Blowfish的加密原理。 blowfish首先需要生成用于加密使用的K數(shù)組和S-box, blowfish在生成最終的K數(shù)組和S-box需要耗費一定的時間何之，每個新的密鑰都需要進行大概4 KB文本的預處理饼灿，和其他分組密碼算法相比，這個會很慢帝美。但是一旦生成完畢碍彭，或者說密鑰不變的情況下，blowfish還是很快速的一種分組加密方法悼潭。

那么慢有沒有好處呢庇忌？

當然有，因為對于一個正常應用來說舰褪，是不會經(jīng)常更換密鑰的皆疹。所以預處理只會生成一次。在后面使用的時候就會很快了占拍。

而對于惡意攻擊者來說略就，每次嘗試新的密鑰都需要進行漫長的預處理捎迫，所以對攻擊者來說要破解blowfish算法是非常不劃算的。所以blowfish是可以抵御字典攻擊的表牢。

Provos和Mazières利用了這一點窄绒，并將其進一步發(fā)展。他們?yōu)锽lowfish開發(fā)了一種新的密鑰設置算法崔兴，將由此產(chǎn)生的密碼稱為 "Eksblowfish"（"expensive key schedule Blowfish"）彰导。這是對Blowfish的改進算法，在bcrypt的初始密鑰設置中敲茄，salt 和 password 都被用來設置子密鑰位谋。然后經(jīng)過一輪輪的標準Blowfish算法，通過交替使用salt 和 password作為key堰燎，每一輪都依賴上一輪子密鑰的狀態(tài)掏父。雖然從理論上來說，bcrypt算法的強度并不比blowfish更好秆剪，但是因為在bcrpyt中重置key的輪數(shù)是可以配置的损同，所以可以通過增加輪數(shù)來更好的抵御暴力攻擊。

bcrypt算法實現(xiàn)

簡單點說bcrypt算法就是對字符串OrpheanBeholderScryDoubt 進行64次blowfish加密得到的結(jié)果鸟款。有朋友會問了，bcrypt不是用來對密碼進行加密的嗎茂卦？怎么加密的是一個字符串何什？

別急，bcrpyt是將密碼作為對該字符串加密的因子等龙，同樣也得到了加密的效果处渣。我們看下bcrypt的基本算法實現(xiàn)：

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)

上述函數(shù)bcrypt 有3個輸入和1個輸出。

在輸入部分蛛砰，cost 表示的是輪循的次數(shù)罐栈，這個我們可以自己指定，輪循次數(shù)多加密就慢泥畅。

salt 是加密用鹽荠诬，用來混淆密碼使用。

password 就是我們要加密的密碼了位仁。

最后的輸出是加密后的結(jié)果hash柑贞。

有了3個輸入，我們會調(diào)用EksBlowfishSetup函數(shù)去初始化18個subkeys和4個1K大小的S-boxes聂抢，從而達到最終的P和S钧嘶。

然后使用P和S對"OrpheanBeholderScryDoubt" 進行64次blowfish運算，最終得到結(jié)果琳疏。

接下來看下 EksBlowfishSetup方法的算法實現(xiàn)：

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個參數(shù)闸拿，返回最終的包含18個子key的P和4個1k大小的Sbox。

首先初始化书幕，得到最初的P和S新荤。

然后調(diào)用ExpandKey，傳入salt和password按咒，生成第一輪的P和S迟隅。

然后循環(huán)2的cost方次，輪流使用password和salt作為參數(shù)去生成P和S励七，最后返回智袭。

最后看一下ExpandKey的實現(xiàn)：

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的結(jié)構(gòu)

我們可以使用bcrypt來加密密碼，最終以bcrypt hash的形式保存到系統(tǒng)中两波，一個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個字節(jié)（128bits）的salt經(jīng)過base64編碼得到的22長度的字符嘀倒。

最后的IjZAgcfl7p92ldGxad68LJZdL17lhWy是24個字節(jié)（192bits）的hash，經(jīng)過bash64的編碼得到的31長度的字符局冰。

hash的歷史

這種hash格式是遵循的是OpenBSD密碼文件中存儲密碼時使用的Modular Crypt Format格式测蘑。最開始的時候格式定義是下面的：

• $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')

但是最初的規(guī)范沒有定義如何處理非ASCII字符，也沒有定義如何處理null終止符康二。修訂后的規(guī)范規(guī)定碳胳，在hash字符串時：

• String 必須是UTF-8編碼
• 必須包含null終止符

因為包含了這些改動，所以bcrypt的版本號被修改成了 $2a$沫勿。

但是在2011年6月挨约，因為PHP對bcypt的實現(xiàn) crypt_blowfish 中的一個bug，他們建議系統(tǒng)管理員更新他們現(xiàn)有的密碼數(shù)據(jù)庫产雹，用$2x$代替$2a$烫罩，以表明這些哈希值是壞的（需要使用舊的算法）。他們還建議讓crypt_blowfish對新算法生成的哈希值使用頭$2y$洽故。 當然這個改動只限于PHP的crypt_blowfish贝攒。

然后在2014年2月，在OpenBSD的bcrypt實現(xiàn)中也發(fā)現(xiàn)了一個bug时甚，他們將字符串的長度存儲在無符號char中（即8位Byte）隘弊。如果密碼的長度超過255個字符哈踱，就會溢出來。

因為bcrypt是為OpenBSD創(chuàng)建的梨熙。所以當他們的庫中出現(xiàn)了一個bug時, 他們決定將版本號升級到$2b$开镣。

本文已收錄于 http://www.flydean.com/37-bcrypt/

最通俗的解讀，最深刻的干貨咽扇，最簡潔的教程邪财，眾多你不知道的小技巧等你來發(fā)現(xiàn)！

歡迎關(guān)注我的公眾號:「程序那些事」,懂技術(shù)质欲，更懂你树埠！