Forscher des französischen Nationalinstituts für Informatik- und Automatisierungsforschung (INRIA) und der Nanyang Technological University (Singapur) verbessert zum SHA-1-Algorithmus, der die Erstellung zweier verschiedener Dokumente mit denselben SHA-1-Hashes erheblich vereinfacht. Der Kern der Methode besteht darin, den Vorgang einer vollständigen Kollisionsauswahl in SHA-1 auf zu reduzieren , bei dem es zu einer Kollision kommt, wenn bestimmte Präfixe vorhanden sind, unabhängig von den restlichen Daten im Satz. Mit anderen Worten: Sie können zwei vordefinierte Präfixe berechnen und wenn Sie eines an ein Dokument und das andere an ein zweites anhängen, sind die resultierenden SHA-1-Hashes für diese Dateien dieselben.
Diese Art von Angriff erfordert immer noch umfangreiche Berechnungen und die Auswahl von Präfixen bleibt komplizierter als die übliche Auswahl von Kollisionen, aber die praktische Effizienz des Ergebnisses ist deutlich höher. Während die bisher schnellste Methode zum Finden von Kollisionspräfixen in SHA-1 277.1 Operationen erforderte, reduziert die neue Methode die Anzahl der Berechnungen auf einen Bereich von 266.9 bis 269.4. Bei diesem Rechenaufwand belaufen sich die geschätzten Kosten eines Angriffs auf weniger als hunderttausend Dollar, was für Geheimdienste und große Unternehmen durchaus erschwinglich ist. Zum Vergleich: Die Suche nach einer regulären Kollision erfordert etwa 264.7 Operationen.
В Google bietet die Möglichkeit, verschiedene PDF-Dateien mit demselben SHA-1-Hash zu generieren Ein Trick, der darin besteht, zwei Dokumente in einer Datei zusammenzuführen, die sichtbare Ebene zu wechseln und die Ebenenauswahlmarkierung in den Bereich zu verschieben, in dem die Kollision auftritt. Bei ähnlichen Ressourcenkosten (Google hat ein Jahr lang auf einem Cluster von 1 GPUs gerechnet, um die erste SHA-110-Kollision zu finden) können Sie mit der neuen Methode eine SHA-1-Übereinstimmung für zwei beliebige Datensätze erzielen. Praktisch gesehen können Sie TLS-Zertifikate vorbereiten, die unterschiedliche Domänen erwähnen, aber über dieselben SHA-1-Hashes verfügen. Mit dieser Funktion kann eine skrupellose Zertifizierungsstelle ein Zertifikat für eine digitale Signatur erstellen, mit dem sich fiktive Zertifikate für beliebige Domänen autorisieren lassen. Das Problem kann auch zur Gefährdung von Protokollen genutzt werden, die auf Kollisionsvermeidung basieren, wie etwa TLS, SSH und IPsec.
Die vorgeschlagene Strategie zur Suche nach Präfixen für Kollisionen beinhaltet die Aufteilung der Berechnungen in zwei Phasen. Die erste Stufe sucht nach Blöcken, die kurz vor einer Kollision stehen, indem zufällige Kettenvariablen in einen vordefinierten Zieldifferenzsatz eingebettet werden. Im zweiten Schritt werden auf der Ebene einzelner Blöcke die resultierenden Differenzketten mit Zustandspaaren verglichen, die zu Kollisionen führen, wobei Methoden traditioneller Kollisionsauswahlangriffe zum Einsatz kommen.
Obwohl die theoretische Möglichkeit eines Angriffs auf SHA-1 bereits 2005 nachgewiesen wurde und es in der Praxis zu einer ersten Kollision kam Im Jahr 2017 wird SHA-1 immer noch verwendet und von einigen Standards und Technologien abgedeckt (TLS 1.2, Git usw.). Der Hauptzweck der geleisteten Arbeit bestand darin, ein weiteres überzeugendes Argument für die sofortige Einstellung der Verwendung von SHA-1, insbesondere in Zertifikaten und digitalen Signaturen, zu liefern.
Darüber hinaus kann darauf hingewiesen werden Kryptoanalyse von Blockchiffren , von der US-amerikanischen NSA entwickelt und 2018 als Standard genehmigt .
Den Forschern gelang es, eine Methode zur Wiederherstellung eines privaten Schlüssels zu entwickeln, die auf zwei bekannten Paaren aus Klartext und Chiffretext basiert. Bei begrenzten Rechenressourcen dauert die Auswahl eines Schlüssels mehrere Stunden bis mehrere Tage. Die theoretische Erfolgsquote des Angriffs wird auf 0.25 geschätzt, die praktische Erfolgsquote für den bestehenden Prototyp liegt bei 0.025.
Source: opennet.ru