截斷 60 位 SHA1 衝突檢測？
因此，我設法為 SHA1 獲得了 52 位的衝突，但經過三天的暴力破解，我無法獲得 60 位的衝突。
我的問題很簡單，我應該如何解決這個問題？
我目前正在使用大約 15 位的隨機十六進制程式碼，並在這些數字之間隨機交替。然後我為此獲取 60 位 SHA1，然後檢查它是否在我的數組中。如果是，我會顯示匹配的 SHA1 值和生成它們的十六進製字元串。
目前還沒有令人沮喪的詞，因此任何指導或幫助都會受到極大的歡迎。
在計算奇怪的最終答案之前，我現在似乎記憶體不足
典型的蠻力問題。
這裡有一個提示：不要將結果儲存在數組中，因為這很可能是目前導致您記憶體不足的原因。看看數字：如果我們假設沒有衝突，你需要你的數組（讀取：記憶體分配）來支持 $ 2^{60} $ 儲存所有 60 位結果的元素；而且我們還沒有計算執行作業系統、執行程式碼和儲存諸如隨機
15 bits十六進制程式碼之類的東西所需的記憶體。當然——由於已知存在 SHA1 衝突——你的數組不會增長到那麼大，所以你不必擔心你可能需要大約 144115 TB 的記憶體來儲存所有“SHA1 截斷為 60 -bit”的結果。考慮到使用普通台式電腦時可用的資源，一個在不耗盡記憶體的情況下使用 60 位截斷 SHA1 的項目應該是可行的。一個 SHA1 雜湊被截斷到它的前 60 位，在碰撞之前應該需要大約 60 或 1.2 億次迭代/雜湊計算——這取決於你有多幸運。除非您的電腦已經使用了 10 年或以上，並且除非您搞砸了您的實現，否則該數量的元素應該很容易放入記憶體中。
記憶體問題的一個潛在解決方案是像目前一樣使用隨機十六進制程式碼，並將事物儲存在由雜湊的前 60 位索引的樹中。（如有疑問，請查找“二進制索引樹”，也稱為“ Fenwick 樹”。）然而，如果這確實是最好的方法，在某種程度上取決於實現細節、可用資源，以及 - 最後但並非最不重要的 -使用的程式語言。當我們在 Crypto.SE 將與編碼相關的問題作為*“離題”*處理時，我將避免深入探討。
背景資訊：指數增長問題
我假設你在實際程式之前做了一些研究。如果你這樣做了，請提醒自己一個事實，即暴力攻擊所需的資源隨著你暴力破解的數據大小（這裡：比特數）呈指數增長。在其他來源中，您可以在有關蠻力攻擊的 Wikipedia 文章中找到此資訊。請注意，當我們談論所需資源的指數增長時，我們不僅僅是在談論原始電腦記憶體——“時間”也是指數增長的因素之一。
這是一個圖形（來自一個 SHA1 蠻力項目），它為您提供了透視圖：
暴力攻擊導致您快速耗盡多種資源這一事實是密碼暴力破解工具和實用程序傾向於使用“字典攻擊”方法來獲取更長密碼的主要原因，這也是主要原因之一為什麼密碼分析員會深入研究密碼算法來發現弱點和/或攻擊向量，從而避免不得不直言不諱地進行暴力破解。
長話短說：除非您是擁有充足資源的政府機構，或者您只是在攻擊小到適合您的台式電腦的東西，否則蠻力攻擊很快就會變得徒勞無功。
優化碰撞攻擊
幸運的是，SHA1 被認為是*“損壞的”*，並且發現了一些比普通的“（截斷和非截斷）SHA1 的暴力衝突”更快的攻擊。有關詳細資訊，您可能需要查看“SHA-1 衝突 - 實際攻擊怎麼樣？”的答案中提到的論文。
為方便起見，以下是相關程式碼段：
我會假設……有足夠的資源來執行一次攻擊，在 SHA-1 上找到兩個不同的 128 字節衝突消息，但有一個小的變化：（任意）160 位初始化值的值。後者是可能的
- 通過蠻力與預期的努力小於 $ 2^{81} $ 使用Paul C. van Oorschot和 Michael J. Wiener 的Parallel Collision Search with Cryptanalytic Applications（密碼學雜誌，1999 年 1 月，第 12 卷，第 1 期；免費稍早的版本可從第一作者的網站獲得）；
- 或者使用複雜的專門方法利用 SHA-1 壓縮功能的弱點以更少的努力，估計的努力相當於
+ $ 2^{69} $ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1 , in proccedings of Crypto 2005), + $ 2^{63} $ 雜湊，作者 Xiaoyun Wang、Andrew C Yao、Frances Yao：SHA-1 密碼分析，Crypto 2005 的臀部會議；另見 Martin Cochran：關於 Wang 等人的註釋。 $ 2^{63} $ SHA-1 差分路徑，在 IACR eprint 檔案中，2007）， + $ 2^{61} $ 雜湊，根據 Marc Stevens：基於最佳聯合局部碰撞分析的 SHA-1 新碰撞攻擊（在 Eurocrypt 2013 的會議記錄中，也可從作者的網站免費獲得）。
根據上述論文中提供的資訊，與目前的非優化蠻力方法相比，您應該能夠得出更優化的方法來查找“截斷的 SHA1”衝突。畢竟，“時間”是一種非常寶貴的資源。
正如e-sushi 提到的，您可以搜尋 $ n $ 位衝突 $ O(2^{n/2}) $ 記憶體，通過儲存您在表中找到的條目並蒐索重複項。
但是，通過使用 Pollard-Rho（閱讀：循環查找）技術，您可以大幅減少所需的記憶體量，而不會大幅增加計算量。
這是它的工作原理；你定義一個序列 $ S_i = H(S_{i-1}) $ ， 在哪裡 $ H $ 是（基於）您的截斷雜湊函式。作為單向函式，序列 $ S_0, S_1, S_2, … $ 最終會重複，並且很有可能不會從序列的開頭重新開始，而是在中間開始重複。也就是說，對於一些 $ i, j $ ， 我們將有 $ S_i \ne S_j $ 和 $ S_{i+1} = S_{j+1} $ . 我們的目標是找到 $ S_i, S_j $ （因為那是我們的雜湊衝突）。
一種方法是選擇您的 $ H $ , 任意起點 $ S_0 $ , 和一個值 $ N $ （和 $ 2^{n/4} $ 是一個不錯的起點）。我們還有一個包含成對值的資料結構 $ (Nk, S_{Nk}) $ , 對於整數 $ k $ . 用對初始化數據庫 $ (0, S_0) $ . 初始化 $ i $ 為 0， $ T $ 至 $ S_0 $ ，然後反复：
計算 $ T := H(T) $ 和 $ i := i+1 $ （不變數： $ T = S_i $ )
掃描數值 $ T $ 查看它是否作為值出現在數據庫中 $ (Nk, S_{Nk}) $ . 如果是這樣：
- 如果 $ Nk = 0 $ ，好吧，失敗（我們從初始值開始；用不同的值再試一次 $ S_0 $ )
- 如果 $ i < 2N $ , 再試一次 $ S_0 $ 和一個更小的 $ N $
- 否則我們有 $ S_i = S_{Nk} $ 但 $ S_{i-N} \ne S_{Nk-N} $ （我們知道後面的不等式，因為我們沒有找到 $ S_{i-N} $ 在我們處理它時的表格中）。重新計算值 $ S_{i-N} $ （使用表中它之前的條目），並檢索值 $ S_{Nk-N} $ 從表。依次計算 $ S_{i-N+j} $ 和 $ S_{Nk-N+j} $ （為了 $ j=1,2,3, … $ ) 直到你找到相等的地方；以前的 $ j $ 給你碰撞
如果條目不在表中，如果 $ i $ 是的倍數 $ N $ , 添加條目 $ (i, T) $ 到桌子上。