EineHashfunktion oderStreuwertfunktion ist eineAbbildung, die eine großeEingabemenge, dieSchlüssel, auf eine kleinereZielmenge, die Hashwerte, abbildet. Eine Hashfunktion ist daher im Allgemeinen nichtinjektiv. Die Eingabemenge kann Elemente unterschiedlicher Längen enthalten, die Elemente der Zielmenge haben dagegen meist eine feste Länge.

Der NameHashfunktion stammt vom englischen Verbto hash, das sich mit „zerhacken“ übersetzen lässt. Der deutsche Name lautetStreuwertfunktion. Beide Namen deuten darauf hin, dass diese Funktionen normalerweise darauf angelegt sind, die Daten zu „verstreuen“ und zu „zerhacken“ (siehe auchZerhacker in der Funktechnik). Speziell in der Informatik verwendet man auch den BegriffHash-Algorithmus (englischhash algorithm), da Hashfunktionen oftmals in Form einesAlgorithmus spezifiziert werden, der die Berechnung dermathematischen Funktion beschreibt.

Die Hash- oder Streuwerte sind meistskalare Werte aus einer begrenzten Teilmenge dernatürlichen Zahlen. Eine gute Hashfunktion liefert dabei für die Eingabedaten Werte derart, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen.

Eine Kollision tritt dann auf, wenn unterschiedlichen Eingabedaten derselbe Hashwert zugeordnet wird. Da die Menge der möglichen Hashwerte meist kleiner ist als die der möglichen Eingaben, sind solche Kollisionen dann prinzipiell unvermeidlich, weshalb es Verfahren zur Kollisionserkennung geben muss. Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt. Für bekannte und beschränkte Eingabemengen können auchperfekte (kollisionsfreie) Hashfunktionen gefunden werden.

In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen, z. B. in einerHashtabelle. BeiPrüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen. Ein Hashwert wird deshalb auch alsenglischFingerprint bezeichnet, da er einenahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt, so wie einFingerabdruck einen Menschen nahezu eindeutig identifiziert. In derKryptologie werden speziellekryptographische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden.

Eine Abbildung${\displaystyle h:K\to S}$ heißtHashfunktion, wenn${\displaystyle |K|\ge |S|}$ gilt. Insbesondere liefert${\displaystyle h}$ eineHashtabelle der Größe${\displaystyle |S|}$. Die Menge${\displaystyle K}$ repräsentiert die Daten, diegehasht werden sollen, und wird auch die Menge der Schlüssel genannt; die Menge${\displaystyle S}$ ist die Menge der möglichen Hashwerte. Typischerweise wird die Menge der Hashwerte als Anfangsstück der natürlichen Zahlen gewählt:${\displaystyle S\subseteq \left\{0,\dots ,m-1\right\}}$. Diese Menge heißt dann auchAdressraum.

Typischerweise wird in der Praxis immer nur eine kleine Teilmenge der Schlüssel${\displaystyle K^{\prime }\subseteq K}$ mit${\displaystyle h}$ abgebildet. Die Menge${\displaystyle S^{\prime }:=\{h(k)|k\in K^{\prime }\}}$ sind dann die tatsächlich genutzten Hashwerte.

Das Verhältnis${\displaystyle \beta =\frac{\left|S^{\prime }\right|}{\left|S\right|}}$ liefert den Belegungsfaktor.

Der Fall${\displaystyle k\ne k^{\prime }\wedge h(k)=h(k^{\prime })}$ wird als Kollision bezeichnet. Eineinjektive Hashfunktion heißt perfekt, u. a. weil sie keine Kollisionen erzeugt.

• Geringe Wahrscheinlichkeit von Kollisionen der Hashwerte für den Eingabewertebereich, also möglichst eineGleichverteilung der Hashwerte auf die erwarteten Eingabewerte.
• Surjektivität – Kein Ergebniswert (Hashwert) soll unmöglich sein, jedes Ergebnis (jeder Hashwert im definierten Wertebereich) soll tatsächlich vorkommen können.
• Effizienz – Die Funktion muss schnell berechenbar sein, ohne großen Speicherverbrauch auskommen (der Speicherbedarf des Hashwertes soll deutlich kleiner sein als jener des Schlüssels / Eingabewertes) und sollte die Quelldaten (Eingabewerte) möglichst nur einmal lesen müssen.

Folgende Kriterien spielen je nach Anwendung eine unterschiedliche Rolle:

• falls die Hashfunktion einensortierten Zugriff in der Hashtabelle einer Datenbank erlauben soll:ordnungserhaltend
• bei kryptologischen Hashfunktionen:Chaos oderLawineneffekt – Die Hashfunktion soll eine guteDiffusion besitzen; ähnliche Quellelemente (Eingabewerte) sollen zu völlig verschiedenen Hashwerten führen. Im Idealfall verändert das Umkippen einesBits in der Eingabe durchschnittlich die Hälfte aller Bits im resultierenden Hashwert.
• bei kryptologischen Hashfunktionen:Konfusion – Vom Hashwert sollen keine Rückschlüsse auf den Eingabewert gemacht werden können.
• bei kryptologischen Hashfunktionen:Unumkehrbarkeit – Es soll kein praktisches Verfahren möglich sein, das aus einem Hashwert den Eingabewert bestimmt.

Hashfunktionen werden typischerweise angewendet, um

• einem komplexen Objekt eineSpeicheradresse zuzuweisen. Zum Beispiel könnte „Max Mustermann“ im Ordner M abgelegt werden, dem ersten Buchstaben des Nachnamens.
• eine kurzePrüfsumme zu dem Objekt zu berechnen. Beispiel sind die Prüfsumme einerISBN und diezyklische Redundanzprüfung zur Erkennung von Übertragungsfehlern von Dateien.
• einen Inhalt nahezu eindeutig, aber mit wenigSpeicherplatz zu identifizieren, ohne etwas über den Inhalt zu verraten, zum Beispiel in derKryptographie.

Je nach Anwendung hat man unterschiedliche Anforderungen an die Funktion. Gruppiert man beispielsweise eine Adresskartei nach dem ersten Buchstaben des Nachnamens, so spart man sich offensichtlich bei der Suche viel Zeit, denn man braucht nur einen von 26 Teilen zu durchsuchen. Diese Hashfunktion ist für den Menschen sehr praktisch, da sie sehr einfach zu berechnen ist, jedoch würde ein Computerprogramm andere Verfahren verwenden, um ein Adressbuch zu organisieren. Für das Programm ist es nämlich wichtig, möglichst wenige Kollisionen zu haben. Es gibt aber offenbar viele Namen, die mit demselben Anfangsbuchstaben beginnen, und sie kommen ungleichmäßig oft vor. Legt man also beispielsweise Personalakten nach diesem Prinzip ab, so hat man oftmals viele Akten im Ordner mit dem Buchstaben S, während der Ordner Q leer bleibt.

Dieeinstellige Quersumme ist eine sehr einfache Hashfunktion. Sie ordnet einer beliebigen Zahl eine einstellige Zahl zu, so wird beispielsweise 25 auf 2 + 5 = 7 abgebildet. Als Prüfsumme ist diese Quersumme aber nicht gut geeignet, da die Vertauschung von Ziffern – ein typischer Fall beim Abtippen von langen Zahlen – nicht erkannt wird. So hat auch die Zahl 52 dieselbe Quersumme 5 + 2 = 7. Prüfsummen wie bei der ISBN eines Buches oder dieCRC-32-Prüfsumme einer Datei, z. B. beim Prüfen einer aus dem Internet heruntergeladenen Datei auf Übertragungsfehler, eignen sich besser, derartige Fehler zu erkennen.

Bei der Identifikation von Inhalten mitkryptographischen Hashfunktionen ist es nicht nur wichtig, dass sich der gesamte Hashwert mit allen Bits bei jeder kleinen Modifikation scheinbar zufällig ändert und dass es fast unmöglich ist, einen zweiten Inhalt mit demselben Hashwert zu erzeugen, um einen Komplettaustausch des Inhaltes zu vermeiden. Ebenso wichtig ist es, dass der Inhalt nicht aus dem Hashwertrekonstruiert werden kann. Hat man zwei Dokumente ausgetauscht und möchte beispielsweise am Telefon die erfolgreiche Übertragung überprüfen, so reicht es, am Telefon die Korrektheit des Hashwertes zu überprüfen. Wird das Gesprächabgehört, so wird dabei nichts über den Inhalt der Nachricht verraten, selbst falls Teile des Inhalts bereits bekannt sein sollten.

Datenbankmanagementsysteme verwenden Hashfunktionen, um Daten in großen Datenbeständen mittelsHashtabellen zu suchen. Darüber wird einDatenbankindex realisiert.

Mittels Hashfunktionen kann zudem dieFragmentierung von Datensätzen realisiert werden. Dabei wird die Hashfunktion auf denPrimärschlüssel des betreffenden Objektes angewandt. Das Ergebnis referenziert dann seinen Speicherort.

Auch für vergleichsweise kleine Datenmengen werden Hashfunktionen benutzt, beispielsweise inKompressionsalgorithmen wieLZW.

Prüfsummen sind ein einfaches Mittel, um die Plausibilität zur Erkennung von Veränderungen an übertragenen Daten zu erhöhen. Nur die Teilmenge der Datenvarianten, die bei Berechnung der Prüfsumme das gleiche Ergebnis wie das der Original-Daten erzeugen, kann noch als Verfälschung unerkannt bleiben. Mit mehreren verschiedenen passend erzeugten Prüfsummen kann die Wahrscheinlichkeit einer Kollision stark reduziert werden.

Ein Fehler ist immer feststellbar, wenn die berechnete Prüfsumme der empfangenen Daten sich von der übertragenen Prüfsumme, also der der Originaldaten, unterscheidet. Falls ein Fehler festgestellt wird, kann die Verfälschung auch ausschließlich in der Prüfsumme enthalten sein. Die Eignung verschiedener Hashfunktionen zur Prüfsummenberechnung hängt von deren Kollisionswahrscheinlichkeit ab.

Wenn die Prüfsumme vor gezielten Manipulationen der Daten schützen soll, wird einekryptographische Hashfunktion verwendet, da hier nur mit sehr hohem Rechenaufwand eine Kollision gefunden werden kann.

Hashwerte haben unter anderem beiP2P-Anwendungen aus verschiedenen Gründen eine wichtige Aufgabe. Die Hashwerte werden hier sowohl zum Suchen und Identifizieren von Dateien als auch zum Erkennen und Prüfen von übertragenen Dateifragmenten verwendet. So lassen sich große Dateien zuverlässig in kleinen Segmenten austauschen.

Zur Anwendung in P2P-Netzen kommen vor allem gestufte Hashfunktionen, bei denen für kleinere Teile einer Datei der Hashwert und dann aus diesen Werten ein Gesamtwert berechnet wird. Bei den NetzwerkenG2 undDirect Connect sind dies zum BeispielTiger-Tree-Hash-Funktionen.

Das Auffinden von Dateien anhand des Hashwertes ihres Inhaltes ist zumindest in den USA als Softwarepatent geschützt. Der Inhaber verfolgt Programme und Firmen, die auf Basis dieses Systems die Suche von Dateien ermöglichen. Sogar Firmen, die im Auftrag derRecording Industry Association of America oder derMotion Picture Association Anbieter von unlizenzierten Inhalten ermitteln wollen, sind betroffen.

Bei der Programmierung von Internet-Anwendungen werden Hashfunktionen zum Erzeugen vonSession-IDs genutzt, indem unter Verwendung von wechselnden Zustandswerten (wie Zeit, IP-Adresse) ein Hashwert berechnet wird.

Kryptographische Hashfunktionen sindkollisionsresistenteEinwegfunktionen. Diese Eigenschaften sind notwendig fürkryptographische Anwendungszwecke wie beispielsweise die Sicherstellung derIntegrität von Daten. Weitere Anwendungsbeispiele sinddigitale Signaturverfahren oderSchlüsselableitung. Bei letzterem wird aus einemPasswort ein Hashwert erzeugt, der entweder der sicheren, unumkehrbaren Speicherung von Passwörtern dient oder alsSchlüssel für ein Verschlüsselungsverfahren verwendet wird.

In der Praxis können oftheuristische Techniken angewendet werden, um eine gute Hashfunktion zu erstellen. Qualitative Informationen über die Verteilung der Schlüssel können in diesem Entwurfsprozess nützlich sein. Generell sollte eine Hashfunktion von jedem einzelnen Bit des Schlüssels abhängen, so dass sich zwei Schlüssel, die sich nur in einem Bit oder einer Bitfolge unterscheiden, unabhängig davon, ob die Folge am Anfang, am Ende oder in der Mitte des Schlüssels oder vorhanden ist, den gesamten Schlüssel-Hash auf verschiedene Werte abbildet. Daher ist eine Hashfunktion, die einfach einen Teil eines Schlüssels extrahiert, nicht geeignet. Wenn zwei Schlüssel einfach Permutationen voneinander sind, z. B. 256 und 625, sollten sie ebenfalls in unterschiedliche Werte gehasht werden.

Heuristische Methoden sind Hashing durch Division und Hashing durch Multiplikation.^[1]

Bei dieser Methode wird ein Schlüssel einem Hashwert zugeordnet, indem derRest des Schlüssels beiDivision durch die Größe derHashtabelle berechnet wird. Das heißt, die Hashfunktion${\displaystyle h}$ ist definiert als

${\displaystyle h(\mathrm{k}\mathrm{e}\mathrm{y})=\mathrm{k}\mathrm{e}\mathrm{y}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}$

Weil nur eine einzige Divisionsoperation erforderlich ist, ist das Hashing durch Division ziemlich schnell. Wenn die Divisionsmethode verwendet wird, sollten bestimmte Werte für die Größe der Hashtabelle vermieden werden. Sie sollte keine Potenz einer Zahl sein. Wenn${\displaystyle \mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}=r^p}$ ist, dann ist der Hashwert${\displaystyle h(\mathrm{k}\mathrm{e}\mathrm{y})}$ immer gleich den letzten Bits von${\displaystyle \mathrm{k}\mathrm{e}\mathrm{y}}$. Wenn wir nicht wissen, dass alle${\displaystyle p}$-Bit-Muster niedriger Ordnung gleich wahrscheinlich sind, ist es besser, die Hashfunktion so zu gestalten, dass sie von allen Bits des Schlüssels abhängt. Es hat sich gezeigt, dass die besten Ergebnisse mit der Divisionsmethode erzielt werden, wenn die Größe der Hashtabelle einePrimzahl ist. Eine Primzahl, die nicht zu nah bei einerZweierpotenz liegt, ist oft eine gute Wahl für die Größe der Hashtabelle.^[1]

Bei dieser Methode wird der Schlüssel${\displaystyle k}$ mit einer konstantenreellen Zahl${\displaystyle c}$ im Bereichmultipliziert und die Nachkommastellen von${\displaystyle k\cdot c}$ genommen. Dann wird dieser Wert mit der Größe derHashtabelle multipliziert und mithilfe derAbrundungsfunktion der ganzzahlige Teil davon berechnet. Die Hashfunktion${\displaystyle h}$ kann dargestellt werden als

${\displaystyle h(\mathrm{k}\mathrm{e}\mathrm{y})=\mathrm{f}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{r}(\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}\cdot (\mathrm{k}\mathrm{e}\mathrm{y}\cdot c\mathrm{m}\mathrm{o}\mathrm{d}1))}$

Ein Vorteil besteht darin, dass die Größe der Hashtabelle nicht kritisch ist. Sie ist typischerweise eineZweierpotenz, weil die Hashfunktion dann schneller implementiert werden kann. Obwohl diese Methode mit jederreellen Zahl${\displaystyle c}$ funktioniert, funktioniert sie mit einigen Werten besser als mit anderen.^[1]

Weitere bekannte Hashfunktionen sind zum Beispiel

• Brent-Hashing
• Doppel-Hashing
• Mittquadratmethode
• Zerlegungsmethode
• Ziffernanalyse

• Ajtai
• Micciancio
• Peikert-Rosen
• Schnelle Fourier-Transformation (FFT-Hashfunktion^[2])
• LASH^[3]

• Fletcher’s Checksum
• Adler-32
• CRC (Zyklische Redundanzprüfung)
• Parität
• Quersumme

• MD2,MD4,MD5
• Secure Hash Algorithm (SHA)
• RIPEMD-160
• Tiger
• HAVAL
• Whirlpool

• LM-Hash
• PBKDF2
• Bcrypt
• Scrypt
• Argon2

• Donald E. Knuth:The Art of Computer Programming. 2. Auflage. Volume 3. Addison-Wesley, 1998,ISBN 0-201-89685-0,S. 513 ff. 
• Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest, Clifford Stein:Algorithmen. Eine Einführung. 2. Auflage. Oldenbourg, München/Wien 2007,ISBN 978-3-486-58262-8,S. 221 ff. 
• Lianhua Chi, Xingquan Zhu:Hashing Techniques: A Survey and Taxonomy. In:ACM Computing Surveys (CSUR).Band 50,Nr. 1, April 2017, 11,doi:10.1145/3047307. 

Wiktionary: Hashfunktion – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• CRC Press –Handbook of Applied Cryptography (Kapitel 9) (PDF; 471 kB)
• Konstruktion von Hashfunktionen (PDF; 841 kB)
• Online Generator für Hashberechnungen (md, sha, ripemd, whirlpool, tiger, snefru, gost, adler, crc, fnv, joaat, haval)

1. ↑^abcGeeksforGeeks:What are Hash Functions and How to choose a good Hash Function?
2. ↑C. P. Schnorr, Serge Vaudenay:Parallel FFT-hashing. In: Fast Software Encryption, pp 149–156, 1993
3. ↑K. Bentahar, D. Page, J. H. Silverman, M.-J. O. Saarinen, N.P. Smart:LASH. 2nd NIST Cryptographic Hash Workshop, 2006
4. ↑J. Wassenberg, J. Alakuijala: Fast strong hash functions: SipHash/HighwayHash (github.com)

• Hash