猜 100 位 md5 雜湊

我在一個兵棋推演網站上發現了以下挑戰：

隨機生成一個 16 字節的字元串，並使用 md5 => HashRandom 進行散列

接下來，在無限循環中發生以下情況：

1. 提示使用者輸入 16 字節
2. 輸入被散列 => HashUser
3. HashUser 與 HashRandom 比較，顯示匹配位數

目標是獲得至少 100 個匹配位。

幾點觀察：

1. 初始隨機字元串是使用小寫/大寫字元、數字和字元生成的.,"...
2. 通常，對於像我這樣的任何使用者輸入字元串，AAAAAAAAAAAAAAAA我會得到 50 到 70 個匹配位

為了更好地了解幕後發生的事情，我閱讀了 md5 和 Wang 的攻擊 ( http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf ) + 其他相關論文。基於此，這裡有一些注意事項：

• 我的輸入看起來像這樣（UI - 使用者輸入 - 我可以控制的字節數）：

m0  - 0xUIUIUIUI
m1  - 0xUIUIUIUI
m2  - 0xUIUIUIUI
m3  - 0xUIUIUIUI
m4  - 0x00000080 - initial padding with 1 + 0's 
m5  - 0x00000000
m6  - 0x00000000
m7  - 0x00000000
m8  - 0x00000000
m9  - 0x00000000
m10 - 0x00000000
m11 - 0x00000000
m12 - 0x00000000
m13 - 0x00000000
m14 - 0x00000000
m15 - 0x00000080 - input size - 128 bits - 16 bytes

• Wang 談到了一種用於生成在 md5 下發生衝突的消息的差分攻擊。我讀到希望它能給我一些提示，但是它不能真正應用於這個挑戰。所描述的方法對每條消息使用兩個 512 位輸入塊。它還對我無法控制的字節施加了限制。
• 我在這方面的唯一突破是能夠在第一輪之後控制雜湊函式（但是，這是微不足道的，我認為它對我沒有幫助）
• 因為我可以得到我想要多少個字元串的匹配位數，所以我可以了解隨機生成的字元串的散列是什麼樣的。因為我只需要 100 位，所以我不需要雜湊到 100%。基本上，如果我可以控制一半的散列（64 位），運氣好的話，我可以得到 36 個其他隨機位來匹配。
• 在 md5 算法的第四輪中，第 63 次操作（即在計算最終值之前）涉及m2（由我控制）：

Q63 = Q62 + Q59 + I (Q62, Q61, Q60) + m2 + 0x2ad7d2bb) <<< 15

Q63也會對Q64.

這可能允許我干預散列函式的最後 64 位；但是，任何更改m2都會影響計算方式，Q63所以Q64我不確定這是否有幫助。

有什麼想法或建議閱讀可以為我指明正確的方向嗎？（GPU + 蠻力是列表中的最後一件事 - 我希望有另一種方法來做到這一點）

我的筆記型電腦（執行 Java）上的 3 分鐘執行時間已經給了我一個 99 位相同的位字元串。這可能是你想多了。

這聽起來像是你應該做的經典工作證明。由於不太可能有任何捷徑，我想你必須暴力破解它。因為它是一個遊戲網站，所以更快的 GPU 可能會勝出。

MD5 仍然有超過的原像電阻 $ 2^{123} $ ，與這裡提到的具體攻擊。由於原像似乎是（未知的）並且已給出，因此僅查找碰撞不會走得太遠。

---

僅在筆記型電腦上進行計算，與全零的雜湊值相比：

100 : 00000000000000000000000625b4aa69 -> 0740a0a42a0074920018000008308212

只需要超過 26,000,000,000（美國為 160 億，我們其他國家為 1600 億）雜湊；值的十六進製表示為 16 字節整數用作輸入。

花了一些時間，但沒有什麼主要的、未優化的、單執行緒 Java 程式碼，在降頻的 i7 筆記型電腦上執行。在具有半優化、多執行緒程式碼的快速機器上，期望至少有 16 倍的改進。

引用自：https://crypto.stackexchange.com/questions/42211