Bittester av kryptografiska hashfunktioner

Kryptografiska hashfunktioner (och krypton) har en egenskap kallas lavineffekten. Lavineffekten innebär att små förändringar av indata ger stora förändring på det genererade hashvärdet.

Hashvärden för SHA-256 när S ändras till T.

Hashvärden för SHA-256 när S ändras till T.

Men hur stor är lavineffekten, och finns det indata som ger olika stor lavineffekt? Jag bestämde mig för att testa på de hashfunktioner som finns i biblioteket OpenSSL (version 0.9.8r).

Jag har använt ordlistan från OpenWalls lösenordsknäckare John The Ripper och behandlat varje enskilt ord som ett sepatat meddelande. För varje meddelande har jag beräknat ett hashvärde. Sedan har jag inverterat den första biten i varje ord och genererat ett nytt hashvärde. Sedan räknar jag alla bitar som växlat mellan de två värdena. Sedan gör jag detta för varje hashfunktion och beräknar statistik. Men närmare 4 miljoner ord i listan blir det många hashfunktionsoperationer.

Så här ser resultatet från körningarna ut:

Statistics for md5
Digest size in bits: 128
Number of words tested: 3917116
Min number of bits changed: 36
Min percentage of digest changed: 28.1
Max number of bits changed: 93
Max percentage of digest changed: 72.7
Average number of bits changed 64.0

Statistics for sha1
Digest size in bits: 160
Number of words tested: 3917116
Min number of bits changed: 49
Min percentage of digest changed: 30.6
Max number of bits changed: 112
Max percentage of digest changed: 70.0
Average number of bits changed 80.0

Statistics for sha224
Digest size in bits: 224
Number of words tested: 3917116
Min number of bits changed: 72
Min percentage of digest changed: 32.1
Max number of bits changed: 150
Max percentage of digest changed: 67.0
Average number of bits changed 112.0
Expected average: 896.0

Statistics for sha256
Digest size in bits: 256
Number of words tested: 3917116
Min number of bits changed: 89
Min percentage of digest changed: 34.8
Max number of bits changed: 171
Max percentage of digest changed: 66.8
Average number of bits changed 128.0

Statistics for sha384
Digest size in bits: 384
Number of words tested: 3917116
Min number of bits changed: 144
Min percentage of digest changed: 37.5
Max number of bits changed: 243
Max percentage of digest changed: 63.3
Average number of bits changed 192.0

Statistics for sha512
Digest size in bits: 512
Number of words tested: 3917116
Min number of bits changed: 201
Min percentage of digest changed: 39.3
Max number of bits changed: 316
Max percentage of digest changed: 61.7
Average number of bits changed 256.0

För samtliga testade hashfunktioner växlar i medelfallet hälften av alla bitar. Däremot är variansen för de äldre funktionerna SHA-1 och speciellt MD5 större än för SHA-2-funktionerna. Den snävare variansen för SHA-2 gör att det blir svårare att genom exempelvis sidoattacker försöka säga något om vilka meddelanden hashfunktionen bearbetar. Ingen av funktionerna ger med något av testmeddelandena en förvånande liten eller stor bitväxlingar.

Nästa steg är att testa finalisterna i NISTS SHA-3-tävling samt även jämföra med hashfunktioner som inte kryptografiskt säkra. Då bör vi se större varians och kanske även lite krockar.

Kommentera

E-postadressen publiceras inte. Obligatoriska fält är märkta *

Följande HTML-taggar och attribut är tillåtna: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>