Avalanche effect

Last updated

In cryptography, the avalanche effect is the desirable property of cryptographic algorithms, typically block ciphers [1] and cryptographic hash functions, wherein if an input is changed slightly (for example, flipping a single bit), the output changes significantly (e.g., half the output bits flip). In the case of high-quality block ciphers, such a small change in either the key or the plaintext should cause a drastic change in the ciphertext. The actual term was first used by Horst Feistel, [1] although the concept dates back to at least Shannon's diffusion .

Contents

The SHA-1 hash function exhibits good avalanche effect. When a single bit is changed the hash sum becomes completely different. Avalanche effect.svg
The SHA-1 hash function exhibits good avalanche effect. When a single bit is changed the hash sum becomes completely different.

If a block cipher or cryptographic hash function does not exhibit the avalanche effect to a significant degree, then it has poor randomization, and thus a cryptanalyst can make predictions about the input, being given only the output. This may be sufficient to partially or completely break the algorithm. Thus, the avalanche effect is a desirable condition from the point of view of the designer of the cryptographic algorithm or device. Failure to incorporate this characteristic leads to the hash function being exposed to attacks including collision attacks, length extension attacks, and preimage attacks. [2]

Constructing a cipher or hash to exhibit a substantial avalanche effect is one of the primary design objectives, and mathematically the construction takes advantage of the butterfly effect. [3] This is why most block ciphers are product ciphers. It is also why hash functions have large data blocks. Both of these features allow small changes to propagate rapidly through iterations of the algorithm, such that every bit of the output should depend on every bit of the input before the algorithm terminates.[ citation needed ]

Strict avalanche criterion

The strict avalanche criterion (SAC) is a formalization of the avalanche effect. It is satisfied if, whenever a single input bit is complemented, each of the output bits changes with a 50% probability. The SAC builds on the concepts of completeness and avalanche and was introduced by Webster and Tavares in 1985. [4]

Higher-order generalizations of SAC involve multiple input bits. Boolean functions which satisfy the highest order SAC are always bent functions, also called maximally nonlinear functions, also called "perfect nonlinear" functions. [5]

Bit independence criterion

The bit independence criterion (BIC) states that output bits j and k should change independently when any single input bit i is inverted, for all i, j and k. [6]

See also

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. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

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.

The Yarrow algorithm is a family of cryptographic pseudorandom number generators (CPRNG) devised by John Kelsey, Bruce Schneier, and Niels Ferguson and published in 1999. The Yarrow algorithm is explicitly unpatented, royalty-free, and open source; no license is required to use it. An improved design from Ferguson and Schneier, Fortuna, is described in their book, Practical Cryptography

In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Shannon's property of confusion. Mathematically, an S-box is a nonlinear vectorial Boolean function.

<span class="mw-page-title-main">CAST-128</span> Block cipher

In cryptography, CAST-128 is a symmetric-key block cipher used in a number of products, notably as the default cipher in some versions of GPG and PGP. It has also been approved for Government of Canada use by the Communications Security Establishment. The algorithm was created in 1996 by Carlisle Adams and Stafford Tavares using the CAST design procedure.

In cryptography, a Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel, who did pioneering research while working for IBM; it is also commonly known as a Feistel network. A large proportion of block ciphers use the scheme, including the US Data Encryption Standard, the Soviet/Russian GOST and the more recent Blowfish and Twofish ciphers. In a Feistel cipher, encryption and decryption are very similar operations, and both consist of iteratively running a function called a "round function" a fixed number of times.

In cryptography, Lucifer was the name given to several of the earliest civilian block ciphers, developed by Horst Feistel and his colleagues at IBM. Lucifer was a direct precursor to the Data Encryption Standard. One version, alternatively named DTD-1, saw commercial use in the 1970s for electronic banking.

<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, a random oracle is an oracle 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 that query is submitted.

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.

<span class="mw-page-title-main">LOKI97</span> Block cipher

In cryptography, LOKI97 is a block cipher which was a candidate in the Advanced Encryption Standard competition. It is a member of the LOKI family of ciphers, with earlier instances being LOKI89 and LOKI91. LOKI97 was designed by Lawrie Brown, assisted by Jennifer Seberry and Josef Pieprzyk.

<span class="mw-page-title-main">MacGuffin (cipher)</span> Block cipher

In cryptography, MacGuffin is a block cipher created in 1994 by Bruce Schneier and Matt Blaze at a Fast Software Encryption workshop. It was intended as a catalyst for analysis of a new cipher structure, known as Generalized Unbalanced Feistel Networks (GUFNs). The cryptanalysis proceeded very quickly, so quickly that the cipher was broken at the same workshop by Vincent Rijmen and Bart Preneel.

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

In cryptography, a pseudorandom permutation (PRP) is a function that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the family of all permutations on the function's domain) with practical effort.

In cryptography, CIPHERUNICORN-E is a block cipher created by NEC in 1998. It was among the cryptographic techniques recommended for Japanese government use by CRYPTREC in 2003. However, it has been dropped to "candidate" level by the CRYPTREC revision of 2013.

Selected Areas in Cryptography (SAC) is an international cryptography conference held every August in Canada since 1994. The first workshop was organized by Carlisle Adams, Henk Meijer, Stafford Tavares and Paul van Oorschot. Through 1999, SAC was hosted at either Queen's University or Carleton University, but starting in 2000, locations have ranged across Canada. SAC has featured research presentations on many cryptographic topics, with a traditional focus on the design and analysis of block ciphers. SAC is regarded as a high-quality venue for presenting cryptographic results, and is the only cryptography conference held annually in Canada. Since 2003, SAC has included an invited lecture called the Stafford Tavares Lecture, in honor of one of its original organizers and strongest supporters.

<span class="mw-page-title-main">Skein (hash function)</span> Cryptographic hash function

Skein is a cryptographic hash function and one of five finalists in the NIST hash function competition. Entered as a candidate to become the SHA-3 standard, the successor of SHA-1 and SHA-2, it ultimately lost to NIST hash candidate Keccak.

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

<span class="mw-page-title-main">Bent function</span> Special type of Boolean function

In the mathematical field of combinatorics, a bent function is a Boolean function that is maximally non-linear; it is as different as possible from the set of all linear and affine functions when measured by Hamming distance between truth tables. Concretely, this means the maximum correlation between the output of the function and a linear function is minimal. In addition, the derivatives of a bent function are balanced Boolean functions, so for any change in the input variables there is a 50 percent chance that the output value will change.

References

  1. 1 2 Feistel, Horst (1973). "Cryptography and Computer Privacy". Scientific American . 228 (5): 15–23. Bibcode:1973SciAm.228e..15F. doi:10.1038/scientificamerican0573-15.
  2. ↑ Upadhyay, D., Gaikwad, N., Zaman, M., & Sampalli, S. (2022). Investigating the Avalanche Effect of Various Cryptographically Secure Hash Functions and Hash-Based Applications. IEEE Access, 10, 112472–112486. https://doi.org/10.1109/ACCESS.2022.3215778
  3. ↑ Al-Kuwari, Saif; Davenport, James H.; Bradford, Russell J. (2011). Cryptographic Hash Functions: Recent Design Trends and Security Notions. Inscrypt '10.
  4. ↑ Webster, A. F.; Tavares, Stafford E. (1985). "On the design of S-boxes". Advances in Cryptology – Crypto '85. Lecture Notes in Computer Science. Vol. 218. New York, NY: Springer-Verlag New York, Inc. pp. 523–534. ISBN   0-387-16463-4.
  5. ↑ Adams, C. M.; Tavares, S. E. (January 1990). The Use of Bent Sequences to Achieve Higher-Order Strict Avalanche Criterion in S-box Design (Report). Technical Report TR 90-013. Queen's University. CiteSeerX   10.1.1.41.8374 .
  6. ↑ William, Stallings (2016). Cryptography and network security : principles and practice (Seventh ed.). Boston. p. 136. ISBN   9780134444284. OCLC   933863805.{{cite book}}: CS1 maint: location missing publisher (link)
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.