是否可以找到減小大小雜湊的原像？
給定消息 $ M $ 和一個 256 位密鑰 $ K $ , 執行 HMAC( $ K $ , $ M $ ) 使用 256 位散列函式，結果為：
$ a $ =
9a58e0eef2effc968d27cd61c47394867ceae43c7a877d59938f8400fe1a0204現在每隔一個十六進制符號生成一個 128 位雜湊：
$ b $ =
a80e2fc6d7d14346ca4ca7d93f40ea24假設攻擊者知道 HMAC 雜湊函式。
- 只知道 $ b $ , 是否有可能找到原像 $ M $ 或者 $ K $ ?
- 只知道 $ b $ , 找到原 $ K $ 或者 $ M $ , 攻擊者是否需要重複相同的過程 (HMAC( $ K $ , $ M $ ) + 每隔一個符號) 並使用 2 256個不同的鍵執行蠻力搜尋以將雜湊匹配回 $ b $ ? 還是有更快的方法？
我們真的不知道找到大多數密碼散列函式的原像有多難。即使對於 MD5，創建碰撞也只是“容易”，而尋找原像仍然被認為是“困難的”。
也就是說，如果我們假設散列函式的隨機預言機，我們可以應用統計工具來估計“最壞情況”。在這種情況下，我們平均需要 $ 2^{255} $ 試圖找到一個 256 位散列的原像。現在，如果我們只尋找部分匹配（只有 128 位，哪個並不重要），我們可以估計平均匹配 $ 2^{127} $ 嘗試。
現在，散列函式接受任意輸入並將其映射到固定大小的輸出。沒有“M 或 K 的原像”，只有原像（映射到相同雜湊值的輸入）。所以一旦你找到了原像，你就有了這個輸入。如果 HMAC 方案需要特定格式的鍵、消息和可能的其他資訊的輸入值，那麼您應該只測試符合這種格式的輸入。
對於您的第二個問題：如果攻擊者只有雜湊值（因為它們相同），則攻擊者無法區分原始消息/密鑰和任何其他原像。這可能只有通過有關消息的附加資訊才能實現：例如，如果消息由 UTF8 中的英文單片語成，則隨機位的原像不是“錯誤的原像”。然而，在這種情況下，他甚至不會嘗試這種隨機輸入。
一般來說，HMAC 和密碼散列函式之間的區別並沒有那麼大。如果從一小組可能的消息中選擇消息，則差異變得很重要。在這種情況下，攻擊者不僅可以測試所有可能性並找到真正的可能性，還必須使用所有鍵（應該大於散列值空間）測試所有消息。但平均而言，他仍然會在 2^{k-1} 次嘗試中找到一個原像以獲得 k 位雜湊值。
最後一點：雖然 $ 2^{127} $ 暴力破解的可能性太大了，這個減少的雜湊值的安全性低於原始雜湊值。雜湊值的每個被忽略的位都將通過蠻力找到原像的複雜性降低了一半。如果您考慮減少到 256 位雜湊值（或任何其他固定的 64 位）的每 4 位，您就會進入“使用當今工具可能找到的”範圍。您必須問自己是否值得為可能更長的消息節省一些位，特別是如果您考慮其他消息成本（例如 IPv4 和 TCP 標頭各 160+ 位）