Snefru

Snefru on Ralph Merklen ehdottama kryptografinen hajautusfunktio . (Itse nimi Snefru, joka jatkaa myös Ralph Merklen kehittämää lohkosalausten Khufu ja Khafre perinnettä , on egyptiläisen faaraon nimi ). Snefru-funktio muuntaa mielivaltaisen pituiset viestit pituudeksi (yleensä tai ). $m$ $m=128$ $m=256$

Hajautusalgoritmin kuvaus

Syöteviesti on jaettu bittipituisiin lohkoihin. Algoritmin perusta on funktio , joka ottaa bittiarvon syötteeksi ja laskee bittiarvon. Viestin jokainen uusi lohko ketjutetaan edelliselle lohkolle lasketun hajautusarvon kanssa ja syötetään funktion tuloon . Ensimmäinen lohko ketjutetaan nollien merkkijonoon. Viimeisen lohkon hash ketjutetaan viestin pituuden binääriesitykseen ( MD - amplification ), ja tuloksena oleva ketjutus tiivistetään viimeisen kerran. $512-m$ $H$ $512$ $m$ $H$

Toiminto perustuu (käännettävään) lohkosalaukseen , joka hyväksyy ja laskee - bittiarvoja. palauttaa XOR - funktion tulon ensimmäisten bittien ja funktion lähdön viimeisten bittien yhdistelmän . Toiminto sekoittaa syöttötiedot useassa vaiheessa. Jokainen vaihe koostuu 64 kierrosta. Yhdellä kierroksella otetaan sanomasana ja sen vähiten merkitsevä tavu käytetään lohkoon, jonka lähtö on myös sana. Seuraavaksi suoritetaan XOR-operaatio vastaanotetulle sanalle kahden vierekkäisen sanoman kanssa. Siten yhdellä kierroksella, käyttämällä yhtä sanatavua, kaksi vierekkäistä sanaa muutetaan sanomassa. Kierroksen lopussa käytetyn sanan tavut sekoitetaan niin, että seuraavan kerran toinen tavu pääsee lohkon sisäänmenoon ( sykleisiä siirtymiä tapahtuu 8, 16 tai 24 bitin verran). Koska kierroksia on 64 ja sanaa 16, kutakin sanaa käytetään neljä kertaa, joten jokaista viestin tavua käytetään lohkosyötteenä. Lohkon rakenne on samanlainen kuin Khafren algoritmissa . $H$ $E$ $512$ $H$ $m$ $E$ $m$ $E$ $E$ $S$ $S$ $S$ $S$

Jos funktion askelmäärä on ( kierrosta), niin Snefru-funktiota kutsutaan kaksivaiheiseksi, jos askelmien määrä on ( kierrosta), niin Snefru on kolmivaiheinen ja niin edelleen. $E$ $2$ $128$ $3$ $192$

Cryptanalysis Snefru

Maaliskuussa 1990 1 000 dollarin palkkio annettiin ensimmäiselle henkilölle, joka mursi kaksivaiheisen Snefrun löytämällä kaksi viestiä samalla hash-koodilla (eli osoittamaan, että Snefru ei kestä tyypin 2 törmäyksiä ). Myöhemmin julkistettiin samanlainen palkkio Snefrun nelivaiheisen muunnelman hakkeroinnista.

Differentiaalianalyysityökalujen avulla Eli Biham ja Adi Shamir osoittivat, että kaksivaiheinen Snefru-funktio (pienellä hashilla ) ei kestä tyypin 1 ja tyypin 2 törmäyksiä . $128$

Kuvaus hyökkäyksestä

Tavallinen hyökkäys hash-funktioita vastaan perustuu "syntymäpäivien" paradoksiin . Jos hajaamme ( , when ) eri viestejä, niin suurella todennäköisyydellä on mahdollista löytää pari, jolla on sama hash. Tällaista hyökkäystä voidaan soveltaa mihin tahansa hajautustoimintoon sen toteutuksesta riippumatta. $2^{m/2}$ $2^{64}$ $m=128$

Biham ja Shamir kehittivät Snefrulle differentiaalisen kryptausanalyysimenetelmän, joka ei riipu lohkojen valinnasta ja jota voidaan käyttää jopa silloin, kun lohkot eivät ole kryptanalyytikon tiedossa . $S$ $S$

Hash -pituudella niiden lohkojen pituus, joihin syöttöviesti on jaettu, on . Tässä hyökkäyksessä käytettiin algoritmia, joka etsii funktion kahta tuloarvoa ( - bittiarvot), jotka eroavat vain tuloviestin lohkoista muodostetuissa ensimmäisissä biteissä, mutta joilla on sama tiiviste. $m=128$ $512-m=384$ $H$ $512$ $384$

Algoritmin vaiheet:

Valitaan mielivaltainen bittipituinen lohko. Siihen lisätään nollien merkkijono (tai mikä tahansa muu bittivektori, esimerkiksi edellisen lohkon hash), joka muodostaa bitin syöttölohkon funktiolle . Laskettu . $384$ $128$ $512$ $H$ $H$
Toinen syöttölohko luodaan funktiolle muuttamalla ensimmäisen lohkon yksi tavu ja sanoja. Tässä tapauksessa ensimmäisten bittien sisältämä osa muuttuu, määritetty merkkijono ei muutu. Muuttuvat tavut sisään ja sanat ovat niitä, joita käytetään lohkon syöttöarvoina kierroksina ja vastaavasti. Laskettu . $H$ $kahdeksan$ $9$ $384$ $kahdeksan$ $9$ $S$ $56$ $57$ $H$
Vaiheissa 1) ja 2) saatuja syöttölohkojen funktioarvoja verrataan. Todennäköisyydellä löydetään pari, jolla on sama hash. $H$ $2^{-40}$

Näin ollen laskemalla noin lohkoparien funktio voidaan löytää tyypin 2 törmäys Snefrulle. $H$ $2^{41}$

Hyökkäysalgoritmin selitys

Koska vaiheessa tehdyt muutokset vaikuttavat vain ja kierroksissa käytettyihin tavuihin, ovat ja vaiheissa < numeroitujen kierrosten jälkeisten lohkojen arvot samat. $2$ $56$ $57$ $56$ $yksi$ $2$

-:nnellä kierroksella -:nnen sanan tavua käytetään -: nnen ja -nnennen sanan muuttamiseksi. Lohkon sisäänmenoon syötetään tavu , jonka lähtö on sana. Seuraavaksi suoritetaan XOR-toiminto sanalla -th ja -th. Jos tätä tavua muutetaan (vaiheessa ), samoin kuin - : nnen kierroksen lohkon syötteenä käytettävän -:nnen sanan tavu sillä todennäköisyydellä, että XOR-toiminnon suorittamisen jälkeen tavu -th sana on sama kuin sama tavu lohkossa -ja kierroksen jälkeen . Sitten syöttämällä tämän tavun -. kierroksen lohkon sisääntuloon, saamme lähdössä saman arvon kuin -. kierroksella, joka suoritetaan lohkolle vaiheesta . Siksi -: s sana on sama kierroksen jälkeen molemmissa vaiheissa. -. kierroksen jälkeen , -. kierroksen jälkeen , ..., - . kierroksen jälkeen, -: kierroksen jälkeen, ..., -. sana kierroksen jälkeen on myös sama , koska lohkon syöttö molemmille vaiheille näillä kierroksilla on sama ja sama. $56$ $kahdeksan$ $7$ $9$ $S$ $7$ $9$ $2$ $9$ $S$ $57$ $1/256$ $9$ $yksi$ $56$ $57$ $S$ $57$ $yksi$ $kymmenen$ $57$ $yksitoista$ $58$ $12$ $59$ $16$ $64$ $yksi$ $65$ $6$ $69$ $S$

$7$ -th sana on erilainen askelille jo -th kierroksen jälkeen. Siksi -: nnellä kierroksella se saa -: nnen ja -nnennen sanan merkitykset muuttumaan erilaisiksi kahdessa vaiheessa. Sama tapahtuu kierroksella sanoille ja . Ja taas todennäköisyydellä -:nnen sanan tavu, jota käytetään lohkosyötteenä -: nnellä kierroksella, on sama askelille ja . Joten -e, ..., -e, -e, ..., -e sanat ovat samat. Muutokset alkavat, kun -th sanaa käytetään -: nnellä kierroksella. $56$ $71$ $6$ $kahdeksan$ $72$ $7$ $9$ $1/256$ $9$ $S$ $73$ $yksi$ $2$ $kymmenen$ $16$ $yksi$ $5$ $6$ $86$

Siten, jos , , , ja -:nnen kierroksen jälkeen -: nnen sanan tavu, jota käytetään lohkon syötteenä seuraavilla kierroksilla, on sama molemmissa vaiheissa, sanat , , … olla sama täysien kierrosten jälkeen . Tämän tapahtuman todennäköisyys . Koska XOR-operaation arvo funktion syöttölohkon ensimmäisistä 4 sanasta ja funktion lähtölohkon ensimmäisistä 4 sanasta otetaan lohkon hajautusarvoksi , molemmissa vaiheissa lasketut hajautusarvot ovat samat. . $56$ $72$ $88$ $104$ $120$ $9$ $S$ $128$ $kymmenen$ $yksitoista$ $16$ $(1/256)^{5}=2^{-40}$ $E$ $E$

Hyökkäyksen vertailu tunnettuihin kryptausanalyysimenetelmiin

Menetelmää sovellettiin myös kolmi- ja nelivaiheiseen Snefru-funktioon, mikä osoitti parempia tuloksia syntymäpäivämenetelmään verrattuna.

Shamirin ja Bihamin hyökkäyksen vertailu "syntymäpäivien" hyökkäykseen

Snefru -toiminnon läpivientien määrä	hashin pituus, $m$	Hyökkäyksen vaikeus	Syntymäpäivän menetelmä
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}$
neljä	128-192	$2^{44.5}$	$2^{64}$ — $2^{{96}}$
neljä	224	$2^{81}$	$2^{112}$

Tämän hyökkäyksen avulla voit löytää useita pareja, joilla on sama hash, ja lisäksi löytää useita viestejä, joiden hash on yhtä suuri kuin tämän viestin tiiviste (ensimmäisen tyyppinen törmäys). Ensimmäisen tyyppisen törmäyksen löytämiseen tarvittavien operaatioiden määrä tässä hyökkäyksessä on pienempi kuin "raaka voima" -menetelmässä .

Shamirin ja Bihamin hyökkäyksen vertailu "raakan voiman" menetelmään

Snefru -toiminnon läpivientien määrä	hashin pituus, $m$	Hyökkäyksen vaikeus	raa'an voiman menetelmä
2	128-224	$2^{24}$	$2^{128}$ — $2^{224}$
3	128-224	$2^{56}$	$2^{128}$ — $2^{224}$
neljä	128-192	$2^{88}$	$2^{128}$ — $2^{192}$

Muistiinpanot

Tällä hetkellä Merkle neuvoo käyttämään Snefru-toimintoa vähintään kahdeksalla läpimenolla. Kuitenkin niin monella siirrolla Snefru-funktion laskenta hidastuu huomattavasti verrattuna MD5- tai SHA -funktioihin .

Kirjallisuus

Eli Biham, Adi Shamir . Snefrun, Khafren, REDOC-II:n, LOKI:n ja Luciferin differentiaalinen kryptausanalyysi (Extended Abstract).
Bruce Schneier. Sovellettu kryptografia. Protokollat, algoritmit, lähdetekstit C-kielellä. - M .: TRIUMPH, 2003. - 816 s. - ISBN 5-89392-055-4 .

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga 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 Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA