Sha-3

如果 SHAKE128/256 的輸出大小是可變的,為什麼安全性固定在 128/256?

  • February 9, 2017

一般的想法是一個好的散列函式的安全強度等於它的輸出長度的一半。SHAKE128 和 SHAKE256 的輸出長度是可變的,但它們的強項仍然分別稱為 128 位和 256 位。為什麼會這樣?

一般的想法是一個好的散列函式的安全強度等於它的輸出長度的一半。

隨機預言機的安全強度確實是其輸出長度的函式,僅此而已。長期以來,人們普遍認為雜湊函式的設計目標應與具有相同輸出大小的隨機預言機相同的安全強度。或者換句話說,隨機預言是“理想”雜湊函式應該表現的經典模型。

近年來,這種普遍的智慧已經讓位於這樣一種觀點,即這種安全目標往往是過度的。例如,一個 512 位的隨機預言機提供 256 位的安全性來抵禦碰撞攻擊,但提供高達512 位的安全級別來抵禦原像攻擊。例如,SHA-512 聲稱具有該安全級別。

但是沒有實際場景需要 512 位安全級別來抵禦任何攻擊。因此,“略過”並針對兩種攻擊提供 256 位安全性的雜湊函式就綽綽有餘了。對於 256 位輸出散列函式,可以做出類似的評論,該函式提供 128 位安全性以防止衝突和原像;對於許多需要 128 位安全性的應用程序來說,這將是一個非常合理的選擇。

因此,Keccak/SHA-3 旨在適應這種較新的範式,即雜湊函式不需要提升到與隨機預言機相同的安全級別。它不是將隨機預言機作為散列函式的理想模型,而是設計為與隨機海綿相同的安全級別——Keccak 內部使用的相同海綿結構,但使用隨機固定大小排列而不是Keccak 所做的具體操作。

隨機海綿模型比隨機預言模型更寬鬆,但它仍然是一個更現實的原則模型。這是有原則的,因為有安全證明可以將隨機海綿的安全性與隨機預言機的安全性進行比較:

> > 我們已經證明了隨機海綿函式與隨機預言機一樣強大,除了有限記憶引起的影響。[來源] > > >

這句話也暗示了為什麼它更現實。一個隨機海綿按順序處理任意長度的消息,一次一個塊,使用一個恆定大小的緩衝區,就像實際的散列函式一樣。因此,隨機海綿很容易受到利用這些選擇的攻擊,但這些是實際雜湊函式無法逃脫的攻擊。另一方面,隨機預言機能夠以任何順序的、恆定空間的雜湊函式無法重現的方式執行——但這使它們成為我們知道無論如何在實踐中都無法達到的標準。

SHAKE128 和 SHAKE256 的輸出長度是可變的,但它們的強項仍然分別稱為 128 位和 256 位。為什麼會這樣?

現在有了哲學,具體的答案是它們是海綿功能,具有以下能力 $ c = 256 $ 和 $ c = 512 $ 相應地,隨機海綿的安全級別永遠不會超過 $ c/2 $ . 只要您選擇足夠的輸出長度,這些安全級別在實踐中就足夠了。

內部函式專門設計為僅支持 128 位或 256 位安全性:它是 256 或 512 位**容量的一半。**基礎功能或結構不會改變。

您可以從以下圖片中看到這一點,該圖片取自 Noekeon 網站關於通用海綿結構(SHA-3 / SHAKE / Keccak 是海綿結構):

在此處輸入圖像描述

容量是 $ c $ 在左手側。

所以輸出是在擠壓階段產生的,而容量(作為輸入 $ f $ 保持 256 或 512 位)。

這可能沒有您想像的那麼重要,256 位安全性被認為足以防止使用量子電腦進行分析。即使產生大的輸出,安全性也不會降低。

可以從 Noekeon 網站獲取更多資訊:

當使用隨機海綿作為安全參考時,人們會考慮特定攻擊的成功。這種成功機率不僅取決於所考慮的攻擊的性質,還取決於隨機海綿的所選參數,即其容量、比特率以及它是否呼叫隨機排列或隨機變換。扁平海綿聲明是一種簡化,因為我們只考慮最壞情況下的成功機率,由隨機預言機微分優勢的上限決定

$$ Bertoni et al., Eurocrypt'08 $$,這完全取決於隨機海綿的容量。因此,它使用一個參數來壓平所有攻擊的聲稱成功機率:聲稱的容量 $ c_{claim} $ .

後來有人提到 $ c_{claim} = c $ .

引用自:https://crypto.stackexchange.com/questions/43718