Sponge Construction
The sponge construction is an algorithmic framework that builds cryptographic primitives from a fixed-length permutation by alternating between absorbing message blocks into a state and squeezing output bits.
Sponge Construction is a versatile high-level algorithmic framework in computation and algorithms that constructs cryptographic primitivesโincluding cryptographic hash functions, pseudo-random number generators, stream ciphers, and authenticated encryption schemesโfrom an underlying fixed-length unkeyed permutation. Formulated in 2007 by cryptographers Guido Bertoni, Joan Daemen, Michaรซl Peeters, and Gilles Van Assche, the sponge construction was catapulted to international prominence when their submission, Keccak, won the NIST cryptographic hash competition to become the official SHA-3 standard.
Prior to the sponge paradigm, the majority of hash functions relied upon the MerkleโDamgรฅrd construction, which chains together fixed-input compression functions. While mathematically proven collision-resistant under ideal assumptions, MerkleโDamgรฅrd structures suffer from structural vulnerabilitiesโmost notably length-extension attacks. The sponge construction resolves this limitation by maintaining an internal capacity state that is never revealed to the external environment, establishing an adaptable primitive capable of processing variable-length inputs into variable-length outputs.
Structural Topology: Bitrate, Capacity, and State
A sponge function operates on an internal state memory of fixed bit length b, referred to as the width:
b = r + c
The width is partitioned into two distinct segments:
- Bitrate (r): The outer portion of the state that directly interacts with input and output blocks. The bitrate dictates the processing throughput: larger values of r process more data per permutation call.
- Capacity (c): The inner portion of the state that remains insulated from direct external modification or readout. The capacity dictates the theoretical security margin: larger values of c elevate resistance against collision and preimage attacks.
The central engine driving the construction is an unkeyed, public, fixed permutation f: {0, 1}b โ {0, 1}b that operates as a bijection over the state space.
Two-Phase Operational Mechanics
Execution proceeds through two sequential operational phases: the Absorbing Phase followed by the Squeezing Phase.
1. The Absorbing Phase
Let the input message M be padded using a reversible multi-rate padding rule (such as pad10*1, which appends a bit 1, followed by the minimum number of 0 bits, and a final bit 1) such that the total length of the padded string is an integer multiple of the bitrate r. The padded message is partitioned into k blocks of r bits: P0, P1, ..., Pkโ1.
- Initialization: The b-bit state S is initialized to all zeros: S = 0b.
- Iterative Absorption: For each block Pi (from 0 to k โ 1):
- The message block Pi is combined with the first r bits of the state using bitwise exclusive-OR (XOR):
S = (S[0...rโ1] โ Pi) || S[r...bโ1]
- The full b-bit state is transformed by evaluating the permutation f:
S = f(S)
Once all k blocks have been absorbed, the internal state encapsulates a cryptographic digest of the complete message stream.
2. The Squeezing Phase
In the squeezing phase, the user extracts the desired number of output bits:
- The first r bits of the state (S[0...rโ1]) are emitted as the first output block Z0.
- If additional output bits are requested, the permutation f is applied to the state (S = f(S)), and the new r-bit prefix is emitted as Z1.
- This process repeats iteratively until the requested output digest length is satisfied.
Because the capacity portion S[r...bโ1] is never exposed during output extraction, an adversary observing the output stream cannot reconstruct the internal state to append additional data, providing native immunity against length-extension attacks.
Security Bounds and the Indifferentiability Framework
In 2008, Bertoni, Daemen, Peeters, and Van Assche proved the security of the sponge construction within the Indifferentiability from a Random Oracle framework formulated by Ueli Maurer, Renato Renner, and Clemens Holenstein.
Assuming the underlying permutation f is an ideal random permutation chosen uniformly from all (2b)! permutations:
- Collision Resistance: Finding a collision requires on the order of 2c/2 operations.
- Preimage Resistance: Finding a preimage for an output of length n requires on the order of min(2n, 2c/2, 2c) operations.
- Second-Preimage Resistance: Finding a second preimage requires on the order of 2c/2 operations.
These bounds demonstrate that the security level is governed solely by the capacity parameter c, independent of the output digest length. For example, in SHA3-256, NIST selected b = 1600, c = 512, and r = 1088 bits, providing 2c/2 = 2256 collision security.
The Duplex Sponge and Authenticated Encryption
A powerful structural extension of the sponge framework is the Duplex Construction. Rather than absorbing all inputs before squeezing, a duplex sponge alternates between absorbing an input block and squeezing an output block in a single call.
This duplex mechanism allows cryptographers to construct lightweight Authenticated Encryption with Associated Data (AEAD) schemes:
- The secret key and nonce are absorbed.
- Associated data blocks are absorbed to update authentication state.
- Plaintext blocks are absorbed while simultaneously XORing the squeezed bitrate bits to generate ciphertext blocks.
- A final tag is squeezed out to provide integrity verification.
This design principles powers modern lightweight ciphers, including Ascon (selected by NIST in 2023 as the international standard for lightweight cryptography).
Parameters Across Sponge Primitives
| Primitive | Width b | Bitrate r | Capacity c | Underlying Permutation | Primary Application |
|---|---|---|---|---|---|
| SHA3-256 | 1600 bits | 1088 bits | 512 bits | Keccak-p[1600, 24] | Standard 256-bit Cryptographic Hashing |
| SHA3-512 | 1600 bits | 576 bits | 1024 bits | Keccak-p[1600, 24] | Standard 512-bit Cryptographic Hashing |
| SHAKE128 | 1600 bits | 1344 bits | 256 bits | Keccak-p[1600, 24] | Extendable-Output Function (XOF) |
| Ascon-128 | 320 bits | 64 bits | 256 bits | Ascon-Permutation [320, 12] | Lightweight Authenticated Encryption |
References
- Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2007). Sponge functions. Ecrypt Hash Workshop 2007.
- Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2008). On the indifferentiability of the sponge construction. Advances in Cryptology โ EUROCRYPT 2008, 181-197.
- National Institute of Standards and Technology. (2015). SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. Federal Information Processing Standards Publication 202.
- Dobraunig, C., Eichlseder, M., Mendel, F., & Schlรคffer, M. (2021). Ascon v1.2: Lightweight cryptography for the Internet of Things. Journal of Cryptology, 34(3), 33.