Výskumníci z francúzskeho štátneho inštitútu pre výskum v informatike a automatizácii (INRIA) a Nanyang Technological University (Singapur) vylepšený algoritmus SHA-1, ktorý podstatne zjednodušuje vytváranie dvoch rôznych dokumentov s rovnakými hashmi SHA-1. Podstata metódy spočíva v znížení operácie úplného hľadania kolízí v SHA-1 na , pri ktorom kolízia nastáva za prítomnosti určitých prefixov, bez ohľadu na ostatné údaje v súbore. Inými slovami, je možné vypočítať dva preddefinované prefixy a ak jeden pripojíme k jednému dokumentu a druhý k druhému — výsledné hash SHA-1 pre tieto súbory budú rovnaké.
Tento typ útoku stále vyžaduje obrovské výpočty a hľadanie prefixov zostáva zložitejšie ako bežné hľadanie kolízií, ale praktická účinnosť výsledku je podstatne vyššia. Ak doteraz najrýchlejší spôsob vyhľadávania prefixov kolízií v SHA-1 vyžadoval vykonanie 277,1 operácií, nový prístup znižuje počet výpočtov na rozsah od 266,9 do 269,4. Pri takejto úrovni výpočtov sa odhadované náklady útoku pohybujú pod sto tisíc dolárov, čo je celkom realista pre spravodajské služby a veľké korporácie. Pre porovnanie, na hľadanie bežnej kolízie je potrebné vykonať približne 264,7 operácií.
V Google pri možnosti generovania rôznych PDF súborov s rovnakým hashom SHA-1 trik s kombinovaním dvoch dokumentov do jedného súboru, prepínaním viditeľnej vrstvy a posúvaním výberu vrstvy na oblasť vzniku kolízie. Pri podobných nákladoch na zdroje (na hľadanie prvej kolízie SHA-1 Google strávil rok výpočtov na klastri z 110 GPU) nový prístup umožňuje dosiahnuť zhodu SHA-1 pre dva ľubovoľné súbory údajov. Z praktického hľadiska je možné pripraviť TLS certifikáty, v ktorých sa uvádzajú rôzne domény, ale zhodujú sa hashe SHA-1. Takáto možnosť umožňuje nekalému certifikačnému úradu vytvoriť certifikát pre digitálny podpis, ktorý môže byť použitý na autorizáciu falošných certifikátov pre ľubovoľné domény. Problém sa dá takisto využiť na kompromitáciu protokolov, ktoré sa spoliehajú na absenciu kolízií, ako sú TLS, SSH a IPsec.
Navrhnutá stratégia vyhľadávania prefixov pre kolízie predpokladá rozdelenie výpočtov na dva kroky. V prvom kroku sa vykonáva vyhľadávanie blokov, ktoré sú na pokraji kolízie, prostredníctvom vkladania náhodných premenných reťazcov do preddefinovanej cieľovej sady rozdielov. V druhom kroku sa na úrovni jednotlivých blokov získané reťazce rozdielov porovnávajú s kolíznymi pármi stavov, pričom sa používajú metódy tradičných útokov zameraných na vyhľadávanie kolízií.
Napriek tomu, že teoretická možnosť útoku na SHA-1 bola preukázaná už v roku 2005, a v praxi bola prvá kolízia v roku 2017, SHA-1 stále ostáva v obehu a je zahrnutý v niektorých štandardoch a technológiách (TLS 1.2, Git atď.). Hlavným cieľom vykonanej práce bolo poskytnúť ďalší presvedčivý argument na okamžité ukončenie používania SHA-1, najmä v certifikátoch a digitálnych podpisoch.
Navyše môžeme spomenúť kryptoanalýzy blokových šifrov , vyvinutých NSA USA a v roku 2018 schválených ako štandard .
Vedcom sa podarilo vyvinúť metódu obnovy súkromného kľúča na základe dvoch známych párov z otvoreného textu a šifrovaného textu. Pri obmedzených výpočtových zdrojích na hľadanie kľúča je potrebné od niekoľkých hodín do niekoľkých dní. Teoretický koeficient úspešnosti útoku je odhadovaný na 0.25, pričom praktický pre existujúci prototyp je 0.025.
Zdroj: opennet.ru
