Avalanche effect

As an avalanche effect is referred to in cryptography, the property of an algorithm to produce a completely different output at a minimum change in the input. This property is a formalization of the requirement that when a block cipher or cryptographic hash function of each bit of the output will depend on the entire input. Thus, the avalanche effect causes a good diffusion.

Strict Avalanche Criterion

The Strict Avalanche Criterion (SAC, engl. " Strict avalanche criterion ") is a formalization of the avalanche effect, which was introduced in 1985 by Webster and Tavares. This criterion requires that upon a change of input bits, each bit of the output with a probability of 50 % changes. The performance of SAC is now a standard requirement for cryptographic systems, it was, for example, fulfilled by all finalists in the AES competition.

Examples

The following examples are given cryptographic approaches and assessed their avalanche effect.

SHA-1

The SHA-1 checksum indicates a strong avalanche effect.

Demonstration by exemplary generation of two SHA-1 checksum (160 -bit) and their comparison:

Input: aaaaaaaaaaaaaaa   Edition: 7e13c003 a8256cd4 21,055,563 c5da6571 d50713c9   Input: aaaaaaaaaaaaaab   Edition: da5f09bc 23d63778 ebf88521 ac5df8aa 2f7298ce The number of different bits ( Hamming distance ): 89 Rate in this example: 55.6 % bit difference.

Both editions are significantly different despite mimimal different inputs.

AES

The AES encryption algorithm shows a strong avalanche effect.

Encryption of 128 -bit words by AES: In both cases, AES -256 is used in Electronic Code Book mode with the alternate key 010101 ... 01.

Input: aaaaaaaaaaaaaaaa   Edition: 0a561d9e 30bb09db 47f8e83d 443865cf   Input: aaaaaaaaaaaaaaab   Edition: c1e768d3 9177e9ef debee33a b92b4450 Number of different bits ( Hamming distance ): 62 Rate in this example: 48.4 % bit difference.

Both editions are significantly different despite mimimal different inputs.

Monoalphabetic substitution

An encryption by monoalphabetic substitution shows no avalanche effect.

In both cases, the following excerpt from a substitution table is used: a → r; b → z

Input: aaaaaaaaaaaaaaa   Edition: rrrrrrrrrrrrrrr   Input: aaaaaaaaaaaaaab   Edition: rrrrrrrrrrrrrrz Both editions are nearly identical.