Hashfunktionen

Theorie:Hashing

Lernziele

Aufgaben

Aufgabe 1: Einfache Hash-Funktion

Implementiere die einfache (und nicht sehr brauchbare) Hash-Funktion aus den Slides:

Schreibe eine Funktion hash_simple(cleartext), …
… die einen String cleartext entgegen nimmt und darauf den folgenden …
- … Hash-Algorithmus anwendet:
  - Summiere von allen Zeichen von Strings die ASCII-Werte zusammen …
  - … und rechne das Resultat $% 16$
  - Resultat ist eine Zahl im Bereich $0,1,...,15$
- Berechne den Hash deines Vornamens.

Aufgabe 2: Eindeutigkeit von Hashes

Hashes sind nicht eindeutig, da immer unendlich viele Klartext-Nachrichten den gleichen Hash produzieren. Doch ist dies in Realität ein Problem? Dies hängt davon ab, was die Länge eines Hashes ist: je länger der Hash, desto unwahrscheinlicher ist es, dass zwei Klartext-Nachrichten den gleichen Hash erzeugen. Analysiere diese Wahrscheinlichkeit für einen $256-$Bit Hash (z.B. SHA-2).

Aufgabe 3: Hash-Tables & Dictionaries

Wir haben gelernt, dass in Python-Dictionaries mithilfe von Hashes der Speicherort des Value eines Key:Value-Paares berechnet wird. Studiere die Theorie unten zu Hash-Tables, die genauer erklärt, wie das funktioniert. Beantworte dann die Fragen unten.

Hash-Tables

Ein Hash-Table, auch als Hash-Map bezeichnet, ist eine Datenstruktur, die Schlüssel-Wert-Paare speichert. Sie bietet effiziente Einfüge-, Lösch- und Abrufoperationen. Die grundlegende Idee hinter einem Hash-Table besteht darin, eine Hash-Funktion zu verwenden, um einen Schlüssel in einen Index in einem Array umzuwandeln, an dem der entsprechende Wert gespeichert wird.

Hier ist, wie es funktioniert:

Hash-Funktion: Eine Hash-Funktion nimmt einen Schlüssel als Eingabe und berechnet mithilfe eines Hash-Algorithmus einen Hash-Code, der eine numerische Darstellung des Schlüssels ist. Der Hash-Code ist in der Regel eine ganze Zahl.
Array: Der Hash-Table verwendet ein Array, um die Schlüssel-Wert-Paare zu speichern. Die Größe des Arrays wird in der Regel im Voraus festgelegt, kann aber bei Bedarf dynamisch angepasst werden.
Index-Berechnung: Der Hash-Code wird verwendet, um den Index zu berechnen, an dem der Wert im Array gespeichert wird. Dies geschieht durch Anwendung einer Modulo-Operation auf den Hash-Code mit der Größe des Arrays. Das Ergebnis der Modulo-Operation liefert den Index.
Umgang mit Kollisionen: Da die Anzahl der möglichen Schlüssel in der Regel größer ist als die Größe des Arrays, ist es möglich, dass zwei unterschiedliche Schlüssel denselben Index erhalten, der durch die Hash-Funktion berechnet wird. Dies wird als Kollision bezeichnet. Es gibt verschiedene Techniken zur Bewältigung von Kollisionen, wie z.B. Chaining (Verwendung von verketteten Listen oder Arrays zum Speichern mehrerer Werte mit demselben Index) oder offenes Adressieren (Suchen eines alternativen Indexes, wenn eine Kollision auftritt).
Speichern und Abrufen: Um ein Schlüssel-Wert-Paar zu speichern, wird die Hash-Funktion auf den Schlüssel angewendet, um den Index zu berechnen. Der Wert wird dann an diesem Index im Array gespeichert. Beim Abrufen eines Werts wird die Hash-Funktion auf den Schlüssel angewendet, um den entsprechenden Index zu finden, und der Wert wird von diesem Index abgerufen.

Hash-Tables ermöglichen einen schnellen Zugriff auf Werte basierend auf Schlüsseln, da die Zeitkomplexität für Einfügen, Löschen und Abrufen in der Regel durchschnittlich $O(1)$ (konstanter Zeitaufwand, also unabhängig von Datengrösse) beträgt, vorausgesetzt, dass eine gute Hash-Funktion und eine geringe Kollisionsrate vorliegen. Im schlimmsten Fall, wenn viele Kollisionen auftreten, kann sich die Zeitkomplexität auf $O(n)$ (linearer Zeitaufwand, also: doppelt so viele Daten, dauert doppelt so lange) verschlechtern, wobei $n$ die Anzahl der Elemente im Hash-Table ist.

Hash-Tables werden aufgrund ihrer effizienten Suche und Speicherung für Datenbanken oder Dictionaries in Python verwendet.

Fragen:

Erkläre in eigenen Worten, wie Python-Dictionaries Hash-Tables verwenden.
Warum können Kollisionen auftreten?
Wie verändert sich die Zugriffszeit in Python-Dictionaries, wenn sich der Datensatz verdoppelt?

Aufgabe 4: SHA-2 in Python

Der heutige Standard-Algorithmus ist SHA-2 (Secure Hash Algorithm 2). Für viele Jahre war MD5 (Message-Digest Algorithm 5) der Standard, mittlerweile ist aber bekannt, dass dieser unsicher ist. Schaue dir dazu dieses Video an:

Der SHA-2 Algorithmus nimmt zum Beispiel einen String, genannt 'Key', als Input und wandelt diesen in einen Hash um, Hexzahl mit einer fixen Länge (typischerweise 256 Bit) um. Verändert man auch nur einen einzigen Buchstaben im String, resultiert am Schluss ein komplett anderer Hash. Natürlich kann man den Hash nicht zurück in den Key umwandeln, da unendlich viele Keys den gleichen Hash erzeugen.

Erwartet man zum Beispiel eine wichtige Nachricht, von der man den korrekten Hash kennt, so kann man bei Erhalt der Nachricht selbst den Hash berechnen und mit dem korrekten vergleichen. Stimmen die beiden überein, kann man sich sehr sicher sein, dass man die Nachricht korrekt empfangen hat und diese nicht von jemandem manipuliert wurde.

Mit Python kannst du ganz einfach den Hash eines Keys generieren:

import hashlib
 
key = "Hello World!"
 
# Convert the string to bytes as hashlib functions expect bytes input
string_bytes = key.encode('utf-8')
 
# Create a SHA-256 hash object,
# different variants are:  hashlib.sha256(), hashlib.sha224(), hashlib.sha384() or hashlib.sha512()
sha2_hash = hashlib.sha256()
 
# Update the hash object with the string bytes
sha2_hash.update(string_bytes)
 
# Get the hexadecimal representation of the hash digest
hash_result = sha2_hash.hexdigest()
print(hash_result)

Für den String "Hello World!" ist der Hash $$\text{7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069}$$
Ändern wir den String minimal ab zu "Hello world!", so ändert sich der Hash komplett und zwar zu $$\text{c0535e4be2b79ffd93291305436bf889314e4a3faec05ecffcbb7df31ad9e51a}$$

Aufgabe:

Theorie oben studieren.
Führe den Code von oben aus und stelle sicher, dass für "Hello World!" der richtige Hash erzeugt wird.
Bestimme den SHA-256-Hash deines Vornamens.

Aufgabe 5: Rainbow-Tables

Erkläre, was ist eine Rainbow-Table ist und wozu solche benutzt werden.
Erstelle eine solche Rainbow-Table für die zehn sehr beliebten Passwörter unten mit SHA-256. Tipp: Verwende die Passwort-Liste anstelle Copy-Paste.
Hanna die Hackerin hat die Datenbank von www.feldwaldwiesenshop.ch gehackt. Zum Glück (resp. Pech für Hanna) werden die Passwörter darin nicht im Klartext sondern als Hashes (aber ohne Salt) gespeichert. U.a. hat sie folgenden Eintrag erbeutet: mail „gerryderromantiker@bluewin.ch“, PW-Hash: „e4ad93ca07acb8d908a3aa41e920ea4f4ef4f26e7f86cf8291c5db289780a5ae“. Was kann Hanna nun damit machen?

Liste sehr beliebter Passwörter:

123456
qwertz
password
admin
a1b2c3
iloveyou
football
monkey
abc123
guest

als Liste: ["123456","qwertz","password","admin","a1b2c3","iloveyou","football","monkey","abc123","guest"]

Lösungen

siehe Slides
Tabelle unten
Hash kommt in deiner Rainbow-Table vor, Hanna kann damit einfach Passwort im Klartext ermitteln und sich so in Gerrys Account einloggen. Die Wahrscheinlichkeit ist gross, dass er das gleiche Passwort auch für andere Accounts verwendet. Hanna kann also das Login für verschiedene Websites (z.B. bluewin.ch) ausprobieren.

Password	Hash
123456	8d969eef6ecad3c29a3a629280e686cf0c3f5d5a86aff3ca12020c923adc6c92
qwertz	d482ba4b7d3218f3e841038c407ed1f94e9846a4dd68e56bab7718903962aa98
password	5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8
admin	8c6976e5b5410415bde908bd4dee15dfb167a9c873fc4bb8a81f6f2ab448a918
a1b2c3	4f32044a655f32e8528edea64dbfd11cba810b8790e6e6e23d28ad3a75980734
iloveyou	e4ad93ca07acb8d908a3aa41e920ea4f4ef4f26e7f86cf8291c5db289780a5ae
football	6382deaf1f5dc6e792b76db4a4a7bf2ba468884e000b25e7928e621e27fb23cb
monkey	000c285457fc971f862a79b786476c78812c8897063c6fa9c045f579a3b2d63f
abc123	6ca13d52ca70c883e0f0bb101e425a89e8624de51db2d2392593af6a84118090
guest	84983c60f7daadc1cb8698621f802c0d9f9a3c3c295c810748fb048115c186ec

Aufgabe 6: Hash von Buch

Finde heraus, wie man von einem ganzes Buch (z.B. die Bibel) einen Hash berechnen kann. Da ein Buch aus vielen Zeichen besteht, kann man es nicht in einem Durchgang hashen, sondern man muss dies in vielen kleinen 'Chunks' machen.

Lösungen

Lösung Aufgabe 1

def hash_simple(cleartext):
    summe = 0
    for b in cleartext:
        summe = summe + ord(b)
    return summe % 16
 
print(hash_simple("ACDC"))

Lösung Aufgabe 5

import hashlib
 
def hash_sha256(key):
    # Convert the string to bytes as hashlib functions expect bytes input
    string_bytes = key.encode('utf-8')
 
    # Create a SHA-256 hash object,
    # different variants are:  hashlib.sha256(), hashlib.sha224(), hashlib.sha384() or hashlib.sha512()
    sha2_hash = hashlib.sha256()
 
    # Update the hash object with the string bytes
    sha2_hash.update(string_bytes)
 
    # Get the hexadecimal representation of the hash digest
    hash_result = sha2_hash.hexdigest()
    return hash_result
 
passwords = ["123456","qwertz","password","admin","a1b2c3","iloveyou","football","monkey","abc123","guest"]
 
print("^ Password ^ Hash ^" ) # header for wiki table
 
for pw in passwords:
    ha = hash_sha256(pw)
    print("|",pw,"|",ha,"|")