Sponge function

Last updated
The sponge construction for hash functions. Pi are blocks of the input string, Zi are hashed output blocks. SpongeConstruction.svg
The sponge construction for hash functions. Pi are blocks of the input string, Zi are hashed output blocks.

In cryptography, a sponge function or sponge construction is any of a class of algorithms with finite internal state that take an input bit stream of any length and produce an output bit stream of any desired length. Sponge functions have both theoretical and practical uses. They can be used to model or implement many cryptographic primitives, including cryptographic hashes, message authentication codes, mask generation functions, stream ciphers, pseudo-random number generators, and authenticated encryption. [1]

Contents

Construction

A sponge function is built from three components: [2]

S is divided into two sections: one of size r (the bitrate) and the remaining part of size c (the capacity). These sections are denoted R and C respectively.

f produces a pseudorandom permutation of the states from S.

P appends enough bits to the input string so that the length of the padded input is a whole multiple of the bitrate, r. This means the input is segmented into blocks of r bits.

Operation

The sponge function "absorbs" (in the sponge metaphor) all blocks of a padded input string as follows:

The sponge function output is now ready to be produced ("squeezed out") as follows:

If less than r bits remain to be output, then R will be truncated (only part of R will be output).

Another metaphor describes the state memory as an "entropy pool", with input "poured into" the pool, and the transformation function referred to as "stirring the entropy pool". [3]

Note that input bits are never XORed into the C portion of the state memory, nor are any bits of C ever output directly. The extent to which C is altered by the input depends entirely on the transformation function f. In hash applications, resistance to collision or preimage attacks depends on C, and its size (the "capacity" c) is typically twice the desired resistance level.

Duplex construction

It is also possible to absorb and squeeze in an alternating fashion. [1] This operation is called the duplex construction or duplexing. It can be the basis of a single pass authenticated encryption system.

Overwrite mode

It is possible to omit the XOR operations during absorption, while still maintaining the chosen security level. [1] In this mode, in the absorbing phase, the next block of the input overwrites the R part of the state. This allows keeping a smaller state between the steps. Since the R part will be overwritten anyway, it can be discarded in advance, only the C part must be kept.

Applications

Sponge functions have both theoretical and practical uses. In theoretical cryptanalysis, a random sponge function is a sponge construction where f is a random permutation or transformation, as appropriate. Random sponge functions capture more of the practical limitations of cryptographic primitives than does the widely used random oracle model, in particular the finite internal state. [4]

The sponge construction can also be used to build practical cryptographic primitives. For example, Keccak cryptographic sponge with a 1600-bit state has been selected by NIST as the winner in the SHA-3 competition. The strength of Keccak derives from the intricate, multi-round permutation f that its authors developed. [5] The RC4-redesign called Spritz refers to the sponge-construct to define the algorithm.

For other examples, a sponge function can be used to build authenticated encryption with associated data (AEAD), [3] as well as a password hashing schemes. [6]

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">HMAC</span> Computer communications hash algorithm

In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. An HMAC is a type of keyed hash function that can also be used in a key derivation scheme or a key stretching scheme.

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

<span class="mw-page-title-main">Substitution–permutation network</span> Cipher design construction

In cryptography, an SP-network, or substitution–permutation network (SPN), is a series of linked mathematical operations used in block cipher algorithms such as AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, and Square.

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In cryptography, confusion and diffusion are two properties of the operation of a secure cipher identified by Claude Shannon in his 1945 classified report A Mathematical Theory of Cryptography. These properties, when present, work together to thwart the application of statistics and other methods of cryptanalysis.

Authenticated Encryption (AE) is an encryption scheme which simultaneously assures the data confidentiality and authenticity. Examples of encryption modes that provide AE are GCM, CCM.

Panama is a cryptographic primitive which can be used both as a hash function and a stream cipher, but its hash function mode of operation has been broken and is not suitable for cryptographic use. Based on StepRightUp, it was designed by Joan Daemen and Craig Clapp and presented in the paper Fast Hashing and Stream Encryption with PANAMA on the Fast Software Encryption (FSE) conference 1998. The cipher has influenced several other designs, for example MUGI and SHA-3.

In cryptography, Galois/Counter Mode (GCM) is a mode of operation for symmetric-key cryptographic block ciphers which is widely adopted for its performance. GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources.

<span class="mw-page-title-main">RadioGatún</span> Cryptographic hash primitive

RadioGatún is a cryptographic hash primitive created by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. It was first publicly presented at the NIST Second Cryptographic Hash Workshop, held in Santa Barbara, California, on August 24–25, 2006, as part of the NIST hash function competition. The same team that developed RadioGatún went on to make considerable revisions to this cryptographic primitive, leading to the Keccak SHA-3 algorithm.

SHA-3 is the latest member of the Secure Hash Algorithm family of standards, released by NIST on August 5, 2015. Although part of the same series of standards, SHA-3 is internally different from the MD5-like structure of SHA-1 and SHA-2.

JH is a cryptographic hash function submitted to the NIST hash function competition by Hongjun Wu. Though chosen as one of the five finalists of the competition, in 2012 JH ultimately lost to NIST hash candidate Keccak. JH has a 1024-bit state, and works on 512-bit input blocks. Processing an input block consists of three steps:

  1. XOR the input block into the left half of the state.
  2. Apply a 42-round unkeyed permutation (encryption function) to the state. This consists of 42 repetitions of:
    1. Break the input into 256 4-bit blocks, and map each through one of two 4-bit S-boxes, the choice being made by a 256-bit round-dependent key schedule. Equivalently, combine each input block with a key bit, and map the result through a 5→4 bit S-box.
    2. Mix adjacent 4-bit blocks using a maximum distance separable code over GF(24).
    3. Permute 4-bit blocks so that they will be adjacent to different blocks in following rounds.
  3. XOR the input block into the right half of the state.

The following outline is provided as an overview of and topical guide to cryptography:

BLAKE is a cryptographic hash function based on Daniel J. Bernstein's ChaCha stream cipher, but a permuted copy of the input block, XORed with round constants, is added before each ChaCha round. Like SHA-2, there are two variants differing in the word size. ChaCha operates on a 4×4 array of words. BLAKE repeatedly combines an 8-word hash value with 16 message words, truncating the ChaCha result to obtain the next hash value. BLAKE-256 and BLAKE-224 use 32-bit words and produce digest sizes of 256 bits and 224 bits, respectively, while BLAKE-512 and BLAKE-384 use 64-bit words and produce digest sizes of 512 bits and 384 bits, respectively.

Gilles Van Assche is a Belgian cryptographer who co-designed the Keccak cryptographic hash, which was selected as the new SHA-3 hash by NIST in October 2012. The SHA-3 standard was released by NIST on August 5, 2015.

Lyra2 is a password hashing scheme (PHS) that can also work as a key derivation function (KDF). It received a special recognition during the Password Hashing Competition in July 2015, which was won by Argon2. Besides being used for its original purposes, it is also in the core of proof-of-work algorithms such as Lyra2REv2, adopted by Vertcoin, MonaCoin, among other cryptocurrencies Lyra2 was designed by Marcos A. Simplicio Jr., Leonardo C. Almeida, Ewerton R. Andrade, Paulo C. F. dos Santos, and Paulo S. L. M. Barreto from Escola Politécnica da Universidade de São Paulo. It is an improvement over Lyra, previously proposed by the same authors. Lyra2 preserves the security, efficiency and flexibility of its predecessor, including: (1) the ability to configure the desired amount of memory, processing time and parallelism to be used by the algorithm; and (2) the capacity of providing a high memory usage with a processing time similar to that obtained with scrypt. In addition, it brings the following improvements when compared to its predecessor:

Shabal is a cryptographic hash function submitted by the France-funded research project Saphir to NIST's international competition on hash functions.

Ascon is a family of lightweight authenticated ciphers that had been selected by US National Institute of Standards and Technology (NIST) for future standardization of the lightweight cryptography.

References

  1. 1 2 3 Bertoni, Guido; Daemen, Joan; Peeters, Michaël; van Assche, Giles. "Duplexing the Sponge: Single-Pass Authenticated Encryption and Other Applications" (PDF). Retrieved 2023-03-27.
  2. ↑ Bertoni, Guido; Daemen, Joan; Peeters, Michaël; van Assche, Giles. "The sponge and duplex constructions" . Retrieved 2023-03-27.
  3. 1 2 Rivest, Ron; Schuldt, Jacob (2014-10-27). "Spritz – a spongy RC4-like stream cipher and hash function" (PDF). Retrieved 2014-12-29.
  4. ↑ Bertoni, Guido; Daemen, Joan; Peeters, Michaël; van Assche, Giles. "On the Indifferentiability of the Sponge Construction" (PDF). Retrieved March 27, 2023.
  5. ↑ Boutin, Chad (2 October 2012). "NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition". NIST . Retrieved 4 October 2012.
  6. ↑ van Beirendonck, M.; Trudeau, L.; Giard, P.; Balatsoukas-Stimming, A. (2019-05-29). A Lyra2 FPGA Core for Lyra2REv2-Based Cryptocurrencies. IEEE International Symposium on Circuits and Systems (ISCAS). Sapporo, Japan: IEEE. pp. 1–5. arXiv: 1807.05764 . doi:10.1109/ISCAS.2019.8702498.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.