Ein Beispiel für einen binären Hashbaum. Die Hashes 0-0 und 0-1 sind die Hashwerte der Datenblöcke L1 bzw. L2, und Hash 0 ist der Hash der Verkettung der Hashes 0-0 und 0-1.

In der Kryptographie und Informatik ist ein Hashbaum (auch Merkle-Baum genannt) ein Baum , in dem jeder Blattknoten mit dem kryptografischen Hash eines Datenblocks beschriftet ist und jeder andere Knoten (auch Zweig , innerer Knoten oder Inode genannt ) mit dem kryptografischen Hash der Beschriftungen seiner Kindknoten beschriftet ist. Ein Hashbaum ermöglicht die effiziente und sichere Überprüfung des Inhalts großer Datenstrukturen . Er ist eine Verallgemeinerung von Hashlisten und Hashketten .

Der Nachweis, dass ein Blattknoten Teil eines gegebenen binären Hashbaums ist, erfordert die Berechnung einer Anzahl von Hashes, die proportional zum Logarithmus der Anzahl der Blattknoten im Baum ist. [ 1 ] Umgekehrt ist die Anzahl in einer Hashliste proportional zur Anzahl der Blattknoten selbst. Ein Merkle-Baum ist daher ein effizientes Beispiel für ein kryptografisches Commitment-Schema , bei dem die Wurzel des Baums als Commitment betrachtet wird und Blattknoten aufgedeckt und als Teil des ursprünglichen Commitments nachgewiesen werden können. [ 2 ]

Das Konzept des Hash-Baums ist nach Ralph Merkle benannt , der es 1979 patentieren ließ. [ 3 ] [ 4 ]

Verwendung

Hashbäume können verwendet werden, um beliebige Daten zu verifizieren, die in und zwischen Computern gespeichert, verarbeitet und übertragen werden. Sie können dazu beitragen, sicherzustellen, dass Datenblöcke, die von anderen Teilnehmern in einem Peer-to-Peer-Netzwerk empfangen werden , unbeschädigt und unverändert ankommen, und sogar zu überprüfen, ob die anderen Teilnehmer keine falschen Datenblöcke senden.

Hashbäume werden verwendet in:

Es wurden Vorschläge zur Verwendung von Hash-Bäumen in vertrauenswürdigen Computersystemen unterbreitet. [ 14 ]

Überblick

Ein Hashbaum ist ein Baum von Hashwerten , dessen Blätter (Blattknoten, manchmal auch „Blätter“ genannt) Hashwerte von Datenblöcken, beispielsweise einer Datei oder einer Gruppe von Dateien, darstellen . Weiter oben im Baum befindliche Knoten sind die Hashwerte ihrer jeweiligen Kinder. Im obigen Beispiel ist Hash 0 das Ergebnis der Hashberechnung der Verkettung von Hash 0-0 und Hash 0-1 . Das heißt: Hash 0 = Hash ( Hash 0-0 + Hash 0-1 ), wobei „+“ die Verkettung bezeichnet.

Die meisten Hash-Baum-Implementierungen sind binär (zwei Kindknoten unter jedem Knoten), aber es können genauso gut viel mehr Kindknoten unter jedem Knoten verwendet werden.

Üblicherweise wird für das Hashing eine kryptografische Hashfunktion wie SHA-2 verwendet. Soll der Hashbaum lediglich vor unbeabsichtigten Beschädigungen schützen, können nicht-kryptografische Prüfsummen wie CRCs eingesetzt werden.

An der Spitze eines Hashbaums befindet sich der Top-Hash (auch Wurzel- oder Master-Hash genannt ). Vor dem Herunterladen einer Datei in einem P2P-Netzwerk wird der Top-Hash in den meisten Fällen von einer vertrauenswürdigen Quelle bezogen, beispielsweise von einem Freund oder einer Website, die für gute Download-Empfehlungen bekannt ist. Sobald der Top-Hash verfügbar ist, kann der Hashbaum von jeder nicht vertrauenswürdigen Quelle, wie etwa einem beliebigen Peer im P2P-Netzwerk, empfangen werden. Der empfangene Hashbaum wird dann mit dem vertrauenswürdigen Top-Hash verglichen. Ist der Hashbaum beschädigt oder gefälscht, wird ein anderer Hashbaum aus einer anderen Quelle ausprobiert, bis das Programm einen findet, der mit dem Top-Hash übereinstimmt. [ 15 ]

Der Hauptunterschied zu einer Hashliste besteht darin, dass jeweils nur ein Zweig des Hashbaums heruntergeladen werden kann und die Integrität jedes Zweigs sofort überprüft werden kann, selbst wenn der gesamte Baum noch nicht verfügbar ist. Beispielsweise kann im Bild die Integrität des Datenblocks L2 sofort überprüft werden, wenn der Baum bereits die Hashwerte 0-0 und 1 enthält. Dazu wird der Datenblock gehasht, das Ergebnis iterativ mit den Hashwerten 0-0 und 1 kombiniert und schließlich mit dem obersten Hashwert verglichen . Analog dazu kann die Integrität des Datenblocks L3 überprüft werden, wenn der Baum bereits die Hashwerte 1-1 und 0 enthält . Dies ist vorteilhaft, da Dateien effizient in sehr kleine Datenblöcke aufgeteilt werden können, sodass bei Beschädigung nur kleine Blöcke erneut heruntergeladen werden müssen. Bei großen gehashten Dateien kann eine solche Hashliste oder Hashkette sehr groß werden. Bei einem Baum hingegen kann ein kleiner Zweig schnell heruntergeladen, dessen Integrität überprüft und anschließend der Download der restlichen Datenblöcke gestartet werden.

Zweiter Vorbildangriff

Der Merkle-Hash-Wurzelwert gibt nicht die Baumtiefe an, was einen Second-Preimage-Angriff ermöglicht . Dabei erstellt ein Angreifer ein anderes Dokument als das Original, das denselben Merkle-Hash-Wurzelwert aufweist. Im obigen Beispiel kann ein Angreifer ein neues Dokument mit zwei Datenblöcken erstellen, wobei der erste Hashwert 0-0 + Hashwert 0-1 und der zweite Hashwert 1-0 + Hashwert 1-1 ist . [ 16 ] [ 17 ]

Eine einfache Lösung ist in Certificate Transparency definiert : Bei der Berechnung von Hashes für Blattknoten wird den Hashdaten ein Byte 0x00 vorangestellt, bei der Berechnung von Hashes für interne Knoten hingegen 0x01. [ 15 ] Die Begrenzung der Hashbaumgröße ist Voraussetzung für einige formale Sicherheitsbeweise und trägt zu deren Verschärfung bei. Manche Implementierungen begrenzen die Baumtiefe mithilfe von Präfixen vor den Hashwerten. Eine extrahierte Hashkette ist daher nur dann gültig, wenn das Präfix in jedem Schritt abnimmt und beim Erreichen des Blattknotens noch positiv ist.

Tigerbaum-Haschisch

Der Tigerbaum-Hash ist eine weit verbreitete Form des Hashbaums. Er verwendet einen binären Hashbaum (zwei Kindknoten unter jedem Knoten), hat üblicherweise eine Datenblockgröße von 1024 Byte und verwendet den Tiger-Hash . [ 18 ]

Tiger-Tree-Hashes werden in den P2P- Dateiaustauschprotokollen Gnutella [ 19 ] , Gnutella2 [ 20 ] und Direct Connect [ 21 ] sowie in Dateiaustauschanwendungen wie Phex [ 22 ] , BearShare , LimeWire , Shareaza , DC++ [ 22 ] und gtk-gnutella [ 23 ] verwendet .

Siehe auch

Referenzen

  1. ^ Becker, Georg (18.07.2008). „Merkle-Signaturschemata, Merkle-Bäume und ihre Kryptoanalyse“ (PDF) . Ruhr-Universität Bochum. P. 16. Archiviert vom Original (PDF) am 22.12.2014 . Abgerufen am 20.11.2013 .
  2. ^ „Handbook of Applied Cryptography“ . cacr.uwaterloo.ca . Abschnitt 13.4.1 . Abgerufen am 7. März 2024 .
  3. ^ Merkle, RC (1988). „Eine digitale Signatur basierend auf einer herkömmlichen Verschlüsselungsfunktion“. Advances in Cryptology – CRYPTO '87 . Lecture Notes in Computer Science. Band 293. S.  369–378 . doi : 10.1007/3-540-48184-2_32 . ISBN 978-3-540-18796-7Die
  4. ^ US-Patent 4309569 , Ralph Merkle, „Verfahren zur Bereitstellung digitaler Signaturen“, veröffentlicht am 5. Januar 1982, zugewiesen an den Vorstand der Leland Stanford Junior University 
  5. ^ "Hashtree-Entwicklerseite" .
  6. ^ Bonwick, Jeff (08.12.2005). „ZFS End-to-End Data Integrity“ . blogs.oracle.com . Archiviert vom Original am 3. April 2012. Abgerufen am 19.09.2013 .
  7. ^ Likai Liu. "Bitrot-Resistenz auf einem einzelnen Laufwerk" . likai.org .
  8. ^ „General Verifiable Federation“ . Google Wave Protocol . Archiviert vom Original am 08.04.2018 . Abgerufen am 09.03.2017 .
  9. ^ „Einführung in ZFS – Aktuelle OpenZFS-Dokumentation“ . openzfs.readthedocs.io . Abgerufen am 27.05.2025 .
  10. ^ Koblitz, Neal; Menezes, Alfred J. (Januar 2016). „Cryptocash, cryptosity, and cryptocontracts“. Designs, Codes and Cryptography . 78 (1): 87–102 . CiteSeerX 10.1.1.701.8721 . doi : 10.1007/s10623-015-0148-5 . S2CID 16594958 .  
  11. ^ D. Benjamin; D. O'Brien; BE Westerbaan; L. Valenta; F. Valsorda (24.05.2026). „Merkle Tree-Zertifikate“ . Internet Engineering Task Force . IETF . Abgerufen am 11.06.2026 .
  12. ^ Dolstra, E. Das rein funktionale Software-Bereitstellungsmodell. Dissertation, Naturwissenschaftliche Fakultät, Utrecht, Niederlande. Januar 2006. S. 21 ISBN 90-393-4130-3Die
  13. ^ Adam Marcus. „Das NoSQL-Ökosystem“ . aosabook.org . Wenn eine Replik längere Zeit ausfällt oder auch der Rechner, der die Hinted Handoffs für eine nicht verfügbare Replik speichert, nicht mehr funktioniert, müssen sich die Replikate untereinander synchronisieren. In diesem Fall implementieren Cassandra und Riak ein von Dynamo inspiriertes Verfahren namens Anti-Entropie. Bei der Anti-Entropie tauschen die Replikate Merkle-Bäume aus, um die nicht synchronisierten Teile ihrer replizierten Schlüsselbereiche zu identifizieren. Ein Merkle-Baum ist eine hierarchische Hash-Verifizierung: Stimmt der Hash des gesamten Schlüsselraums zwischen zwei Replikaten nicht überein, tauschen sie Hashes immer kleinerer Teile des replizierten Schlüsselraums aus, bis die nicht synchronisierten Schlüssel gefunden sind. Dieser Ansatz reduziert unnötige Datenübertragungen zwischen Replikaten, die größtenteils ähnliche Daten enthalten.
  14. ^ Kilian, J. (1995). „Verbesserte effiziente Argumente“ (PDF) . Fortschritte in der Kryptologie – CRYPT0' 95. Lecture Notes in Computer Science. Band 963. S.  311–324 . doi : 10.1007/3-540-44750-4_25 . ISBN 978-3-540-60221-7Die
  15. ^ a b Laurie, B.; Langley, A.; Kasper, E. (Juni 2013). "Certificate Transparency" . IETF RFC6962. doi : 10.17487/rfc6962 .
  16. Elena Andreeva, Charles Bouillaguet, Orr Dunkelman und John Kelsey (Januar 2009). „Herding-, Second-Preimage- und Trojaner-Angriffe jenseits des Merkle-Damgård-Algorithmus“. Ausgewählte Bereiche der Kryptographie . Lecture Notes in Computer Science. Band 5867. SAC. S.  393–414 . doi : 10.1007/978-3-642-05445-7_25 . ISBN 978-3-642-05443-3Die
  17. Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan J. Hoch, John Kelsey, Adi Shamir und Sebastien Zimmer (2008). „Second Preimage Attacks on Dithered Hash Functions“. In: Smart, Nigel (Hrsg.). Advances in Cryptology – EUROCRYPT 2008. Lecture Notes in Computer Science. Band 4965. Istanbul, Türkei. S.  270–288 . doi : 10.1007/978-3-540-78967-3_16 . ISBN 978-3-540-78966-6. S2CID  12844017 .{{cite book}}CS1 Wartung: Standort des fehlenden Herausgebers ( Link )
  18. ^ Chapweske, J.; Mohr, G. (4. März 2003). „Tree Hash EXchange format (THEX)“ . Archiviert vom Original am 3. August 2009.
  19. ^ "tigertree.c Dateireferenz" . Gtk-Gnutella . Abgerufen am 23. September 2018 .
  20. ^ „Audit: P2P DirectConnect Application“ . Symantec . Archiviert vom Original am 29. Januar 2015. Abgerufen am 23. September 2018 .
  21. ^ Arne Babenhauserheide (7. Januar 2007). „Phex 3.0.0 veröffentlicht“ . Phex . Abgerufen am 23. September 2018 .
  22. ^ „Funktionsliste von DC++“ . dcplusplus.sourceforge.net .
  23. ^ „Entwicklung“ . GTK-Gnutella . Abgerufen am 23. September 2018 .

Weiterführende Literatur