Forscher des französischen Nationalen Instituts für Informatik und Automatisierung (INRIA) und der Nanyang Technological University (Singapur) ein verbessertes Verfahren für den SHA-1-Algorithmus entwickelt, das die Erstellung von zwei unterschiedlichen Dokumenten mit identischen SHA-1-Hashes erheblich vereinfacht. Der Kern der Methode besteht darin, die operationale vollständige Suche nach Kollisionen im SHA-1 zu reduzieren auf , bei denen eine Kollision auftritt, wenn bestimmte Prefixe vorhanden sind, unabhängig von den übrigen Daten im Satz. Mit anderen Worten, es ist möglich, zwei vordefinierte Prefixe zu berechnen, und wenn man das eine an ein Dokument und das andere an ein zweites anhängt, werden die resultierenden SHA-1-Hashes für diese Dateien identisch sein.
Diese Art von Angriff erfordert weiterhin enorme Berechnungen, und das Anpassen von Prefixen bleibt komplexer als normale Kollisionen, doch die praktische Effizienz des Ergebnisses ist deutlich höher. Während die schnellste Methode zur Auffindung von Kollisions-Prefixen im SHA-1 zuvor 277,1 Operationen erforderte, senkt die neue Methode die Anzahl der Berechnungen auf einen Bereich von 266,9 bis 269,4. Bei einem solchen Berechnungsniveau liegt die geschätzte Kosten für einen Angriff bei weniger als eintausend Dollar, was für Geheimdienste und große Unternehmen durchaus erschwinglich ist. Zum Vergleich, für die Auffindung einer normalen Kollision sind etwa 264,7 Operationen erforderlich.
Im von Google über die Möglichkeit, verschiedene PDF-Dateien mit identischem SHA-1-Hash zu generieren Ein Trick zur Kombination zweier Dokumente in eine Datei, indem die sichtbare Schicht umgeschaltet und der Auswahlmarkierungsstempel in den Bereich der Kollision verschoben wird. Bei ähnlichen Ressourcenaufwendungen (Google benötigte ein Jahr Berechnungen auf einem Cluster aus 110 GPUs, um die erste SHA-1-Kollision zu finden) ermöglicht das neue Verfahren, Übereinstimmungen von SHA-1 für zwei beliebige Datensätze zu erzielen. Praktisch gesehen können TLS-Zertifikate vorbereitet werden, in denen unterschiedliche Domains erwähnt werden, aber die SHA-1-Hashes übereinstimmen. Diese Möglichkeit erlaubt es unehrlichen Zertifizierungsstellen, ein Zertifikat für digitale Signaturen zu erstellen, die zur Authentifizierung gefälschter Zertifikate für beliebige Domains verwendet werden können. Das Problem kann auch zur Kompromittierung von Protokollen genutzt werden, die auf der Abwesenheit von Kollisionen beruhen, wie TLS, SSH und IPsec.
Die vorgeschlagene Strategie zur Suche nach Präfixen für Kollisionen sieht vor, die Berechnungen in zwei Phasen zu unterteilen. In der ersten Phase wird nach Blöcken gesucht, die kurz vor der Kollision stehen, indem zufällige Variablen in eine vordefinierte Zielmenge von Abweichungen eingebettet werden. In der zweiten Phase werden auf der Ebene einzelner Blöcke die erhaltenen Unterschiede mit den zu Kollisionen führenden Zustandspaaren verglichen, unter Verwendung von Methoden traditioneller Kollisionen.
Obwohl die theoretische Möglichkeit eines Angriffs auf SHA-1 bereits 2005 nachgewiesen wurde, wurde die erste Kollision in der Praxis im Jahr 2017, bleibt SHA-1 dennoch im Umlauf und wird von einigen Standards und Technologien abgedeckt (TLS 1.2, Git usw.). Das Hauptziel dieser Arbeit war es, ein weiteres starkes Argument für die sofortige Einstellung der Verwendung von SHA-1, insbesondere in Zertifikaten und digitalen Signaturen, zu liefern.
Zusätzlich kann vermerkt werden Kryptoanalyse von Blockchiffren , die von der NSA entwickelt und 2018 als Standard genehmigt wurden .
Die Forscher konnten eine Methode zur Wiederherstellung des privaten Schlüssels auf der Grundlage von zwei bekannten Paaren aus Klartext und Chiffretext entwickeln. Bei begrenzten Rechenressourcen wird zur Schlüsselgenerierung eine Zeitspanne von mehreren Stunden bis zu mehreren Tagen benötigt. Der theoretische Erfolgsfaktor des Angriffs wird auf 0,25 geschätzt, während der praktische für das vorhandene Prototype 0,025 beträgt.
Quelle: opennet.ru
