密碼學/破解雜湊演算法

從密碼學的角度來看，密碼學雜湊函式是最難破解的東西之一。

密碼學雜湊函式專門設計為“單向”：如果你有一些訊息，很容易向前推匯出相應的雜湊值；但如果你只有雜湊值，密碼學雜湊函式專門設計為難以計算出產生該雜湊值的原始訊息——或任何其他產生相同雜湊值的的訊息。

正如我們在之前的雜湊中提到的，密碼學安全的雜湊旨在具有以下屬性

• 抗原像：給定 H，應該很難找到 M 使得 H = hash(M)。
• 抗第二原像：給定輸入 m1，應該很難找到另一個輸入 m2（不等於 m1）使得 hash(m1) = hash(m2)。
• 抗碰撞：應該很難找到兩個不同的訊息 m1 和 m2 使得 hash(m1) = hash(m2)。

密碼學家區分對雜湊函式的三種不同型別的攻擊

• 碰撞攻擊：嘗試找到任何兩個不同的訊息 m1 和 m2 使得 hash(m1) = hash(m2)。
• 原像攻擊：僅給定雜湊值 H，嘗試恢復 *任何* M 使得 H = hash(M)。
• 第二原像攻擊：給定輸入 m1，嘗試找到另一個輸入 m2（不等於 m1）使得 hash(m1) = hash(m2)。
• 一些雜湊函式（MD5、SHA-1、SHA-256 等）容易受到“長度擴充套件攻擊”。

（唉，不同的密碼學家對這三種攻擊使用不同的，有時是矛盾的術語。在這本書之外，一些密碼學家使用“碰撞”來指代對這三種攻擊型別的任何一種的成功攻擊，並使用術語“自由碰撞”來指代本書所說的“成功碰撞攻擊”，或“繫結碰撞”來指代“成功原像攻擊”或“成功第二原像攻擊”中的任何一種。）

在設計需要雜湊函式的新系統時，大多數密碼學家建議使用據我們所知能夠抵抗所有這些攻擊的雜湊函式（例如 SHA-3、BLAKE、Grøstl、Skein 等）。

碰撞攻擊是最容易的攻擊型別，也是最難防禦的攻擊型別。 由於有無限數量的可能的郵件，鴿籠原理告訴我們，理論上存在無限數量的雜湊碰撞，即使對於“理想的”隨機預言機雜湊也是如此。 密碼學雜湊旨在使其難以——僅使用我們太陽系中可用的資源，在實際上是不可能的——找到 *任何* 這些雜湊到給定雜湊值的郵件。

一些應用程式需要抗碰撞性。 當可能的攻擊者生成一條訊息，並且我們想要確認該人向愛麗絲展示的訊息與該人向鮑勃展示的訊息相同，以確保訊息完整性時，我們需要一個具有抗雜湊碰撞性的雜湊。

許多應用程式實際上不需要抗碰撞性。 例如，密碼雜湊需要抗原像和抗第二原像（以及其他一些特殊特性），但不需要抗碰撞性。 例如，重複資料刪除檔案系統、主機證明檔案系統（如 IPFS）、數字簽名等，僅需要抗第二原像性，不需要抗原像或抗碰撞性，因為在這些應用程式中，假設攻擊者已經知道雜湊到給定值的原始訊息。 例如，使用 HMAC 的訊息認證不需要抗碰撞性，並且不受長度擴充套件的影響；因此，截至 2011 年，密碼學家認為在現有應用程式中使用 HMAC-MD5 訊息認證是可以接受的，儘管他們建議新應用程式使用其他一些替代方法，例如 HMAC-SHA256 或 AES-CMAC。

在實際上不需要抗碰撞性的應用程式中，MD5 和 SHA-1 雜湊函式仍然被認為是足夠的。

許多人出於錯誤的原因批評 MD5 和 SHA1。 目前沒有已知的針對 MD5 或 SHA-1 的實際或近似實際的抗原像攻擊，更不用說抗第二原像攻擊了，只有碰撞攻擊。

這些碰撞攻擊包括

• Dobbertin 在 1996 年宣佈了 MD5 壓縮函式的碰撞...
• 截至 2009 年，在筆記型電腦上找到 MD5 中的選定字首碰撞大約需要 30 秒。
• Manuel 和 Peyrin 的 SHA-0 攻擊
• Nat McHugh 的 MD5 碰撞攻擊

• 等等
• 等等

在接下來的章節中，我們將討論

• 碰撞
• 生日攻擊
• 彩虹表