Avalanche effect

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The SHA1 hash function has good avalanche effect. When a single bit is changed the hash sum becomes completely different.

The avalanche effect (“landslide effect”) is a property of block ciphers and cryptographic hash functions 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 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[change | change source]

The origin of the name are landslides. A small rock can fall down, go along with some snow and make a destructive landslide. The rock was small, but could cause many destruction. The is the same as what this effects does. A small change in the input (the rock) should change the output (the landscape).

Strict avalanche criterion[change | change source]

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[change | change source]

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[change | change source]

References[change | change source]