Merkle-Signatur

digitales Signaturverfahren
(Weitergeleitet von XMSS)

Die Merkle-Signatur ist ein digitales Signaturverfahren, das auf Merkle-Bäumen sowie Einmalsignaturen wie etwa den Lamport-Einmalsignaturen basiert. Es wurde von Ralph Merkle in den späten 1970er Jahren entwickelt und stellt eine Alternative zu traditionellen digitalen Signaturen wie dem Digital Signature Algorithm oder auf RSA basierenden Signaturen dar. Im Gegensatz zu diesen ist es resistent gegen Angriffe durch Quantencomputer, da seine Sicherheit nur von der Existenz sicherer Hashfunktionen abhängt.

Ein Problem von Einmalsignaturen, wie der Lamport-Signatur, ist die Übertragung des öffentlichen Schlüssels. Da jeder Schlüssel nur genau einmal verwendet werden kann, kommt eine größere Datenmenge zusammen, die zuverlässig an den Empfänger weitergegeben werden muss.

Das Merkle-Signaturverfahren löst dieses Problem, indem das gesamte (öffentliche) Schlüsselmaterial von   Einmalsignaturen in einem mehrstufigen Hash-Verfahren zu einem einzigen Hashwert   zusammengefasst wird. Als öffentlicher Schlüssel braucht nur   veröffentlicht zu werden, anschließend lassen sich mit ihm   Nachrichten signieren.

Die Signatur einer Nachricht besteht dann aus zwei Teilen:

  • Einem der   öffentlichen Schlüssel, sowie die mit dem entsprechenden privaten Schlüssel signierte Nachricht. Der Empfänger kann verifizieren, dass der Sender tatsächlich in Besitz des privaten Schlüssels war.
  • Einem Nachweis, dass es sich bei dem öffentlichen Schlüssel um einen der   Schlüssel handelt, aus denen der Hashwert   berechnet wurde.

Schlüsselerzeugung

Bearbeiten
 
Merkle-Baum mit 8 Blättern

Das Merkle-Signaturverfahren kann nur verwendet werden, um eine begrenzte Anzahl von Nachrichten mit einem öffentlichen Schlüssel   zu signieren. Die Anzahl möglicher Nachrichten entspricht einer Zweierpotenz und wird daher als   bezeichnet.

Der erste Schritt bei der Generierung des öffentlichen Schlüssels   ist die Generierung des privaten Schlüssels   und des öffentlichen Schlüssels   von   Einmalsignaturen. Für jeden öffentlichen Schlüssel   mit   wird ein Hash-Wert   berechnet. Mit diesen Hash-Werten   wird ein Hash-Baum aufgebaut.

Ein Knoten des Baums wird mit   identifiziert, wobei   die Ebene des Knotens bezeichnet. Die Ebene eines Knotens ist über seinen Abstand zu den Blättern definiert. Somit hat ein Blatt die Ebene   und die Wurzel die Ebene  . Die Knoten jeder Ebene sind von links nach rechts durchnummeriert, sodass   der Knoten ganz links auf Ebene   ist.

Im Merkle-Baum sind die Hash-Werte   die Blätter des Binärbaums, sodass  . Jeder innere Knoten des Baums ist der Hash-Wert der Konkatenation seiner beiden Kinder. Beispielsweise ist   und  .

Auf diese Weise wird ein Baum mit   Blättern und   Knoten aufgebaut. Die Wurzel des Baums   ist der öffentliche Schlüssel   des Merkle-Signaturverfahrens.

Signierung

Bearbeiten
 
Merkle-Baum mit Pfad A und Authentifizierungspfad für i=2

Um eine Nachricht   mit dem Merkle-Signaturverfahren zu signieren, wird die Nachricht   zuerst mit einem Einmalsignaturverfahren signiert, wodurch die Signatur   entsteht. Dazu wird eines der Schlüsselpaare aus privatem und öffentlichem Schlüssel   verwendet.

Das einem privaten Einmalschlüssel   zugehörige Blatt des Hash-Baums ist  . Der Pfad im Hash-Baum von   zur Wurzel wird mit   bezeichnet. Der Pfad   besteht aus   Knoten,  , wobei   die Blätter sind und   die Wurzel des Baums ist. Um diesen Pfad   zu berechnen wird jedes Kind der Knoten   benötigt. Es ist bekannt, dass   ein Kind von   ist. Um den nächsten Knoten   des Pfades   zu berechnen, müssen beide Kinder von   bekannt sein. Daher wird der Bruder von   benötigt. Dieser Knoten wird mit   bezeichnet, sodass  . Deswegen werden   Knoten   benötigt, um jeden Knoten des Pfades   zu berechnen. Diese Knoten   werden berechnet und gespeichert. Sie bilden zusammen mit einer Einmalsignatur   von   die Signatur   des Merkle-Signaturverfahrens.

Verifizierung

Bearbeiten

Der Empfänger kennt den öffentlichen Schlüssel  , die Nachricht  , und die Signatur  . Zuerst verifiziert der Empfänger die Einmalsignatur   der Nachricht  . Falls   eine gültige Signatur von   ist, berechnet der Empfänger  , indem er den Hash-Wert des öffentlichen Schlüssels der Einmalsignatur berechnet. Für   werden die Knoten   des Pfades   berechnet, mit  . Wenn   dem öffentlichen Schlüssel   des Merkle-Signaturverfahrens entspricht, so ist die Signatur gültig.

Weiterentwicklungen

Bearbeiten

Im Zuge der Suche nach quantencomputerresistenten Signaturverfahren ist das Verfahren in der letzten Zeit wieder stärker in den Fokus gerückt. Inzwischen wurden verbesserte Varianten des Merkle-Signaturverfahrens veröffentlicht, u. a.

  • XMSS (eXtended Merkle Signature Scheme), das 2018 als RFC 8391[1] standardisiert wurde[2]
  • LMS (Leighton-Micali Hash-Based Signatures), das 2019 als RFC 8554 standardisiert wurde[3]
  • SPHINCS mit größeren Signaturen als XMSS, dafür aber zustandslos[4][5]

Literatur

Bearbeiten
  • G. Becker: Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis. Seminar 'Post Quantum Cryptology' an der Ruhr-Universität Bochum.
  • E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, L. C. Coronado Garca: CMSS – an improved merkle signature scheme. (PDF; 264 kB). Progress in Cryptology – Indocrypt 2006, 2006.
  • E. Klintsevich, K. Okeya, C. Vuillaume, J. Buchmann, E. Dahmen: Merkle signatures with virtually unlimited signature capacity (PDF; 179 kB). 5th International Conference on Applied Cryptography and Network Security – ACNS07, 2007.
  • Ralph Merkle: Secrecy, authentication and public key systems / A certified digital signature. Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979; merkle.com (PDF; 1,9 MB)
  • Silvio Micali, M. Jakobsson, T. Leighton, M. Szydlo: Fractal merkle tree representation and traversal. RSA-CT 03, 2003.

Einzelnachweise

Bearbeiten
  1. RFC 8391 – XMSS: eXtended Merkle Signature Scheme. September 2018 (englisch).
  2. Johannes Buchmann, Erik Dahmen, Andreas Hülsing: XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions. In: Post-Quantum Cryptography. PQCrypto 2011 (= Lecture Notes in Computer Science. Band 7071). Springer, Berlin / Heidelberg 2011, S. 117–129, doi:10.1007/978-3-642-25405-5_8.
  3. D. McGrew, M. Curcio, S. Fluhrer: RFC 8554 – Leighton-Micali Hash-Based Signatures. April 2019 (englisch).
  4. Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, Zooko Wilcox-O’Hearn: SPHINCS: practical stateless hash-based signatures. In: Elisabeth Oswald, Marc Fischlin (Hrsg.): Advances in Cryptology – EUROCRYPT 2015 (= Lecture Notes in Computer Science. Band 9056). Springer, Berlin / Heidelberg 2015, ISBN 978-3-662-46799-2, S. 368–397, doi:10.1007/978-3-662-46800-5_15.
  5. SPHINCS: Introduction. In: sphincs.cr.yp.to. Abgerufen am 25. Januar 2019 (englisch).