使用有限的輸入和部分資訊攻擊 MD5
如果我知道 MD5 輸入僅限於字元集。我可以根據輸出找到有關輸入的任何資訊嗎？
例子：
輸入由列表中的 16 個字元組成
$$ 1,2,3,4,5 $$. 問題：
基於 md5 輸出有沒有辦法找出有關輸入的資訊？即哪個字元在開頭或者輸入主要由特定字元組成？
讓我們從什麼是 MD5 開始；
- MD5的摘要大小為 128 位，塊大小為 512 位，由 Ronald Rivest 在 1992 年創建的基於Merkle-Damgård 構造的雜湊函式。
從我們想要的安全散列函式，128 位原像和次級原像抗性，以及 64 位抗碰撞性。MD5防撞破，分分鐘找碰撞。
對 MD5 的原像抗性有一個攻擊，它具有 $ 2^{123.4} $ -cost 但是，由於記憶體成本，您不會以這種方式進行，而是會執行完整的蠻力或更好地建構並行機器。
原像攻擊
- 今天最大的已知集體電腦力量是比特幣礦工，可以達到 $ \approx 2^{92} $ 每年的 SHA2d 計算。這意味著即使是他們也需要 35 年才能找到一個。
- 目前對原像的最佳實際攻擊是當有多個目標時（如果仍然使用不加鹽的 MD5 等，我們總是可以擁有）。建構並行蠻力機器並使用Oechslin 的彩虹表；
為了 $ t $ 建立的目標 $ t^2 $ 併機與 $ p $ 找到第一個目標的成功機率，你需要 $ 2^{128}p/t $ 面積*時間成本。這比單個目標的蠻力要好得多。在這裡查看更多。
- 還需要考慮 Grover 的非結構化量子搜尋算法，該算法將搜尋時間減少到它的平方根。如果建成，那麼（忽略執行成本）搜尋時間將在 $ 2^{64} $ .
也可以並行化；然而，建築 $ k^2 $ 機器將提供 $ k $ 加速。
基於 md5 輸出有沒有辦法找出有關輸入的資訊？比如開頭是哪個字元，或者輸入主要由哪個字元組成？
不，您所描述的實際上是對原像抗性的破壞。
如果你能找到第一個字元（字節），那麼原像電阻下降到 $ c \cdot 2^{120} $ 在哪裡 $ c $ 是確定第一個字元的成本。下一個問題將是什麼阻止了攻擊者確定下一個字節，然後下一個？散列函式被設計成具有雪崩效應，它改變輸入的一位應該隨機影響所有輸出位，即所有輸出位翻轉50％。
如果您可以通過查看散列來找出字元空間（假設有一個預言機告訴我們這一點），例如 5 個數字，那麼如果您查看 128 位資訊，則圖像前搜尋會被削弱， $ 5^{16} \approx 2^{38} $ . 這並不意味著必須在這個 128 位空間中找到原像。不過，我們可以看看字元串長度為 32，搜尋時間將是 $ 2^{76} $ -時間
或者，實際上，您在問類似的問題；
- 如果輸入空間少於 16 個字元 $ [1,2,3,4,5] $ 那麼這就是散列函式上的短輸入空間問題。由於雜湊的計算是免費的，因此可以很容易地搜尋這些值。 $ 2^{38} $ 當今的普通 CPU 可以輕鬆訪問搜尋空間。
為了緩解這種情況，您可以使用鍵控散列函式，例如 $ \operatorname{HMAC-MD5}(k,m) $ . 只要密鑰保密，就可以了。注意，如果沒有使用 MD4 的限制，首選 $ \operatorname{HMAC-SHA-256}(k,m) $
實際問題是我有一個 SHA-256 字元串作為輸入（64 個字元和十六進制），我想向我的使用者顯示這個輸入的 MD5，重要的是他們無法根據 MD5 輸出找到任何資訊。我想知道它是否是一個短的輸入空間
十六進制是您將擁有的 4 位 $ 4^{64} $ 輸入空間進行搜尋；那是 $ 2^{128} $ -少量。這對於單個目標來說太高了。然而;
- 如果 $ t $ 使用者可以聚在一起，可以使用彩虹表建構並行機器，然後他們可以找到第一個目標 $ 2^{128}p/t $ 面積*時間成本。因此，您可以使用此資訊調整您的號碼。