Hashfunktionen begegnet man überall, wo es darum geht, Zeichenketten (z.B. Nutzernamen oder Passwörter) oder beliebige Daten (z.B. Download – Archive) voneinander zu unterscheiden. Oft werden Hashs im Hintergrund gerechnet, ohne dass der User das sieht. Anders beim Download von Programmen über das Internet: Hier wird auf der Downloadseite oft ein Hashwert des Downloads (syn. Hash- oder Programm-„Signatur“) angegeben, damit man nach dem Herunterladen (und vor dem Starten des Programms) noch einmal prüfen kann, ob das Programm vollständig und unverändert geladen wurde. Hashfunktionen sind vor allem im Verborgenen unverzichtbar – sie übernehmen das Encoding/Decoding von Zeichenfolgen zu Hashtables, die der schnellen Zuweisung von Befehlen zu Codes im Kern der Programmiersprachen und beim Kompilieren dienen (Wer mehr dazu wissen will, findet hier einen Videomitschnitt vom 29. CCC-Kongress, der das Dilemma (Hash-Table Flooding) „schlechter“ Hashfunktionen verdeutlicht.
Das Berechnen des Hashwerts kann eine rechenintensive Aufgabe sein. Ein Hash-Algorithmus liest Daten schrittweise ein und verrechnet den Stream zu einem Hashwert, der je nach Güte und Art des Hashprogramms in einen „seltenen“ oder sogar „einzigartigen“ Zahlenwert besteht (oft im Hexadezimalformat ausgegeben).
Hashfunktionen allgemein werden nach der Länge des Ausgabewertes (Angabe in Bit) unterschieden, kryptologische Hashfunktionen liefern Hashs mit einer fixen Länge (z.B. SHA256->256Bits ; SHA512->512Bits) , andere Funktionen liefern Hashwerte bis zu einem Maximalwert.
Kryptologisch sichere Hashfunktionen sind unter anderem dahingehend optimiert, dass es keine – nicht einmal theoretische – Kollisionen gibt (Kollisionen sind gleiche Hashwerte für ungleiche Eingangsdaten). Außerdem sind die Algorithmen so gestaltet, dass zwei Eingaben, die sich nur sehr geringfügig unterscheiden, bereits stark unterschiedliche Hashergebnisse (Signaturen) ergeben. Dabei ist es wichtig, dass der Rechenweg so konzipiert ist, dass sie sogenannte „Einwegfunktionen“ darstellen und vom Hash nicht auf die Eingabedaten zurück gerechnet werden kann. Will man also von einer kryptologischen Signatur auf den Eingabewert zurückschließen, so ginge dies nur, wenn man eine Tabelle mit allen möglichen Eingabewerten und zugehörigen Hash-Ausgaben hat. Liegen solche Tabellen (z.B. „Rainbow-Tables“ für Strings in typischer Passwortlänge) einmal vor, so ist diese Hashfunktion natürlich nicht mehr sicher und sollte im sicherheitsrelevanten Zusammenhängen – zum Beispiel fürs Speichern von Passwörtern – nicht weiter benutzt werden: MD5, SHA-1; Weiteres siehe: https://de.wikipedia.org/wiki/Kryptologische_Hashfunktion ).
Erwähnenswert: Zu den ganz neuen kryptologischen Hashfunktionen gehören BLAKE2s (32 Bit Maschinen) und BLAKE2b (64 Bit Maschinen) https://blake2.net, die Jean-Philippe Aumasson et al. unter Verwendung von Daniel Bernsteins ChaCha Code entwickelt haben. Blake2 Hashfunktionen sind so schnell wie MD5 oder SHA-1, im Unterschied zu vorgenannten sind sie jedoch (derzeit) kryptologisch sicher.
Nicht kryptologische Hashfunktionen
Im Gegenzug sind aufgrund zusätzlicher Rechenschritte kryptologische Hashfunktionen vergleichsweise langsamer als nicht kryptologische Hashfunktionen (Faktor 30x-300x). Für die Verarbeitung nicht sicherheitsrelevanter Daten, bei denen kryptologische Eigenschaften des Hashs keine Rolle spielen, werden darum einfachere (= schnellere) Hashfunktionen eingesetzt. Eventuell ist auch Kollisionsfreiheit weniger wichtig als Geschwindigkeit oder das Risiko von Kollisionen wird verringert, indem mehrere (zwei +) Hashs mit verschiedenen schnellen, aber nicht kollisionssicheren Hashfunktionen berechnet und kombiniert werden. Trotzdem speilt Kollisionssicherheit eine grosse Rolle und die neuesten Hash-Algorithmen punkten hier deutlich.
0815 Nutzen: Hashen jenseits von Passwort/Nutzernamen
Nehmen wir an, eine Reihe Bilder, die sich eventuell nur um den Farbwert einzelner Pixel unterscheiden, sollen daraufhin geprüft werden, ob sie exakt einer Referenz (Original) entsprechen. Ein „naiver“ Ansatz wäre, jedes der Bilder Pixel für Pixel mit der Referenz zu vergleichen. Geht es aber nur darum festzustellen, ob sich die Bilder von der Referenz unterscheiden, so ist die Verwendung eines Hashes die effektivere Lösung.
Erstelle einen Hash der Referenz
Für jedes Bild
erstelle einen Hasch
vergleiche den Bild-Hash mit dem Referenz-Hash
gib zurück: gleich / ungleich
Habe ich einen schnellen Hash-Algorithmus so kann ich die Vergleichsdaten auch in Segmente unterteilen und dann die Segment-Hashs untersuchen und vergleichsweise resourcen-sparsam und schnell Unterschiede lokalisieren.
Erstelle einen Hash der Referenz
Für n-Segmente der Referenz
erstelle je einen Referenz-Segment-Hash
Für jedes Bild
erstelle einen Hasch
vergleiche den Bild-Hash mit dem Referenz-Hash
wenn ungleich
für n-Segmente des Bildes
erstelle Bild-Segment-Hash
vergleiche Bild-Segment-Hash mit Referenz-Segment-Hash
gib zurück: ungleiche Segmente
Statt ganze Bilder, Pixel für Pixel mit einer Referenz zu vergleichen, ist dann nur noch ein Vergleich der Segmente, die ungleiche Hashwerte hatten, nötig, um unterschiedliche Pixel exakt zu lokalisieren.
Welche Hashfunktion ist die richtige für meinen Zweck
Viele Hashfunktionen sind optimiert für die schnelle Verarbeitung großer Datenmengen. Das geschieht z.B. durch die Verarbeitung von Byte-Gruppen in einem Durchgang. Dass die Hashrechnung selbst etwas aufwendiger ist, fällt dabei dann weniger ins Gewicht, als bei Funktionen, die einen Stream/String Byte für Byte verrechnen. In der Gegenüberstellung zu Googles xxHash http://code.google.com/p/xxhash/ finden sich Vertreter dieses (neueren) Hashtyps auf den oberen sechs Plätzen der Rankingtabelle. Siehe auch hier: http://brainspec.com/blog/2012/10/29/fast-hashing-with-cityhash/ Zur Entwicklung von Hashfunktionen neueren Typs, die bei großen Datenmengen auch die Möglichkeiten aktueller Prozessoren zur parallelen Berechnungen ausnutzen: http://web.stanford.edu/class/ee380/Abstracts/121017-slides.pdf
Für eine Aufgabe, wie die oben geschilderten Vergleiche von Bilddateien, können diese „modernen“ hochperformanten Hashfunktionen gut geeignet sein. Wenn man allerdings nur kurze Strings hashen muss (z.B. IP-Adressen oder Log-Einträge) und ohnehin nur 32Bit oder 64Bit Ergebnisse braucht, waren die Hash-Funktionen 2. und 3. Generation bei meinen eigenen Benchmarks allesamt langsamer als SDBM, FNV oder DJB2, da die Byte-Gruppen-Verarbeitung einen recht großen Overhead (Initialisierung, Finalisieren) mitbringt.
Schnelle, nicht kryptologische Hashfunktionen
Im Folgenden eine Liste mit Links zu verschiedenen Webseiten, die sich mit Hash-Berechnungen beschäftigen:
FNV-Hash Family http://www.isthe.com/chongo/tech/comp/fnv/index.html based on prime calculations.
Bob Jenkins Sites http://burtleburtle.net/bob/
Hash-/Block-Cipher http://burtleburtle.net/bob/hash/index.html
lookUP3 http://burtleburtle.net/bob/c/lookup3.c
SpookyhashV2 (2012) http://burtleburtle.net/bob/hash/spooky.html
und Grundlagen: http://burtleburtle.net/bob/hash/integer.html Integer Hashes mit verschiedenen Beispielen.
Pearson Hash mit random Hashtable (klassisches BASIC) http://burtleburtle.net/bob/hash/pearson.html
Arash Partow Zusammen-&Gegenüberstellung klassischer Hashfunktionen http://partow.net/programming/hashfunctions/index.html
Die Seite diskutiert verschiedenste Hashfunktionen und erlaubt den Download in verschiedenen Programmiersprachen z.B. CPP oder Python:
// citation: An algorithm proposed by Donald E. Knuth in The Art Of Computer Programming Volume 3,
// under the topic of sorting and search chapter 6.4.
def DEKHash(key):
hash = len(key);
for i in range(len(key)):
hash = ((hash << 5) ^ (hash >> 27)) ^ ord(key[i])
return hash
DEKHash in Go:
func (bl Bloom) DEKHash(b *[]byte) (hash uint64) {
hash := uint64(len(*b))
for _, c := range *b {
hash = ((hash << 5) ^ (hash >> 27)) ^ uint64(c)
}
return hash
}
http://www.cse.yorku.ca/~oz/hash.html – DJB2 und SDBM-Hash Funktionen in C
Google-Code Seiten
http://code.google.com/p/cityhash/ CityHash
http://code.google.com/p/xxhash/ xxHash und ein Benchmarking verschiedener Hash-Funktionen: xxHash, cityHash, lookUp3, SpookyHash2, Murmur3, FNV …
Eine ausführliche Diskussion verschiedener Hashfunktionen mit vielen Links findet sich auch hier:http://blog.reverberate.org/2012/01/state-of-hash-functions-2012.html