海綿函數

海綿功能操作如下：

1、狀態S初始化為零

2、填充輸入字符串。這意味着使用填充函數P將輸入轉換為r位塊。

3、對於填充輸入的每個r位塊B：

a.R被R XOR B替換（使用按位異或）

b.S被f（S）取代

這個過程“吸收”（在海綿比喻中）填充輸入字符串的所有塊。

海綿功能輸出可以生成（“擠出”），如下所示：

1、輸出狀態存儲器的R部分。

2、重複直到輸出足夠的位：

a.S被f（S）取代。

b.輸出狀態存儲器的R部分

如果剩餘少於r位要輸出，則R將被截斷（僅輸出R的一部分）。

另一個比喻將狀態記憶描述為“熵池”，輸入“湧入”池中，轉換函數稱為“攪動熵池”。

注意，輸入位永遠不會異或進入狀態存儲器的C部分，也不會直接輸出任何C位。輸入改變C的程度完全取決於變換函數f。在哈希應用中，對碰撞或前像攻擊的抵抗力取決於C，並且其大小（“容量”c）通常是所需阻力水平的兩倍。

海綿函數是由三個部份組成：

1.一個內存狀態S，包含b個位元

2.一個能置換或者轉換內存狀態，固定大小的轉換函式f

3.一個填充函式(padding function)P

內存狀態會分成兩個區塊，R（大小為r位元）與C（大小為b - r位元）。這裏的參數r又叫做轉換率（bitrate），而c叫做容量（capacity）。

填充函式會在輸入裏面增加足夠的長度，讓輸入的位元流長度變成r的整數倍。因此填充過後的輸入可以被切成長度為r的數個分段。

然後，海綿函數運作如下：

1.S先初始化為零

2.輸入經過填充函式處理

3.填充後輸入的前面r個位元會與R進行XOR運算

4.S經過函式f轉換成f(S)

5.如果填充後輸入還有剩餘，下一r位元的分段與R進行XOR運算

6.S轉換成f(S)

…

這過程一直重複到所有的輸入都用完為止（在海棉的譬喻裏面，被函數"吸收"了）。

海綿函數可以依照如下的過程輸出（"擠出"內容）：

1.此時R裏面的資料是輸出的前面r個位元

2.如果需要更多輸出，先把S轉換成f(S)

3.此時R裏面的資料是輸出的下面r個位元

…

這過程會重複到滿足輸出所需要的長度為止。

這裏值得注意的地方是，輸入絕對不會與C這部份的內存作XOR運算，而且C這一部份內存也不會直接被輸出。C這一部份的內存僅僅只和轉換函式f相關。在雜湊裏面，防止撞擊攻擊(Collision attack)或者原像攻擊(preimage attack)是依靠C這段內存作到的。一般實做上C的大小會是所希望防止等級的兩倍。

海綿函數可以在理論上面或者實做上面應用。在密碼分析理論上，隨機海綿函數(random sponge function)是一個轉換函式f為隨機置換的海綿函數。隨機海綿函數比起經常使用的隨機預言（有關預言的部份請參考預言機）滿足更多加密基元(cryptographic primitives)的限制，像是有限大小的內存狀態 ^[1]  。

海綿函數也可以用來建造實際的加密基元。例如，Keccak雜湊函數就是以海綿函數的方式建立的。Keccak雜湊函數使用1600位元大的版本被國家標準技術研究所(NIST)在SHA-3競賽之中選為贏家。Keccak算法的特點在於作者所開發複雜、多次的置換函數。