Snefru

Snefru er en kryptografisk hashfunktion foreslået af Ralph Merkle . (Selve navnet Snefru, der fortsætter traditionen med blokcifrene Khufu og Khafre , også udviklet af Ralph Merkle, er navnet på en egyptisk farao ). Snefru-funktionen konverterer beskeder af vilkårlig længde til en hash af længde (normalt eller ). $m$ $m=128$ $m=256$

Beskrivelse af hashing-algoritmen

Indgangsmeddelelsen er opdelt i blokke med bitlængde. Grundlaget for algoritmen er en funktion , der tager en bitværdi som input og beregner en bitværdi. Hver ny blok i meddelelsen sammenkædes med hashen beregnet for den forrige blok og føres til funktionens input . Den første blok er sammenkædet med en streng af nuller. Den sidste bloks hash sammenkædes med den binære repræsentation af meddelelseslængden ( MD - amplification ), og den resulterende sammenkædning hashes en sidste gang. $512-m$ $H$ $512$ $m$ $H$

Funktionen er baseret på en (reversibel) blokchifferfunktion, der accepterer og beregner - bitværdier. returnerer XOR - en kombination af de første bits af funktionens input og de sidste bits af funktionens output . Funktionen blander inputdataene i flere trin. Hvert trin består af 64 runder. I én runde tages et meddelelsesord, og den mindst signifikante byte af det ord påføres en blok, hvis output også er et ord. Dernæst udføres XOR-operationen af det modtagne ord med to naboord i meddelelsen. Således ændres to tilstødende ord i meddelelsen i én runde ved at bruge en byte af et ord. I slutningen af runden blandes bytene af det brugte ord, så næste gang en anden byte kommer til input af blokken (der forekommer et antal cykliske skift med 8, 16 eller 24 bit). Da der er 64 runder og 16 ord, bruges hvert ord fire gange, derfor bruges hver byte af meddelelsen som en blokinput. Konstruktionen af blokken svarer til konstruktionen i Khafre- algoritmen . $H$ $E$ $512$ $H$ $m$ $E$ $m$ $E$ $E$ $S$ $S$ $S$ $S$

Hvis antallet af trin i funktionen er ( runder), så kaldes Snefru-funktionen to-pas, hvis antallet af skridt er ( runder), så er Snefru tre-pas, og så videre. $E$ $2$ $128$ $3$ $192$

Kryptanalyse Snefru

I marts 1990 blev der givet en belønning på $1.000 til den første person, der knækkede to-pass Snefru ved at finde to beskeder med den samme hash-kode (det vil sige for at vise, at Snefru ikke er modstandsdygtig over for type 2 kollisioner ). En lignende dusør blev senere annonceret for hacking af fire-pass varianten af Snefru.

Ved hjælp af differentialanalyseværktøjer viste Eli Biham og Adi Shamir , at to-pass Snefru-funktionen (med en smule hash) ikke er modstandsdygtig over for type 1 og type 2 kollisioner . $128$

Beskrivelse af angrebet

Standardangrebet på hash-funktioner er baseret på "fødselsdage" -paradokset . Hvis vi hash ( , når ) forskellige beskeder, så vil det med stor sandsynlighed være muligt at finde et par med den samme hash. Et sådant angreb kan anvendes på enhver hashfunktion, uanset dens implementering. $2^{m/2}$ $2^{64}$ $m=128$

For Snefru udviklede Biham og Shamir en differentiel kryptoanalysemetode, der ikke afhænger af valget af blokke og endda kan bruges, når blokkene ikke er kendt af kryptoanalytikeren . $S$ $S$

Med en hash- længde er længden af de blokke, som inputmeddelelsen er opdelt i, . I dette angreb blev der brugt en algoritme, der søger efter to inputværdier af funktionen ( - bitværdier), der kun adskiller sig i de første bits, der er dannet fra blokke af inputmeddelelsen, men som samtidig har den samme hash. $m=128$ $512-m=384$ $H$ $512$ $384$

Algoritme trin:

En vilkårlig blok med bitlængde er valgt. En streng af nuller føjes til den (eller en hvilken som helst anden bitvektor, for eksempel hashen fra den foregående blok), og danner en bitinputblok for funktionen . Beregnet . $384$ $128$ $512$ $H$ $H$
En anden inputblok oprettes til funktionen ved at ændre en byte i og ord i den første blok. I dette tilfælde er det den del, der er indeholdt i de første bits, der ændres, den tildelte streng ændres ikke. De foranderlige bytes i og ord er dem, der vil blive brugt som blokinputværdier henholdsvis i og runder. Beregnet . $H$ $otte$ $9$ $384$ $otte$ $9$ $S$ $56$ $57$ $H$
Funktionsværdierne fra inputblokkene opnået i trin 1) og 2) sammenlignes. Med sandsynlighed vil et par med samme hash blive fundet. $H$ $2^{-40}$

Ved at beregne en funktion af cirka par af blokke kan man således finde en type 2-kollision for Snefru. $H$ $2^{41}$

Forklaring af angrebsalgoritmen

Da ændringerne, der anvendes i trinnet , kun påvirker de bytes, der bruges i og -runderne, vil værdierne af blokkene efter runderne nummereret < i og -trinene være de samme. $2$ $56$ $57$ $56$ $en$ $2$

I den -te runde bruges byten fra det -te ord til at ændre -th og -th ord. En byte føres til blokkens input, hvis output er et ord. Dernæst udføres XOR-operationen med det -te og -te ord. Hvis denne byte ændres (i trin ), samt byten af det -th ord, som bruges som input til blokken i -th runde, med sandsynlighed for, at efter at have udført XOR-operationen, byten i -th ord vil være det samme som den samme byte i blokken i trin efter -og runder. Derefter, ved at levere denne byte i -th runde til input af blokken, vil vi få den samme værdi ved output som i -th runde, udført på blokken fra trin . Derfor vil det -te ord være det samme efter runden for begge trin. Det -te ord efter runden, -te ord efter runden, ..., -te ord efter runden, -te ord efter runden, ..., -te ord efter runden vil også være det samme , da input af blokken for begge trin i disse runder er det samme og det samme. $56$ $otte$ $7$ $9$ $S$ $7$ $9$ $2$ $9$ $S$ $57$ $1/256$ $9$ $en$ $56$ $57$ $S$ $57$ $en$ $ti$ $57$ $elleve$ $58$ $12$ $59$ $16$ $64$ $en$ $65$ $6$ $69$ $S$

$7$ -th ord er anderledes for trin allerede efter -th runde. Derfor vil det ved -th runde få betydningen af -th og -th ord til at blive forskellige for de to stadier. Det samme vil ske i th runde for ordene og . Og igen, med sandsynlighed , vil byten i det -te ord, der vil blive brugt som blokinput i -th runde, være den samme for trin og . Så -e, ..., -e, -e, ..., -e ordene vil være de samme. Ændringer vil begynde, når det -th ord bruges i -th runde. $56$ $71$ $6$ $otte$ $72$ $7$ $9$ $1/256$ $9$ $S$ $73$ $en$ $2$ $ti$ $16$ $en$ $5$ $6$ $86$

Så hvis efter , , , og -th runder byten i det -th ord, som vil blive brugt som input for blokken i de følgende runder, er den samme for begge trin, så vil ordene , ... , være den samme efter hele runder . Sandsynligheden for denne begivenhed . Da værdien af XOR-operationen fra de første 4 ord i funktionens inputblok og de første 4 ord i funktionens outputblok tages som blokkens hash , vil hasherne beregnet i begge trin være de samme . $56$ $72$ $88$ $104$ $120$ $9$ $S$ $128$ $ti$ $elleve$ $16$ $(1/256)^{5}=2^{-40}$ $E$ $E$

Sammenligning af angrebet med kendte metoder til kryptoanalyse

Metoden blev også anvendt på tre-pass og fire-pass Snefru-funktionen, hvilket viser bedre resultater sammenlignet med fødselsdagsmetoden.

Sammenligning af angrebet af Shamir og Biham med angrebet af "fødselsdage"

Antal afleveringer af Snefru-funktionen	hash længde, $m$	Angrebssvær	Fødselsdagsmetoden
2	128 - 192	$2^{12.5}$	$2^{64}$ — $2^{{96}}$
2	224	$2^{12.5}$	$2^{112}$
3	128 - 192	$2^{28.5}$	$2^{64}$ — $2^{{96}}$
3	224	$2^{{33}}$	$2^{112}$
fire	128 - 192	$2^{44.5}$	$2^{64}$ — $2^{{96}}$
fire	224	$2^{81}$	$2^{112}$

Ved at bruge dette angreb kan du finde mange par, der har samme hash, og derudover finde flere beskeder, hvis hash er lig med hashen af denne besked (kollision af 1. slags). Antallet af operationer, der kræves for at finde en kollision af 1. slags i dette angreb, er mindre end i "brute force"-metoden .

Sammenligning af Shamir og Bihams angreb med "brute force"-metoden

Antal afleveringer af Snefru-funktionen	hash længde, $m$	Angrebssvær	brute force metode
2	128 - 224	$2^{24}$	$2^{128}$ — $2^{224}$
3	128 - 224	$2^{56}$	$2^{128}$ — $2^{224}$
fire	128 - 192	$2^{88}$	$2^{128}$ — $2^{192}$

Noter

På nuværende tidspunkt råder Merkle til at bruge Snefru-funktionen med mindst otte gennemløb. Men med så mange gennemløb sænkes beregningen af Snefru-funktionen betydeligt sammenlignet med MD5- eller SHA- funktionerne .

Litteratur

Eli Biham, Adi Shamir . Differentiel kryptoanalyse af Snefru, Khafre, REDOC-II, LOKI og Lucifer (Udvidet abstrakt).
Bruce Schneier. Anvendt kryptografi. Protokoller, algoritmer, kildetekster i C-sprog. - M. : TRIUMPH, 2003. - 816 s. - ISBN 5-89392-055-4 .

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE