Hashing
Der Begriff Hashing (deutsch: zerhacken) bezeichnet die Transformation eines beliebig großen Datensatzes in eine Zeichenkette mit einer festen, kürzeren Länge, die den ursprünglichen Datensatz referenziert. Mittels einer Hashfunktion werden die einzelnen Elemente aus dem Datensatz zunächst einem Schlüssel und dann den Hashwerten zugeordnet, die die originalen Daten auf bestimmte Weise repräsentieren. Der Datensatz kann aus Zeichenfolgen, Listen, Dateien oder anderen Inhalten bestehen; die Schlüssel, die für diese Daten stehen, geben die Position der Elemente im Datensatz an, die mit ihnen durch Hashwerte verknüpft werden.
Die Hashfunktion bildet die Elemente des Datensatzes über einen Schlüssel ab und erzeugt Hashwerte. Beim Hashing werden die Daten in kleine Teile zerlegt und in einer Datenstruktur geordnet. Die Hashwerte erlauben es in Datenbanken beispielsweise, bestimmte Elemente weitaus schneller zu finden, weil nur die Datenstruktur, nicht der gesamte Datensatz durchsucht werden muss. Möchte man einzelne Daten finden oder verändern, muss nur die Struktur durchsucht werden – die eigentlichen Daten müssen nicht rekonstruiert werden.
Allgemeine Informationen zum Thema
Hashing kommt in unterschiedlichen Bereichen zum Einsatz, um den Umgang mit großen Datenmengen zu erleichtern und eine sichere digitale Kommunikation zu ermöglichen. Hashing wird beispielsweise verwendet:
- bei der Speicherung von großen Datenmengen in Datenbanken,
- bei Prüfsummen (engl.: checksums) zur Überprüfung der Integrität von Daten,
- in der Programmierung zur dynamischen Referenzierung von Programmbefehlen (assoziative Arrays),
- bei der Ver- und Entschlüsselung, um die Integrität und Authentizität von Nachrichten, Sendern und Empfängern zu gewährleisten.
Die Einsatzmöglichkeiten von Hashfunktionen und damit verknüpften Konzepten ist überaus vielfältig. Das Prinzip ist jedoch meist ähnlich: Daten werden transformiert und so weit verkürzt oder verändert, dass Speicherplatz gespart wird und der Zugriff auf „gehashte“ Datensätze schneller erfolgen kann.
In der Verschlüsselung haben Hashfunktionen zudem spezielle Eigenschaften, die es unmöglich machen, dass die Daten rekonstruiert werden, ohne über einen Schlüssel zu verfügen. Eine dieser Eigenschaften wird auch als kollisionsresistent bezeichnet: Es ist mit herkömmlicher Rechenleistung nicht durchführbar, die Hashfunktion zu entschlüsseln und die damit verknüpften Datensätze aufgrund von Übereinstimmungen zwischen Hashwerten und/ oder Datensätzen zu rekonstruieren. Dazu werden verschiedenste Operationen auf den Daten durchgeführt, etwa Vermengung, Verdichtung oder Vermischung. Angreifer dürfen die Daten nicht nachträglich entschlüsseln können.
Funktionsweise
Zur Verdeutlichung des Prinzips Hashing werden zwei wichtige Anwendungsfälle erklärt:
Hashing in Datenbanken
In Datenbanken wird Hashing eingesetzt, um Index- oder Datenstrukturen zu bilden. Diese Strukturen werden als Hashtabellen beschrieben, wobei die Einträge in der Hashtabelle mit Elementen aus den Daten über eine Funktion verbunden werden. Soll ein Eintrag in eine Datenbank eingefügt werden, erhält dieser durch die Hashfunktion einen Schlüssel. Der Schlüssel weist auf die Position in der Datenbank hin und erleichtert zum Beispiel die Suche nach dem Eintrag. Soll ein Eintrag entfernt werden, nutzt die Hashfunktion diesen Umweg, um den richtigen Eintrag zu finden und daraufhin zu löschen. Hashing in Datenbanken ist allerdings nur eine Variante, Daten zu organisieren und zu verwalten. Je mehr Einträge existieren, desto mehr Hashwerte müssen gebildet werden. Dabei steigt die Wahrscheinlichkeit von Kollisionen. Nur wenn die Hashtabelle in ihrem Umfang vergrößert und jeder Eintrag neu gehasht wird, können größer werdende Datenbanken auch mit Hashing verwaltet werden. So kommt Hashing in den Bereichen Business Intelligence, OLAP sowie Data Warehouse in den verschiedensten Varianten zum Einsatz.[1][2]
Beispiel
In einer Kundendatenbank können Kunden mit Namen, Adressen und anderen Parametern gespeichert werden. Die Suche nach einem beliebigen Kunden würde relativ viel Zeit in Anspruch nehmen, wenn die gesamte Datenbank durchsucht werden müsste: der Computer würde Zeichen für Zeichen nach einer Übereinstimmung suchen. Um dies zu verhindern, werden Datenblöcke gebildet, die als Schlüssel bezeichnet werden. Diese Schlüssel werden mittels Hashfunktion in Hashwerte übertragen. Jeder Kunde könnte beispielsweise alphabetisch oder anhand anderer Eigenschaften geordnet werden.
Die alphabetische Ordnung der Daten ist die Daten- oder Indexstruktur, die die Suche nach einem Eintrag vereinfacht. Der Computer springt bei einer Suchanfrage an einen Punkt in der Datenstruktur, weil er die Position durch den Hashwert kennt. Wenn die dort gefundene Information mit der Sucheingabe des Benutzers übereinstimmt, ist der Suchvorgang beendet. Andernfalls ist die Zuordnung nicht eindeutig oder es existiert kein Eintrag für die Sucheingabe.
Hashing in der Verschlüsselung
Bei der Verschlüsselung und der Entschlüsselung wird Hashing in Form von Hashing-Algorithmen verwendet. Digitale Dokumente wie Dateien verschiedenster Inhaltstypen (Text, Audio und visuelle Medien zum Beispiel) können als Folge von Nullen und Einsen beschrieben werden. Soll ein digitales Dokument gehasht werden, führen Informatiker unterschiedliche Operationen durch, um die Folge von Nullen und Einsen in eine wesentlich kürzere Folge von Nullen und Einsen mit fester Länge zu übertragen. Dazu werden die Informationen verändert und verdichtet, sodass sie identifiziert, aber nicht ohne Kenntnis des Schlüssels rekonstruiert werden können. Jedes Ergebnis einer Hashfunktion soll eindeutig mit einem Datensatz referenziert sein. Deshalb sind kryptologische Hashfunktionen idealerweise auch Einwegfunktionen: Die Zuordnung ist eindeutig und es kommt zu keinen Kollisionen. Wird nun eine Nachricht übermittelt, die einen eindeutigen Hashwert besitzt, können Sender und Empfänger die Integrität einer Nachricht überprüfen – die Tatsache, dass sie nicht von Dritten verändert wurde – und Sender und Empfänger können sich gegenseitig digital signieren, um festzustellen, ob die Nachricht beim Empfänger unverändert ankommt und von dem tatsächlichen Sender verschickt worden ist. Kryptologische Hashfunktionen besitzen spezifische Eigenschaften, die es praktisch unmöglich machen, aus einem Hashwert die Schlüssel und somit die Ursprungsinformation zu berechnen. Es kann sich demnach kein Dritter in die Nachrichtenübermittlung einklinken und mithören.[3]
Beispiel
Der MD5-Hashalgorithmus (Message-Digest Algorithm 5 )ist ein Ver- und Entschlüsselungsalgorithmus, der aus beliebig langen Zeichenketten (Strings) einen Hashwert erzeugt, der immer 128 Bit lang ist. Eine kleine Änderung eines Strings resultiert dabei in einem völlig anderen Hashwert.
- Der String „Heinrich Müller" wird übertragen in den Hashwert 6f9ba3588f545844f2eeeaa71d6e5ada
- „Jutta Weilert“ bekommt den Hashwert 93638fd8b5127c0ed5ec74549646b209
- „Super Hero“ erhält den Hashwert a98c85f741fc5d7194fd9e0b9add2230
- „Willkürliche Beispiele“ wird übersetzt in den Hashwert d4fd38d5ecf1359de8d795bf5c8b16ca[4]
MD5 Algorithmen gelten aktuell als nicht mehr sicher, wenn sie nicht durch weitere Verfahren (wie Salt zur Speicherung von Passwörtern) verfeinert werden.[5] Inwiefern Hashfunktionen sicher sind, hängt jedoch nicht nur davon ab, ob zwei Strings denselben Hash erzeugen (Kollision), sondern auch davon, welche Verfahren zur Integritäts- und Authentizitätsprüfung eingesetzt werden. Deshalb wird mittlerweile auch von Kryptosystemen gesprochen, statt von einzelnen Algorithmen oder Hashverfahren.
Bedeutung für die Programmierung
Hashing wird nicht nur in unterschiedlichen Bereichen der Informationstechnik und -sicherheit angewandt, sondern Hashing-Algorithmen existieren auch in den verschiedensten Ausführungen. Insbesondere in der Verschlüsselung werden verschiedene Hashing-Verfahren und Algorithmen verwendet, um die Sicherheit zu erhöhen. Prinzipiell ist das Maß an Sicherheit aber relativ: Kryptologen arbeiten ständig daran, die Sicherheit von Systemen zu erhöhen und Hacker sowie Cracker versuchen, Sicherheitslücken aufzudecken und die Funktionsweise der Algorithmen zu entlarven.[6] Wenn von sicheren Hashing-Algorithmen die Rede ist, beziehen sich derartige Aussagen immer nur auf den aktuellen Forschungsstand. Zudem ist die Wahl von Hashing-Algorithmen auch von der Rechenleistung und der beanspruchten Zeit zum Entschlüsseln abhängig. Für andere Anwendungen wie Datenbanken oder der Prüfung von übermittelten Daten können teilweise Algorithmen verwendet werden, deren Hashwerte deutlich kürzer sind als bei kryptologischen Hashverfahren.
Einzelnachweise
- ↑ Hashing (Zerhacken) openbook.rheinwerk-verlag.de. Abgerufen am 29.08.2016
- ↑ Algorithmen und Datenstrukturen: Hashverfahren cg.informatik.uni-freiburg.de. Abgerufen am 29.08.2016
- ↑ Hashfunktion itwissen.info. Abgerufen am 29.08.2016
- ↑ MD5-Hash erzeugen lemats.net. Abgerufen am 29.08.2016
- ↑ Passwort – Sicherer mit Hash und Salt datenschutzbeauftragter-info.de. Abgerufen am 29.08.2016
- ↑ An Illustrated Guide to Cryptographic Hashes unixwiz.net. Abgerufen am 29.08.2016