Snefru

Snefru je kryptografická hashovací funkce navržená Ralphem Merklem . (Samotné jméno Snefru, navazující na tradici blokových šifer Khufu a Khafre , rovněž vyvinuté Ralphem Merklem, je jméno egyptského faraona ). Funkce Snefru převádí zprávy libovolné délky na hash délky (obvykle nebo ). $m$ $m=128$ $m=256$

Popis hashovacího algoritmu

Vstupní zpráva je rozdělena do bloků bitové délky. Základem algoritmu je funkce , která bere jako vstup bitovou hodnotu a vypočítává bitovou hodnotu. Každý nový blok zprávy je zřetězen s hash vypočítaným pro předchozí blok a je přiváděn na vstup funkce . První blok je zřetězen řetězcem nul. Hash posledního bloku je zřetězen s binární reprezentací délky zprávy ( MD - amplifikace ) a výsledné zřetězení je hašováno naposledy. $512-m$ $H$ $512$ $m$ $H$

Funkce je založena na funkci (reverzibilní) blokové šifry , která přijímá a počítá - bitové hodnoty. vrací XOR – kombinaci prvních bitů vstupu funkce a posledních bitů výstupu funkce . Funkce míchá vstupní data v několika krocích. Každý krok se skládá z 64 kol. V jednom kole se vezme slovo zprávy a nejméně významný bajt tohoto slova se aplikuje na blok, jehož výstupem je také slovo. Dále se provede operace XOR přijatého slova se dvěma sousedními slovy ve zprávě. V jednom kole se tedy pomocí jednoho bajtu slova změní dvě sousední slova ve zprávě. Na konci kola se bajty použitého slova smíchají tak, aby se příště na vstup bloku dostal další bajt (dochází k řadě cyklických posunů o 8, 16 nebo 24 bitů). Protože existuje 64 kol a 16 slov, každé slovo je použito čtyřikrát, proto je každý bajt zprávy použit jako vstup bloku. Konstrukce bloku je podobná konstrukci v algoritmu Khafre . $H$ $E$ $512$ $H$ $m$ $E$ $m$ $E$ $E$ $S$ $S$ $S$ $S$

Je-li počet kroků ve funkci ( kol), pak se funkce Snefru nazývá dvouprůchodová, je-li počet kroků ( kol ), pak je Snefru tříprůchodová atd. $E$ $2$ $128$ $3$ $192$

Kryptoanalýza Snefru

V březnu 1990 byla udělena odměna 1 000 $ tomu, kdo jako první prolomil dvouprůchodový Snefru tím, že našel dvě zprávy se stejným hash kódem (to znamená, že ukázal, že Snefru není odolný vůči kolizím typu 2 ). Podobná odměna byla později oznámena za hacknutí čtyřprůchodové varianty Snefru.

Eli Biham a Adi Shamir pomocí nástrojů diferenciální analýzy ukázali , že dvouprůchodová funkce Snefru (s bitovým hashem) není odolná vůči kolizím typu 1 a typu 2 . $128$

Popis útoku

Standardní útok na hashovací funkce je založen na paradoxu „narozenin“ . Pokud hashujeme ( , when ) různé zprávy, pak s vysokou pravděpodobností bude možné najít pár se stejným hashem. Takový útok je použitelný pro jakoukoli hashovací funkci bez ohledu na její implementaci. $2^{m/2}$ $2^{64}$ $m=128$

Pro Snefru Biham a Shamir vyvinuli metodu diferenciální kryptoanalýzy, která nezávisí na výběru bloků a může být dokonce použita, když kryptoanalytik bloky nezná . $S$ $S$

U hash length je délka bloků, do kterých je vstupní zpráva rozdělena, . V tomto útoku byl použit algoritmus, který hledá dvě vstupní hodnoty funkce ( - bit values), které se liší pouze v prvních bitech vytvořených z bloků vstupní zprávy, ale zároveň mají stejný hash. $m=128$ $512-m=384$ $H$ $512$ $384$

Kroky algoritmu:

Je vybrán libovolný blok bitové délky. Je k němu přidán řetězec nul (nebo jakýkoli jiný bitový vektor, například hash předchozího bloku), čímž se vytvoří bitový vstupní blok pro funkci . Vypočteno . $384$ $128$ $512$ $H$ $H$
Pro funkci se vytvoří druhý vstupní blok změnou jednoho bajtu a slov prvního bloku. V tomto případě se mění část obsažená v prvních bitech, přiřazený řetězec se nemění. Proměnlivé bajty a slova jsou ty, které budou použity jako vstupní hodnoty bloku v a zaokrouhlení. Vypočteno . $H$ $osm$ $9$ $384$ $osm$ $9$ $S$ $56$ $57$ $H$
Porovnají se funkční hodnoty ze vstupních bloků získaných v krocích 1) a 2). S pravděpodobností bude nalezen pár se stejným hashem. $H$ $2^{-40}$

Výpočtem funkce přibližně párů bloků lze tedy najít kolizi typu 2 pro Snefru. $H$ $2^{41}$

Vysvětlení algoritmu útoku

Vzhledem k tomu, že změny použité v kroku ovlivňují pouze bajty použité v kolech a , budou hodnoty bloků po kolech očíslovaných < v krocích a stejné. $2$ $56$ $57$ $56$ $jeden$ $2$

V -tém kole se bajt z -tého slova použije ke změně -tého a -tého slova. Na vstup bloku je přiveden bajt, jehož výstupem je slovo. Dále se provede operace XOR s -tým a -tým slovem. Pokud se tento bajt změní (v kroku ), stejně jako bajt -tého slova, které je použito jako vstup bloku v -tém kole, s pravděpodobností, že po provedení operace XOR se bajt v -té slovo bude stejné jako stejný bajt v bloku v kroku po -a zaokrouhlí. Poté, když tento bajt dodáme v -tém kole na vstup bloku, dostaneme na výstupu stejnou hodnotu jako v -tém kole, provedené na bloku z kroku . Proto -té slovo bude po kole stejné pro oba kroky. -té slovo po kole, -té slovo po kole, ..., -té slovo po kole, -té slovo po kole, ..., -té slovo po kole bude také stejné , protože vstup bloku pro oba kroky v těchto kolech je stejný a stejný. $56$ $osm$ $7$ $9$ $S$ $7$ $9$ $2$ $9$ $S$ $57$ $1/256$ $9$ $jeden$ $56$ $57$ $S$ $57$ $jeden$ $deset$ $57$ $jedenáct$ $58$ $12$ $59$ $16$ $64$ $jeden$ $65$ $6$ $69$ $S$

$7$ -té slovo je jiné pro kroky již po -tém kole. Proto v -tém kole způsobí, že se významy -tého a -tého slova pro obě fáze budou lišit. Totéž se stane v tém kole pro slova a . A opět, s pravděpodobností , bajt v -tém slově, který bude použit jako vstup bloku v -tém kole, bude stejný pro kroky a . Takže slova -e, ..., -e, -e, ..., -e budou stejná. Změny začnou, když se v -tém kole použije -té slovo . $56$ $71$ $6$ $osm$ $72$ $7$ $9$ $1/256$ $9$ $S$ $73$ $jeden$ $2$ $deset$ $16$ $jeden$ $5$ $6$ $86$

Pokud tedy po , , , a -th zaokrouhlí bajt v -tém slově, který bude použit jako vstup pro blok v následujících kolech, stejný pro oba kroky, pak budou slova , , … , být stejný po celých kolech . Pravděpodobnost této události . Protože hodnota operace XOR z prvních 4 slov vstupního bloku funkce a prvních 4 slov výstupního bloku funkce je brána jako hash bloku , hash vypočítaný v obou krocích bude stejný. . $56$ $72$ $88$ $104$ $120$ $9$ $S$ $128$ $deset$ $jedenáct$ $16$ $(1/256)^{5}=2^{-40}$ $E$ $E$

Srovnání útoku se známými metodami kryptoanalýzy

Metoda byla také aplikována na tříprůchodovou a čtyřprůchodovou funkci Snefru, přičemž vykazovala lepší výsledky ve srovnání s narozeninovou metodou.

Srovnání útoku Shamira a Bihama s útokem "narozenin"

Počet průchodů funkce Snefru	hash délka, $m$	Obtížnost útoku	Narozeninová metoda
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}$
čtyři	128–192	$2^{44.5}$	$2^{64}$ — $2^{{96}}$
čtyři	224	$2^{81}$	$2^{112}$

Pomocí tohoto útoku můžete najít mnoho dvojic, které mají stejný hash, a navíc najít několik zpráv, jejichž hash je roven hashu této zprávy (kolize 1. druhu). Počet operací potřebných k nalezení kolize 1. druhu při tomto útoku je menší než u metody „hrubé síly“ .

Srovnání útoku Shamira a Bihama s metodou „hrubé síly“.

Počet průchodů funkce Snefru	hash délka, $m$	Obtížnost útoku	metoda hrubé síly
2	128–224	$2^{24}$	$2^{128}$ — $2^{224}$
3	128–224	$2^{56}$	$2^{128}$ — $2^{224}$
čtyři	128–192	$2^{88}$	$2^{128}$ — $2^{192}$

Poznámky

V tuto chvíli Merkle doporučuje používat funkci Snefru s alespoň osmi průchody. S tolika průchody se však výpočet funkce Snefru výrazně zpomaluje ve srovnání s funkcemi MD5 nebo SHA .

Literatura

Eli Biham, Adi Shamir . Diferenciální kryptoanalýza Snefru, Khafre, REDOC-II, LOKI a Lucifer (rozšířený abstrakt).
Bruce Schneier. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojové texty v jazyce C. - M. : TRIUMPH, 2003. - 816 s. - ISBN 5-89392-055-4 .

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga 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 Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA