加速對 MD5 的部分已知明文原像恢復攻擊
假設有 3 條不同長度的消息
A，組合B起來的長度為 16 個 DWORD。C我知道 and 的明文和長度，A並且C只知道B. 在嘗試恢復 的原像時是否可以利用這些知識MD5(A || B || C)？我的目標是“原始”MD5 轉換，C實際上是填充和位長，所以我用 16 個 DWORD 的輸入提供它，並期望得到 4 個 DWORD 的摘要。
A長度為 8 個DWORDB，C每個長度為 4 個 DWORD。我只能考慮在使用長消息時盡可能多地預計算第一輪
A，但這並沒有帶來那麼大的加速。任何元編譯技術？**UPD1：**我有以下想法，但我不確定它在這種情況下和一般情況下是否有任何價值。我將不勝感激審查它。
可以將每個 DWORD 表示為獨立位的集合，每個位可能處於三種狀態 - 設置 (0)、未設置 (1) 和
未知狀態。所有未知位都有其唯一的 ID，並保存它們的創建歷史 - 由於異或兩個未知位的結果也是未知的，我們在必要時產生更多唯一的未知位。未知位可能通過 AND 與 0 或 ORing 與 1 來“確定”，因此結果不再是未知的。此外，將其與自身進行異或會使其為 0，而將未知位與其反轉的對應物異或會使其成為 1，依此類推。旋轉對位本身沒有影響，只會影響它們在“DWORD 集合”中的順序。DWORD的按位運算以明顯的方式縮小到位，並且通過ADD運算表示加法，該運算返回結果和進位位，當加法器的結果是MSB時，進位位又被忽略。
在這樣的跟踪或“元計算”之後，我們將最終得到有向圖，該圖中有 128 個未知輸入位（消息 B）和 128 個幾乎不與輸入位扭曲和糾纏的摘要輸出位。圖的每個節點都是操作（XOR、AND、OR、NAND、NOR、NOT、ADD 等），傳入邊將是這些函式的參數，傳出邊是結果。對稱傳遞二進制操作可以使用行為定義擴展到任意數量異或。
所以第一個想法是盡量使用上面表達的規則來簡化這個圖，然後展開每個位的歷史，揭示使用
B消息中初始未知位的 AND/OR/XOR 的長表達式，並嘗試找到公共鏈可以一次計算的操作。這種方法的問題是我將計算過度複雜化了 32 次，因為 DWORD 被分解成位……也許有辦法以某種方式將它們綁定回來，產生一些函式，接收B消息候選並以最緊湊的方式返回單個 DWORD？我不知道。另外我不知道我是否可以使用相同的方法，但使用 DWORD 而不是最低級別的位。第二個想法是嘗試反轉該圖，將所需的 MD5 輸出輸入“輸出未知位”並嘗試找出產生此類結果的參數 - 例如，如果
OR(A, B, C, ...) == X，而 X 是未知位，則顯示為零，這是不可能的因為 A、B 和 C（以及其他）不為零，所以可以繼續傳播。同樣適用於AND(A, B, C, ...) == X，其中設置了 X - A、B 和 C 必須全部設置。對於模棱兩可的情況，應該發生分支，將目前圖形狀態推入堆棧，選擇一個可能的參數佈局並繼續進行直到第一次沖突 - 例如，根據一個表達式未知位應該被取消設置，並且根據其他表達式應該設置相同的位，這意味著先前選擇的可能路徑之一是錯誤的，應該嘗試下一個。所以，由於這還沒有實現，它有問題。究竟是什麼問題？我認為它可能會計算出穿過所有分支所需的時間超過蠻力時間，但我不確定。
你的想法相當於做“不斷折疊”或“部分編譯”。這不太可能有太大的不同（詳細解釋見下文）。
但是，即使撇開這一點不談，還有一個更重要的原因是您無法找到
B. 在您的情況下，未知部分 (B) 長 4 個 DWORD，即 128 位長。這意味著您必須反复嘗試所有 $ 2^{128} $ 的可能性B，無論你做了多少優化，它仍然需要永遠。即使只需要時鐘週期來嘗試猜測B， $ 2^{128} $ 時鐘週期大約是永遠。因此，即使我們考慮到您的優化想法，您的問題也是無望的。解釋為什麼您的想法不會提供太多加速：基本上，您的想法等同於以下內容：
- 寫下完整的 MD5 計算，作為一組直執行緒式碼。
A接下來，您可以將一些輸入（與和對應的部分C）修復為特定的編譯時常量。- 現在遍歷計算圖。任何時候你看到對兩個變數的操作，它們的值都是編譯時常量，你可以用它的預先計算的值替換那個表達式。
例如，如果您看到表達式
x+y，其中x和y都是編譯時常量——分別是 5 和 7——您可以x+y用它的值替換，即 12。如果您看到一個 assignmentz = 12，那麼此後的值z是已知是編譯時常量，可用於觸發進一步的優化。
- 重複這個簡化過程，直到沒有進一步的簡化是可能的。
剩下的是計算的優化版本，只有需要的操作（其值無法提前預測）。在編譯器社區中，這種優化被稱為“常量折疊”。它等同於您提出的建議。
不幸的是，這不太可能有太大幫助。如果您在一個範例上進行嘗試，您會發現在 MD5 計算期間計算的大多數中間值實際上都依賴於
B並且因此不能被常量折疊（優化）掉。因此，您的想法不會導致很大的加速。如果
B更短，可能還有其他方法可以加快窮舉搜尋的速度。您可以查看優化 MD5 蠻力搜尋的標準方法。例如，您可能會查看密碼破解工具如何優化該過程。我認為#1 最重要的技術是使用 GPU，並在您的 GPU 上執行 MD5 計算——這會產生重大的加速。但請閱讀有關密碼破解工具使用的技術的更多資訊。他們都應該延續到你的情況。然而，對於 128 位的值
B，這一切都沒有實際意義。不管你有多少 GPU，或者你做了多少優化：你將無法B通過對所有可能性的詳盡搜尋來找到。