Hash-Baum

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Tiger-Tree Hash)
Wechseln zu: Navigation, Suche
Ein binärer Hash-Baum

In der Kryptographie und Informatik ist ein Hash-Baum (englisch 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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Der Tiger-Tree-Hash ist ein weit verbreiteter binärer Hash-Baum, der auf der krytologischen 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 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++.[4]

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.

Weblinks[Bearbeiten]

Quellen[Bearbeiten]

  • 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.

Einzelnachweise[Bearbeiten]

  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]