Hashfunktionen
Dieser Artikel wurde für die folgenden Ubuntu-Versionen getestet:
Dieser Artikel ist größtenteils für alle Ubuntu-Versionen gültig.
Zum Verständnis dieses Artikels sind folgende Seiten hilfreich:
Eine Hash-Funktion ist eine mathematische Funktion, die eine beliebig große Menge an Eingabewerten möglichst gleichmäßig auf eine eingeschränkte Ausgabemenge abbildet. Je nach Verwendungszweck muss die Funktion verschiedene Eigenschaften erfüllen. Am bekanntesten sind wohl mittlerweile die kryptografischen Hashfunktionen, z.B. MD5 oder SHA1. Zum leichteren Verständnis werden hier aber zuerst einfachere Anwendungsmöglichkeiten beschrieben.
Nicht verwechseln sollte man Hashfunktionen mit dem Datentyp "Hash" verschiedener Programmiersprachen, auch als "Assoziatives Array" bekannt.
Gerechte Verteilung¶
Die einfachsten Hashfunktionen dienen einfach nur dazu, eine unbestimmte Menge von Eingaben möglichst gerecht in eine bestimmte Anzahl Töpfe aufzuteilen. Ein Beispiel, das bestimmt jeder kennt, sind Behörden, in denen die Anfangsbuchstaben der Kundennamen bestimmten Sachbearbeitern zugeordnet werden. Alleine den Anfangsbuchstaben des Namens als Kriterium zu nehmen, wäre allerdings eine ziemlich schlechte Hashfunktion, weil die Namen nicht gleichmäßig über das Alphabet verteilt sind. Deswegen gibt es meistens eine Tabelle, die auf Grund statistischer Auswertungen der Einwohnermeldedaten erstellt wird, und jeweils die ersten drei Buchstaben des Namens berücksichtigt.
Auch Computerprogramme nutzen gelegentlich vergleichbare Funktionen.
Prüfsummen¶
Bei Übertragungen von Daten treten gelegentlich Fehler auf - unabhängig davon, ob es sich um die elektronische Übertragung riesiger Datenmengen oder bloß um die mündliche Weitergabe einer Telefonnummer handelt. Während man die Telefonnummer noch problemlos komplett wiederholen kann, um sicher zu gehen, wird das bei umfangreicheren Daten schnell ineffizient. Deswegen werden in solchen Fällen oft an beiden Enden der Verbindung nach festgelegten Algorithmen kurze Prüfsummen berechnet. Stimmt die Prüfsumme überein, wird davon ausgegangen, dass die Daten korrekt empfangen wurden. Ein solcher Algorithmus, der in Modemzeiten gängig war und auch heute noch an Stellen verwendet wird, wo es auf Schnelligkeit und Effizienz ankommt, ist z.B. CRC-32.
Die im vorangegangenen Abschnitt beschriebene Methode mit den Anfangsbuchstaben funktioniert hier leider nicht, da Übertragungsfehler im Namen jenseits des dritten Buchstabens den Hashwert nicht modifizieren.
Ein einfacheres Beispiel, wie man die Funktionsweise von Prüfsummen verstehen kann, sind die 13-stelligen ISBN- bzw. EAN-Nummern auf Büchern. Diese bestehen in Wahrheit nur aus zwölf signifikanten Ziffern und die dreizehnte ist die Prüfziffer, welche wie folgt berechnet wird:
Addiere die Ziffern an den ungeraden Positionen der Nummer.
Addiere dazu das dreifache der Ziffern an den geraden Positionen.
Nimm nur die letzte Ziffer und ziehe sie von 10 ab.
Das Ergebnis ist die Prüfziffer, außer es lautet 10, dann ist die Prüfziffer 0.
Beispiel:
Die ISBN lautet 978-3-82732-478-8 - die letzte 8 ist die Prüfziffer.
9+8+8+7+2+7 + 3*(7+3+2+3+4+8) = 122
Die letzte Ziffer lautet 2.
10 - 2 = 8
Wenn jetzt bei einer telefonischen Buchbestellung eine Zahl falsch verstanden wird, stimmt die Summe nicht mehr, und die ISBN wird ungültig. So verhindert man, dass aus Versehen ein falsches Buch bestellt wird. Das Verdreifachen jeder zweiten Ziffer dient übrigens dazu, dass das Vertauschen zweier benachbarter Ziffern ebenfalls zu einer veränderten Prüfziffer führt.
Hinweis:
Die alten, 10-stelligen ISBN-Nummern wurden übrigens nach einem leicht abweichenden Algorithmus berechnet und eignen sich deswegen nicht dazu, dieses Beispiel nachzuvollziehen.
Kryptografische Hashs¶
Die im vorigen Abschnitt beschriebenen Prüfsummenalgorithmen eignen sich, um versehentliche Übertragungsfehler zu entdecken, die durch gekippte Bits, rauschende Leitungen oder undeutliche Sprache entstehen. Gegen absichtliche Verfälschungen übertragener Nachrichten sind sie jedoch so gut wie wirkungslos. Es wäre kein Problem, bei einer Buchbestellung die ISBN durch eine völlig andere mit derselben Prüfsumme zu ersetzen. An dieser Stelle kommen "kryptografische Hashs" ins Spiel.
Eine kryptografische Hashfunktion muss mindestens diese Eigenschaften haben:
Es muss eine Einwegfunktion sein, d.h. es darf keine Möglichkeit geben, aus dem Hashwert die Originalnachricht zu extrahieren, außer man probiert alle möglichen Nachrichten aus. (sog. "Brute-Force")
Alle Hashwerte müssen gleich wahrscheinlich sein.
Kleine Abweichungen in den Ausgangsdaten müssen möglichst große, sichtbare Veränderungen im Hashwert erzeugen.
Das Erzeugen zweier verschiedener Datensätze, die denselben Hashwert haben ("Kollision"), darf ebenfalls nicht einfacher möglich sein, als durch die Brute-Force-Methode.
Die bekanntesten und verbreitetsten derartigen Funktionen sind MD5 und die SHA-Familie. Code-Bibliotheken, die diese Algorithmen implementieren, sind für alle gängigen Programmiersprachen verfügbar und auch Kommandozeilenprogramme, um solche kryptografischen Prüfsummen zu erzeugen bzw. zu verifizieren, sind unter Ubuntu standardmäßig installiert. Sie heißen md5sum, sha1sum, sha224sum, sha256sum, sha384sum und sha512sum und werden allesamt auf dieselbe Art und Weise bedient [1]. Die SHA-Versionen unterscheiden sich dabei in der Länge des Hashs in Bits. SHA1-Hashs sind 160 Bit lang, die weiteren Versionen tragen ihre Länge im Namen.
Ohne Optionen werden die Prüfsummen von beliebig vielen Dateien errechnet, oder auch von der Standardeingabe:
$ md5sum .bashrc .profile 0c3c03e88fadd038c0ff7003987197a4 .bashrc 7d97942254c076a2ea5ea72180266420 .profile $ echo 'Hallo Welt!' | md5sum 3827eeabc49e4509e9c77e904ab6311c -
Die Ausgabe des Befehls kann man auch in eine Datei umleiten und die Prüfsummen so dem Empfänger zur Prüfung der empfangenen Daten zur Verfügung stellen. Dazu benutzt man die Option -c und übergibt den Dateinamen der Prüfsummendatei. Die Namen der zu prüfenden Dateien sind ja in dieser Liste enthalten. Im folgenden Beispiel wird zuerst eine gefälschte Prüfsumme in eine Prüfsummen-Datei eingeschleust und später enttarnt:
$ md5sum .bashrc .profile > MD5SUMs $ echo 'deadbeefdeadbeefdeadbeefdeadbeef .bash_history' >> MD5SUMs $ cat MD5SUMs 0c3c03e88fadd038c0ff7003987197a4 .bashrc 7d97942254c076a2ea5ea72180266420 .profile deadbeefdeadbeefdeadbeefdeadbeef .bash_history $ md5sum -c MD5SUMs .bashrc: Ok .profile: Ok .bash_history: Fehlschlag md5sum: WARNING: 1 of 3 computed checksums did NOT match
Hinweis:
Diese Beispiele funktionieren genauso mit den verschiedenen SHA-Befehlen, statt mit md5sum. Nur die erzeugten Hashs unterscheiden sich selbstverständlich.
Salted Hashs¶
"Gesalzene Hashs" sind die Antwort auf Rainbow Tables. Wenn es um sehr kurze Eingabedaten geht, wie z.B. um Passwörter die verschlüsselt abgespeichert werden sollen, entsteht das Problem, dass man Brute-Force-Angriffe dadurch wesentlich vereinfachen kann, indem man vorgefertigte, große Tabellen mit allen möglichen Buchstaben- und Zahlenkombinationen und den zugehörigen Hashwerten verwendet. Damit wird das Cracken von Passwörtern teilweise zum Kinderspiel.
Um diesen Angriffen zu begegnen, wurde dazu übergegangen, beim Hashen des Passworts ein zufällig bestimmtes "Salt" (Salz) mit einzuberechnen. Dieses Salt wird dann im Passwort-Hash mit abgespeichert und steht somit bei der Überprüfung immer zur Verfügung. Die nötige Größe der Rainbow Tables multipliziert sich aber dadurch um die Anzahl der möglichen Salts und macht damit ihren Einsatz für Cracker unattraktiv.
Ein Beispiel für diese Vorgehensweise ist die Datei /etc/shadow, in der Ubuntu die Systempasswörter ablegt. Allerdings wird dafür kein einfacher MD5-Algorithmus verwendet, sondern dieser wird mehrfach unter Kombination mit dem Salt angewendet. Auch wird der Hash nicht wie üblich in Hexadezimalzahlen abgespeichert, sondern als Base64. Ein fertiger Hash sieht dann bspw. aus wie $1$uJinzljS$Pi782r.fLfnFhkQvmmdcy0, wobei die einzelnen Felder durch das $-Zeichen getrennt werden. Die 1 bestimmt die Verwendung des gesalteten MD5-Algorithmus, uJinzljS ist in diesem Beispiel das Salt, und der Rest ist der Hashwert.
Sicherheit¶
Vertrauen¶
Über eines muss man sich im Klaren sein: Ein korrekter MD5-Wert einer Datei bedeutet zwar, dass die Datei exakt in dem Zustand vorliegt, wie zum Zeitpunkt als der Hash errechnet wurde, das heißt aber noch lange nicht, dass der Inhalt vertrauenswürdig ist. Wenn ein Angreifer in einen Server einbricht und ein Programmpaket durch eine trojanisierte Version ersetzt, ist es ihm ein leichtes, die MD5-Datei ebenfalls zu ersetzen. Davor schützen kann man sich als Anbieter nur, wenn man die MD5-Datei bspw. mit GnuPG digital signiert. Für den Anwender können einfache MD5-Summen aber trotzdem nützlich sein, wenn man sie z.B. vom vertrauenswürdigen Hauptserver des Projekts herunter lädt, und das Paket selber aus einer weniger zuverlässigen Quelle wie einem Mirror oder P2P-Netz.
Angriffe gegen MD5 und SHA1¶
In den letzten Jahren erregten erfolgreiche Angriffe gegen die verbreiteten Algorithmen MD5 und SHA1 die Fachwelt. Hierbei handelte es sich jedoch "nur" um Kollisionsattacken, also die erfolgreiche Erzeugung zweier verschiedener Datensätze mit gleichem Hashwert. Das könnte in Zukunft relevant werden, wenn digitale Signaturen im Alltag Einzug halten um Verträge abzuschließen. Verbreitete Dateiformate bieten genug Möglichkeiten, Fülldaten unterzubringen, die im Dokument nicht sichtbar sind. Es wäre also denkbar, dass man die MD5-Summe eines Kaufvertrags digital signiert ohne zu wissen, dass der Geschäftspartner, der diesen Vertrag entworfen hat, heimlich eine fast identische Version besitzt die sich aber trotz gleicher Prüfsumme in der Höhe des Kaufpreises (und im unsichtbaren Füllstoff) unterscheidet.
Um so etwas zu verhindern, sollte man deshalb nach Möglichkeit die längeren, z.Zt. als sicher geltenden Versionen SHA256 oder größer verwenden.
Angriffe, in denen man Kollisionen zu bereits vorgegebenen Daten findet ("Pre-Image-Angriff") sind dagegen (noch) nicht bekannt, so dass die Sicherheit dieser Algorithmen für Passwortdateien oder zur Verifikation von Software-Paketen z.Zt. nicht zur Disposition steht. Es spricht natürlich trotzdem nichts dagegen, wenn man die Wahl hat auch für diese Zwecke die stärkeren SHA-Algorithmen zu nutzen.
Programme¶
Die Kommandozeilenbefehle md5sum, sha1sum, sha256sum usw. sind im Paket coreutils enthalten, das unter Ubuntu vorinstalliert ist. Bevorzugt man dagegen eine grafische Oberfläche, kann man das Programm GtkHash verwenden.
Links¶
MD5 RFC 🇬🇧