Hash-Baum

Ein binärer Hash-Baum

In der Kryptographie und Informatik ist ein Hash-Baum (engl. hash tree oder merkle tree) eine Datenstruktur, die einen Baum aus Hashwerten von Datenblöcken bildet, 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 or Tiger Tree Hashes bezeichnet.

Geschichte

Hash-Bäume wurden 1979 von Ralph Merkle erfunden.^[1] Der ursprüngliche Zweck war die effiziente Handhabung vieler Lamport-Einmalsignaturen. Lamport-Signaturen gelten selbst im Angesicht von Quantencomputern als sicher. Leider kann ein 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 durch das Merkle-Signaturverfahren realisiert wird.

Anwendungen

Neben den 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] und der Online-Datensicherung Tarsnap eingesetzt.

Funktionsweise

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 Kryptologische Hashfunktion wie SHA-1, Whirlpool oder Tiger verwendet. Soll der Hash-Baum lediglich gegen unbeabsichtigten 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. 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.

Tiger Tree Hash

Der Tiger Tree Hash (TTH) ist ein weit verbreiteter Hash-Baum. Er verwendet einen Binärbaum – normalerweise mit einer Blockgröße von 1024 Bytes – sowie die kryptografisch sichere Tiger-Hashfunktion.

TTHs werden von den Filesharing-Protokollen Gnutella, Gnutella2 und Direct Connect verwendet, sowie von Filesharing-Anwendungen wie Phex, BearShare, LimeWire, Shareaza, DC++^[4] und Valknut.

Siehe auch

• Kryptologische Hashfunktion
• Binärbaum – eine Baumstruktur.
• Ralph Merkle – Erfinder von Hash-Bäumen (merkle trees).
• Lamport-Signatur – Hash-Bäume wurden ursprünglich erfunden, um Lamport-Einmalsignaturen effizient handhaben zu können.
• Merkle-Signatur

Quellen

• 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) – Eine detaillierte Beschreibung von Tiger-Trees.
• Efficient Use of Merkle Trees – Erklärung von RSA Security zum ursprünglichen Zwecks 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. ↑ Jeff Bonwick's Blog ZFS End-to-End Data Integrity
3. ↑ Google Wave Federation Protocol Wave Protocol Verification Paper
4. ↑ "DC++'s feature list"[1]

Weblinks

• http://www.codeproject.com/cs/algorithms/thexcs.asp – Tiger Tree Hash (TTH) Quelltext in C# – von Gil Schmidt
• http://sourceforge.net/projects/tigertree/ – Tiger Tree Hash (TTH) Implementierung in C and Java
• RHash, ein Open Source Kommandozeilentool, welches TTHs und Magnet-Links mit TTHs berechnen kann.