Hashfunktionen

Theorie: Slides

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.

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).

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

Fragen:

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

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:

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

1. Erkläre, was ist eine Rainbow-Table ist und wozu solche benutzt werden.
2. 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.
3. 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 gespeichert. U.a. hat sie folgenden Eintrag erbeutet: mail „gerdiderromantiker@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