The sponge construction, used in the context of cryptography, is a method of operation that creates a function that maps variable-length input to variable-length output using a fixed-length permutation (or transformation) and a padding rule. A sponge function is one such function. It accepts an element of Z_{2}, or a binary string of arbitrary length, as input and returns an element of Z^{n}_{2} or a binary string with the user-supplied value of n. A sponge function is a generalization of both stream ciphers with a fixed input length and hash functions, which have a fixed output length. It works by repeatedly applying the inner permutation on a finite state while entering input or retrieving output.
A broad range of symmetric cryptographic functions may be implemented using the sponge construction and its sibling design, known as the duplex construction. This covers message authentication code (MAC) calculation, authenticated encryption, key derivation, hashing, and resealable pseudo-random bit sequence creation. A fixed-length permutation is the fundamental cryptographic primitive that underlies all of this. These permutation-based modes offer compelling alternatives to the cryptographic technique now dominated by block ciphers. A permutation provides:
The benefits of not having a key schedule.
Not requiring an efficient inverse.
Having an elegant conceptual design.
The Sponge Construction
A function F with variable-length input and arbitrary output length can be built using the sponge construction, a straightforward iterative construction. It starts with a fixed-length permutation (or transformation) f that operates on a fixed number b of bits. Here, b is referred to as the breadth.
The sponge construction uses the state of b=r+c bits. The valuer and the capacity by the value c denote the bitrate.
A Sponge Function
The input string is first divided into blocks of r bits and padded with a reversible padding rule. The state's b bits are then set to zero, and the sponge is constructed in two stages:
The r-bit input blocks are XORed into the state's initial r bits during the absorption phase, with applications of the function f interspersed. The sponge architecture enters the squeezing phase after processing each input block.
The first r bits of the state are returned as output blocks during the squeezing phase, spaced apart by applications of the function f. The user has complete discretion over the number of output chunks.
The final c bits of the state are never emitted during the squeezing stage and are never directly impacted by the input blocks
Applications of Sponge Construction
There are theoretical and practical applications for sponge functions. A random sponge function in theoretical cryptanalysis is a sponge construction where f is a random permutation or transformation, as necessary. Compared to the widely used random oracle model, random sponge functions better capture the practical constraints of cryptographic primitives, particularly the finite internal state.
Practical cryptographic primitives may also be created by using sponge construction. For instance, NIST chose Keccak's 1600-bit state cryptographic sponge as the winner of the SHA-3 competition. The complex, multi-round permutation f that Keccak's creators created gives it power. The sponge architecture defines the algorithm in the RC4-redesign known as Spritz.
For additional examples, authenticated encryption with associated data (AEAD) and password hashing schemes can be created using a sponge function.
SHA-3
The newest member of the SHA family of standards, SHA-3 (Secure Hash Algorithm 3), was introduced by NIST on August 5, 2015. SHA-3 differs internally from the MD5-like structure of SHA-1 and SHA-2 while being a member of the same family of standards.
With RadioGatn as its foundation, Guido Bertoni, Joan Daemen, Michal Peeters, and Gilles Van Assche created the larger cryptographic primitive family Keccak, of which SHA-3 is a part. A cipher, an authenticated encryption system, a "tree" hashing technique enabling quicker hashing on some architectures, and the AEAD ciphers Keyak and Ketje are just a few of the other uses for Keccak that have not (yet) been defined by NIST, according to the function's inventors. Keccak is built on a cutting-edge strategy known as sponge Construction. Based on a comprehensive random function or random permutation, sponge construction enables any amount of data to be input (referred to as "absorbing") and output (referred to as "squeezing") while acting as a pseudo-random function with respect to all prior inputs. This results in a lot of versatility.
Design
The sponge construction used by SHA-3 allows data to be "absorbed" into the sponge and subsequently "squeezed" out. During the absorption stage, message blocks is XORed into a subset of the state, later completely changed using a permutation function f. In the "squeeze" phase, the state transformation function f is alternated with reading output blocks from the same subset of the state. The size of the state's writeable and readable portion is referred to as the "rate" (denoted r), while the size of the portion that is spared from input/output is referred to as the "capacity" (denoted c). The security of the system is determined by capacity. Half of the capacity is the most significant degree of protection.
The sponge construction for hash functions. Pi is input, and Zi is hashed output. The unused "capacity" c should be twice the desired resistance to collision or preimage attacks.
Given an input bit string of N, a padding function of the pad, a permutation function of f, a rate of r, and an output length of d, we have a capacity of c = b - r, and the sponge construction of Z = [f, pad, r](N, d), which produces a bit string.
The pad function is used to pad the input N, producing a padded bit string P with a length that may be divided by r.
Divide P into n successive r-bit pieces, P0,..., Pn-1.
Set the state S to a string of b zero bits at startup.
Incorporating the state's input: for each block Pi
Pi is extended at the end by a string of c zero bits, producing one of length b that is XORed with S.
The result is then subjected to the block permutation f producing a new state S.
while Z's length is shorter than d
add S's first r bits to Z's first bit.
Applying f to S will result in a new state S if the Z is still less than d bits long.
truncate Z to d bits
The vulnerability of SHA-2, SHA-1, MD5, and other hash functions based on the Merkle-Damgrd architecture to length extension attacks is eliminated by the internal state S's inclusion of c extra bits of data in addition to what is sent to Z.
In SHA-3, the state S is made up of a 5-5 array of words that are each w bits long (w = 64), giving a total of 1600 bits. Additionally, Keccak is specified for power-of-2 word sizes as tiny as 1 bit (total state of 25 bits). Small state sizes (from w = 8200 bits to w = 32800 bits) can be used to evaluate cryptanalytic attacks, while intermediate state sizes (from these values) can be applied in real-world, lightweight applications.
The leading d bits of state are the target hash for SHA3-224, SHA3-256, SHA3-384, and SHA3-512 instances since r is bigger than d. As a result, no further block permutations are required in the squeezing phase. On the other hand, the arbitrary output length feature of SHAKE128 and SHAKE256 is helpful in applications like the best asymmetric encryption padding.
Parameters and Security Levels for SHA-3
The term "collision security" describes the difficulty of finding a collision; if the collision security equals t, the attack will take roughly 2t steps. Similar in meaning, the term "preimage security" refers to attempts to locate either preimages or second preimages.
Hash Function
b
r
c
Collision security
Preimage security
SHA3-224
1600
1152
448
112
224
SHA3-256
1600
1088
512
128
256
SHA3-384
1600
832
768
192
384
SHA3-512
1600
576
1024
256
512
SHAKE128
1600
1344
256
min{d/2, 128}
min{d,128}
SHAKE256
1600
1088
512
min{d/2,256}
min{d,256}
Frequently Asked Questions
What is sponge construction?
The sponge construction, used in the context of cryptography, is a method of operation that creates a function that maps variable-length input to variable-length output using a fixed-length permutation (or transformation) and a padding rule.
What are some applications of sponge construction?
Authenticated encryption with associated data (AEAD) and password hashing schemes can both be created using a sponge construction.
Who are the designers of SHA-3?
Joan Daemen, DesGuido Bertoni, MichaÃ«l Peeters, and Gilles van Assche.
Why is SHA-3 developed?
In order to immediately replace SHA-2 in existing applications and greatly increase the resilience of NIST's whole hash algorithm toolbox, SHA-3 was developed.
Why is padding required in SHA-3?
Padding is necessary to ensure the message can be split into r-bit blocks equally.
Conclusion
This article discussed the sponge construction in hash functions and about SHA-3, its design, and security levels.