Fortgeschrittene Algorithmen und Programmierung
Prof. Dr. Alexandra Mikityuk
HTW Berlin
Die Hacker laden die Datenbank mit allen Nutzern herunter. Was finden sie?
username | passwort
---------|---------
anna | sommer2024
bob | passwort123
carla | mein_kater_max
...Die Hacker haben jetzt alle Passwörter im Klartext. Sie probieren dieselben Logins auf Banking, E-Mail, Amazon — viele Leute nutzen ja dasselbe Passwort.
username | hash
---------|---------------
anna | 5e88489...d80f9
bob | 8d969ef...e7140
carla | 2cf24db...e6a8b
...Die Hacker sehen nur Hashes — Zahlensalat. Aus diesen können sie die echten Passwörter nicht zurückrechnen.
Ein Fingerabdruck für Daten. Du steckst Text rein → bekommst eine feste Zahl raus.
Immer derselbe Hash. "hallo" ergibt heute und morgen denselben Wert.
Hash ausrechnen: Mikrosekunden. Ein Computer macht Millionen pro Sekunde.
Hash → Original: geht nicht. Hash ist eine Einbahnstraße.
Das nennt man Avalanche-Effekt — eine Mini-Änderung wird zur Lawine.
SHA-256("Hallo Welt") → d6e3...8f2b
SHA-256("Hallo welt") → 9c4a...e1d7 // nur "W" zu "w"
SHA-256("Hallo Welt!") → 7b1c...3a05 // nur ein "!" angefügtWir wissen jetzt: aus jedem Text kommt am Ende eine Zahl raus. Aber wie würdet ihr selbst so eine Funktion in C schreiben?
Wir haben einen String wie "Hallo". Wir wollen eine Zahl daraus machen.
Wie würdet ihr das versuchen?
Wie kommt man von einem Buchstaben überhaupt zu einer Zahl? Können wir mit 'H' rechnen?
Und wenn wir die Zahlen aller Buchstaben hätten — wie würden wir sie zu einer Hash-Zahl kombinieren?
char ist eigentlich eine ZahlBevor wir Hashes selbst bauen, ein C-Trick, den ihr vielleicht bisher übersehen habt.
In C ist char technisch eine kleine Ganzzahl (1 Byte = 0-127 für ASCII). Ein „Buchstabe" ist nichts anderes als eine Zahl in Verkleidung.
'A' = 65 'a' = 97
'B' = 66 'b' = 98
'0' = 48 ' ' = 32
'9' = 57 '\n' = 10char c = 'a';
printf("%d\n", c);
// → 97 (die Zahl)
printf("%c\n", c);
// → a (als Zeichen)str[i] + 1 oder summe += str[i], rechnet C einfach mit dem ASCII-Wert. Das nutzen wir auf der nächsten Slide für unsere erste (sehr schlechte) Hash-Funktion.
Sieht in C harmlos aus — ist aber katastrophal als Krypto-Hash. Wir summieren die ASCII-Werte (s. vorige Slide) zu einer einzigen Zahl:
// "Schlechter" Hash: einfach die ASCII-Werte addieren
unsigned int bad_hash(char str[]) {
unsigned int hash = 0;
for (int i = 0; str[i] != '\0'; i++) {
hash += str[i]; // ASCII-Wert addieren
}
return hash;
}
bad_hash("abc"); // → 294 (= 97 + 98 + 99)
bad_hash("bac"); // → 294 ✗ KOLLISION!
bad_hash("cab"); // → 294 ✗ noch eineNiemals selbst eine kryptografische Hash-Funktion schreiben. Eine gute Hash zu bauen, hat 30 Jahre Forschung gekostet. Eure Aufgabe: eine bestehende Library richtig aufrufen.
Bevor wir SHA-256 in C aufrufen — eine Sache verstehen wir noch nicht.
echte_hash("Hi") → 32 Bytes
echte_hash(5 MB Buch) → 32 Bytes
Beides ergibt genau 32 Bytes. Wie?
Wie kann ein 5-MB-Input auf dieselbe Größe wie ein 2-Zeichen-Input eingedampft werden — ohne dass die Hashes gleich werden?
bad_hash überhaupt überlaufen?unsigned int hat in C nur Platz für eine begrenzte Zahl — typisch 4 294 967 295 (≈ 4,3 Mrd., also 2³² − 1). Mehr passt nicht rein.
Wir summieren aber immer weiter ASCII-Werte auf. Irgendwann ist der Platz alle → die Zahl wickelt sich um zurück auf 0 und zählt wieder hoch.
// Bei langem Text:
hash = 4 294 967 290
hash += 10;
// → 4 (statt 4 294 967 300)
// alles davor: verloren!Folge: bei einem 5-MB-Buch summieren wir Millionen Werte auf, überlaufen mehrfach, und am Ende ist die Zahl praktisch zufällig — aber schlecht zufällig. Eine richtige Hash-Funktion macht das nicht. Was kann sie anders machen?
Wie schafft SHA-256 es, aus einem 5-Zeichen-Wort UND aus einem 5-MB-Buch jeweils genau 256 Bit rauszuholen?
Wir haben einen kleinen Speicher (den State) — bei SHA-256 sind das 256 Bit. Der State wächst nicht, egal wie lang der Input ist.
Mit einem festen Anfangswert. Bei SHA-256 sind das 256 Bit, vorgegebene Zahlen.
Wild kombinieren: addieren, mischen, durcheinanderwerfen. Aus state + char wird neuer state.
Wenn alle Input-Zeichen durch sind, ist der State unser Hash.
Vereinfachte Hash-Funktion, die ihr auf Papier mitrechnen könnt. Idee wie SHA-256, nur viel kleiner.
a mod b = der Rest beim Teilen. In C: der %-Operator. Beispiel: 2337 mod 1000 = 337 → behält nur die letzten 3 Ziffern. Genau so bleibt unser State immer 3-stellig.
// State: eine Zahl von 0 bis 999
state = 0
// Für jeden Buchstaben:
state = (state × 31 + ASCII(c)) mod 1000Warum genau × 31 und mod 1000? → schauen wir auf der nächsten Slide an.
// 'H' hat ASCII 72
state = (0 × 31 + 72) mod 1000
state = 72
// 'i' hat ASCII 105
state = (72 × 31 + 105) mod 1000
state = 2337 mod 1000
state = 337
Hash("Hi") = 337Hash("OK") mit Bleistift. Tipp: 'O' = 79, 'K' = 75.
Unsere Formel: state = (state × 31 + ASCII(c)) mod 1000. Jeder Teil hat eine konkrete Aufgabe:
Was tut es? Multipliziert den alten State, bevor der neue Buchstabe drauf addiert wird. Das wirbelt den State durcheinander → die Reihenfolge der Buchstaben zählt (ohne den × würden "abc" und "cab" denselben Hash haben).
Warum eine Primzahl? Sie teilt nichts glatt → kein Muster beim Modulo. Bei × 10 hätten alle Hashes ähnliche Endziffern.
Warum gerade 31? Eigentlich beliebig — 7, 13, 31, 37 würden alle ähnlich funktionieren. Wir nehmen 31, weil Javas String.hashCode() es seit 30 Jahren tut: groß genug zum Mixen, klein genug, dass nicht sofort alles überläuft.
Hier kommt der neue Buchstabe in den State rein. Jeder Buchstabe verändert das Ergebnis — sonst wäre es ja keine Hash-Funktion vom Inhalt.
Die ASCII-Werte kennt ihr von der vorigen Slide: 'H' = 72, 'i' = 105.
Schneidet alles über 999 ab → State bleibt 3-stellig, egal wie lang der Input ist.
Genau diese feste Größe macht SHA-256 in groß — dort: 256 Bit statt 3 Ziffern.
× 31-Formel ist eine Lehrbuch-Vereinfachung — kein Krypto-Standard. Echte Hash-Funktionen wie SHA-256 nutzen keine simple Multiplikation, sondern komplexe Bit-Operationen (Rotation, XOR, viele Konstanten). Das Prinzip „State + pro Buchstabe mischen" ist aber dasselbe — nur die Misch-Mathematik ist bei SHA-256 viel ausgefuchster.
Mit derselben Mini-Hash rechnen wir drei ähnliche Wörter. Schaut, was passiert.
H (72) → 72
A (65) → 297
L (76) → 283
L (76) → 849
O (79) → 398H (72) → 72
A (65) → 297
L (76) → 283
L (76) → 849
I (73) → 392 // nur 6 andersB (66) → 66
A (65) → 111
L (76) → 517
L (76) → 103
O (79) → 272 // 126 anders!unsigned char hash[32] auf der nächsten Slide)Mit openssl/sha.h ist es fünf Zeilen. Kompilieren mit gcc datei.c -lcrypto.
#include <stdio.h>
#include <string.h>
#include <openssl/sha.h>
int main(void) {
char passwort[] = "sommer2024";
unsigned char hash[32]; // SHA-256 liefert 32 Bytes
SHA256((unsigned char *)passwort, strlen(passwort), hash);
// Hash als Hex-Zahlen ausgeben (jedes Byte → 2 Zeichen)
for (int i = 0; i < 32; i++) {
printf("%02x", hash[i]);
}
printf("\n");
return 0;
}
// Ausgabe: 5e88489dd80f9bc99b5e80f5b8df...unsigned char = ein einzelnes Byte (Werte 0-255). Hash ist Rohdaten, keine lesbaren Buchstaben.%02x bei printf = Zahl als Hex mit führender Null. 5 → 05, 255 → ff.(unsigned char *) = „OpenSSL erwartet eine Byte-Folge, kein char-Array — sind aber technisch dasselbe, daher der Cast."gcc datei.c -lcrypto · das -lcrypto verlinkt die OpenSSL-Library. Ohne das findet der Linker SHA256 nicht.
Die Webseite muss prüfen können, ob du das richtige Passwort eingibst — ohne dein echtes Passwort gespeichert zu haben.
So sieht die einfachste Variante aus — funktioniert, aber wir werden sie gleich kritisieren.
// --- vereinfacht: C-Details ausgelassen, Logik im Fokus ---
// Vergleicht eingegebenes Passwort mit dem gespeicherten Hash
verify_naiv(eingabe, gespeicherter_hash) {
// 1. Eingabe hashen
hash_neu = SHA256(eingabe);
// 2. Mit gespeichertem Hash vergleichen
return hash_neu == gespeicherter_hash;
}Sie haben eine Idee: vorberechnete Tabellen — Hashes von Millionen Standard-Passwörtern.
| Passwort | SHA-256 |
|---|---|
123456 | 8d969ef...e7140 |
passwort | e2c569be...da1d |
sommer2024 | 5e88489...d80f9 |
| … 1 Milliarde weitere … | … |
Wenn der Hacker den Hash 5e88489...d80f9 in der DB findet → er schaut nur nach. Passwort ist „sommer2024".
Das Problem ist klar: gleiche Passwörter → gleiche Hashes → ein Hacker baut eine Tabelle und schaut nach. Wie löst man das?
Anna und Bob nutzen beide das Passwort "sommer2024". In der DB stehen ihre Hashes nebeneinander — und beide sind identisch.
Wie könnten wir dafür sorgen, dass die zwei Hashes verschieden sind — obwohl das Passwort identisch ist?
Was müsste sich beim Hashen zwischen Anna und Bob unterscheiden, damit unterschiedliche Hashes rauskommen?
Und wenn wir was hinzufügen — woher nehmen wir das? Muss es geheim sein? Muss es bei jedem User gleich sein?
Für jeden User wird eine zufällige Zahl generiert (das Salt) — und vor dem Hashen ans Passwort angehängt.
// Anna registriert sich mit "sommer2024"
salt_anna = "X9q!2pZ" // zufällig generiert
hash_anna = SHA-256("sommer2024" + "X9q!2pZ") // → a3f5...c2d1
// Bob registriert sich auch mit "sommer2024"
salt_bob = "L#8mNqW" // anderes Salt!
hash_bob = SHA-256("sommer2024" + "L#8mNqW") // → 9b41...f78e
// Gleiches Passwort → KOMPLETT VERSCHIEDENE Hashes!Salt muss kryptografisch zufällig sein. Das ist wichtig — nicht jede Zufalls-Quelle taugt.
rand()srand(time(NULL));
int salt = rand(); // vorhersagbar!Ein Angreifer kennt den Sekunden-Zeitpunkt der Registrierung → kann das Salt nachrechnen.
RAND_bytes#include <openssl/rand.h>
unsigned char salt[16];
RAND_bytes(salt, 16);
// nutzt intern /dev/urandomrand(). Immer eine echte Zufalls-Quelle: OpenSSL (RAND_bytes), libsodium (randombytes_buf), oder direkt /dev/urandom.
| username | salt | hash |
|---|---|---|
anna | X9q!2pZ | a3f5...c2d1 |
bob | L#8mNqW | 9b41...f78e |
carla | k7Vp@3H | 7c2e...4b8a |
X9q!2pZ aus der DB.SHA-256("sommer2024" + "X9q!2pZ").Es gibt viele — aber für Passwörter sind die meisten nicht die richtige Wahl.
| Algorithmus | Für Passwörter? | Warum? |
|---|---|---|
| MD5 | ❌ NEIN | kaputt — Kollisionen bekannt, sekundenschnell zu knacken |
| SHA-1 | ❌ NEIN | seit 2017 als unsicher eingestuft |
| SHA-256 | ⚠️ Geht, aber… | zu schnell! Moderne GPUs probieren Milliarden Hashes/Sek |
| bcrypt | ✅ JA | absichtlich langsam — schützt vor Brute Force |
| Argon2 | ✅ JA (modern) | aktueller Sieger, gewinnt seit 2015 alle Wettbewerbe |
Klingt verkehrt. Der Trick liegt in der Asymmetrie zwischen Login-User und Angreifer.
Loggt sich einmal ein. Wartet 250 ms — merkt er gar nicht.
250 ms = ein viertel Wimpernschlag.
Probiert Milliarden Passwörter durch. Wenn jeder Versuch 250 ms dauert, dauert das Knacken plötzlich länger als ein Menschenleben.
In der Tabelle stand „absichtlich langsam — schützt vor Brute Force". Schauen wir mal, wer das gebaut hat und wie er das macht.
Eine Hash-Funktion, die nur für Passwörter entwickelt wurde. 1999 von Niels Provos & David Mazières für OpenBSD erfunden.
Genau wie SHA-256 nimmt sie Text + Salt rein und gibt einen Hash raus. Der Unterschied: sie tut das absichtlich langsam.
Ihr legt vorher fest, wie langsam sie sein soll — über den Parameter Cost:
| Hash | Brute-Force-Versuche/Sek (GPU) | 8-Zeichen-PW knacken |
|---|---|---|
| SHA-256 | ~ 10 Mrd. | ~ 16 Stunden |
| bcrypt (Cost 12) | ~ 40 | ~ 450 000 Jahre |
Auf Linux liefert crypt.h (aus libxcrypt) bcrypt direkt mit. Kein selbst-bauen, kein Pfusch.
#include <crypt.h>
#include <string.h>
// --- vereinfacht: Typ-Angaben weggelassen, alles als „String" denken ---
// Registrierung — Passwort hashen
setting = "$2b$12$abcdefghijklmnopqrstuv";
// │ │ └─ Salt (22 Zeichen base64)
// │ └──── Cost Factor (12 = 2^12 Runden)
// └──────── Algorithmus: bcrypt 2b
hash = crypt("sommer2024", setting);
// → "$2b$12$abcdefghijklmnopqrstuv9.l4f8...kCe2"
// in der DB speichern (komplett, inkl. Salt und Cost)
// Login — Passwort prüfen
check = crypt("sommer2024", stored_hash);
if (strcmp(check, stored_hash) == 0) {
printf("Login OK\n");
}"$2b$12$..."?
$2b$ = welcher Algorithmus (hier bcrypt Version 2b)$12$ = Cost Factor (2¹² = 4 096 interne Runden)gcc datei.c -lcrypt — -lcrypt verlinkt libxcrypt. Ohne das findet der Linker crypt nicht.
Wo ihr noch überall auf Hashes treffen werdet:
Beim Download zeigt eine Webseite oft den SHA-256-Hash an. Du rechnest ihn lokal nach → wenn er stimmt, kam die Datei unverändert an.
Jeder Bitcoin-Block hat den Hash des vorherigen drin. So entsteht die unveränderliche Kette (siehe VS-Vorlesungen 4/5).
Hash-Tabellen (kommen später) — der Schlüssel zu O(1)-Lookups in vielen Datenstrukturen.
Echte Beispiele — und was die Konsequenzen waren.
153 Millionen Accounts geleakt. Passwörter mit 3DES verschlüsselt (nicht gehasht!) — und der Schlüssel war auch in der Leak-Datei. Folge: alle Passwörter im Klartext lesbar.
117 Millionen Accounts. Passwörter mit SHA-1 ohne Salt. Innerhalb von Tagen waren 90% der Hashes geknackt — wegen Rainbow Tables.
Du kannst nicht steuern, wie die Webseite deine Passwörter speichert. Aber du kannst deinen Schaden begrenzen.
Nie dasselbe Passwort für mehrere Seiten. Wenn eine geleakt wird, sind sonst alle anderen Logins auch in Gefahr.
Bitwarden, 1Password, KeePass. Generieren lange Zufalls-Passwörter — du musst dir nur eines merken.
Zweiter Faktor (TOTP-App, Hardware-Key). Selbst wenn das Passwort weg ist, kommt niemand rein ohne Handy.
bcrypt oder Argon2. Niemals selbst „mal kurz" hashen.SHA-256(passwort) ohne Salt. Ist das sicher?bcrypt oder Argon2 — niemals MD5 oder SHA-1.Was ihr lesen solltet, wenn ihr tiefer einsteigen wollt:
openssl/sha.h, openssl/rand.h, openssl/hmac.hcrypt.h (bcrypt, yescrypt)crypto_pwhash (Argon2)Schönen Feierabend! 🌙
Prof. Dr. Alexandra Mikityuk
HTW Berlin · Büro Raum 308
Tel +49 30 5019-2664
Nächste Woche: Sicherheit II — Verschlüsselung