Avalanche effect

The avalanche effect (“landslide effect”) is a property of block ciphers and cryptographic hash function algorithms. It is often desired in cryptography. The effect says that a lot of the output must change, even when the input changes only a little. In good block ciphers this means: A small change in the key or the plaintext should cause a strong change in the ciphertext.

This means that small changes can spread fast, when the algorithm uses iterations. Thus, every bit of the output depends on every bit of the input.

The term avalanche effect was first used by Horst Feistel (Feistel 1973). Later, the concept was identified by Shannon's property of confusion.

If a block cipher or cryptographic hash function does not satisfy the avalanche effect to a significant degree, then it has poor randomization. Thus, a cryptanalyst can make forecasts about the input, if given only the output. This may be sufficient to partially or completely break (crack) the algorithm.

It is one of the primary design objectives when people create a strong cipher or cryptographic hash function. They try to build a good avalanche effect in it. Mathematically this uses the butterfly effect. This is why most block ciphers are product ciphers. It is also why hash functions have large data blocks.

Name

The name comes from landslides. A small rock can fall down, go along with some snow and make a destructive landslide. The rock was small, but was able to cause a lot of destruction. This is the same as what this effect does. A small change in the input (the rock) should change the output (the landscape).

Strict avalanche criterion

The Strict Avalanche Criterion (SAC; a “strong landslide criterion”) is a property of boolean functions. It is of importance to cryptography. It is satisfied if all output bits change with a probability of 50 percent, if a single input bit is changed.

The SAC was built on the concepts of evolution completeness and avalanche. It was introduced by Webster and Tavares in 1985. Nowadays it is a requirement for every modern cryptographic system. It was e.g. satisfied by all finalists of the AES competition.

Bit independence criterion

The Bit independence criterion (BIC; a criterion independent from the bit) is a criterion. It goes: When a single input bit is changed (inverted), two output bits should change independently of each other. This applies to all bits.

It would e.g. not be satisfied, if the one output bit only changes, when the other output bit also changes. They might only change, because the input bit changed. Otherwise, the output bits would depend on each other.

Related pages

Confusion and diffusion

References

A. F. Webster and Stafford E. Tavares, "On the design of S-boxes", Advances in Cryptology - Crypto '85 (Lecture Notes in Computer Science), vol. 219, pp. 523–534, 1985.
Practical example Archived 2008-09-27 at the Wayback Machine (32 bits), taken from the extensive justification of the hash function HSH 11/13
Horst Feistel, "Cryptography and Computer Privacy." Scientific American, Vol. 228, No. 5, 1973. (JPEG format scanned) Archived 2003-10-13 at the Wayback Machine