Hash-Baum

Begriff und Zweck

Ein Hash-Baum, auch Hash Tree oder Merkle Tree genannt, ist eine Datenstruktur der Kryptographie und Informatik. Er besteht aus Hashwerten von Datenblöcken, beispielsweise den Blöcken einer Datei. Hash-Bäume erweitern das Prinzip von Hash-Listen und dienen dazu, die Integrität von Daten sicherzustellen. Integrität bedeutet hier, dass Daten unbeschädigt und unverändert geblieben sind.

Ein Hash-Baum kann grundsätzlich binär sein, also höchstens zwei Kindknoten pro Knoten besitzen. Er kann aber auch einen höheren Ausgangsgrad verwenden. Die Blätter enthalten die Hashwerte einzelner Datenblöcke. Die darüberliegenden Knoten enthalten Hashwerte ihrer jeweiligen Kindknoten. An der Spitze steht ein einzelner Hashwert, der Top-Hash, Root-Hash oder Master-Hash genannt wird.

Entstehung und ursprünglicher Zweck

Hash-Bäume wurden 1979 von Ralph Merkle erfunden. Ihr ursprünglicher Zweck war die effiziente Handhabung vieler Lamport-Einmalsignaturen. Diese zählen zu den quantensicheren Verfahren.

Ein einzelner Lamport-Schlüssel kann nur verwendet werden, um eine einzige Nachricht zu signieren. In Verbindung mit Hash-Bäumen kann ein Lamport-Schlüssel dagegen für viele Nachrichten verwendet werden. Dies wird im Merkle-Signaturverfahren umgesetzt.

Aufbau und Integritätsprüfung

Normalerweise verwendet ein Hash-Baum eine kryptographische Hashfunktion, zum Beispiel SHA-1, Whirlpool oder Tiger. Wenn lediglich Schutz vor unbeabsichtigten Beschädigungen erforderlich ist, kann auch eine kryptografisch unsichere Prüfsumme wie CRC eingesetzt werden.

Bei einer Datei werden zunächst die Datenblöcke auf der Blattebene gehasht. Anschließend werden die Hashwerte benachbarter Kinder miteinander verknüpft und erneut gehasht. Dieses Verfahren wird bis zur Wurzel fortgesetzt. Der Top-Hash fasst dadurch den gesamten Inhalt des Baumes zusammen.

In einem P2P-Netzwerk wird der Top-Hash meist vor dem Herunterladen einer Datei von einer vertrauenswürdigen Quelle bezogen, beispielsweise von einem Freund oder einer Website mit guter Bewertung. Der restliche Hash-Baum kann anschließend auch von einer nicht vertrauenswürdigen Quelle, etwa einem beliebigen Peer, heruntergeladen werden. Der erhaltene Baum wird gegen den vertrauenswürdigen Top-Hash geprüft und bei einer Abweichung abgelehnt.

Der wesentliche Unterschied zu einer Hash-Liste besteht darin, dass einzelne Zweige des Hash-Baums heruntergeladen und sofort geprüft werden können, obwohl der vollständige Baum noch nicht verfügbar ist. Um beispielsweise den Datenblock L2 zu prüfen, wird aus L2 zunächst der Hash 0-1 berechnet. Dieser wird mit Hash 0-0 verknüpft, wodurch Hash 0 entsteht. Hash 0 wird anschließend mit Hash 1 verknüpft. Das Ergebnis muss mit dem vertrauenswürdigen Top-Hash übereinstimmen.

Dateien werden für die Übertragung zweckmäßig in sehr kleine Blöcke aufgeteilt. Bei einer Beschädigung muss dann nur ein kleiner Teil neu geladen werden. Bei sehr großen Dateien entstehen dadurch allerdings relativ große Hash-Listen oder Hash-Bäume. Einzelne Zweige können trotzdem schnell geladen und geprüft werden, sodass das Herunterladen der eigentlichen Datei bereits beginnen kann. Wenn der vollständige Baum vorhanden ist, lässt sich ein fehlerhafter Datenblock in einer Integritätsprüfung in {\displaystyle {\mathcal {O}}(\operatorname {ld} (n))} ermitteln.

Sicherheitsgrenze

Im Top-Hash sind keine Informationen über die Tiefe des Baumes enthalten. Deshalb sind zweite Urbild-Angriffe möglich. Dabei wird ein anderer Hash-Baum mit Datenblöcken erzeugt, deren Hashwerte den Kindern des Top-Hashes des angegriffenen Baumes entsprechen.

Auf den im Artikel beschriebenen Baum bezogen könnten zwei Datenblöcke erzeugt werden, deren Hashwerte jeweils Hash 0 und Hash 1 entsprechen. Werden diese Werte zusammengeführt, entsteht derselbe Top-Hash, obwohl ein anderer Baum beziehungsweise andere Datenblöcke verwendet wurden.

Tiger-Tree-Hash

Der Tiger-Tree-Hash ist ein weit verbreiteter binärer Hash-Baum, der auf der kryptographischen Hashfunktion Tiger basiert. Er wird häufig verwendet, um die Integrität großer Dateien während oder nach der Übertragung zu überprüfen.

Auf der Blattebene verarbeitet der Tiger-Tree-Hash typischerweise Datenblöcke von jeweils 1024 Byte. 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 sowohl die einzelnen Dateiblöcke auf Korrektheit prüfen als auch gleichzeitig feststellen, ob der Hashbaum selbst korrekt ist.

Verwendet wird der Tiger-Tree-Hash unter anderem von den Filesharing-Protokollen Gnutella, Gnutella2 und Direct Connect sowie von den Filesharing-Anwendungen Phex, BearShare, LimeWire, Shareaza und DC++.

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

Anwendungen

Hash-Bäume können neben digitalen Signaturen allgemein Daten schützen, die gespeichert oder ausgetauscht werden. Ihre derzeitige Hauptanwendung ist die Sicherstellung, dass Datenblöcke, die in P2P-Netzwerken von anderen Peers empfangen werden, unbeschädigt und unverändert sind.

Es gibt außerdem Vorschläge für den Einsatz beim Trusted Computing. Sun Microsystems verwendet Hash-Bäume im Dateisystem ZFS. Weitere im Artikel genannte Anwendungen sind Google Wave, Apples Signed System Volume und die Online-Datensicherung Tarsnap.

Bekannte Implementationen sind die Blockchain der Kryptowährung Bitcoin, Apples Signed System Volume und die Versionsverwaltung Git.