Sponge Construction

Sponge construction is a versatile cryptographic mode of operation that defines a sponge function. It operates in two phases:

• Absorbing Phase: Input data is XORed into a fixed-size internal state.
• Squeezing Phase: Output bits are extracted from the same state. Its security is based on the indifferentiability from a random oracle, making it suitable for hashing, pseudorandom number generation, and authenticated encryption.

The most prominent implementation is the Keccak family of hash functions, which won the NIST SHA-3 competition. Ethereum uses Keccak-256 (often called SHA-3 in Ethereum contexts) for:

• Generating addresses from public keys.
• Creating transaction and block hashes.
• Powering the Ethash proof-of-work algorithm (pre-Merge). Its sponge-based design provides resistance to length-extension attacks, a vulnerability in Merkle-Damgård constructions like SHA-2.

A key advantage of the sponge construction is its ability to produce an output (digest) of any desired length by simply continuing the squeezing phase. This is crucial for:

• Extendable-Output Functions (XOFs): Like SHAKE128 and SHAKE256, used in post-quantum cryptography (e.g., Dilithium signatures).
• Stream encryption: The squeezed output can serve as a keystream.
• Custom cryptographic protocols that require non-standard hash lengths without additional complexity.

The security of a sponge function hinges on its internal permutation, f. This is a fixed transformation applied to the state during each absorption and squeezing step.

• In Keccak, this is the Keccak-f permutation, which operates on a state of 1600 bits arranged in a 5x5x64 3D array.
• The permutation provides diffusion and confusion, making the function resistant to cryptanalysis. The bitrate (r) and capacity (c) parameters, where r + c = state size, trade between speed and security.

The Duplex construction is an extension of the sponge, enabling authenticated encryption and interactive protocols. It allows for interleaved absorption and squeezing, making it stateful. This is used in:

• Authenticated Encryption: Modes like Ketje and Keyak.
• Zero-Knowledge Proof Systems: Some ZK-SNARK and STARK protocols use sponge/duplex constructions as a Fiat-Shamir transform to make interactive protocols non-interactive, critically relying on their random oracle properties.

Sponge construction addresses several limitations of the older Merkle-Damgård structure (used in MD5, SHA-1, SHA-2):

• No Length-Extension Attacks: Appending data to a hash is not feasible without the secret internal state.
• Built-in Domain Separation: Easier to create different functions from the same permutation.
• Flexible Security Level: The security parameter (capacity c) can be tuned independently of output size. This makes it a more modern and resilient foundation for cryptographic standards.

A core security goal for sponge functions is indifferentiability from a Random Oracle (RO). This means that, given a secure underlying permutation, the sponge construction behaves like an ideal random function for any adversary with bounded computational resources. This property is crucial for ensuring the hash function's security in protocols that assume a RO model.

• Proof Framework: Security is formally proven under the assumption that the internal permutation is a public random permutation.
• Implication: Any attack on the sponge hash function implies an attack on the underlying permutation.

The capacity (c) of the sponge state directly determines its collision resistance and preimage resistance security levels.

• Collision Resistance: Security is c/2 bits. For a 256-bit capacity, collision resistance is 128 bits.
• Preimage & Second Preimage Resistance: Security is c bits. For a 256-bit capacity, resistance is 256 bits.
• Key Rule: The rate (r) absorbs input/output speed but does not contribute to these core security bounds. The internal state size is r + c, but only c is hidden from the adversary.

When used in duplex mode for authenticated encryption or reseedable PRNGs, the construction is vulnerable to state recovery attacks if an adversary can manipulate or observe the internal state.

• Threat: If an attacker learns the full internal state, they can forge messages or predict future outputs.
• Mitigation: Use a sufficiently large capacity and ensure proper domain separation between phases (absorbing, squeezing) to prevent state leakage through outputs.

Unlike Merkle-Damgård constructions (e.g., SHA-256), the basic sponge is not vulnerable to length extension attacks. This is because the output is a truncation of the internal state after finalization.

• Key Difference: An attacker cannot take a hash output H(M) and compute H(M || pad || X) without knowing the full internal state at the end of processing M.
• Note: Some variants (e.g., SHAKE256) are extendable-output functions (XOFs), allowing arbitrary-length output, which is a feature, not a vulnerability.

Real-world security depends on a leak-resistant implementation of the permutation (e.g., Keccak-f).

• Timing Attacks: The permutation should execute in constant time to prevent data-dependent timing variations.
• Power Analysis: Hardware implementations must be resistant to Differential Power Analysis (DPA).
• Fault Attacks: Resistance to glitching or inducing computational errors to reveal state information is critical for hardware security modules.

The sponge's security proof is generic; it assumes the internal permutation is ideal. Therefore, the security of a specific sponge hash (like SHA3-256) reduces to the cryptographic strength of its permutation (Keccak-f[1600]).

• Primary Risk: If a cryptanalytic breakthrough finds weaknesses in the permutation (e.g., non-random properties, efficient distinguishers), the security guarantees of the sponge construction degrade proportionally.
• Defense: Use permutations with large, well-analyzed state sizes (e.g., 1600-bit for SHA-3) to provide a large security margin.

The sponge operates in two distinct phases. First, in the absorbing phase, input data is broken into blocks and XORed into a fixed-size internal state, which is then transformed by a permutation function f. In the squeezing phase, output bits are extracted from this same state, with f applied between extractions to generate more output if needed. This allows for variable-length input and output.

The security and efficiency of a sponge hinge on its underlying permutation function. This is a fixed-length, bijective transformation applied to the state. Famous examples include:

• Keccak-f[1600]: The permutation at the heart of the SHA-3 standard (e.g., SHA3-256).
• Gimli: A lighter permutation used in some blockchain and IoT protocols. The function f provides the cryptographic diffusion and confusion, making the sponge construction resistant to attacks.

The internal state is divided into two parts: the rate (r) and the capacity (c).

• Rate (r): The number of state bits absorbed or squeezed per iteration. A higher rate increases speed.
• Capacity (c): The remaining state bits that are not directly input or output. This represents the security level; a larger capacity increases resistance to collisions and pre-image attacks. The security claim is that the sponge's strength is approximately 2^(c/2) against generic attacks.

The sponge construction was designed as a successor to the older Merkle-Damgård structure (used in MD5, SHA-1, SHA-2). Key advantages include:

• Built-in resistance to length-extension attacks, a major flaw in Merkle-Damgård.
• Native support for variable-length output (e.g., for generating keystreams), not just fixed-length digests.
• Simplicity and flexibility, allowing a single primitive to be used for hashing, encryption, and MACs.

An extension of the sponge that enables authenticated encryption. The duplex construction operates like a sponge but allows for interleaved absorption and squeezing in a single session. This enables a stateful, bidirectional communication channel, making it ideal for protocols that require both encryption and authentication in a single pass, such as the Ketje and Keyak authenticated ciphers.

The sponge is not just theoretical; it underpins major cryptographic standards.

• SHA-3 (Keccak): The NIST-standardized hash function family.
• Zero-Knowledge Proofs: Many zk-SNARK and STARK protocols use sponge-based hash functions (like Rescue or Poseidon) for their arithmetic-friendly properties within circuits.
• Lightweight Cryptography: Its efficiency makes it suitable for constrained environments, powering various blockchain state commitment schemes and Layer 2 solutions.

The duplex construction is an extension of the sponge model for authenticated encryption and other modes. It enables interleaved data absorption and squeezing within a single session, maintaining state between calls. This is fundamental to protocols like Ketje and Keyak, and forms the basis for the sponge-based pseudo-random function (PRF) used in many cryptographic suites.

Sponge functions are a cornerstone in modern zero-knowledge proof systems, particularly zk-SNARKs and zk-STARKs. They serve as the cryptographic sponge for building collision-resistant hash functions within arithmetic circuits. Their efficiency and security properties make them ideal for creating the Fiat-Shamir transform, which converts interactive proofs into non-interactive ones, and for generating public parameters.

Rescue and Poseidon are families of arithmetic-friendly hash functions designed using a sponge construction. They are optimized for efficiency in ZK-SNARK and STARK proof systems, where operations are performed over finite fields. Their design uses fewer multiplicative constraints than earlier designs like MiMC, making them significantly faster to prove in circuits like those used by zkSync and StarkNet.

The sponge construction naturally lends itself to creating cryptographically secure pseudo-random number generators (CSPRNGs). By seeding the sponge's internal state and then repeatedly squeezing it, a deterministic, unpredictable stream of random bits is produced. This is used in various deterministic key derivation functions and within the internal state management of some blockchain clients for entropy generation.

A key theoretical result for the sponge construction is its proven indifferentiability from a random oracle when the underlying permutation is assumed to be ideal. This proof, formalized in the Random Sponge model, provides strong security guarantees. It means a sponge hash can securely replace a random oracle in most cryptographic protocols, a critical foundation for its adoption in post-quantum and advanced protocol design.