In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
, a sponge function or sponge construction is any of a class of
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s with finite
internal state that take an input
bit stream
A bitstream (or bit stream), also known as binary sequence, is a sequence of bits.
A bytestream is a sequence of bytes. Typically, each byte is an 8-bit quantity, and so the term octet stream is sometimes used interchangeably. An octet may ...
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 primitive
Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build cryptographic protocols for computer security systems. These routines include, but are not limited to, one-way hash functions an ...
s, including
cryptographic hash
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output ...
es,
message authentication codes,
mask generation functions,
stream cipher
stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
s,
pseudo-random number generators, and
authenticated encryption
Authenticated Encryption (AE) and Authenticated Encryption with Associated Data (AEAD) are forms of encryption which simultaneously assure the confidentiality and authenticity of data.
Programming interface
A typical programming interface for ...
.
Construction
A sponge function is built from three components:
* a state memory, ''S'', containing ''b'' bits,
* a function
* a padding function ''P''
''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
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process.
Background
The generation of random numbers has many uses, such as for random ...
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
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
Sponges, the members of the phylum Porifera (; meaning 'pore bearer'), are a basal animal clade as a sister of the diploblasts. They are multicellular organisms that have bodies full of pores and channels allowing water to circulate throug ...
metaphor) all blocks of a padded input string as follows:
*''S'' is initialized to zero
*for each ''r''-bit block ''B'' of ''P''(string)
**''R'' is replaced with ''R'' XOR ''B'' (using bitwise
XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , ...
)
**''S'' is replaced by ''f''(''S'')
The sponge function output is now ready to be produced ("squeezed out") as follows:
*repeat
**output the ''R'' portion of ''S''
**''S'' is replaced by ''f''(''S'') unless output is full
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
In computing, a hardware random number generator (HRNG) or true random number generator (TRNG) is a device that random number generation, generates random numbers from a physical process, rather than by means of an algorithm. Such devices are o ...
", with input "poured into" the pool, and the transformation function referred to as "stirring the entropy pool".
[
]
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
In physics, a collision is any event in which two or more bodies exert forces on each other in a relatively short time. Although the most common use of the word ''collision'' refers to incidents in which two or more objects collide with great fo ...
or
preimage attack
In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage (set of possible inputs).
In the context of attack, the ...
s 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.
This operation is called the duplex construction or duplexing. It can be the basis of a single pass authenticated encryption system.
*The state ''S'' is initialized to zero
*''R'' is XORed with the first ''r''-bit block of the input
*''S'' is replaced by ''f''(''S'')
*''R'' is now the first ''r'' bits of the output.
*''R'' is XORed with the next ''r''-bit block of the input
*''S'' is replaced by ''f''(''S'')
*''R'' is now the next ''r'' bits of the output.
*…
Overwrite mode
It is possible to omit the XOR operations during absorption, while still maintaining the chosen
security level
In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of "bits of security" (also security strength ...
.
[ 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
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time tha ...
model, in particular the finite internal state.
The sponge construction can also be used to build practical cryptographic primitives. For example, Keccak
SHA-3 (Secure Hash Algorithm 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 stru ...
cryptographic sponge with a 1600-bit state has been selected by NIST
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sc ...
as the winner in the SHA-3 competition. The strength of Keccak derives from the intricate, multi-round permutation ''f'' that its authors developed. 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
Authenticated Encryption (AE) and Authenticated Encryption with Associated Data (AEAD) are forms of encryption which simultaneously assure the confidentiality and authenticity of data.
Programming interface
A typical programming interface for ...
with associated data (AEAD),[ as well as a password hashing schemes.]
References
{{reflist
Cryptographic hash functions
Theory of cryptography