====== Hashfunktionen ======

Theorie:{{ :gf_informatik:daten_sca:gfif_hashing.pdf |Hashing}}

++++Lernziele|

Prüfungsrelevant ist alles, was in den Lektionen und Übungen behandelt wurde. Die Lernziele unten dienen als Gradmesser und sind nicht unbedingt komplett.

   * Erklären, was Hashes und Hash-Funktionen sind uns was die Idee hinter diesen ist.
   * Wichtigste Eigenschaften kennen von Hash-Funktionen.
   * Beispiele machen für einfache Hash-Funktionen.
   * Wissen, welcher Hash-Algorithmus heute der Standard ist.
   * Versch. Anwendungsbereiche kennen von Hash-Funktionen.
   * Sind Hash-Funktionen für das Verschlüsseln von Nachrichten geeignet? Warum (nicht)?
   * Hashes generieren mit Python.
   * Erklären, was eine Rainbow-Table ist, wie man sie erstellt, wie Hacker diese verwenden und wie man sich dagegen schützen kann.

++++

==== 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:

   1. 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.
   1. 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.
   1. 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.
   1. 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).
   1. 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:**

   1. Erkläre in eigenen Worten, wie Python-Dictionaries Hash-Tables verwenden.
   1. Warum können Kollisionen auftreten?
   1. 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:

{{youtube>b4b8ktEV4Bg?}}

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:
<code python>
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)
</code>

   * 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.
   1. Führe den Code von oben aus und stelle sicher, dass für `"Hello World!"` der richtige Hash erzeugt wird.
   1. Bestimme den SHA-256-Hash deines Vornamens.


=== Aufgabe 5: Rainbow-Tables ===

   1. Erkläre, was ist eine **Rainbow-Table** ist und wozu solche benutzt werden.
   1. 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.
   1. 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|

   1. siehe Slides
   1. Tabelle unten
   1. 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 ====

<nodisp 2>

++++Lösung Aufgabe 1|

<code python>
def hash_simple(cleartext):
    summe = 0
    for b in cleartext:
        summe = summe + ord(b)
    return summe % 16

print(hash_simple("ACDC"))
</code>

++++

++++Lösung Aufgabe 5|

<code python>
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,"|")
</code>

++++

</nodisp>