Avalanche effect (cryptography)

In cryptography, the avalanche effect is the property of an algorithm to generate a completely different output with a minimal change in the input. This property is a formalization of the requirement that with a block cipher or cryptological hash function, every bit of the output should depend on the entire input. As a result, the avalanche effect causes good diffusion .

Strict Avalanche Criterion

The Strict Avalanche Criterion ( SAC , English "strict avalanche criterion ") is a formalization of the avalanche effect, which was introduced in 1985 by Webster and Tavares. This criterion requires that when an input bit changes, every bit of the output changes with a probability of 50%. Nowadays, compliance with the SAC is a standard requirement for cryptographic systems; for example, it was fulfilled by all finalists in the AES competition .

Examples

Examples of cryptographic approaches are given below and their avalanche effect is assessed.

SHA-1

The SHA-1 checksum algorithm shows a strong avalanche effect.

Demonstration through exemplary generation of two SHA-1 checksums (160 bits) and their comparison:

 Eingabe: aaaaaaaaaaaaaaa
 Ausgabe: 7e13c003 a8256cd4 21055563 c5da6571 d50713c9

 Eingabe: aaaaaaaaaaaaaab
 Ausgabe: da5f09bc 23d63778 ebf88521 ac5df8aa 2f7298ce

Number of different bits ( Hamming distance ): 89
Quota in this example: 55.6% bit difference.

Both editions are significantly different despite the slightly different entries.

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 alternating key 010101… 01.

 Eingabe: aaaaaaaaaaaaaaaa
 Ausgabe: 0a561d9e 30bb09db 47f8e83d 443865cf

 Eingabe: aaaaaaaaaaaaaaab
 Ausgabe: c1e768d3 9177e9ef debee33a b92b4450

Number of different bits (Hamming distance): 62
Quota in this example: 48.4% bit difference.

Both editions are significantly different despite the slightly different entries.

Monoalphabetic substitution

Encryption by monoalphabetic substitution shows no avalanche effect.

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

 Eingabe: aaaaaaaaaaaaaaa
 Ausgabe: rrrrrrrrrrrrrrr

 Eingabe: aaaaaaaaaaaaaab
 Ausgabe: rrrrrrrrrrrrrrz

Both editions are almost identical.

Individual evidence

↑ Wolfgang Ertel : Applied cryptography . Hanser Verlag , 2007, ISBN 9783446411951 , p. 66.
↑ Webster AF, Stafford E. Tavares: On the design of S-boxes . In: Advances in Cryptology - Crypto '85 (= Lecture Notes in Computer Science ). tape 218 . Springer, 1985, p. 523-534 ( PDF ).
↑ James Nechvatal et al .: Report on the Development of the Advanced Encryption Standard (AES) . NIST, 2000, p. 27 ( PDF ).

[1] Wolfgang Ertel : Applied cryptography . Hanser Verlag , 2007, ISBN 9783446411951 , p. 66.

[WT-2] Webster AF, Stafford E. Tavares: On the design of S-boxes . In: Advances in Cryptology - Crypto '85 (= Lecture Notes in Computer Science ). tape 218 . Springer, 1985, p. 523-534 ( PDF ).

[NIST-3] James Nechvatal et al .: Report on the Development of the Advanced Encryption Standard (AES) . NIST, 2000, p. 27 ( PDF ).