Hash-Baum

Ein Hash-Baum (englisch hash tree oder Merkle tree, nach dem Wissenschaftler Ralph Merkle) ist eine Datenstruktur in der Kryptographie und Informatik. Ein Hash-Baum ist ein Baum aus Hashwerten von Datenblöcken, beispielsweise von einer Datei. Hash-Bäume sind eine Erweiterung von Hash-Listen und dienen gleichermaßen dazu, die Integrität von Daten sicherzustellen. Wenn sie die Tiger-Hashfunktion als Grundlage verwenden, so werden sie als Tiger Trees oder Tiger Tree Hashes bezeichnet.

Hash-Bäume wurden 1979 von Ralph Merkle erfunden.^[1] Der ursprüngliche Zweck war die effiziente Handhabung vieler Lamport-Einmalsignaturen, die zu den quantensicheren Verfahren zählen. Jedoch kann ein einzelner Lamport-Schlüssel nur verwendet werden, um eine einzige Nachricht zu signieren. In Kombination mit Hash-Bäumen kann jedoch ein Lamport-Schlüssel für viele Nachrichten verwendet werden, was im Merkle-Signaturverfahren realisiert wird.

Neben Signaturen können Hash-Bäume verwendet werden, um jegliche Art von Daten, die gespeichert und ausgetauscht werden, vor Veränderungen zu schützen. Die Hauptanwendung ist derzeit die Sicherstellung in P2P-Netzwerken, dass Datenblöcke, die von anderen Peers empfangen werden, unbeschädigt und unverändert sind. Es gibt Vorschläge, Hash-Bäume beim Trusted Computing einzusetzen. Sun Microsystems verwendet sie im ZFS.^[2] Hash-Bäume werden auch bei Google Wave,^[3] Apples Signed System Volume und der Online-Datensicherung Tarsnap eingesetzt.

Bekannte Implementationen von Hash-Bäumen sind die Blockchain der Kryptowährung Bitcoin,^[4] Apples „Signed System Volume“^[5] sowie die Versionsverwaltung Git.

Ein Hash-Baum ist ein Baum von Hash-Werten, wobei die Blätter Hash-Werte von Datenblöcken sind, beispielsweise einer Datei. Knoten weiter oben im Baum sind Hash-Werte ihrer Kinder. Die meisten Implementierungen benutzen einen Binärbaum (jeder Knoten besitzt höchstens zwei Kindknoten), jedoch kann genauso gut ein höherer Ausgangsgrad verwendet werden.

Normalerweise wird eine kryptographische Hashfunktion wie SHA-1, Whirlpool oder Tiger verwendet. Soll der Hash-Baum lediglich gegen unbeabsichtigte Beschädigungen schützen, so kann eine (kryptografisch unsichere) Prüfsumme wie CRC verwendet werden.

Die Wurzel des Hash-Baums wird als Top-Hash, Root-Hash oder Master-Hash bezeichnet. Vor dem Herunterladen einer Datei in einem P2P-Netzwerk wird meist der Top-Hash von einer vertrauenswürdigen Quelle bezogen, beispielsweise einem Freund oder einer Website mit guter Bewertung. Liegt der Top-Hash vor, so kann der restliche Hash-Baum auch von einer nicht vertrauenswürdigen Quelle bezogen werden, also auch von jedem Peer eines P2P-Netzwerks. Er kann dann gegen den vertrauenswürdigen Top-Hash geprüft und gegebenenfalls abgelehnt werden.

Der Hauptunterschied zu einer Hash-Liste ist, dass jeder Zweig des Hash-Baums einzeln heruntergeladen und sofort auf Integrität geprüft werden kann, selbst wenn der komplette Baum noch nicht verfügbar ist. So kann zum Beispiel die Integrität des Datenblocks L2 im Bild überprüft werden, sobald der Baum die Hashwerte 0-0 und 1 enthält. Dazu wird zuerst aus dem Datenblock L2 der Hash 0-1 berechnet und mit Hash 0-0 verknüpft, um Hash 0 zu erhalten. Hash 0 wird schlussendlich mit Hash 1 verknüpft und das Ergebnis mit dem (vertrauenswürdigen) Top-Hash verglichen. Es ist effizienter, Dateien zwecks Übertragung in sehr kleine Blöcke aufzuspalten, sodass bei Beschädigungen nur kleine Teile neu geladen werden müssen. Dadurch entstehen bei sehr großen Dateien allerdings auch relativ große Hash-Listen oder Hash-Bäume. Werden Bäume verwendet, so können aber einzelne Zweige schnell geladen und auf Integrität geprüft werden, sodass das Herunterladen der eigentlichen Datei beginnen kann. Ist der ganze Baum verfügbar, so kann ein fehlerhafter Datenblock in einer Datenintegritätsprüfung in O ( ld ⁡ ( n ) ) {\displaystyle {\mathcal {O}}(\operatorname {ld} (n))} ermittelt werden.

Da im Top-Hash keine Informationen über die Tiefe des Baumes enthalten sind, lassen sich zweite Urbild-Angriffe durchführen, indem ein Hash-Baum mit Datenblöcken erzeugt wird, deren Hash-Werte den Kindern des Top-Hashes des anzugreifenden Hash-Baumes entsprechen. So kann also ein Angriff auf den Hash-Baum im Bild ausgeführt werden, indem zwei Datenblöcke erzeugt werden, deren Hash-Werte jeweils Hash 0 und Hash 1 entsprechen, um so den gleichen Top-Hash zu erzeugen.

Der Tiger-Tree-Hash ist ein weit verbreiteter binärer Hash-Baum, der auf der kryptographischen Hashfunktion Tiger basiert. Er wird häufig dazu genutzt, die Integrität großer Dateien bei oder nach der Übertragung zu überprüfen. Der Tiger-Tree-Hash hasht auf der Blattebene typischerweise je 1024 Byte große Datenblöcke aus der Datei. Der Roothash ist dann – mit hoher Wahrscheinlichkeit – ein eindeutiger Identifikator für die Datei. Liegt dem Client der vollständige Tiger-Hashbaum vor, kann er einerseits verifizieren, ob die einzelnen Dateiblöcke korrekt sind, sowie andererseits gleichzeitig überprüfen, ob der Hashbaum selbst korrekt ist.

Tiger-Tree-Hashes werden von den Filesharing-Protokollen Gnutella, Gnutella2 und Direct Connect verwendet, sowie von Filesharing-Anwendungen wie Phex, BearShare, LimeWire, Shareaza und DC++.^[6]

In Textdarstellung werden die Werte üblicherweise als Base32 kodiert angegeben, entweder direkt oder als Uniform Resource Name, z. B. urn:tree:tiger:LWPNACQDBZRYXW3VHJVCJ64QBZNGHOHHHZWCLNQ für eine 0-Byte-Datei.

• Gil Schmidt: Tiger Tree Hash (TTH) Quelltext in C#
• Tiger Tree Hash (TTH) Implementierung in C und Java
• RHash, ein Open Source Kommandozeilentool, welches TTHs und Magnet-Links mit TTHs berechnen kann.

• Patent US4309569: Method of providing digital signatures. Veröffentlicht am 5. Januar 1982, Erfinder: Ralph C. Merkle (Erklärt sowohl die Struktur von Hash-Bäumen als auch deren Verwendung für viele Einmalsignaturen).‌
• Tree Hash EXchange format (THEX) (Memento vom 16. März 2008 im Internet Archive) – Eine detaillierte Beschreibung von Tiger-Trees.
• Efficient Use of Merkle Trees (Memento vom 6. Dezember 2006 im Internet Archive) – Erklärung von RSA Security zum ursprünglichen Zweck von Merkle-Bäumen: der Handhabung vieler Lamport-Einmalsignaturen.

1. ↑ R. C. Merkle: A digital signature based on a conventional encryption function, Crypto ’87
2. ↑ ZFS End-to-End Data Integrity. (Memento vom 12. Oktober 2010 im Internet Archive) In: Jeff Bonwick’s Blog
3. ↑ Wave Protocol Verification Paper. (Memento vom 12. November 2010 im Internet Archive) Google Wave Federation Protocol
4. ↑ Satoshi Nakamoto: Bitcoin: Ein elektronisches Peer-to-Peer-Cash-System. (PDF; 323 kB) (Übersetzung des Original-Papers von Daniel Deckner). In: bitcoin.org. Abgerufen am 11. März 2024. 
5. ↑ Sicherheit des Signed System Volume bei macOS. Abgerufen am 9. Januar 2022. 
6. ↑ Features. Funktionen von D++. In: dcplusplus.sourceforge.io. Abgerufen am 11. März 2024 (englisch).