Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The Sponge Construction 
3.
Applications of Sponge Construction 
4.
SHA-3
5.
Design 
6.
Parameters and Security Levels for SHA-3 
7.
Frequently Asked Questions
7.1.
What is sponge construction?
7.2.
What are some applications of sponge construction?
7.3.
Who are the designers of SHA-3?
7.4.
Why is SHA-3 developed?
7.5.
Why is padding required in SHA-3?
8.
Conclusion
Last Updated: Mar 27, 2024

The Sponge Construction in Hash Functions

Introduction

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 Z2, or a binary string of arbitrary length, as input and returns an element of Zn2 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.

The sponge Construction in hash functions

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 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) that operates on a fixed number b of bits. Here, 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.

Sponge Function

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 

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. 

SHA-3

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. 

Spnge function

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. 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles interview experiences, and interview bundle for placement preparations. Read our blogs on aptitudecompetitive programminginterview questionsIT certifications, and data structures and algorithms for the best practice.

Live masterclass