En mer effektiv metod för att bestämma kollisionens prefix för SHA-1 har presenterats

Forskare från det franska statliga institutet för forskning inom datavetenskap och automation (INRIA) och Nanyang Technological University (Singapore) har utvecklat ett förbättrat metod attacker SHA-1-algoritm som avsevärt förenklar skapandet av två olika dokument med samma SHA-1-hashar. Kärnan i metoden går ut på att minska operationen för fullständig sökning av kollisioner i SHA-1 till en kollisionattack med ett givet prefix, där en kollision uppstår vid förekomsten av specifika prefix, oavsett övriga data i satsen. Med andra ord kan man beräkna två fördefinierade prefix och om man kopplar ett prefix till ett dokument och det andra till det andra — kommer de resulterande SHA-1-hasharna för dessa filer att vara desamma.

Denna typ av attack kräver fortfarande enorma beräkningar och att hitta prefix är fortfarande mer komplicerat än vanliga kollisioner, men den praktiska effektiviteten av resultatet är avsevärt högre. Om den snabbaste metoden för att hitta prefixkollisioner i SHA-1 hittills krävde 277,1 operationer, minskar den nya metoden antalet beräkningar till intervallet 266,9 till 269,4. Vid sådan nivå av beräkningar uppskattas kostnaden för attacken till mindre än hundratusen dollar, vilket är överkomligt för underrättelsetjänster och stora företag. För jämförelse krävs cirka 264,7 operationer för att hitta en vanlig kollision.

I den förra demonstrationer Google av möjligheten att generera olika PDF-filer med samma SHA-1-hash användes En trick för att kombinera två dokument till en fil, genom att växla mellan de synliga lagren och förflytta markeringen av lagret till kollisionsområdet. Med nära nog samma resurskostnader (för att hitta den första SHA-1-kollisionsen tillbringade Google ett år med beräkningar på en kluster av 110 GPU:er) gör den nya metoden det möjligt att uppnå en SHA-1-matchning för två slumpmässiga datamängder. Praktiskt sett kan man förbereda TLS-certifikat som nämner olika domäner men har identiska SHA-1-hashar. Denna möjlighet gör det möjligt för en oärlig certifikatutfärdare att skapa ett certifikat för en digital signatur som kan användas för att auktorisera falska certifikat för slumpmässiga domäner. Problemet kan också utnyttjas för att kompromettera protokoll som förlitar sig på att det inte finns några kollisioner, såsom TLS, SSH och IPsec.

Den föreslagna strategin för prefixsökning för kollisioner innebär att beräkningarna delas upp i två steg. I det första steget utförs sökandet av block som ligger på gränsen till kollisioner genom att införa slumpmässiga variabler i en förutbestämd måluppsättning av skillnader. I det andra steget, på nivån av individuella block, jämförs de resulterande skillnaderna med kollisionspar av tillstånd, med hjälp av metoder för traditionella kollisionstest.

Trots att den teoretiska möjligheten till en attack på SHA-1 bevisades redan 2005, och att den första kollisionen i praktiken upptäcktes år 2017, används SHA-1 fortfarande och omfattas av vissa standarder och teknologier (TLS 1.2, Git m.fl.). Huvudsyftet med det utförda arbetet var viljan att tillhandahålla ännu ett starkt argument för omedelbar upphörande av användningen av SHA-1, särskilt i certifikat och digitala signaturer.

Dessutom kan det nämnas publiceringen resultat av kryptanalys av blockchiffer SIMON-32/64, utvecklade av NSA i USA och antagna som standard 2018 ISO/IEC 29167-21:2018.
Forskare har lyckats utveckla en metod för att återställa den privata nyckeln baserat på två kända par av klartext och chiffertext. Med begränsade beräkningsresurser krävs från flera timmar till flera dagar för att knäcka nyckeln. Den teoretiska framgångsfaktorn för attacken uppskattas vara 0.25, medan den praktiska för den befintliga prototypen är 0.025.

Källa: opennet.ru