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

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

前言

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

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

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

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

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

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

儲存用戶密碼之方法

1. 明碼(plaintext)

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

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

img

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

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

2. 簡易雜湊法 (Pure Hash)

演算法為: Hash(明碼)。

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

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

img

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

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

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

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

img

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

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

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

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

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

img

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

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

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

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

img

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

img

此時,再用原本查表式的攻擊時,就很容易找到 “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” 在資料庫會是:

img

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

img

這意謂著 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” 儲存。

img

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

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

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

img

3. HMAC 隨機加料式演算法

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

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

img

更新:2012-07-16

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

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

為了有效增加機器「駭」出 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 頁擷圖。

Scrypt

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

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