Hash-funktion törmäys

Hash-funktion törmäys on kaksi erilaista syötetietolohkoa ja hash-funktiolle sellainen , että $x$ $y$ $H$ $H(x)=H(y).$

Törmäyksiä esiintyy useimmissa hash-funktioissa, mutta "hyvien" hash-funktioiden esiintymistiheys on lähellä teoreettista minimiä. Joissakin erikoistapauksissa, kun eri syötetietojen joukko on äärellinen , on mahdollista määritellä injektiivinen hash-funktio, jossa ei määritelmän mukaan ole törmäyksiä. Kuitenkin tiivistefunktioissa, jotka ottavat muuttuvan pituisen syötteen ja palauttavat vakiopituisen tiivisteen (kuten MD5 ), törmäyksiä on oltava, koska vähintään yhdelle hash-funktion arvolle vastaava syötetietojoukko ( täysi esikuva ) on ääretön - ja minkä tahansa kahden joukon tiedot tästä joukosta muodostavat törmäyksen.

Esimerkki

Tarkastellaan esimerkkinä kokonaislukujoukolle määritettyä hash-funktiota . Sen arvoalue koostuu 19 elementistä ( jäännösrenkaat modulo 19), ja sen määritelmäalue on ääretön. Koska esikuvien joukko on selvästi suurempi kuin arvojen joukko, törmäyksiä täytyy olla. $H(x)=x\ {\bmod \ }19$

Tehdään törmäys tälle hajautusfunktiolle syötearvolle 38, jonka hash-summa on nolla. Koska funktio on jaksollinen jaksolla 19, millä tahansa syötearvolla y arvolla y + 19 on sama hash-summa kuin y . Erityisesti syöttöarvolle 38 syötearvoilla 57, 76 jne. on sama hash-summa. Siten syötearvojen (38.57), (38.76) parit muodostavat tiivistefunktion törmäyksiä . $H(x)$ $H(x)$

Kryptografisten hash-funktioiden törmäykset

Koska kryptografisia hajautusfunktioita käytetään vahvistamaan alkuperäisen tiedon muuttumattomuutta, kyky löytää nopeasti törmäys niille merkitsee yleensä huonoa luottoa . Jos esimerkiksi hajautusfunktiota käytetään digitaalisen allekirjoituksen luomiseen , kyky löytää törmäyksiä sille vastaa itse asiassa kykyä väärentää digitaalinen allekirjoitus. Siksi hajautusfunktion kryptografisen vahvuuden mittana on törmäyksen löytämisen laskennallinen monimutkaisuus . Ihannetapauksessa ei pitäisi olla nopeampaa tapaa löytää törmäyksiä kuin raaka voima . Jos jollakin hash-funktiolla on tapa saada törmäyksiä paljon nopeammin kuin tyhjentävä haku, tätä hash-toimintoa ei enää pidetä salauksenkestävänä eikä sitä enää käytetä salaisen tiedon lähettämiseen ja tallentamiseen. Törmäysten löytämisen ja käytön teoreettisia ja käytännön kysymyksiä käsitellään vuosittain kansainvälisissä konferensseissa (kuten CRYPTO tai ASIACRYPT ), useissa Internet-resursseissa sekä monissa julkaisuissa.

Salaustiivistefunktioiden ominaisuudet

Jotta tiivistefunktiota H voitaisiin pitää kryptografisesti turvallisena, sen on täytettävä kolme perusvaatimusta, joihin useimmat salausfunktioiden sovellukset perustuvat:

Peruuttamattomuus : Tietylle hash-arvolle m pitäisi olla käytännössä mahdotonta löytää tietolohkoa, jolle . $X$ $H(X) = m$
Ensimmäisen tyyppinen törmäyskestävyys : tietylle viestille M pitäisi olla käytännössä mahdotonta löytää toista viestiä N , jolle . $H(N)=H(M)$
Toisen tyypin törmäyskestävyys : pitäisi olla käytännössä mahdotonta poimia viestiparia, joilla on sama hash. ${\näyttötyyli (M,M')}$

Törmäysten käyttö hakkerointiin

Harkitse esimerkkinä yksinkertaista käyttäjän todennusmenettelyä :

rekisteröityessään järjestelmään käyttäjä syöttää salasanansa, johon käytetään jotain hash-toimintoa , jonka arvo tallennetaan tietokantaan ;
joka kerta kun annat salasanan, siihen sovelletaan samaa hajautustoimintoa ja tulosta verrataan tietokantaan tallennettuun.

Tällä lähestymistavalla, vaikka hyökkääjä pääsisi tietokantaan, hän ei pysty palauttamaan käyttäjien alkuperäisiä salasanoja (edellyttäen, että käytetty hash-toiminto on peruuttamaton). Jos hyökkääjä kuitenkin osaa löytää törmäyksiä käytetylle hash-funktiolle, hänen ei ole vaikea löytää ei-alkuperäistä salasanaa, jolla on sama hash-summa kuin käyttäjän salasanalla.

Törmäyksillä voidaan väärentää viestejä: esimerkiksi valuuttatapahtumia koskevat tiedot salataan usein hash-funktioilla; hyökkääjä, jolla on menetelmä löytää tämän hash-funktion törmäykset, voi korvata viestin väärennetyllä ja siten vaikuttaa valuuttatapahtuman kulkuun.

Vastaavasti törmäyksiä voidaan käyttää digitaalisten allekirjoitusten ja sertifikaattien väärentämiseen .

Törmäyssuoja

On olemassa useita suojautumismenetelmiä hakkerointia vastaan , suojaus salasanojen, allekirjoitusten ja varmenteiden väärentämiseltä , vaikka hyökkääjä tietäisi menetelmät törmäysten luomiseen mille tahansa hash-toiminnolle .

Eräs tapa on lisätä " suola " eli lisätä hajautustietoihin jokin merkkijono, jota käytetään esimerkiksi tallennettaessa UNIX - salasanoja. Tässä tapauksessa sama "suola" lisätään myös tuloksena olevaan hashiin , mikä lisää merkittävästi monimutkaisuutta ensimmäisen luokan törmäysten samanaikaisessa rakentamisessa salasanojen ryhmään , koska jokaisen tässä ryhmässä on aloitettava omalla (ainutlaatuisella) "suolan" arvo. "suola" ei kuitenkaan vaikeuta hyökkäystä jokaiseen salasanaan erikseen .

Toinen suosittu mutta rikkinäinen menetelmä on tiivisteiden yhdistäminen kahdesta eri tiivistefunktiosta. Uskotaan, että tässä tapauksessa törmäysten valitsemiseksi hash-funktiolle , joka on tiivistefunktioiden ketjutus ja , on tarpeen tietää menetelmät törmäysten muodostamiseksi sekä , että . Samaan aikaan on olemassa tutkimuksia, jotka osoittavat, että hash-ketjujen käyttö lisää hieman säätelyn tiivisteen vastustuskykyä törmäyksille, eikä sillä ole väliä, kuinka paljon hash-funktiot eroavat toisistaan [1] . Jos jokin hash-funktioista on tarpeeksi heikko löytääkseen siitä törmäyksen, toinen ei pysty vahvistamaan tuloksena olevaa tiivistettä. $C(x)=y(x)\|z(x)$ $y(x)$ $z(x)$ $y(x)$ $z(x)$

Törmäysten havaitsemismenetelmät

Yksi yksinkertaisimmista ja monipuolisimmista tavoista löytää törmäyksiä on syntymäpäivähyökkäys . Tällä hyökkäyksellä törmäyksen löytäminen bittipituiselle hash-funktiolle vaatii keskimäärin noin operaatiota. Siksi n - bittistä hash-funktiota pidetään turvallisena, jos sen törmäysten löytämisen laskennallinen monimutkaisuus on lähellä . $n$ $2^{{n/2}}$ $2^{{n/2}}$

Lisäksi on olemassa sanomaa pidentävä hyökkäys , joka tunnetulla arvolla sallii laskea , jossa tarkoittaa ketjutusta . Joidenkin hash-funktioiden laajennushyökkäys toimii myös samalla kun se tarjoaa tyypin 1 törmäysvastuksen , tyypin 2 törmäysvastuksen ja peruuttamattomuuden ominaisuuden . Ymmärretään, että ei ole välttämätöntä tietää , mutta riittää, että tietää vain sen hash . Näin voit esimerkiksi lisätä jonkun muun viestiin lisätietoja. Tämän hyökkäyksen estämiseen käytetään useita menetelmiä: ne lisäävät ylimääräisen hajautuskierroksen , joka eroaa edellisistä; käytä useampaa tiivistystä; tai käytä kahden edellisen menetelmän yhdistelmää. $H(x)$ $H(x\|y)=H(H(x)\|y)$ $\|$ $X$

Mutta laajennushyökkäystä voidaan tarkastella myös toiselta puolelta: jos meillä on jokin viesti , ja hash-funktio on alttiina laajennushyökkäykselle, on helppo löytää ensimmäisen tyyppinen törmäys: , , , eli ensimmäisen tyyppisten törmäysten vastustuskykyä rikotaan. $X$ $M_{1}=X\|Y$ $M_{2}=H(X)\|Y$ $H(M_{1})=H(M_{2})$

Useimmilla nykyaikaisilla hash-funktioilla on sama rakenne, joka perustuu syötetyn tekstin jakamiseen lohkoihin ja sitten iterointiin, jossa jokaisessa iteraatiossa käytetään jotakin funktiota , missä x on syötetyn tekstin seuraava lohko ja y on edellisen tulos. operaatio. Tällainen kaavio ei kuitenkaan ole täydellinen, koska funktion tuntemalla on mahdollista analysoida dataa iteraatioiden välissä , mikä helpottaa törmäysten etsimistä. $G(x,y)$ $G$

Usein tiivistefunktion törmäysten löytämistä edeltää sen pseudo -törmäysten etsiminen , eli alkuperäisen puskurin kaksi eri arvoa, jotka samalle viestille antavat samat hash-arvot.

MD4:n ja MD5:n hash-funktioiden törmäykset

Vuonna 1996 Hans Dobbertin löysi pseudotörmäyksiä MD5:stä käyttämällä tiettyjä epästandardeja alustusvektoreita . Kävi ilmi, että tunnetulle viestille on mahdollista rakentaa toinen viesti siten, että siinä on sama hash kuin alkuperäisellä. Matematiikan näkökulmasta tämä tarkoittaa, että MD5(IV,L1) = MD5(IV,L2) , jossa IV on puskurin alkuarvo ja L1 ja L2 ovat eri sanomia.

Vuonna 2004 kiinalaiset tutkijat Wang Xiaoyun Yu Hongbo ilmoittivat haavoittuvuudesta, jonka he olivat löytäneet algoritmista, joka mahdollisti heidänja Lai Xuejia, Feng Dengguo, ) löytääksesi törmäyksiä.

Vuonna 2005 tutkijat Wang Xiaoyun ja Yu Hongbo Shandongin yliopistosta Kiinasta julkaisivat algoritmin törmäysten löytämiseksi MD5-hajautusfunktiossa , ja heidän menetelmänsä toimii kaikille alustusvektorille, ei vain standardin käyttämälle vektorille. Käyttämällä tätä menetelmää MD4 :ssä voit löytää törmäyksen alle sekunnissa. Se koskee myös muita hash-funktioita, kuten RIPEMD ja HAVAL .

Vuonna 2008 Alexander Sotirov, Marc Stevens, Jacob Appelbaum julkaisivat artikkelin 25. Chaos Communication Congressissa, joka osoitti mahdollisuuden luoda väärennettyjä digitaalisia varmenteita MD5-törmäysten käyttöön perustuen.

SHA-1 hash-funktion törmäykset

Tammikuussa 2005 Vincent Rayman ja Elisabeth Oswald julkaisivat hyökkäyksen SHA-1 :n katkaistua versiota vastaan (53 laukausta 80 kierroksen sijaan ), mikä mahdollistaa törmäysten havaitsemisen alle 280 operaatiossa.

Helmikuussa 2005 Wang Xiaoyun , Lisa Yin Yiqun ja Yu Hongbo esittivät hyökkäyksen täyttä SHA-1:tä vastaan, joka vaatii alle 269 operaatiota.

Elokuussa 2005 CRYPTO 2005 -tapahtumassa samat asiantuntijat esittelivät parannetun version täysimittaiseen SHA-1:een kohdistuvasta hyökkäyksestä, jonka laskennallinen monimutkaisuus on 263 toimintoa. Joulukuussa 2007 Martin Cochran tarkasteli tämän parannuksen yksityiskohdat.

Christophe de Kanier ja Christian Rechberg esittelivät myöhemmin parannetun hyökkäyksen SHA-1:tä vastaan, josta heidät palkittiin parhaana paperina vuoden 2006 ASIACRYPT- konferenssissa . He esittivät kahden lohkon törmäyksen 64 kierroksen algoritmilla, jonka laskennallinen monimutkaisuus on noin 2 35 operaatiota.

Koska teoreettiset hyökkäykset SHA-1:tä vastaan ovat onnistuneet, NIST aikoo luopua kokonaan SHA-1:n käytöstä digitaalisissa allekirjoituksissa .

Törmäykset muiden hash-funktioiden kanssa

RIPEMD- ja HAVAL - tiivistefunktiot ovat myös haavoittuvia Wang Xiaoyunin, Feng Dengguon, Lai Xuejian ja Yu Hongbon vuonna 2004 julkaisemalle MD5 -törmäysalgoritmille.

WHIRLPOOL - hajautusfunktion toiselle muunnokselle , nimeltään Whirlpool-T, vuodelle 2009 ei ehdoteta algoritmeja törmäysten tai pseudotörmäysten löytämiseksi. merkittävä rajoitus niiden löytämiselle on itse funktion monimutkaisuus ja lähtöavaimen suuri pituus (512 bittiä).

Hajautusfunktio GOST R 34.10-2001 kryptografisen vahvuuden suhteen eroaa vähän GOST R 34.10-94 : stä , ja törmäysten löytäminen rajoittuu diskreetin logaritmin laskemiseen oletettavasti eksponentiaalisen monimutkaisen elliptisen käyrän pisteryhmässä . Esimerkiksi 256 - bittisille parametreille diskreetti logaritmi käyttäen ρ-menetelmää tai Pollardin λ-menetelmää vaatii noin 2 operaatiota. ${10}^{{30}}$

Törmäysresoluutio hash-taulukoissa

Törmäykset vaikeuttavat hash-taulukoiden käyttöä , koska ne rikkovat hajakoodien ja datan välisen vastaavuuden. On kuitenkin olemassa erityisiä tekniikoita esiin tulevien vaikeuksien voittamiseksi:

Ketjutusmenetelmä : Elementtien ketjutustekniikka (chaining) koostuu siitä, että joukon elementit , jotka vastaavat samaa hash-arvoa, linkitetään ketjuluetteloon. Paikkanumero i tallentaa osoittimen niiden elementtien luettelon päähän, joiden avaimen hash-arvo on yhtä suuri kuin i; jos joukossa ei ole tällaisia alkioita, kirjoitetaan NULL kohtaan i .
Avoin osoitus : Toisin kuin ketjutettu hajautus, avoimessa osoittamisessa ei ole luetteloita, ja kaikki merkinnät tallennetaan itse hash-taulukkoon. Jokainen taulukon solu sisältää joko dynaamisen joukkoelementin tai NULL:n.
Törmäysten eliminointi : Toisin kuin kahdessa edellisessä menetelmässä, törmäysten esiintyminen hash-taulukossa eliminoidaan elementtien lisäysvaiheessa. Osoitetun elementin hash-koodi on tiedon hash + satunnainen arvo. Jos hash-koodi on jo taulukossa, satunnainen arvo luodaan uudelleen ja elementti, jolla on eri hash, lisätään uudelleen hash-taulukkoon. Näin ollen törmäysten esiintyminen on poissuljettu, ja elementit voidaan löytää niiden ainutlaatuisten tiivisteiden perusteella, jotka osoittavat ne yksilöllisesti hash-taulukossa.

Muistiinpanot

↑ Antoine Joux . Haettu 3. lokakuuta 2017. Arkistoitu alkuperäisestä 19. toukokuuta 2017. (määrätön)

Katso myös

Linkit

Bruce Schneier, MD5 ja SHA Cryptanalysis
Cryptography Research , Hash Collision Q& A
Rogue CA -sertifikaatin luominen , Alexander Sotirov , MD5 -pohjainen varmenneväärennös
Kansainvälisen kryptologisen tutkimuksen yhdistyksen verkkosivusto
Hash-funktioiden MD4, MD5, HAVAL-128 ja RIPEMD , Xiaoyun Wang ja Dengguo Feng sekä Xuejia Lai ja Hongbo Yu törmäykset ( ( englanti ) )
Parannettu törmäyshyökkäys MD5:n hajautustoimintoon , erittäin tekninen
NIST kommentoi SHA :n kryptanalyyttisiä hyökkäyksiä - 1
Tietokonealgoritmien ohjaaja

Kirjallisuus

Bruce Schneier , Applied Cryptography, 2. painos, ISBN 0-471-11709-9 , ch.18, One-Way Hash Functions
Ross Anderson , turvallisuustekniikka , Wiley, ISBN 0-471-38922-6