Hash-Baum

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.

Inhaltsverzeichnis

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

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


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hash-Tabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Evidence Record Syntax — Die Evidence Record Syntax, kurz ERS, ist ein Teil der Spezifikation des Long Term Archiving and Notary Service, kurz LTANS. Er beschreibt das Datenformat für eine Nachweisdatei, den Evidence Record, der dazu dient, den Beweis für die Integrität… …   Deutsch Wikipedia

  • AICH (eMule) — Advanced Intelligent Corruption Handling (kurz AICH) ist ein Fehlerkorrektursystem, das dazu gedacht ist, Übertragungsfehler im P2P Netzwerk eDonkey2000 mit minimalem Aufwand zu beheben. Es soll langfristig das ältere, aber wesentlich schlechtere …   Deutsch Wikipedia

  • Intelligent Corruption Handling — Advanced Intelligent Corruption Handling (kurz AICH) ist ein Fehlerkorrektursystem, das dazu gedacht ist, Übertragungsfehler im P2P Netzwerk eDonkey2000 mit minimalem Aufwand zu beheben. Es soll langfristig das ältere, aber wesentlich schlechtere …   Deutsch Wikipedia

  • Merkle-Signatur — Die Merkle Signatur ist ein digitales Signaturverfahren, das auf Merkle Bäumen sowie Einmalsignaturen wie etwa dem Lamport Einmalsignaturen basiert. Es wurde von Ralph Merkle in den späten Siebzigern entwickelt und stellt eine Alternative zu… …   Deutsch Wikipedia

  • Advanced Intelligent Corruption Handling — (kurz AICH) ist ein Fehlerkorrektursystem, das dazu gedacht ist, Übertragungsfehler im P2P Netzwerk eDonkey2000 mit minimalem Aufwand zu beheben. Es soll langfristig das ältere, aber wesentlich schlechtere Intelligent Corruption Handling (kurz… …   Deutsch Wikipedia

  • ArchiSig — Das Konzept ArchiSig beschreibt ein Verfahren für die sichere und Beweiskraft erhaltende, langfristige Archivierung von elektronischen Dokumenten im Kontext deutscher Gesetzgebung. In einem vom Bundesministerium für Wirtschaft und Arbeit im… …   Deutsch Wikipedia

  • Hashmap — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashtable — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashverfahren — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”