無法理解彩虹表中的歸約函式
我正在繼續對彩虹表進行一些個人研究，但由於某種原因，我無法理解如何選擇正確的歸約函式。維基百科指出
“只有當攻擊者對可能的明文有很好的了解時，他們才能選擇一個函式 R，以確保時間和空間僅用於可能的明文，而不是可能的密碼的整個空間。”
在這種情況下，將雜湊的最後 6 個字元作為歸約函式之類的歸約函式如何在彩虹表中提供服務，以嘗試查找 Password123 之類的密碼？如果有人能為我解釋這一點，那將非常有幫助。謝謝
在這種情況下，將雜湊的最後 6 個字元作為歸約函式之類的歸約函式如何在彩虹表中提供服務，以嘗試查找 Password123 之類的密碼？
它不能。假設歸約函式採用最後六個字節的輸出，它只能用於生成最多 6 個 (ASCII) 字元長的密碼。
要破解任何長達 6 個字元的密碼，您需要預先計算一些雜湊值，其順序為 $ 256^{6} $ . 這需要比實際需要更多的空間/時間。如果您不針對使用非 ASCII 或不可列印的 ASCII 字元的密碼，那麼您可以減少 $ 256^6 $ 大概 $ 95^6 $ . ( $ 95 $ 是“可列印”字元的數量。）
那麼你用一個更複雜的函式替換你的簡化函式，它只是重新解釋二進制數據，用 6 個字節的雜湊輸出替換一個 6 個字元長的字元串。您可以將輸出的字節轉換為以95 為基數的數字，然後創建一個 ASCII 字元串，其中 0 到 95 的每個值對應於一個可列印的ASCII 字元。
您不想使用第一個歸約函式，因為它會創建不太可能的密碼。範圍內沒有任何字元的 ASCII 字元串
$$ 0, 31 $$或者$$ 127, 255 $$很可能是一個真實世界的密碼，所以如果你使用這個縮減功能，你的彩虹表將是低效的。 我給出的 base-95 範例是一種減少函式，它可以提高效率，因為它避免了這兩個範圍內的字元。對於 6 個字節的雜湊輸出，您實際上可以生成 7 個字元長的密碼。（因為 $ \log_{95} (256^6) \approx 7.30 $ )
可以使用更有效的歸約函式，但它們需要更複雜。也許您想排除連續有 4 個或更多相同字母的候選密碼，除非它採用“aaaa…..a”或“aaaa…123”的形式。然後你必須對現實世界中被認為是“可能”的密碼做出假設，然後你需要找到一種有效實施它的方法。
這種選擇需要權衡取捨。如果您從歸約函式可以產生的一組可能輸出中省略一個字元串，那麼如果它們在現實世界中使用，您的彩虹表**就無法破解這些密碼。**如果歸約函式不能產生一個字元串，那麼彩虹表就不能破解那個密碼。
您可以通過增加歸約函式使用的位數來破解一組更大的潛在密碼。在簡單的實現中，如果使用六個字節，您最多可以破解六個字元的密碼。如果使用七個字節，則為七個字元。等等。
但是，當您增加該密碼集時，您還需要進行更多的預計算（在查詢期間我們需要更多的時間和/或記憶體）。在實踐中，您會通過使用越來越多的字節來獲得遞減收益。
如果您不進行與整體成比例的預計算工作，那麼您的表將僅涵蓋所有可能密碼的一小部分。如果您的密碼設置是 $ X $ 元素大，你做 $ X \over 2 $ 那麼，只有不到一半的候選密碼實際上會被彩虹表覆蓋。
較大的候選密碼集大小意味著您需要進行更多的散列，即使對於彩虹表也是如此。彩虹表對於定位長的低熵密碼無效。取而代之的是基於字典的破解和基於規則的暴力破解。
彩虹表不再是密碼破解的首選算法。它是一種基於預計算的破解方法。通過使用唯一的（每個密碼）隨機鹽，任何使用加密雜湊算法的健全密碼雜湊的預計算方法都可以很容易地失效。
今天，人們試圖通過使用並行執行的暴力破解方法來破解正確的散列密碼。GPU 與 CPU 硬體的不同之處在於它們並行執行相同的操作。GPU 比 CPU 擁有更多（更簡單）的核心，因此它們更擅長並行執行某些任務。
在使用正確的密碼散列（使用鹽）時，彩虹表不再那麼重要。而且對於長密碼，它們從來都不是很好用。