Syntymäpäivähyökkäykset ja törmäyshyökkäykset

Kun ryhmässä on 23 henkilöä, todennäköisyys sille, että kahdella on sama syntymäpäivä, ylittää 50 %. Kun henkilöitä on 70, todennäköisyys ylittää 99,9 %. Matemaattisesti: N:n kokoisessa joukossa törmäyksen todennäköisyys ylittää 50 % noin √N näytteen jälkeen. Tätä kutsutaan syntymäpäivärajaksi.

n-bittiselle hash-funktiolle törmäys (H(m1) = H(m2), m1 ≠ m2) voidaan löytää noin 2^{n/2} satunnaiskokeella. SHA-256:lla (256-bittinen) törmäyksen löytämiseen tarvitaan noin 2^{128} työtä — laskennallisesti mahdotonta. MD5:llä (128-bittinen) tarvitaan noin 2^{64} työtä — juuri ja juuri mahdollista.

Yleinen törmäysten etsintä: luo 2^{n/2} satunnaista viestiä, laske tiivisteet, lajittele tiivistearvon mukaan ja etsi kaksoiskappaleet. Muistin vaativuus on O(2^{n/2}). Rho-algoritmi (Floyd'n syklinetsintä) pienentää muistin vaativuuteen O(1) samalla aikavaativuudella. van Oorschot–Wienerin rinnakkainen törmäyshaku lyhentää aikaa laitteiston avulla.

Wang et al. (2004) löysivät MD5:n käytännön törmäykset differentiaalista kryptanalyysiä käyttäen — eivät syntymäpäivähyökkäystä. Kaksi erilaista 1024-bittistä viestiä, joilla on sama MD5-tiiviste, voidaan tuottaa sekunneissa. Hertzbleed-/valitun etuliitteen törmäykset mahdollistavat sertifikaattitörmäykset. MD5 on törmäyskestävyyden kannalta täysin murrettu.

Tehokkaampaa on, että annettuna kaksi mielivaltaista etuliitettä P1, P2 etsitään jälkiliitteet S1, S2 siten, että H(P1||S1) = H(P2||S2). Stevens et al. (2017) löysivät valitun etuliitteen MD5-törmäyksiä. Menetelmää käytettiin luomaan haitallinen varmenteenmyöntäjän sertifikaatti, jolla oli kelvollinen MD5-allekirjoitus. MD5 poistettiin sertifikaattien käytöstä.

Googlen SHAttered (2017): ensimmäinen käytännön SHA-1-törmäys. Kaksi erilaista PDF-tiedostoa, joilla on sama SHA-1-tiiviste. Se vaati 2^{63.1} SHA-1-pakkausfunktion suoritusta — vastaa 6 500 CPU-vuotta ja 110 GPU-vuotta. Kustannus oli noin 110 000 dollaria. Selaimet poistivat SHA-1-sertifikaatit käytöstä vuonna 2017.

Merkle-Damgard-hajautusfunktioissa (MD5, SHA-1, SHA-2) voidaan laskea H(m||padding||m') tuntematta m:ää, jos H(m) tunnetaan. Tämä rikkoo MAC-rakenteet, kuten H(secret||message). Korjaus: käyttäkää HMACia, joka käyttää sisempää ja ulompaa täytettä, tai SHA-3:a, jonka sienirakenne kestää pituuden laajennushyökkäykset.

Törmäyskestävyys: etsitään mitkä tahansa kaksi toisistaan poikkeavaa viestiä, joilla on sama hajautusarvo (vaatii työn 2^{n/2}). Toisen esikuvan kestävyys: kun m tunnetaan, etsitään m' ≠ m, jolla on sama hajautusarvo (vaatii työn 2^n). Esikuvankestävyys: etsitään annetulle hajautusarvolle mikä tahansa viesti (vaatii työn 2^n). Törmäyskestävyys on aina heikoin.

Jos MAC käyttää törmäyksille altista hajautusfunktiota, törmäyksiä löytävä hyökkääjä saattaa pystyä väärentämään MAC-arvoja. HMAC-MD5:tä pidetään turvallisena MD5-törmäyksistä huolimatta, koska HMAC-rakenne edellyttää esikuvahyökkäyksiä eikä pelkkiä törmäyksiä. Uusissa järjestelmissä HMAC-MD5:stä kannattaa silti siirtyä pois.

Joux (2004): Merkle-Damgard-hajautuksissa 2^k-suuntaisten törmäysten (2^k viestiä, joilla on sama hajautusarvo) löytäminen vaatii vain k kertaa yhden törmäyksen löytämiseen tarvittavan työn, ei 2^k-kertaista työmäärää. Tämä voimistaa yhdistettyjen hajautusten haavoittuvuuksia: H1(m)||H2(m) ei ole niin vahva kuin voisi ajatella.

Käyttäkää törmäyskestävään hajautukseen SHA-256:ta tai SHA-3:a. Älkää käyttäkö MD5:tä tai SHA-1:tä mihinkään tietoturvatarkoitukseen. MAC-arvoihin sopivat HMAC-SHA-256 tai HMAC-SHA-3. Salasanojen hajautukseen käytetään Argon2:ta, ei suoraan SHA-2:ta. Käyttäkää aina SHA-3:a, kun tarvitaan suojaa pituuden laajennushyökkäyksiä vastaan.

Birthday-hyökkäys löytää hajautusarvojen törmäyksiä työmäärällä 2^{n/2}. MD5:lle on käytännöllisiä valitun etuliitteen törmäyksiä, ja SHA-1 murrettiin vuonna 2017. Pituuden laajennushyökkäykset rikkovat naiivit H(key||msg)-MACit. Käyttäkää SHA-256:ta tai SHA-3:a ja viestien todentamiseen HMACia. Seuraavaksi: keskikohtaushyökkäykset.