開發者工具 · SHA 雜湊計算器
Merkle–Damgård 解釋：SHA-1 和 SHA-2 背後的構造
· 背景
sha-256 密碼學 瀏覽器 API
固定大小的壓縮函數無法自行散列任意輸入。 Merkle-Damgård 將其逐塊連結起來；這篇文章解釋了它的結構、證明思想以及它的弱點。
任意輸入，固定輸出－每個雜湊函數首先要解決的問題
雜湊函數必須將任意輸入映射到固定輸出。三個位元組的訊息和三個兆位元組的訊息都必須為 SHA-256 準確產生 256 位元的輸出。哈希必須是確定性的，因此相同的輸入總是產生相同的輸出。輸出看起來必須是隨機的；改變輸入的單一位元應該改變大約一半的輸出位元。
乍一看，這些是矛盾的要求，因為單一快速演演算法無法處理任意長度的訊息並產生統一的固定寬度輸出。 Merkle-Damgård 結構透過重複使用固定大小的壓縮函數，將每個應用程式的輸出輸入到下一個應用程式的輸入中，解決了這個問題。此結構由 SHA-1 和所有 SHA-2 （SHA-256、SHA-384 和 SHA-512）使用。
壓縮函數－一個固定大小的混合器，它接受一個狀態和一個區塊並傳回一個新狀態
壓縮函數是為 Merkle–Damgård 雜湊提供支援的核心加密原語。它採用固定大小的狀態（對於 SHA-256 通常為 256 位，對於 SHA-512 通常為 512 位）和固定大小的輸入區塊（對於 SHA-256 通常為 512 位，對於 SHA-512 通常為 1024 位）。壓縮函數使用位元運算、旋轉和表格查找將它們混合在一起，產生相同大小的新狀態。這個函數必須是抗衝突的：找到產生相同輸出的兩個不同的（狀態，塊）對一定很困難。
壓縮函數本身並不是一個完整的雜湊函數——它不處理任意輸入長度，甚至不處理沒有先前狀態的第一個輸入。相反，它是建造更大建築的基石。壓縮函數是唯一重複執行的密碼操作；其他一切都是簿記，將該函數連接到完整的雜湊。
連結和初始化向量－區塊如何從固定的起始狀態相互饋送
初始化向量是固定的起始狀態，仔細選擇以避免對稱性或弱點。對於 SHA-256，IV 是從前八個質數的平方根的小數部分派生的八個 32 位元字。這些值是任意的但具有確定性，因此每個實作都會產生相同的結果。第一個訊息區塊使用壓縮函數與 IV 混合，產生一個新的狀態。第二個訊息區塊與該狀態混合，產生另一個新狀態，依此類推，直到訊息的每個區塊。
這種連結是至關重要的部分：一個區塊的輸出取決於所有先前的區塊，因此更改任何先前區塊的任何位元都會更改所有後續區塊。當處理最後一個區塊時，狀態包含輸入每一位的資訊。填充是讓這個結構聽起來更合理的技巧。訊息並不總是均勻地分成塊。 Merkle-Damgård 結構使用 MD 強化：在訊息中附加一位，然後附加零，直到剩下幾乎一個完整的區塊，然後附加原始訊息長度。
用訊息長度填充－為什麼 MD 強化可以讓結構聽起來更合理
Merkle–Damgård 的安全論點說，如果壓縮函數是抗碰撞的，那麼整個雜湊就是抗碰撞的。證明是一個簡化：如果你能在雜湊中找到衝突，你就可以在壓縮函數中提取衝突，這與壓縮函數難以衝突的假設相矛盾。直覺是，雜湊中的任何衝突最終都必須在壓縮函數呼叫之一中產生衝突，因為狀態被完全向前推進。
儘管基本結構很健全，但隨著時間的推移，Merkle-Damgård 的弱點也被發現了。長度擴展就是其中之一：看到訊息摘要的攻擊者可以擴展訊息並計算較長訊息的有效摘要，而無需了解有關輸入的任何資訊。第二個原像攻擊是另一種：給定一則訊息，找到具有相同雜湊值的不同訊息比某些類型的訊息更容易。這些弱點激發了 SHA-3 的設計，它使用了一種稱為海綿結構的不同方法。
長度編碼填充分隔填充的訊息；完整的安全證明是外部儲存庫證據
SHA-256 的壓縮函數採用 256 位元狀態（八個 32 位元字）和 512 位元區塊。此操作使用 64 輪，每輪將狀態與區塊中的常數和字混合。混合使用位元運算：XOR、AND、NOT。它使用旋轉和移位來移動位元而不改變設定的位元。它使用表格查找來提供單獨 XOR 無法實現的非線性混合。
SHA-512 使用與 SHA-256 相同的結構，但使用 64 位元操作而非 32 位元操作。狀態為 512 位元（八個 64 位元字），區塊大小為 1024 位元。壓縮函數有80輪而不是64，常數和表格查找也不同。對於 SHA-384，狀態和壓縮函數與 SHA-512 相同，但僅輸出最終狀態的前 384 位元。最後 128 位元將會被丟棄。這種截斷就是 SHA-384 抵抗長度擴展的原因。
延伸長度為經核實的施工邊界；多重碰撞和 SHA-3 動機宣告被省略
Merkle–Damgård 雜湊的安全性取決於所持有的多個屬性。壓縮函數必須是抗碰撞的，因此直接攻擊它是不可行的。填充方案必須確保不同的訊息產生不同的填充形式，因此雜湊中的每次衝突都必須涉及壓縮函數衝突。區塊大小和狀態大小必須足夠大，否則暴力破解是不可行的。更廣泛的狀態擴大了通用搜尋空間，但本文沒有在沒有內聯推導和審查來源的情況下附加操作計數或可行性日期。
如果攻擊者發現壓縮函數中的弱點，或者量子電腦變得實用並可以在 sqrt(2^n) 時間內而不是 2^n 時間內搜尋非結構化空間，那麼安全裕度就會受到侵蝕。引發 SHA-3 的弱點不是壓縮功能的破壞，而是長度擴展問題和其他結構漏洞。海綿結構透過從不發布其完整的內部狀態來避免這些問題。
這不包括什麼 - SHA-256 的特定輪函數，在單獨的帖子中介紹
Merkle–Damgård 結構如何處理每個輸入大小是其設計的實際結果。將訊息分割成 512 位元區塊，填滿最後一個區塊，透過壓縮函數依序處理每個區塊，並輸出最終狀態。對於一位元組輸入，填入會產生 512 位元區塊（一位元組訊息、一個填入、447 位元零和 64 位元長度）。壓縮次數為 512 位元區塊的數量，與訊息長度成正比。
ToolAcre SHA 雜湊計算器產生的每個摘要都來自此構造。 64 字元 SHA-256 摘要是以十六進位列印的最終 256 位元狀態。 128 字元 SHA-512 摘要是以十六進位列印的最終 512 位元狀態。 96 字元 SHA-384 摘要是最終 512 位元狀態的前 384 位元。幕後的填充可確保每個可能的訊息準確地產生正確數量的區塊和正確的摘要寬度。這是在瀏覽器中執行的標準 Merkle–Damgård 結構。
重點：四種演演算法背後的骨架相同 — ToolAcre SHA 雜湊計算器產生的每個摘要都來自此構造
瞭解其結構有助於了解為什麼摘要始終具有相同的寬度以及為什麼更改輸入的一位會更改整個摘要。連結屬性意味著輸入的每一位透過一系列混合操作影響輸出的每一位。訊息早期的一位變更將傳播到所有後續壓縮，因此最終的摘要完全不同。此屬性稱為雪崩效應，是健全雜湊函數的簽名。
Merkle–Damgård 結構已經使用了數十年，並構成了最廣泛部署的雜湊函數的基礎。 SHA-1 和 SHA-2 建立在這個結構之上，許多已部署的系統依賴它們的輸出。建築物是已建成的而不是實驗性的，但歷史並不能保證每次使用都是安全的；長度擴展是一種有記錄的邊界。了解這種結構有助於開發人員理解為什麼某些安全屬性保持不變以及為什麼存在某些攻擊向量。