A02:2021 - Cryptographic failures - Colisiones Hash

A02:2021 – Kryptografische Fehler – Colisiones Hash

Olga Borrallo


Was sind kryptografische Fehler?

Ein kryptografischer Fehler tritt auf, wenn der Datenschutz nicht ausreichend ist, unabhängig davon, ob der Fehler auf eine fehlerhafte Verwendung eines kryptografischen Algorithmus, einen Fehler bei seiner Implementierung oder die Verwendung unsicherer Praktiken zurückzuführen ist. Die auftretenden Schwachstellen können die Vertraulichkeit und Integrität der Informationen einer Anwendung beeinträchtigen.

Kryptografische Fehler stellen ein Sicherheitsrisiko dar, da sie es einem potenziellen böswilligen Akteur ermöglichen, Informationen zu entschlüsseln, zu manipulieren oder darauf zuzugreifen, auf die er eigentlich keinen Zugriff haben sollte.

Unter moderner Kryptographie versteht man den Einsatz robuster und somit sicherer Algorithmen. Darunter sind AES; Dennoch ist die korrekte Implementierung von RSA oder SHA-256 von entscheidender Bedeutung. Falsche Schlüsselgenerierung, Verwendung veralteter Algorithmen wie SHA1 oder MD5; oder die Inbetriebnahme vorhersagbarer Zahlengeneratoren kann zu Angriffen auf die Kryptografie der Anwendung führen.


Verwendung veralteter Algorithmen

Einer der häufigsten kryptografischen Fehler ist die Verwendung veralteter Hash-Funktionen und Verschlüsselungsalgorithmen, wie bereits erwähnt, SHA1 und MD5. Obwohl sie zu ihrer Zeit (1995 bzw. 1992) Standard waren, gelten sie heute aufgrund der Fortschritte bei Angriffstechniken wie der Suche nach Hash-Kollisionen nicht als sicher. Diese Angriffe ermöglichen es einem potenziellen böswilligen Akteur, zwei verschiedene Eingaben zu generieren, die denselben Hash erzeugen, was zu Informationsdiebstahl führen könnte.

Es müssen auch symmetrische Verschlüsselungsalgorithmen berücksichtigt werden, darunter auch einige, die als veraltet gelten, nämlich DES oder 3DES, die für die Zeiten, in denen wir uns befinden, keine ausreichende Robustheit bieten, da die Daten mit ausreichend Zeit und Ressourcen entschlüsselt werden können .


Geschichte: MD5 und SHA1

Die Algorithmen MD5 (Message Digest 5) und SHA1 (Secure Hash Algorithm 1) sind Hash-Funktionen, die häufig zur Überprüfung der Datenintegrität verwendet werden. Im Laufe der Zeit wurden jedoch schwerwiegende Schwachstellen in beiden Algorithmen entdeckt, die es böswilligen Akteuren (unter anderem) ermöglichten, Kollisionsangriffe durchzuführen, was zu einer Sicherheitsverletzung führte. Daher gelten sowohl MD5 als auch SHA1 als veraltet und werden nicht für die Verwendung in Funktionen empfohlen, die eine hohe Sicherheit erfordern.


MD5 - Nachrichtenübersicht 5

Der 1991 entwickelte Algorithmus generiert einen 128-Bit-Hash aus einem Datensatz beliebiger Größe. Ursprünglich verwendet, um die Integrität von Dateien und Bildern sowie Passwort-Hashes zu überprüfen.

  • Kollisionsangriffe: 2004 die Forscher Xiaoyun Wang, Dengguo Feng, Xuejia Lai und Hongbo Yu; zeigte, dass MD5 anfällig für Kollisionen ist.
    • Xie, T., Liu, F. & Feng, D. (2013). Schneller Kollisionsangriff auf MD5. Kryptologie-ePrint-Archiv.
  • Preimage-Angriffe: Obwohl seltener, sind Preimage-Angriffe in MD5 theoretisch möglich, bei denen ein böswilliger Akteur versuchen könnte, die ursprüngliche Nachricht aus dem Hash zu rekonstruieren.
    • Sasaki, Y. & Aoki, K. (2009). Schnelleres Auffinden von Vorbildern im vollständigen MD5 als bei einer umfassenden Suche. In Advances in Cryptology-EUROCRYPT 2009: 28. Internationale Jahreskonferenz zur Theorie und Anwendung kryptografischer Techniken, Köln, Deutschland, 26.–30. April 2009. Proceedings 28 (S. 134–152). Springer Berlin Heidelberg.


SHA1 – Sicherer Hash-Algorithmus 1

SHA1, 1993 von der NSA entwickelt, generiert einen 160-Bit-Hash. Seine Verwendung war standardisiert und findet sich in Protokollen wie SSL/TLS und PGP. In den letzten Jahren hat sich gezeigt, dass es anfällig für Kollisionsangriffe ist.

Im Jahr 2017 hat Google in Zusammenarbeit mit der Universität Amsterdam gezeigt, dass es bei der Veröffentlichung von SHA1 zu Kollisionen kommen kann https://shattered.io/ zur kostenlosen öffentlichen Konsultation.


Hash-Kollisionen


Hash-Funktionen

Eine Hash-Funktion ist ein Algorithmus, der eine Eingabe variabler Länge in eine variable Ausgabe (Hash oder Digest) umwandelt. Hash-Funktionen sind unidirektional konzipiert, die Eingabe kann nicht aus der Ausgabe wiederhergestellt werden und kollisionssicher. Bei bestimmten Algorithmen wurde jedoch bereits gezeigt, dass die Widerstandsfähigkeit gegenüber Kollisionen nicht immer perfekt ist.


Aber was sind Hash-Kollisionen?

Eine Hash-Kollision tritt auf, wenn zwei verschiedene Eingaben dieselbe Ausgabe oder denselben Digest erzeugen. Diese Situation zerstört eine der wesentlichen Eigenschaften von Hash-Funktionen, die Einzigartigkeit des Digests.


Die Sicherheit von Systemen wie digitalen Signaturen, Dateiintegrität und SSL/TLS-Zertifikaten kann durch Hash-Kollisionen gefährdet werden. Wenn es einem böswilligen Akteur gelingt, den Inhalt einer Nachricht zu ändern, ohne deren Hash zu ändern, kann er sicherstellen, dass die Änderungen unbemerkt bleiben und die Nachricht als legitim betrachtet wird.


Kollisionsbeispiel in MD5

Für das Kollisionsbeispiel werden zwei Textstrings verwendet, die sich um ein Byte unterscheiden. Dank geht an Marc Stevens für seine Veröffentlichung .

  • String1:

TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak 

  • Zeichenfolge 2:

TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak


TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak

|

TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak

Um dies zu demonstrieren, wird ein kleiner Proof of Concept in C durchgeführt:

#include 
#enthalten
#include 
int main() {
    char *input1 = "TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak";
    char *input2 = "TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak";
    vorzeichenloses Zeichen hash1[MD5_DIGEST_LENGTH];
    vorzeichenloses Zeichen hash2[MD5_DIGEST_LENGTH];
    MD5((unsigned char*)input1, strlen(input1), hash1);
    MD5((unsigned char*)input2, strlen(input2), hash2);
    for(int i = 0; i 
    printf("\n");
    for(int i = 0; i 
    printf("\n");
    printf(memcmp(hash1, hash2, MD5_DIGEST_LENGTH) == 0 ? „Kollision gefunden!\n“: „Keine Kollision\n“);
    gebe 0 zurück;
}


Und es kommt zu einer Hash-Kollision, zwei verschiedene alphanumerische Zeichenfolgen führen zum gleichen MD5-Hash. Wenn dies auf ein Zugangssystem übertragen wird, in dem die Zugangsdaten mithilfe von MD5-Hashes gespeichert werden, könnte dies zu einem unbefugten Zugriff mit einem anderen Zugangsdaten als dem Original führen.


Wie findet man Hash-Kollisionen? → Ausgewählte Präfix-Kollision

Das Erkennen einer Hash-Kollision ist wie das Finden einer Nadel im Heuhaufen. Der Aufwand an Rechenressourcen, der erforderlich ist, um beispielsweise zwei beliebige Zeichenfolgen zu finden, die zum gleichen Hash führen, ist enorm.

Aus diesem Grund wurden Techniken wie Chosen Prefix Collision (CPC) entwickelt, bei denen zwei Nachrichten mit bestimmten Präfixen ausgewählt und Variationen erstellt werden können, die zu einer Hash-Kollision führen.

Theoretischer Rahmen


Das Ziel des Angriffs besteht darin, zwei Nachrichten M1 und M2 zu finden, jede mit bekannten und kontrollierten Präfixen P1 und P2 , was zum gleichen Digest führt. Es kann ausgedrückt werden als:


Wo:

  • H ist die Hash-Funktion (MD5 oder SHA1).
  • P1 und P2 sind die gewählten Präfixe.
  • M1 und M2 sind die zu identifizierenden variablen Teile.
  • ∣∣ bezeichnet Verkettung.

Das von diesem speziellen Angriff ausgehende Risiko ist hoch, da die Präfixe Teil einer Datei oder Nachricht mit bekannter Struktur (z. B. einem digitalen Zertifikat) sein können, wodurch Daten strategisch manipuliert werden könnten, um die Kollision zu erreichen, ohne dass dies sichtbar ist oder kritische Elemente geändert werden.


Angriffsprozess

Betrachten Sie die Struktur einer Hash-Funktion, die in Blöcke unterteilt ist:


Wobei My die Blöcke fester Größe in der Eingabe darstellt. Die Berechnung der Hash-Funktion H wird iterativ für diese Blöcke durchgeführt, wobei jeder Block einen Zwischenzustand Si modifiziert.


Beim CPC-Angriff werden zunächst die Präfixe P1 und P2 verarbeitet, wodurch ein Zwischenzustand für die Hash-Berechnung entsteht.


Um das Ziel zu erreichen, zwei Blöcke M1 und M2 zu finden, die, verkettet mit den Präfixen P1 und P2, ergeben Um den gleichen endgültigen Hashwert zu erhalten, müssen die Blöcke M1 und M2 so angepasst werden, dass die Unterschiede zwischen S1 und S2 i > werden in nachfolgenden Zwischenzuständen aufgehoben.

Mindestens ein My Block muss den Unterschied zwischen den Zwischenzuständen ausgleichen.

Wo:

  • ⊕ stellt die XOR-Operation dar.
  • ΔS ist die in den Zwischenzuständen eingeführte Differenz, um die Ungleichheit zwischen S1 und S2 auszugleichen.

Wenn man vereinfacht davon ausgeht, dass eine Kollision von Zwischenzuständen erzwungen werden kann, erhalten wir am Ende der ausgewählten Blöcke:



Dies führt zur Anpassung von M1 und M2, so dass trotz unterschiedlicher Präfixe P1 und P2 das gleiche Finale entsteht Zwischenzustand S1 tritt ein.

Um Gleichheit zu erreichen, müssen berechnete Unterschiede in den Nachrichtenblöcken M1 und M2 eingeführt und Unterschiede in den Bits des Nachrichtenblocks angewendet werden, die den Unterschieden in den Zwischenzuständen der Hash-Funktion entgegenwirken. Diese Unterschiede werden so berechnet, dass ihre Ausbreitung durch die Hash-Funktion zum gleichen Endzustand führt.

Angenommen, im Nachrichtenblock M1 werden Unterschiede eingeführt, beispielsweise ΔM, sodass:


Mit dem Ziel, dass der Zwischenzustand nach Anwendung des Blocks M1⊕ΔM gleich dem Zwischenzustand nach Anwendung des Blocks M2 ist.


Abschluss

Der Chosen Prefix Collision-Angriff nutzt die interaktive Natur von Hash-Funktionen aus. Durch die Manipulation von Datenblöcken und die Anwendung berechneter Unterschiede können Zwischenzustände angepasst werden, was dazu führt, dass die endgültige Hash-Ausgabe kollidiert.

Dieser Angriff ist ein Test der grundlegenden Schwächen von Hash-Funktionen wie MD5 und SHA1, vor allem gegen fortgeschrittene Angriffe, die Eingabedaten kontrolliert manipulieren.



Autor: Daniel Puente


Zurück zum Blog

Hinterlasse einen Kommentar

Bitte beachten Sie, dass Kommentare vor der Veröffentlichung genehmigt werden müssen.