Keccak/SHA3 針對生日攻擊的安全性
如果我正確理解它的安全性 $ \operatorname{Keccak} $ 取決於容量 $ c $ ，這意味著我的安全級別為 $ 2^{128} $ 為了 $ c=128 $ （我省略了值 $ r $ 在這裡，因為我認為這與我的問題無關……但如果我錯了，請糾正我）。
但在我發現的每一份出版物中（甚至在 $ \operatorname{Keccak} $ 網站），據說安全性不取決於輸出長度。我不明白它的價值如何 $ c $ 與生日攻擊有關。對於每一個散列函式，我都可以執行生日攻擊而不考慮散列函式的內部構造，對吧？這意味著對於一個 $ \operatorname{Keccak} $ 實施與 $ c=128 $ 但是輸出長度可以說 $ 64 $ 位，我可以找到碰撞後 $ 2^{32} $ 使用生日悖論的步驟，無論 $ c $ ， 正確的？
讓我們更進一步。Keccak 怎麼樣 $ c=128 $ 並且 1 位的輸出長度仍然安全嗎？對於實際應用，它根本不可能…
讓我們更正您的一些數字。容量大小是預期安全邊際大小的兩倍（針對生日攻擊）。這就是扁平海綿塊等的想法
當使用隨機海綿作為安全參考時，人們會考慮特定攻擊的成功。這種成功機率不僅取決於所考慮的攻擊的性質，還取決於隨機海綿的所選參數，即其容量、比特率以及它是否呼叫隨機排列或隨機變換。扁平海綿聲明是一種簡化，因為我們只考慮最壞情況下的成功機率，由隨機預言機微分優勢的上限決定
$$ Bertoni et al., Eurocrypt'08 $$，這完全取決於隨機海綿的容量。因此，它使用一個參數來壓平所有攻擊的聲稱成功機率：聲稱的容量 $ c_{\mathit{claim}} $ .$$ source $$
因此，如果您的目標是安全邊際 $ 128 $ 位，你需要有一個容量 $ 256 $ 位。
在這種方法中，人們設計了一個排列 $ f $ 上 $ b=r+c $ 位並在海綿構造中使用它來建構海綿功能 $ F $ . 此外，有人提出了一個扁平海綿聲稱 $ F $ 聲稱的容量等於海綿結構中使用的容量，即 $ c_{\mathit{claim}}=c $ . 換句話說，該聲明指出，最好的攻擊 $ F $ 必須是泛型攻擊。因此， $ c_{\mathit{claim}}=c $ 意味著任何攻擊 $ F $ 預期復雜度低於 $ 2^{c/2} $ 意味著結構上的區分 $ f $ ，因此排列的設計試圖避免這種區分。請注意，結構區分符的存在 $ f $ 並不一定意味著攻擊或弱點 $ F $ . 例如，任何區分符 $ f $ 成功機率為零以下 $ 2^{c/2} $ 不構成威脅，因為扁平海綿的主張對可能發送更多 $ 2^{c/2} $ 查詢。$$ source $$
TL;DR：安全邊際是容量的一半。如果您的目標是 128 位，則需要 256 位的容量。
話雖如此，我們可以解決您的誤解。你說得對，如果你的輸出長度為 $ 1 $ 位，你不會有 $ 64 $ 位安全聲明…因為您正在尋找輸出中的衝突。
當你使用 $ \operatorname{Keccak} $ ，您可以檢索比特率的完整大小（ $ r $ ）。您還可以擴展此輸出，因為這些輸出是相關的 （因為您基本上總是知道比特率部分的內容）。因此，您不知道的唯一部分是容量。如果您能夠猜測或在這部分發生衝突，那麼輸出就會受到影響。
容量是狀態中唯一你不知道的部分。
當您想要發生衝突時，您可能會在容量部分或比特率部分發生衝突，這通常大於容量……
讓 $ a,b $ 是兩個輸入和 $ c,c_1,c_2 $ 容量部分。在以下情況下發生碰撞： $$ f(a) \to [\theta \mathbin| c_1]\f(b) \to [\theta \mathbin| c_2] $$ 在哪裡 $ [\theta \mathbin| c] $ 是完整的狀態和 $ \theta $ 是結果輸出（這裡你的輸出長度很重要）。
找到碰撞的另一種方法是設法獲得： $$ f(a) \to [\alpha \mathbin| c]\f(b) \to [\beta \mathbin| c] $$ （容量衝突），因為那樣你可以（由於簡化的海綿結構）： $$ \begin{align} f(a \mathbin| 0) & \to [\alpha \mathbin| c] &\Rightarrow&&& f([\alpha \oplus 0 \mathbin| c]) \to \theta \ f(b \mathbin| \beta \oplus \alpha) & \to [\beta \mathbin| c] &\Rightarrow&&& f([\beta \oplus \beta \oplus \alpha \mathbin| c] ) = f([\alpha \mathbin| c]) \to \theta \end{align} $$
TL；DR 2：正如@CodeInChaos 所說，碰撞阻力是 $ \min(c/2,n/2) $ 和原像抗性 $ \min(c/2,n) $ 其中 n 是輸出大小。. 但大多數論文搜尋碰撞 $ \operatorname{Keccak}[1600] $ 因此，為什麼他們通常會聲明這個更通用的安全邊際（ $ 2^{\mathit{capacity}/2} $ ).