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

, the avalanche effect is the desirable property of cryptographic

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

s, typically block ciphers and

cryptographic hash function 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 re ...

s, 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 Key or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (map ...

or the

plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of comp ...

should cause a drastic change in the

ciphertext In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...

. The actual term was first used by

Horst Feistel Horst Feistel (January 30, 1915 – November 14, 1990) was a German-American cryptographer who worked on the design of ciphers at IBM, initiating research that culminated in the development of the Data Encryption Standard (DES) in the 1970s. The ...

, although the concept dates back to at least Shannon's ''

diffusion Diffusion is the net movement of anything (for example, atoms, ions, molecules, energy) generally from a region of higher concentration to a region of lower concentration. Diffusion is driven by a gradient in Gibbs free energy or chemical p ...

''.

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 Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...

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. 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. This is why most block ciphers are

product cipher In cryptography, a product cipher combines two or more transformations in a manner intending that the resulting cipher is more secure than the individual components to make it resistant to cryptanalysis.Handbook of Applied Cryptography by Alfred J. ...

s. 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 The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...

of the output should depend on every bit of the input before the algorithm terminates.

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. Higher-order generalizations of SAC involve multiple input bits. Boolean functions which satisfy the highest order SAC are always

bent function In the mathematics, mathematical field of combinatorics, a bent function is a special type of Boolean function which is maximally non-linear; it is as different as possible from the set of all linear map, linear and affine functions when measure ...

s, also called maximally nonlinear functions, also called "perfect nonlinear" functions.

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

References

{{Cryptography navbox , block , hash Symmetric-key cryptography

Strict avalanche criterion

Bit independence criterion

See also

References