By Yun
前言
一般來說，系統在儲存密碼時不會以明文儲存，而是透過雜湊函式將密碼轉為雜湊值再儲存，這是因為雜湊值具有不可逆的特性。那如果真的想解雜湊值該怎麼做呢？同明文使用固定雜湊函式進行雜湊，不論進行多少次都會取得相同結果。而使用不同明文則會產生不同結果，可能偶爾發生特殊情況才會產生相同結果。
如此一來，雖然不能直接計算回推，但我只要將明文與其對應雜湊值記錄下來，以後只要看到這個雜湊值，我不就知道明文是什麼了嗎？這就是本文要介紹的—彩虹表，關於它的一個簡單概念。
什麼是彩虹表？
彩虹表是一個針對各種可能的字元組合，預先計算其雜湊值並記錄下結果的表，常用於破解固定長度與固定字元種類的密碼，常見雜湊函式為MD5、SHA1、SHA128、SHA256、NTLM…等。但如果將所有明文與其雜湊值一對一記錄下來，檔案會非常龐大，於是，「歸約函式」出現了。
歸約函式（Reduce function）：將雜湊值轉換為特定格式的字元組合（與明文格式相同）。
彩虹表是由好幾條雜湊鏈所構成，雜湊鏈的產生方式為：
（以下以 H 代表雜湊函式，R 代表歸約函式。）
密碼明文 → H → 雜湊值 → R → 密碼明文→ H → 雜湊值 → R → 密碼明文
將密碼明文進行 H 後取得雜湊值，再利用 R 取得新的密碼明文，重複相同的動作形成一條雜湊鏈。
密碼明文 → H → 雜湊值 → R1 → 密碼明文→ H → 雜湊值 → R2 → 密碼明文
過程中使用同個 R 有機率產生重複的明文，造成後續出現重複的結果。為了避免這種狀況發生，在不同的位置需要使用不同的 R。
利用彩虹表進行雜湊值破解的過程則與產生鏈的過程相反：
雜湊值 → R → 密碼明文 → H → 雜湊值→ R → 密碼明文 → H → 雜湊值
- 利用 R 將雜湊值轉換為密碼明文。
- 與彩虹表中鏈終點做比對。
- 若找到相同明文就去找對應之鏈起點，若無則做 H 回步驟1。
- 重建對應之雜湊鏈，尋找目標雜湊值。
- 若找到目標雜湊值，前一個節點即為其明文。若無則回步驟2。
時間-記憶體取捨問題 time-memory trade-off
在彩虹表中，只會儲存雜湊鏈的起始和終點，其他都不會儲存，故每條鏈的大小固定。而鏈長度越長表示鏈中儲存的可解明文越多，也表示在查找時需要花較多時間。
在相同可解明文範圍內，如果：
- 想花較少查詢時間
減短 鏈的長度 → 增加 鏈的數量 → 增加 彩虹表儲存空間
- 想花較少儲存空間
增加 鏈的長度 → 減少 鏈的數量 → 增加 查詢時間
在產生彩虹表時需考慮自身設備之記憶體空間及期望的執行效率，來決定彩虹表的規模。
如何避免雜湊值被彩虹表破解？
在「密碼的破解與防護」一文當中曾提過該如何設定較安全的密碼，除了使用者可以設定具一定複雜性的長密碼之外。系統方面，在儲存密碼的時候應該先在密碼中加鹽（salt）再進行雜湊。
加鹽指的是在密碼中任意位置插入字串。如此一來，即使被破解出明文，也是經過混淆的明文。需要注意的是不同使用者密碼應使用不同的鹽（需記錄下來），也不應該使用太短的鹽。
結語
雖然目前沒辦法直接逆向回推雜湊值，但我們可以透過預先計算的方式來找出明文。利用特殊演算法產生的彩虹表能快速破解雜湊值，但需要在查找時間與儲存空間之間做取捨。使用者要注意不要使用簡單的密碼，系統方需注意不要直接以明文儲存密碼，而是應該加鹽後進行雜湊再儲存。
小提醒
最後小提醒，本文在於從攻擊手法做對應的防禦策略，隨意嘗試破解他人帳號密碼，可能需要負法律責任[5]哦！