Matyas-Meyer-Oseas 用於超快速單塊雜湊函式
使用Matyas-Meyer-Oseas構造將像 AES 這樣的快速分組密碼轉換為真正快速的單塊雜湊函式基本上是安全和正確的嗎？
我所說的單塊散列函式是指對 128 位輸入進行散列並產生 128 位輸出的函式。我不需要可變或更大的消息大小，如果需要，我會使用 SHA-2、SHA-3 等，但對於非常短的固定長度消息來說，這些要慢得多。基準測試表明，這種 AES 結構在具有 AES-NI CPU 擴展的機器上散列單個塊長度消息的速度是 10 倍以上。
如果我理解 Matyas–Meyer–Oseas，散列函式將由使用靜態預定義密鑰初始化的 AES 組成，然後用於加密單個輸入塊（“ECB”模式）。然後將加密結果與原始塊進行異或運算以產生輸出雜湊。由於您只是散列大小等於塊大小的消息，因此不會使用後續塊進一步初始化密碼。
如果您好奇，該應用程序將是 Winternitz 一次性簽名。Winternitz 簽名涉及大量單個塊大小消息的迭代散列。原像抗性很重要，因此需要一個良好的散列函式，但對於緊湊簽名，您希望增加簽名中“列”的高度。
使用 Matyas-Meyer-Oseas 構造將像 AES 這樣的快速分組密碼轉換為真正快速的單塊雜湊函式基本上是安全和正確的嗎？
大多數情況下，是的。這是將排列轉換為單向函式的一種標準方法（費用相當小）。它確實有一些奇怪的屬性（例如，很容易找到固定點，即散列到自身的塊），但這些通常不是問題。
如果您好奇，該應用程序將是 Winternitz 一次性簽名。
這帶來了一些擔憂。一方面，Winternitz 一次性簽名由一系列 $ H(x) $ 價值觀，如果你能找到任何一個，你就可以偽造 $ x $ 價值觀。您使用的是完全相同的 $ H $ 每次迭代的函式；攻擊者可以做的是編譯列表 $ H(x) $ 他正在尋找和計算的值 $ H(y) $ 對於不同的值 $ y $ ; 如果它恰好匹配他的任何目標 $ H(x) $ 價值觀，他贏了。例如，如果您的簽名由 34 個長度為 255 的 Winternitz 鏈組成（即 256 位，加上校驗和），那麼預期有 4000 多個雜湊是潛在目標
$$ 1 $$; 這會將您的安全性降低 12 位。這可以通過為不同的鏈使用不同的 AES 密鑰來緩解，但這不是免費的，它只會減少擔憂。 進行 Winternitz 的現有建議，例如XMSS或LMS，通過在每次 Winternitz 迭代中加入不同的值來解決這個問題（因此每個 $ H $ 呼叫是不同的），因此這種多重衝突攻擊不適用。
另一個反對意見取決於您使用 OTS 的原因（而不是更標準的簽名算法，例如 RSA 或 E
$$ Cd $$DSA）。一個潛在的原因是量子阻力。為此，128 位的雜湊輸出不會削減它。現在，還有其他潛在原因（例如，您的簽名者或您的驗證者資源受限），因此該反對意見可能不適用。
$$ 1 $$：注意：不僅簽名中出現的雜湊是潛在目標，鏈中後面的任何雜湊也是潛在目標。