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

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date for smaller files. It is recommended Blowfish should not be used to encrypt files larger than 4GB in size, Twofish should be used instead.

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 authentication 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.

<span class="mw-page-title-main">Block cipher mode of operation</span> Cryptography algorithm

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">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 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.

Disk encryption is a special case of data at rest protection when the storage medium is a sector-addressable device. This article presents cryptographic aspects of the problem. For an overview, see disk encryption. For discussion of different software packages and hardware devices devoted to this problem, see disk encryption software and disk encryption hardware.

<span class="mw-page-title-main">One-way compression function</span> Cryptographic primitive

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly or approximately to the original data.

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.

The NIST hash function competition was an open competition held by the US National Institute of Standards and Technology (NIST) to develop a new hash function called SHA-3 to complement the older SHA-1 and SHA-2. The competition was formally announced in the Federal Register on November 2, 2007. "NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process for the Advanced Encryption Standard (AES)." The competition ended on October 2, 2012, when NIST announced that Keccak would be the new SHA-3 hash 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.

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 function as a key derivation function (KDF). It gained recognition during the Password Hashing Competition in July 2015, which was won by Argon2. It is also used in proof-of-work algorithms such as Lyra2REv2, adopted by Vertcoin and MonaCoin, among other cryptocurrencies.

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.