不少人都有重用密碼的習慣，始終要想出一個能符合各種密碼規則，而且又能記住的密碼的確很難。加上近年密碼的要求都頗為繁複，更加劇了重用密碼的機會。例如，要有大小寫英文字母、數字及符號等。一但網站資料庫外泄，而營運者又沒有對密碼做好保護，其他使用相同密碼的帳戶便會岌岌可危。為了讓大家了解重用密碼的風險，筆者將會向大家介紹密碼的存儲方法、黑客們如何破解密碼，以及安全儲存密碼的方法。為了容易理解，文中部份技術細節會被簡略。

究竟密碼是怎樣儲存的？

Figure 1: 把密碼明文輸入 hash function 進行運算， 在資料庫中只儲存 username 和 hash value。用戶登入時只需重新運算 hash value 並對比資料庫中的字串。

一般情況下，網站並不會直接儲存用戶的密碼 (即「密碼明文」)，因為這樣會造成重大的安全風險。例如，網管人員將能直接取得用戶的密碼，增加系統遭到內部攻擊 (Insider attack) 的風險；再者，一但儲存密碼的資料庫外泄，用戶的密碼便會直接被公開。當用戶註冊帳號時，網站伺服器會先把密碼通過 hash function 換算成 hash value，再儲存至資料庫中 (如 Figure 1 所示)。所謂的 hash function，大家可以理解為一個運算式，它會將密碼明文轉換成一段固定長度的字串。這個過程是很難反過來運算的，因此，即使別人得到了 hash value，亦很難知道原來的密碼是什麼。但是，如果資料庫只儲存 hash value，網站又怎樣確認用戶登入提交的密碼是一樣的呢？其實 hash function 是一種確定性算法 (Deterministic algorithm)，也就是說，只要用戶提供一樣的密碼，hash function 所產生的 hash value 必然是相同的。在用戶登入時，伺服器只需要重複同樣的 hash 運算，並把運算出的 hash value 比對資料庫的 hash value 即可 (如 Figure 1 所示)。

聰明的讀者們可能會問，那不同的密碼會產生相同的 hash value 嗎？基於鴿巢原理 (Pigeonhole principle)，如果有 n 個鴿巢，但卻有 n + 1 隻鴿子，那麼必然會有兩隻鴿子住在同一個鴿巢裏。同樣道理，假如密碼的組合比 hash value 的組合要多，那麼必然會有不同密碼被對應相同的 hash value。以最常見用於密碼的 hash function —— bcrypt 算法為例，它所產生的 hash value 長度為 。基於生日攻擊 (Birthday attack)，理論上需要嘗試 個 inputs，才會找到相同的 hash value。因此，出現相同 hash value 是可能的，但機會率極低。一般來說，我們都會認為利用 hash function 確認密碼是安全的。

黑客如何通過外泄數據庫取得用戶密碼？

既然黑客只能在外泄的數據庫中取得密碼的 hash value，那用戶的密碼是不是就很安全了？雖然我們很難通過 hash value 取得密碼明文，但常見的 hash function 是公開的，每個人都能重複運算。如 Figure 2 所示，黑客可以預先準備固定長度及複雜程度的所有密碼組合，運算出它們的 hash value 並儲存到一個表 (Lookup table) 裏。假如目標網站的密碼要求與黑客準確的一致，黑客便可以直接在表中尋找 hash value 對應的密碼明文。

Figure 2: 預先運算可能密碼組合的 hash value 並儲存到 lookup table。破解密碼時，只須以 hash value 搜尋密碼明文即可。

有讀者可能會好奇，需要多少空間才能儲存所有密碼組合和相對應的 hash value。我們簡單計算一下，假設密碼組合只有數字和小寫英文字母，規定長度為 8 位。hash function 為 SHA-1，所產生的 hash value 長度為 160 bits。

(密碼長度 + hash value 長度) 所有密碼組合 TiB

的確，71.84 TiB 的大小不是一個小數字，但還是可以儲存的。假如密碼長度再長一個位，所需空間便會暴增至 2678.68 TiB。所以，密碼的安全性其實很大程度上取決於長度。當然，道高一尺，魔高一丈，黑客並不會直接儲存所有組合，而是通過建立彩虹表 (Rainbow table)，以破解時間的增加換取空間減少。由於彩虹表的原理較為複雜，就留待下一篇文章介紹吧。

密碼也可以加「鹽」？是要煮密碼嗎？

Figure 3: 用戶註冊時，把隨機產生的 salt 接在密碼後，並以此進行 hash 運算。進行登入認證時，同樣把 salt 接在密碼後運算即可。

加「鹽」不是要煮密碼啦！所謂的「鹽」(Salt) 是一段隨機字串，需要在進行 hash 運算前加於密碼之中。如 Figure 3 所示，salt 可以放置於密碼明文的後面，並以合併字串進行 hash 運算。注意的是，salt 必須是完全隨機，而且每一個用戶都使用不同的 salt。從運算結果可以看到，即使兩個用戶使用不同的密碼，但運算後的 hash value 並不一樣。這樣便能對抗 lookup table 的攻擊了，因為黑客所運算的 hash value 不再適用。由此不同用戶的 salt 並不一樣，即使加入新的 salt 再重新運算 lookup table，也只能用於破解一位用戶的密碼，大幅增加破解難度。當然，為了登入時可以認證，salt 必須以明文儲存在資料庫中。由於 salt 的目的只為對抗 lookup table 攻擊，即使以明文方式儲存，也不會有安全問題。

總括而言，加入隨機 salt 之後的 hash value 基本上對 lookup table 類型的攻擊免疫。不過要注意 salt 需要夠長，最好是和密碼長度相同。如果 salt 太短的話，黑客可以把 salt 當成是密碼的一部份，重新運算 lookup table 或 rainbow table。另外，有些網站可能會重複使用相同的 salt，這會導致 salt 失去原有的防護能力，是絕對錯誤的。由於我們不知道外面的網站是如何儲存用戶密碼，所以筆者還是建議大家不應該重用密碼啊。

參考資料

• Birthday Attacks, Collisions, And Password Strength
• Adding Salt to Hashing: A Better Way to Store Passwords
• Salted Password Hashing - Doing it Right