Investigating Algorithms - jonelo/jacksum GitHub Wiki

Avalanche Effect

What is the Avalance Effect?

In cryptography, the avalanche effect is the desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions, wherein if an input is changed slightly (for example, flipping a single bit), the output changes significantly (e.g., half the output bits flip). See also https://en.wikipedia.org/wiki/Avalanche_effect

Printing the Avalanche Effect for an Algorithm

Let's print the avalanche effect for sha256.

> jacksum -a sha256 --info
...

  Avalanche effect:
    input length in bytes:                9
    input length in bits:                 72
    hash calculations:                    144
    input [hex]:                          313233343536373839
    input [bin]:                          001100010011001000110011001101000011010100110110001101110011100000111001
    avalanche min effect:                 42.19 %
    avalanche avg effect:                 50.04 %
    avalanche max effect:                 57.03 %
...

The default input is '123456789', and if we flip each bit we can see that the avalance average effect is 50.04 % for that input. If we compare that to let's say CRC32 ...

> jacksum -a crc32 --info
...
  Avalanche effect:
    input length in bytes:                9
    input length in bits:                 72
    hash calculations:                    73
    input [hex]:                          313233343536373839
    input [bin]:                          001100010011001000110011001101000011010100110110001101110011100000111001
    avalanche min effect:                 34.38 %
    avalanche avg effect:                 45.53 %
    avalanche max effect:                 62.50 %
...

... the avalanche avg. effect decreases to 45.53 %, because the CRC32 is a CRC, and not a cryptographic hash function. The effect decreases further if we use a very short checksum such as bsd_sum:

> jacksum -a bsd_sum --info
...
  Avalanche effect:
    input length in bytes:                43
    input length in bits:                 344
    hash calculations:                    345
    input [hex]:                          54686520717569636b2062726f776e20666f78206a756d7073206f76657220746865206c617a7920646f67
    input [bin]:                          0101010001101000011001010010000001110001011101010110100101100011011010110010000001100010011100...
    avalanche min effect:                 6.25 %
    avalanche avg effect:                 10.83 %
    avalanche max effect:                 25.00 %
...

Calculating the Avalanche Effect with a Different Input

With a customized string

> jacksum -a sha256 -q "txt:The quick brown fox jumps over the lazy dog" --info
...
  Avalanche effect:
    input length in bytes:                43
    input length in bits:                 344
    hash calculations:                    345
    input [hex]:                          54686520717569636b2062726f776e20666f78206a756d7073206f76657220746865206c617a7920646f67
    input [bin]:                          0101010001101000011001010010000001110001011101010110100101100011011010110010000001100010011100100110111101110111...
    avalanche min effect:                 39.84 %
    avalanche avg effect:                 49.85 %
    avalanche max effect:                 57.81 %
...

The avalanche avg effect is still almost 50 % for sha256.

With a File input

A larger input, such as the gpl-3.0.txt license file reveals that sha256 is very robust with respect to the avalanche effect.

> jackum -a sha256 -q file:gpl-3.0.txt --info
...
  Avalanche effect:
    input length in bytes:                35149
    input length in bits:                 281192
    hash calculations:                    281193
    input [hex]:                          2020202020202020202020202020202020202020474e552047454e45...
...
    avalanche min effect:                 33.20 %
    avalanche avg effect:                 50.00 %
    avalanche max effect:                 63.28 %
...

Investigate CRC polys

Go to https://github.com/jonelo/jacksum/wiki/Working-with-CRCs#investigate_crc_parameters