โ† Wiki Index / Computation & Algorithms / Sponge Construction
๐Ÿ’ป Computation & Algorithms

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:

  1. 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.
  2. 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

PrimitiveWidth bBitrate rCapacity cUnderlying PermutationPrimary Application
SHA3-2561600 bits1088 bits512 bitsKeccak-p[1600, 24]Standard 256-bit Cryptographic Hashing
SHA3-5121600 bits576 bits1024 bitsKeccak-p[1600, 24]Standard 512-bit Cryptographic Hashing
SHAKE1281600 bits1344 bits256 bitsKeccak-p[1600, 24]Extendable-Output Function (XOF)
Ascon-128320 bits64 bits256 bitsAscon-Permutation [320, 12]Lightweight Authenticated Encryption

References

  1. Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2007). Sponge functions. Ecrypt Hash Workshop 2007.
  2. Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2008). On the indifferentiability of the sponge construction. Advances in Cryptology โ€” EUROCRYPT 2008, 181-197.
  3. National Institute of Standards and Technology. (2015). SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. Federal Information Processing Standards Publication 202.
  4. 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.
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision