Esitleti efektiivsem meetod SHA-1 konflikti prefiksite määramiseks

Prantsuse riikliku arvutitehnika ja automaatika uurimisinstituudi (INRIA) ja Nanyangi Tehnoloogia Ülikooli (Singapur) teadlased on arendanud täiustatud meetod rünnakud SHA-1 algoritmi vastu, mis oluliselt lihtsustab kahe erineva dokumendi loomist sama SHA-1 hajuvusväärtusega. Meetodi olemus seisneb SHA-1 tõelise konflikti leidmise operatsiooni vähendamises konflikti rünnaku jaoks, millel on määratud prefiks, kus konflikt esineb teatud prefiksite olemasolu korral, sõltumatult ülejäänud andmestikust. Teisisõnu, saab arvutada kaks ettemääratud prefiksit ja kui üks lisatakse ühele dokumendile ja teine teisele — siis on nende failide SHA-1 hajuvusväärtused identsed.

Selle tüübi rünnak nõuab endiselt tohutuid arvutusi ja prefiksite leidmine jääb keerulisemaks kui tavaline konflikti leidmine, kuid ka tulemuse praktiline efektiivsus on oluliselt kõrgem. Kui varasem kõige kiirem konflikti prefiksite leidmise meetod SHA-1-s nõudis 277,1 operatsiooni, siis uus meetod vähendab arvutuste arvu vahemikku 266,9 kuni 269,4. Sellise taseme arvutustega on rünnaku hinnanguline maksumus vähem kui sada tuhat dollarit, mis on täiesti taskukohane luureteenistustele ja suurtele korporatsioonidele. Võrdluseks, et tavalise konflikti leidmiseks on vaja teha umbes 264,7 operatsiooni.

Uues eelmisel demonstreerimisel Google'i võimet genereerida erinevaid PDF-faile sama SHA-1 hajuvusväärtusega kasutati trikk, mis ühendab kahe dokumendi üheks failiks, vahetades nähtava kihi ja nihutades valikukihti piirkonda, kus toimub kollisioon. Sarnaste ressursside kulude juures (SHA-1 esimese kollisiooni leidmine nõudis Google'ilt aasta arvutusi 110 GPU klastris) võimaldab uus meetod saavutada SHA-1 sobivust kahe vabalt valitud andmekogumi jaoks. Praktiliselt saab ette valmistada TLS-sertifikaate, milles mainitakse erinevaid domeene, kuid SHA-1 häšid kattuvad. Selline võimalus võimaldab petlikul sertifitseerimisasutusel luua digitaalallkirja sertifikaadi, mida saab kasutada vale sertifikaatide autoriseerimiseks juhuslike domeenide jaoks. Probleemi saab kasutada ka protokollide kompromiteerimiseks, mis sõltuvad kollisioonide puudumisest, näiteks TLS, SSH ja IPsec.

Eelnähtud kollisioonide prefiksite leidmise strateegia tähistab arvutuste jagamist kaheks etapiks. Esimeses etapis otsitakse blokke, mis on kollisiooni piiril, sisestades juhuslikke muutujaid kettidesse ettemääratud sihikomplekti erinevustest. Teises etapis võrreldakse saadud erinevuste ahelad individuaalsete plokkide tasemel kollisioonidega koos seotud olekute paaridega, kasutades traditsioonilisi kollisioonide tabamise meetodeid.

Kuigi teoreetiline rünnaku võimalus SHA-1 vastu on tõestatud juba 2005. aastal, ja esimene kollisioon tuvastati praktikas leiti 2017. aastal, on SHA-1 endiselt laialdaselt kasutusel ja esindab mõningaid standardeid ja tehnoloogiaid (näiteks TLS 1.2, Git jne). Peamine eesmärk tehtud töös oli pakkuda veel üht kaalukat argumenti SHA-1 viivitamatuks lõpetamiseks, eriti sertifikaatides ja digitaalallkirjades.

Lisaks võib märkida avaldamist tulemused blokeeringute šifreerimise krüptoanalüüsist SIMON-32/64, mis on välja töötatud USA NSA poolt ja kinnitatud 2018. aastal standardina ISO/IEC 29167-21:2018.
Uurijatel õnnestus välja töötada meetod privaatvõtme taastamiseks kahe tuntud ploki paariga avatud teksti ja šifreeritud teksti põhjal. Piiratud arvutusressursside puhul võib võtme leidmine võtta paarist tunnist kuni paar päeva. Teoreetiline nurga eduvõime on hinnatud 0,25, praktikas olemasoleva prototüübi puhul on see 0,025.

Allikas: opennet.ru