Best practicing for password protection

如何有效保護用戶密碼的議題，估計在網路上討論不下數千次。本篇文章除了整理並分析何種方式是個 “壞方法” 外，也希望經過不斷的思考來理出最佳的解決方案(Best practices)。

本篇文章標題取用 “Best practicing” 而非 “Best practices” 的意義，在於內容所建議的方法，目前可能並非是最佳解決方案，未來若有更好的方法也將持續更新本篇的內容。

前言

現在做 “好” 一個網路應用是非常困難的事 (前提是如果 “想” 做好的話)。因為單是如何保護好客戶的密碼，就是一門大學問。

首先，我們要思考的是 “是否有必要儲存客戶的密碼在我們的系統中”? 如果將認證的系統由他方服務提供而不會影響商業模式的運作時，那麼與其它系統整合會是個比較好的，例如使用 Facebook 的帳號登入網站或系統的認證方式。

反之，如果決定要自行建置，則考量點就會有很多。除了需要考量安全性外，還需要考慮效能的問題，因為 “通常” 安全性高的同時也伴隨著低效能的壞處。這意謂著同樣是數萬人上線的網站，若選擇安全性高的方法，可能會比安全性低的方法額外需要更多的機器來運作。

另外在資料外洩的議題上，本篇將討論 “資料庫外洩” 以及 “資料庫與網站程式皆外洩” 的兩種情形，後者在網路上是目前比較少人探討的議題。有時資料外洩的並不只是資料庫的資料，更嚴重的是除了資料庫外，連整個網站的程式也一併遭到竊取，而這兩種情形面對著不同層級的威脅。

然而一旦資料外洩後，有心人士可以依照密碼保存的方式，決定採用 “Unhash/Decrypt attacks” 或 “Statistics attacks” 等攻擊方式。不管是何種方式，目的就是希望能夠還原用戶的密碼，而我們想做的就是盡量降低被還原的可能性。

以下是筆者整理的常見方法及其分析。

儲存用戶密碼之方法

1. 明碼(plaintext)

最簡單的保存方式，就是將用戶註冊時所輸入的密碼，不經過任何的處理，原封不動的儲存在資料庫中。例如密碼為 “123456”，在資料庫中則以 “123456” 儲存。然而這種簡單的方式也是最危險的。

例如，用戶 ant 帳號所使用的密碼為 “123456”, 則在資料庫中以 “123456” 儲存，如下:

如果資料庫外洩時，任何人都可以直接看到所有用戶的密碼。另一個問題是，只要是有權限瀏覽資料庫的人，也幾乎都可能隨時取得用戶的密碼，例如資料庫管理員或甚至是程式設計師。

這種方式不管是面對 “資料庫外洩” 或 “資料庫與網站程式皆外洩” 的情形都沒有任何防護措施，因此明碼是最不建議使用的方式。

2. 簡易雜湊法 (Pure Hash)

演算法為: Hash(明碼)。

雜湊法 (Hash) 可以視為一數學函式，專職將某值轉換成另一值。常見的雜湊法有很多，例如 MD5, SHA1 等。

假設選定為 MD5, 在實際操作上，當用戶註冊的密碼為 “123456” 時，此時會先將 “123456” 經由 MD5 函式運算，也就是 MD5(123456) 會得到 “f447b20a7fcbf53a5d5be013ea0b15af” 結果，再將 “f447b20a7fcbf53a5d5be013ea0b15af” 值寫入資料庫中，而不是將明碼 “123456” 寫入資料庫。

當下次該用戶嘗試登入時，會將輸入的值經過 MD5 函式運算後，再與資料庫的值進行比對，如果字串完全符合則表示用戶輸入了正確的密碼，進而允許用戶登入網站或系統。所以當用戶以 “ant” 為用戶名及密碼為 “123456” 登入時，則網站或系統會先將 “123456” 以 MD5 函式運算後得值為 “f447b20a7fcbf53a5d5be013ea0b15af”，再使用 “姓名=ant AND 密碼=f447b20a7fcbf53a5d5be013ea0b15af” 為搜尋值於資料庫中查詢。

整個密碼的處理流程中，明碼 “123456” 將不會永久性的儲存在系統或資料庫中，而可避免資料庫人員在瀏覽資料庫時，可以直接看到明碼的情形。另外當使用這種方式保存密碼時，如果資料庫外洩時，對方取得的密碼欄位會是 “f447b20a7fcbf53a5d5be013ea0b15af” ，而不是明碼 “123456”。

取得資料庫的有心人士若想要知道原本的明碼，就需要解譯 “f447b20a7fcbf53a5d5be013ea0b15af” 的還原值為何，這在數學原理中是比較困難的。因為雜湊 )(Hash) 演算法是一種單向 (one-way) 運算函式，在原理上是難以從計算值推回原先的值，也就是幾乎無法由 “f447b20a7fcbf53a5d5be013ea0b15af” 經運算逆推回 “123456”，進而保護了所有用戶的原始密碼。

雖然從這點上看起來比明碼的方式好太多了，但仍然存在著弱點，例如目前常見的 “查表法” 式的攻擊。簡單來說，攻擊者可以事先準備好所有可能性的 MD5 清單表，如:

如此攻擊者只需要把 “f447b20a7fcbf53a5d5be013ea0b15af” 值於資料庫中查詢即可馬上比對出明碼為 “123456”，進而得知該用戶的密碼。所以理論上，只要查表資料庫夠齊全(即收集夠多的明碼對照表)，即可把解譯任何雜湊 (Hash) 值。所以，簡易雜湊法仍然不夠安全。

3. 加料式雜湊法 (Salted Hash)

演算法為: Hash(亂定值 + 明碼)。

面對 “查表法” 類的攻擊時，最直覺的方法就是增加查表的困難度。我們知道查表資料庫理論上可以收集所有可能之明碼的雜湊 (Hash) 值，但在實作上是有困難度的，因為攻擊者在空間與時間上，不太可能收集 “所有” 可能的查表值，而是僅盡量收集常見的對照值，例如 “password”, “123456” 等。因此，在這種限制下，查表資料庫 “通常” 不會收錄較無規則或看似亂碼的明碼值，例如 “i3flm234rmsldk543kf2jvl2sdfj123456”，這也是認定用戶通常不會真的將這麼難記的值當作密碼。

於是在防護手法上，網站或系統可以 “自動” 替用戶密碼添加 “亂定數” (salty)，如 “i3flm234rmsldk543kf2jvl2sdfj”。在這種情況下，當用戶使用 “123456” 密碼註冊時，程式會將 “亂定數” 加上其密碼後，才經由雜湊 (Hash) 函式運算，再儲存至資料庫中。如 MD5(“i3flm234rmsldk543kf2jvl2sdfj” + “123456”)，得出值為 “d0a970cc71d15aa10b07584a7bd31ff6”。

因此當用戶下次登入時，輸入密碼 “123456” 後，程式會再 “自動” 替用戶密碼添加 “亂定數” (salty)，成為 MD5(“i3flm234rmsldk543kf2jvl2sdfj” + “123456”) 來運算，則得出的值就會與資料庫的值一樣。這種防護方法就是賭定查表資料庫不會有 “亂定數” 為首的對照表。以此例來說，就是賭查表資料庫沒有 “i3flm234rmsldk543kf2jvl2sdfj” + “123456” 的對照表。

加料式雜湊法 (Salted Hash) 加強原本簡易雜湊法的安全性，加上操作簡單的特性，所以目前成為最常見的密碼保護方式。不過筆者要提醒的是，這種方法是基於賭上查表資料庫 “可能” 不會有 “亂定數” 前提下的保護策略，所以 “亂定數” 取值就變得非常重要，例如值不得太短，且值必須不是常見的值(盡量是亂數或近乎亂數產生的值)。

另外，加料式雜湊法的另一個前提是，網站或系統程式碼未遭受外洩。如果入侵行為導致除了資料庫外，程式也一併外洩時，此時有心人士可以從程式碼中得知 “亂定數” 之值，那麼依然可以有效地利用 “查表法” 進行解譯的攻擊。

例如，有心人士手中的查表資料庫如下:

此時從網站或系統程式碼中，發現 “亂定數” 為 “i3flm234rmsldk543kf2jvl2sdfj”，則可以據此來重新產生查表資料庫的對照值，例如原本的 “password” 明碼，改用 MD5(“i3flm234rmsldk543kf2jvl2sdfj” + “password”) 來取值，以此類推從而產生針對此資料庫的查表資料庫:

此時，再用原本查表式的攻擊時，就很容易找到 “d0a970cc71d15aa10b07584a7bd31ff6” 的對照值為 “123456”。

4. 加密方法 (Encrypted Password)

演算法為: Encrypt(明碼, 金鑰值)。

有些人會使用加解密的方式來保護密碼，例如 DES, AES 等。但這種方法的問題也不少，第一，加密耗用的資源比單一雜湊 (Hash) 演算法多；第二，加密金鑰需妥善保管，否則知道金鑰的人都可以解出所有用戶的密碼；第三，如果資料庫、程式與金鑰外洩，則此防護方式等同虛設，因為有心人士不需查表就可以直接用解密的方式還原密碼。

因此，筆者認為除非有完善的配套措施，否則不建議使用此種保護方法。

5. 複合式雜湊法

基於加料式雜湊法 (Salted Hash) 可以衍生出許多不同的變形。

A. “亂定數” 使用兩次以上

其中一種演算法為: 亂定數 + Hash(亂定數 + 明碼)。

延伸先前舉例的 “i3flm234rmsldk543kf2jvl2sdfj” 亂定數，則雜湊值為 “i3flm234rmsldk543kf2jvl2sdfj” + MD5(“i3flm234rmsldk543kf2jvl2sdfj” + “123456”)，並得其值為 “i3flm234rmsldk543kf2jvl2sdfj” + “d0a970cc71d15aa10b07584a7bd31ff6”。

這種複合式雜湊法加強的是查表資料庫的困難度，但是仍然沒有解決若程式一併外洩時的問題，因為有心人士從程式碼中得知 “亂定數” 後，可以直接將 “亂定數” 去除，進而留下 “d0a970cc71d15aa10b07584a7bd31ff6”。如此強度與加料式雜湊法 (Salted Hash) 是差不多的。

B. 使用兩種以上的加料式雜湊演算法

其中一種演算法為: MD5(SHA1(亂定數 + 明碼))。

以 PHP 程式語言為例:

$salty = "i3flm234rmsldk543kf2jvl2sdfj";
$password_hash = md5(sha1($salty + $password));

這種複合式雜湊法加強的是查表資料庫的困難度，因為要建立這種查表資料庫需要耗用較多的運算資源(因為使用兩次雜湊演算法)，但相對而言，比加料式雜湊法 (Salted Hash) 來得安全許多。但是最大的缺點就是我們網站或系統的運算資源也會耗用較多。

因此，有心人士取得資料庫及網站程式時，即使在知道 “亂定數” 的條件下，要重新產生查表資料庫也是一件很耗資源的事情。

6. HMAC 加料式演算法

其中一種演算法為: HMAC(SHA1, 亂定數 + 明碼, 金鑰值)。

以 PHP 程式語言為例:

$key = "146c07ef2479cedcd54c7c2af5cf3a80";
$salty = "i3flm234rmsldk543kf2jvl2sdfj";
$password_hash = hash_hmac("sha1", $salty + $password, $key);

HMAC 演算法有著加料式及加密方法的優點，使得查表式攻擊的成本以等比級數倍增，但因為 HMAC 耗用的資源更多，所以運算量要求最大，這也會造成網站或系統的負載需求更高。

統計特徵值的攻擊方法

排除不建議或類似的防護方法，筆者建議的是 “加料式雜湊法 (Salted Hash)”, “使用兩種以上的加料式雜湊演算法” 或 “HMAC 加料式演算法”，但若您有著更高安全的需求，則建議採用後面兩者。

另外，筆者在前言中有提到 “Statistics attacks”，此種攻擊方式是針對 “亂定數” 的手法。以前例的 “加料式雜湊法 (Salted Hash)” 來說，所有的用戶密碼皆是加上 “定數” 來處理，例如 “i3flm234rmsldk543kf2jvl2sdfj”，則用戶 ant 的密碼 “123456” 在資料庫會是:

我們知道 “123456” 其實是個常見的密碼，所以如果網站或系統的用戶數夠多，那麼我們可以假設 “123456” 為密碼的用戶比例，就會存有顯著的統計特徵值，例如資料庫可能為:

這意謂著 ant, guest 及 newbie 的密碼因為都是 “123456” 所以其值皆相同。此時就算僅有資料庫外洩，有心人士依然可以取得其統計特徵值，來猜測最多人使用的 “123456” 來進行猜 “亂定數” 的破解，而只要解譯 “亂定數” 後再取得明碼就不難了。

因此為了防止 “Statistics attacks”，加料 (Salted) 的東西就不能是個 “定數” 而必須是個 “隨機數”，且這個隨機數需依每個人有所不同。例如 ant 的隨機數是 “i3flm234rmsldk543kf2jvl2sdfj”, 而 guest 的隨機數是 “43kf2jvl2sdfji3flm234rmsldk5”，那麼即使 ant 及 guest 的明碼是一樣的，儲存在資料庫的 Hash 值仍然是不一樣的。”隨機數” 的值可以是亂數產生，然後儲存在某一資料庫欄位，以利事後的比對，或者直接取用原本用戶資料表裡的唯一值，例如註冊時間也可以。

最後，如果擔心 “Collision attacks” 的話，上述所有方法皆可以將 MD5 或 SHA1，改成更複雜的 SHA256 或 SHA512，但是運算資源也會倍增。

總結

在安全性及效能的綜合考量下，筆者建議 “隨機加料式雜湊法”, “使用兩種以上的隨機加料式雜湊演算法” 或 “HMAC 隨機加料式演算法”。愈後者安全性愈高，但效能的要求也愈高。

1. 隨機加料式雜湊法

演算法為: Hash(隨機數 + 明碼)。

當 Hash 為 MD5 時，用戶 ant 之密碼為 “123456”，系統會隨機產生一隨機數為 “i3flm234rmsldk543kf2jvl2sdfj”，則經運算後密碼以 “d0a970cc71d15aa10b07584a7bd31ff6” 儲存。當用戶 guest 之密碼為 “123456”，系統會隨機產生另一隨機數為 “43kf2jvl2sdfji3flm234rmsldk5”，則經運算後密碼以 “171773b4cbdc81b0e697ab3c21a7366d” 儲存。

2. 使用兩種以上的隨機加料式雜湊演算法

演算法為: Hash1(Hash2(隨機數 + 明碼)。

當 Hash1 為 MD5 且 Hash2 為 SHA1 時，用戶 ant 之密碼為 “123456”，系統隨機產生的隨機數為 “i3flm234rmsldk543kf2jvl2sdfj”，則經運算後密碼以 “1a2379a1f4e28eacb9151734f3773b23” 儲存。當用戶 guest 之密碼為 “123456”，系統隨機產生的另一隨機數為 “43kf2jvl2sdfji3flm234rmsldk5”，則經運算後密碼以 “0332d18e7e836c4df785641b4ac198cd” 儲存。

3. HMAC 隨機加料式演算法

演算法為: HMAC(Hash, 隨機數 + 明碼, 金鑰值)。

當 Hash 為 SHA1，Key 為 “mykey” 時，用戶 ant 之密碼為 “123456”，系統隨機產生的隨機數為 “i3flm234rmsldk543kf2jvl2sdfj”，則經運算後密碼以 “466b2528c18f4f0893be264bcc16d95d63053054” 儲存。當用戶 guest 之密碼為 “123456”，系統隨機產生的隨機數為 “43kf2jvl2sdfji3flm234rmsldk5”，則經運算後密碼以 “d7b9f21f0740e12a80e7f2cbb0df9a7f5c98bece” 儲存。

更新：2012-07-16

先前有前輩指出文章內容並沒有考慮到更好的演算法，於是剛好今日有空閒與心情，來補充本篇的內容，希望本文不會過於冗長才好。

上述提到的演算法對於 Rainbow tables 與 GPU 等攻擊方式沒有提供相對好的解決方法，若對於此類型的攻擊，我們該怎麼辦呢？

為了有效增加機器「駭」出 Hash(雜湊)的時間成本。Niels Provos and David Mazières 在 1999 年發表了 bcrypt 的演算法，另外在 2000 年，Kaliski 也發表了 PBKDF2，兩者在某種程度上都能夠相對有效的解決這個問題。

但目前需要擔心的其實是跳脫摩爾定律的 GPU 計算能力。GPU 技術發展了很久，但直到 2000 年後才開始逐漸被重視，不管是 bcrypt 及 PBKDF2 雖然都能夠降低 GPU 型式的攻擊，但增加的時間成本並沒有達到巨量級的程度。

於是在 2009 年，Colin Percival 在 BSDCan 上發表了新的 scrypt 演算法。相較於 bcrypt 及 PBKDF2 能夠更有效的增加 GPU 計算的時間。下圖為該簡報的第 19 頁擷圖。

對於 PHP 的使用者，若想使用 bcrypt，可以從我的 Github 專案中找到 php-bcrypt。若想使用 scrypt，則可以使用 php-scrypt。

但需要注意的是，當安全等級要求愈高，意謂著我們系統平常的計算量也會相對的提高，效能勢必會降低。