Ensimmäinen käytännön SHA-1-törmäys
- helmikuuta 2017 hollantilainen tutkimuslaitos CWI Amsterdam ja Google julkistivat tuloksen, jota oli odotettu ja pelätty vuosia. He olivat tuottaneet ensimmäisen käytännön törmäyksen SHA-1-tiivistealgoritmille. Tutkimus sai nimen SHAttered, ja se osoitti konkreettisesti, että algoritmi, joka oli yhä laajalti käytössä, ei enää tarjonnut sitä turvaa, johon moni järjestelmä luotti.
Aiemmin SHA-1:n heikkous oli ollut teoreettinen. Tutkijat tiesivät, että törmäyksen pitäisi olla löydettävissä huomattavasti pienemmällä työllä kuin algoritmin pituus antaisi olettaa, mutta kukaan ei ollut vielä esittänyt todellista esimerkkiä kahdesta tiedostosta, joilla on sama SHA-1-tiiviste. SHAttered muutti tilanteen teoriasta käytännöksi.
Mikä on törmäys ja miksi se rikkoo luottamuksen
Kryptografinen tiivistefunktio ottaa minkä tahansa kokoisen syötteen ja tiivistää sen kiinteänmittaiseksi arvoksi. SHA-1:n tapauksessa tulos on 160 bittiä. Koska syötteitä on rajattomasti mutta tiivisteitä rajallinen määrä, on matemaattisesti väistämätöntä, että jotkut eri syötteet tuottavat saman tiivisteen. Tällaista tilannetta kutsutaan törmäykseksi.
Turvallisen tiivistefunktion koko idea on, että vaikka törmäyksiä on olemassa, niiden löytäminen on käytännössä mahdotonta. Hyökkääjän ei pitäisi pystyä tarkoituksella rakentamaan kahta eri sisältöä, jotka tiivistyvät samaan arvoon. Kun tämä ominaisuus pettää, koko luottamusketju rakoilee.
Ajattele esimerkkiä. Allekirjoitusjärjestelmä laskee tiivisteen sopimuksesta ja allekirjoittaa sen. Jos hyökkääjä pystyy luomaan toisen, sisällöltään erilaisen sopimuksen samalla tiivisteellä, alkuperäinen allekirjoitus pätee yhtä lailla väärennetylle versiolle. Vastaanottaja ei voi tiivisteen perusteella erottaa aitoa väärennöksestä. Sama logiikka koskee ohjelmistojen allekirjoituksia, varmenteita ja versiohallintaa.
Kaksi PDF-tiedostoa, sama tiiviste
SHAttered-tutkimuksen vakuuttavin todiste oli kaksi PDF-tiedostoa. Tiedostot näyttävät erilaisilta ja niiden sisältö poikkeaa toisistaan, mutta molemmilla on täsmälleen sama SHA-1-tiiviste:
38762cf7f55934b34d179ae6a4c80cadccbb7f0a
Olennaista on, että vaikka tiedostot jakavat saman SHA-1-arvon, ne eroavat selvästi toisistaan vahvemmalla SHA-256-algoritmilla laskettuna. Tämä havainnollistaa täsmälleen oikean asian. SHA-1 ei enää pysty erottamaan kahta eri tiedostoa toisistaan, mutta SHA-256 pystyy. Juuri tästä syystä siirtymä vahvempaan algoritmiin oli välttämätön.
Voit tarkastella tutkimuksen tuottamia tiedostoja itse. Molemmat törmäyksen PDF-tiedostot ovat saatavilla osoitteissa shattered-1.pdf ja shattered-2.pdf. Tutkimuksen tieteellinen artikkeli, joka kuvaa menetelmän tarkemmin, löytyy osoitteesta shattered.pdf.
Valtava laskentaponnistus
Törmäys ei ollut helppo löytää. Se vaati poikkeuksellisen suuren laskentamäärän, ja juuri sen mittakaava teki tutkimuksesta niin merkittävän.
Hyökkäys edellytti noin 9,2 triljoonaa SHA-1-laskentaa. Kyseessä on luku, jota on vaikea hahmottaa. Käytännössä tämä vastaa noin 6 500 prosessorivuotta tavallisilla suorittimilla laskettuna, minkä lisäksi tarvittiin noin 110 näytönohjainvuotta laskenta-aikaa. Toisin sanoen, jos yksittäinen tietokone tekisi työn yksin, siihen kuluisi tuhansia vuosia. Vasta valtavan rinnakkaislaskennan ansiosta törmäys saatiin tuotettua kohtuullisessa ajassa.
Tämä luku oli sanoma kahteen suuntaan. Toisaalta se osoitti, että hyökkäys oli aidosti mahdollinen, ei pelkkä teoreettinen uhka. Toisaalta se osoitti, että hyökkäys oli edelleen kallis ja vaati huomattavia resursseja. Se ei ollut jotain, mitä kuka tahansa voisi tehdä kotikoneellaan, mutta hyvin resursoidulle toimijalle se oli täysin saavutettavissa. Ja koska laskentateho halpenee jatkuvasti, oli selvää, että hyökkäyksen hinta laskisi vain ajan myötä.
Seuraukset: SHA-1:n nopea alasajo
SHAttered antoi alalle konkreettisen syyn tehdä se, mitä monet olivat jo suositelleet. SHA-1:n käytöstä luovuttiin turvallisuuskriittisissä yhteyksissä nopeasti tutkimuksen jälkeen.
TLS-varmenteet. Verkkoselainten ja varmentajien ekosysteemi oli jo aiemmin alkanut siirtyä pois SHA-1:stä, mutta SHAttered vahvisti päätöksen. SHA-1-pohjaiset varmenteet poistuivat käytöstä, ja vahvemmat SHA-2-pohjaiset varmenteet tulivat normiksi.
Versiohallinta. Git tunnisti olioita SHA-1:n avulla, mikä herätti kysymyksiä törmäysten vaikutuksesta versiohistorian eheyteen. Tutkimus vauhditti työtä, jossa lisättiin törmäysten havaitsemista ja siirryttiin kohti vahvempia tiivisteitä.
Allekirjoitukset. Ohjelmistojen ja asiakirjojen allekirjoituksissa SHA-1:n käyttö muuttui kestämättömäksi. Koska allekirjoitus lasketaan tiivisteen yli, törmäyksen tuottaminen tarkoitti, että allekirjoituksen sitovuuteen ei voinut enää luottaa.
Mitä SHAtteredista jäi käteen
SHAttered ei ollut yksittäinen kuriositeetti vaan käännekohta. Se muutti SHA-1:n murtamisen teoreettisesta mahdollisuudesta julkisesti todistetuksi tosiasiaksi ja antoi koko alalle selvän syyn toimia. Tärkein opetus on yleisempi kuin yksi algoritmi: kryptografiset standardit eivät ole ikuisia. Se mikä on turvallista tänään, voi olla murrettavissa huomenna, kun laskentateho kasvaa ja menetelmät kehittyvät.
Tästä syystä SHA-256 ja muut SHA-2-perheen algoritmit ovat nyt suositeltuja valintoja, ja vanhentuneista algoritmeista luopuminen ajoissa on osa vastuullista tietoturvatyötä. SHAttered muistuttaa, että algoritmin ikääntymistä kannattaa seurata ja että siirtymä uuteen kannattaa tehdä ennen kuin heikkous muuttuu hyökkäykseksi.
