彩虹表如何用於字典攻擊？
我正在為我的公司製定密碼策略。我非常希望避免需要復雜的密碼，並且更願意要求長度。
我可以強制執行的最大長度是 14 個字元。我可以使用鍵盤上的任何東西計算出 14 個隨機小寫字元比 8 個字元強。但是我建議人們使用片語、歌曲名稱等類似的東西。
我認為我不需要防止有人猜測密碼，因為我們的系統會在 5 次失敗後鎖定您。我想我正在防止有人竊取我們密碼的雜湊值。因此，我想如果有的話，攻擊方式將是通過彩虹表。
我認為 14 個隨機小寫字元對彩虹表是相當安全的（我們有 Windows Server 2008，據我所知消除了 LM 兼容性弱點）。但是，如果使用片語，則與隨機字元相比，可能性要小得多。
有誰知道彩虹表是否可以與字典單詞一起設計，比如通過標記它們？
除此之外，我相信 NTLM 密碼是經過雜湊處理但沒有加鹽的——有人知道這是否屬實嗎？如果事實證明它們是鹹的，那麼我想我沒什麼好擔心的。
為彩虹表找到一個體面的解釋是我一直在努力的事情，所以首先我將介紹它們是什麼。最後我會回答你的問題。我的資料來源是本指南和維基百科文章。
為什麼我不能只使用一大桶雜湊？
首先，建立反向查找表的天真方法是這樣的。假設我們要使用 set 為每個存在的 8 位密碼生成所有雜湊值
[A-Za-z0-9]。在這種情況下，有 62 個唯一字元，並且使用計數功能 $ n^r $ 在哪裡 $ n $ 是可能的輸出數量和 $ r $ 是我們可以做出的選擇的數量，那麼有 $ 218340105584896 $ 此輸出空間中的可能字元串。簡單地儲存這些數據，我們可以將 8 個字元串作為每個字元佔用 8 位（因此每個字元串花費 64 位）加上一個分隔符加上 sha256 的 256 位輸出，總成本為 $ 218340105584896(64+1+256) = 70087173892751616 $ 位。將其轉換為字節，即 $ \frac{70087173892751616}{8*(1024)^3} \approx 8159220 $ 千兆字節。對此有兩點說明：
- 它只考慮 8 個字元的密碼。如果要考慮包含 4-8 個條目的密碼，則需要 $ 62^4+62^5+62^6+62^7+62^8 $ .
- 它假定您實際上要以原始形式儲存該數據。可能有更好的方法來處理這個問題。
所以第一個問題是儲存。上面，我們簡單地計算了雜湊函式的總輸出空間。
什麼是彩虹桌？
彩虹桌背後的想法是解決空間問題。為此，讓我們定義一些東西：首先我們有一個搜尋域，我們將呼叫它 $ \mathbb{P} $ 以及我們將呼叫的雜湊輸出域 $ \mathbb{H} $ . 然後我們有一個我們想要反轉的雜湊，我們將定義為 $ \mathcal{H}: \mathbb{P} \rightarrow \mathbb{H} $ . 即散列函式採用搜尋域的一個元素並在散列輸出域中產生一個值。
然後我們引入一個稱為鍊式的概念。為此，考慮我們可以定義一個相當簡單地映射另一種方式的函式；讓我們稱之為 $ \mathcal{R}: \mathbb{H} \rightarrow \mathbb{P} $ . 在彩虹表中，鏈以起始值開始並應用 $ \mathcal{H} $ 然後一個 $ \mathcal{R} $ 交替地，但總是成對的，這樣完成後你會得到第一個和最後一個元素 $ p_0, p_k \in \mathbb{P} $ . 這就是您儲存的內容。
彩虹表比使用彩虹表稍微複雜一些 $ \mathcal{R} $ 每對；這有與碰撞有關的問題。如果兩條鏈產生相同的值，它們就會收斂，這意味著我們浪費時間花在計算所述鏈上——這就是鏈碰撞。我很難想像這個，所以畫了一個圖表：
a_1 ----> a_2 ----> a_3 / b_2 --> a_4 / b_3 --> a_5 / b_4 ---> a_6 / b_5 | | b_1 --------------------- -----> b_6.相反，一組函式 $ {\mathcal{R}0, \ldots, \mathcal{R}{k-1}} $ 應用，每對鏈一個。因此，當鏈使用這種設置合併時，它們總是產生相同的最終值，然後可以進行重複數據刪除，從而節省空間——在生成時檢測浪費的空間也容易得多。
然後：
生成彩虹表：選擇長度 $ k $ 並定義功能 $ \mathcal{R}{0}, \ldots, \mathcal{R}{k-1} $ . 然後，對於給定的輸入 $ p \in \mathbb{P} $ 我們計算 $ c_0 = p, c_{n+1} = \mathcal{R}{n-1}(r{n}), r_{n} = \mathcal{H}(c_{n});;(n=0,1,2,\ldots, k) $ . 這些 $ c $ 形成一個鏈條 $ C $ . 我們計算我們的鏈，對於每條鏈，我們只儲存一對 $ (c_0, c_k) $ .
搜尋彩虹表。現在，假設我們想要反轉一個雜湊值 $ h $ . 為此，我們執行這個過程，從 $ i=k-1 $ :
- 生成鍊為 $ h $ 開始於 $ R_{i} $
- 使用上述鏈的最終值，在我們的最終值列表中搜尋計算鏈。如果我們找到一個匹配的結束值，一次計算它的鏈項（我們可以這樣做，因為我們知道起始值）。如果我們發現 $ h $ 就像說 $ r_n $ 在那個鏈中，然後對應的 $ c_n $ 值是倒數 $ h $ . 停止。如果我們在鍊錶中沒有找到最終值，則繼續。如果我們沒有在生成的鏈中找到我們確實找到鏈值的散列，請繼續。
- 如果 $ i \neq 0 $ 做 $ i=i-1 $ 並返回到 1。
- 如果我們到了這裡，我們還沒有找到逆。
對了，到底有什麼好處？
這是空間/時間的權衡。具體來說，反向查找表佔用了大量空間。這是一個佔用更少空間的方案，但每次查找需要更多時間才能工作。由於完整的反向表的大小對於大多數人來說是令人望而卻步的，因此增加的計算成本通常是可取的。儲存空間大大減少，但實際上更難計算，因為它取決於 $ k $ , 和 $ \mathcal{R} $ 你用。
顯然，在彩虹表的長度方面，我們也有不同的選擇。 $ k $ . 越長 $ k $ ，在所有元素之前的總鏈數越少 $ \mathbb{P} $ 被覆蓋的。但是，這也會增加查找的執行時間。
哦不，現在我不知道鹽是怎麼進來的？！
鹽增加體積 $ \mathbb{P} $ 通過增加 $ r $ 在 $ n^r $ . 這使得逆雜湊列表變得非常大，也增加了彩虹表所需的大小和計算時間。
攻擊者有兩種選擇：
- 生成特定於給定鹽的彩虹表，使其對不同的鹽無效。
- 製作一個巨大的彩虹桌。
那麼慢散列函式呢？
到目前為止，我們主要討論了空間作為考慮因素，而不考慮查找函式所花費的時間。大多數加密散列被設計得相當快，所以這對於說 MD5 來說最終是可行的。
現在如果我們選擇會發生什麼 $ \mathcal{H} $ 我們知道計算每個雜湊大約需要一秒鐘？假設沒有捷徑可以消除這個額外的時間成本，巨大的逆表將採取 $ 218340105584896 $ 秒，或大約 $ 6923519 $ 年。您的彩虹表也將需要很長時間才能生成 - 假設您從未發生衝突並覆蓋整個域，只要雜湊反向查找，加上搜尋的額外成本，具體取決於 $ k $ .
將兩者結合起來是對彩虹表的相當有效的防禦，使其既特定於給定的鹽，又產生和使用昂貴。
為什麼密碼策略會提到諸如字元類之類的東西，例如必須有一個大寫字母，必須有一個標點符號？
我們定義了 $ \mathbb{P} $ 作為集合
[A-Za-z0-9]。如果在混音中添加標點符號，則會增加 $ \mathbb{P} $ 再次增加彩虹表的大小（需要的鏈數）。密碼長度要求也可以做到這一點。那麼字典？
一部相當著名的 XKCD 漫畫背後的整個前提是資訊熵的概念。粗暴對待一個相當有趣的科學領域（對不起！）基本上你所說的是，雖然 $ \mathbb{P} $ 很大，實際上，其中很多對人類來說完全沒有意義，如果可以選擇，我們也不會使用它們。XKCD 漫畫說，實際上，如果您對可能的密碼格式做出某些判斷，使用資訊熵作為這些格式中不確定性的度量，那麼較長的密碼片語實際上比較短的複雜密碼得分更好。
沒有理由不能使用一組考慮到這種假設的歸約函式來生成彩虹表。
字典只是這種猜測的簡化版本 - 即你假設你正在反轉的東西實際上是一個已知的字典單詞。您還可以使用已知的字典密碼生成彩虹表。
在這兩種情況下，您都在減少 $ \mathbb{P} $ 通過擴展減少彩虹表的大小和執行查找的時間；但是，這種技術很容易受到您對密碼的近似表示可能不正確的影響。
彩虹表的複雜性是什麼？
假設我們要建構一個彩虹表來覆蓋一組 $ N $ 潛在的密碼。（換句話說， $ N = |\mathbb{P}| $ 。） 讓 $ t $ 表示平均鍊長；這是一個您可以自由選擇的參數，以優化攻擊成本。
那麼，建表的成本大約是 $ 1.7N $ 雜湊計算（是的，它比對集合進行簡單的窮舉搜尋要貴 70%）。儲存成本為 $ N/t $ 尺寸元素至少 $ \lg N $ （但不一定要大得多）。攻擊密碼的成本約為 $ t^2/2 $ 雜湊計算，以及 $ t $ 查找（“查找”是指您實際在硬碟中查找數據；它通常比散列計算慢得多）。