密碼學系列之:bcrypt加密算法詳解

簡介

今天要給大家介紹的一種加密算法叫做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的基本算法實作：

上述函數bcrypt 有3個輸入和1個輸出。

在輸入部分，cost 表示的是輪循的次數，這個我們可以自己指定，輪循次數多加密就慢。

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

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

最後的輸出是加密後的結果hash。

有了3個輸入，我們會調用eksblowfishsetup函數去初始化18個subkeys和4個1k大小的s-boxes，進而達到最終的p和s。

然後使用p和s對”orpheanbeholderscrydoubt” 進行64次blowfish運算，最終得到結果。

接下來看下 eksblowfishsetup方法的算法實作：

代碼很簡單，eksblowfishsetup 接收上面我們的3個參數，傳回最終的包含18個子key的p和4個1k大小的sbox。

首先初始化，得到最初的p和s。

然後調用expandkey，傳入salt和password，生成第一輪的p和s。

然後循環2的cost方次，輪流使用password和salt作為參數去生成p和s，最後傳回。

最後看一下expandkey的實作：

expandkey主要用來生成p和s，算法的生成比較複雜，大家感興趣的可以詳細研究一下。

bcrypt hash的結構

我們可以使用bcrypt來加密密碼，最終以bcrypt hash的形式儲存到系統中，一個bcrypt hash的格式如下：

比如：

上面例子中，<code>$2a$</code> 表示的hash算法的唯一标志。這裡表示的是bcrypt算法。

10 表示的是代價因子，這裡是2的10次方，也就是1024輪。

n9qo8uloickgx2zmrzomye 是16個位元組（128bits）的salt經過base64編碼得到的22長度的字元。

最後的ijzagcfl7p92ldgxad68ljzdl17lhwy是24個位元組（192bits）的hash，經過bash64的編碼得到的31長度的字元。

這種hash格式是遵循的是openbsd密碼檔案中存儲密碼時使用的modular crypt format格式。最開始的時候格式定義是下面的：

<code>$1$</code>: md5-based crypt (‘md5crypt’)

<code>$2$</code>: blowfish-based crypt (‘bcrypt’)

<code>$sha1$</code>: sha-1-based crypt (‘sha1crypt’)

<code>$5$</code>: sha-256-based crypt (‘sha256crypt’)

<code>$6$</code>: sha-512-based crypt (‘sha512crypt’)

但是最初的規範沒有定義如何處理非ascii字元，也沒有定義如何處理null終止符。修訂後的規範規定，在hash字元串時：

string 必須是utf-8編碼

必須包含null終止符

因為包含了這些改動，是以bcrypt的版本号被修改成了 <code>$2a$</code>。

但是在2011年6月，因為php對bcypt的實作 crypt_blowfish 中的一個bug，他們建議系統管理者更新他們現有的密碼資料庫，用<code>$2x$</code>代替<code>$2a$</code>，以表明這些哈希值是壞的（需要使用舊的算法）。他們還建議讓crypt_blowfish對新算法生成的哈希值使用頭<code>$2y$</code>。 當然這個改動隻限于php的crypt_blowfish。

然後在2014年2月，在openbsd的bcrypt實作中也發現了一個bug，他們将字元串的長度存儲在無符号char中（即8位byte）。如果密碼的長度超過255個字元，就會溢出來。

因為bcrypt是為openbsd建立的。是以當他們的庫中出現了一個bug時, 他們決定将版本号更新到<code>$2b$</code>。

本文已收錄于 http://www.flydean.com/37-bcrypt/ 最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！ 歡迎關注我的公衆号:「程式那些事」,懂技術，更懂你！