Hash-Baum

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 19. November 2017 um 19:29 Uhr durch Rmcharb (Diskussion | Beiträge) (EN korr). Sie kann sich erheblich von der aktuellen Version unterscheiden.
Zur Navigation springen Zur Suche springen
Ein binärer Hash-Baum

Ein Hash-Baum (englisch hash tree oder merkle tree) ist eine Datenstruktur in der Kryptographie und Informatik. Ein Hash-Baum bildet einen 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 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 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. Möchte man zum Beispiel die Integrität des Datenblockes L2 im Bild überprüfen, reicht es, den Hash 0-0 und den Hash 1 zu kennen. Aus dem Datenblock 2 kann der Hash 0-1 berechnet werden und mithilfe des Hashes 0-0 der Hash 0. Weiter wird mit Hash 0 und Hash 1 nun der Top Hash berechnet. 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 ist ein weit verbreiteter binärer Hash-Baum, der auf der kryptologischen 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

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) (Memento vom 16. März 2008 im Internet Archive) – 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

  1. ↑ R. C. Merkle: A digital signature based on a conventional encryption function, Crypto ’87
  2. ↑ ZFS End-to-End Data Integrity. In: Jeff Bonwick’s Blog
  3. ↑ Wave Protocol Verification Paper. Google Wave Federation Protocol
  4. ↑ DC++’s feature list
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Hash-Baum&oldid=171171052“