Merkle-Signatur

Die Merkle-Signatur i​st ein digitales Signaturverfahren, d​as auf Merkle-Bäumen s​owie Einmalsignaturen w​ie etwa d​en Lamport-Einmalsignaturen basiert. Es w​urde von Ralph Merkle i​n den späten 1970er Jahren entwickelt u​nd stellt e​ine Alternative z​u traditionellen digitalen Signaturen w​ie dem Digital Signature Algorithm o​der auf RSA basierenden Signaturen dar. Im Gegensatz z​u diesen i​st es resistent g​egen Angriffe d​urch Quantencomputer, d​a seine Sicherheit n​ur von d​er Existenz sicherer Hashfunktionen abhängt.

Idee

Ein Problem v​on Einmalsignaturen, w​ie der Lamport-Signatur, i​st die Übertragung d​es öffentlichen Schlüssels. Da j​eder Schlüssel n​ur genau einmal verwendet werden kann, k​ommt eine größere Datenmenge zusammen, d​ie zuverlässig a​n den Empfänger weitergegeben werden muss.

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

Die Signatur e​iner Nachricht besteht d​ann aus z​wei Teilen:

• Einem der ${\displaystyle 2^{n}}$ ö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 ${\displaystyle 2^{n}}$ Schlüssel handelt, aus denen der Hashwert ${\displaystyle pub}$ berechnet wurde.

Schlüsselerzeugung

Merkle-Baum mit 8 Blättern

Das Merkle-Signaturverfahren kann nur verwendet werden, um eine begrenzte Anzahl von Nachrichten mit einem öffentlichen Schlüssel ${\displaystyle pub}$ zu signieren. Die Anzahl möglicher Nachrichten entspricht einer Zweierpotenz und wird daher als ${\displaystyle N=2^{n}}$ bezeichnet.

Der erste Schritt bei der Generierung des öffentlichen Schlüssels ${\displaystyle pub}$ ist die Generierung des privaten Schlüssels ${\displaystyle X_{i}}$ und des öffentlichen Schlüssels ${\displaystyle Y_{i}}$ von ${\displaystyle 2^{n}}$ Einmalsignaturen. Für jeden öffentlichen Schlüssel ${\displaystyle Y_{i}}$ mit ${\displaystyle 1\leq i\leq 2^{n}}$ wird ein Hash-Wert ${\displaystyle h_{i}=H(Y_{i})}$ berechnet. Mit diesen Hash-Werten ${\displaystyle h_{i}}$ wird ein Hash-Baum aufgebaut.

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

Im Merkle-Baum sind die Hash-Werte ${\displaystyle h_{i}}$ die Blätter des Binärbaums, sodass ${\displaystyle h_{i}=a_{0,i}}$. Jeder innere Knoten des Baums ist der Hash-Wert der Konkatenation seiner beiden Kinder. Beispielsweise ist ${\displaystyle a_{1,0}=H(a_{0,0}||a_{0,1})}$ und ${\displaystyle a_{2,0}=H(a_{1,0}||a_{1,1})}$.

Auf diese Weise wird ein Baum mit ${\displaystyle 2^{n}}$ Blättern und ${\displaystyle 2^{n+1}-1}$ Knoten aufgebaut. Die Wurzel des Baums ${\displaystyle a_{n,0}}$ ist der öffentliche Schlüssel ${\displaystyle pub}$ des Merkle-Signaturverfahrens.

Signierung

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

Um eine Nachricht ${\displaystyle M}$ mit dem Merkle-Signaturverfahren zu signieren, wird die Nachricht ${\displaystyle M}$ zuerst mit einem Einmalsignaturverfahren signiert, wodurch die Signatur ${\displaystyle sig'}$ entsteht. Dazu wird eines der Schlüsselpaare aus privatem und öffentlichem Schlüssel ${\displaystyle (X_{i},Y_{i},)}$ verwendet.

Das einem privaten Einmalschlüssel ${\displaystyle X_{i}}$ zugehörige Blatt des Hash-Baums ist ${\displaystyle a_{0,i}=H(Y_{i})}$. Der Pfad im Hash-Baum von ${\displaystyle a_{0,i}}$ zur Wurzel wird mit ${\displaystyle A}$ bezeichnet. Der Pfad ${\displaystyle A}$ besteht aus ${\displaystyle n+1}$ Knoten, ${\displaystyle A_{0},\ldots ,A_{n}}$, wobei ${\displaystyle A_{0}=a_{0,i}}$ die Blätter sind und ${\displaystyle A_{n}=a_{n,0}=pub}$ die Wurzel des Baums ist. Um diesen Pfad ${\displaystyle A}$ zu berechnen wird jedes Kind der Knoten ${\displaystyle A_{1},\ldots ,A_{n}}$ benötigt. Es ist bekannt, dass ${\displaystyle A_{i}}$ ein Kind von ${\displaystyle A_{i+1}}$ ist. Um den nächsten Knoten ${\displaystyle A_{i+1}}$ des Pfades ${\displaystyle A}$ zu berechnen, müssen beide Kinder von ${\displaystyle A_{i+1}}$ bekannt sein. Daher wird der Bruder von ${\displaystyle A_{i}}$ benötigt. Dieser Knoten wird mit ${\displaystyle auth_{i}}$ bezeichnet, sodass ${\displaystyle A_{i+1}=H(A_{i}||auth_{i})}$. Deswegen werden ${\displaystyle n}$ Knoten ${\displaystyle auth_{0},\ldots ,auth_{n-1}}$ benötigt, um jeden Knoten des Pfades ${\displaystyle A}$ zu berechnen. Diese Knoten ${\displaystyle auth_{0},\ldots ,auth_{n-1}}$ werden berechnet und gespeichert. Sie bilden zusammen mit einer Einmalsignatur ${\displaystyle sig'}$ von ${\displaystyle M}$ die Signatur ${\displaystyle sig=(sig',auth_{0},auth_{1},\ldots ,auth_{n-1})}$ des Merkle-Signaturverfahrens.

Verifizierung

Der Empfänger kennt den öffentlichen Schlüssel ${\displaystyle pub}$, die Nachricht ${\displaystyle M}$, und die Signatur ${\displaystyle sig=(sig',auth_{0},auth_{1},\ldots ,auth_{n-1})}$. Zuerst verifiziert der Empfänger die Einmalsignatur ${\displaystyle sig'}$ der Nachricht ${\displaystyle M}$. Falls ${\displaystyle sig'}$ eine gültige Signatur von ${\displaystyle M}$ ist, berechnet der Empfänger ${\displaystyle A_{0}=H(Y_{i})}$, indem er den Hash-Wert des öffentlichen Schlüssels der Einmalsignatur berechnet. Für ${\displaystyle j=1,..,n-1}$ werden die Knoten ${\displaystyle A_{j}}$ des Pfades ${\displaystyle A}$ berechnet, mit ${\displaystyle A_{j}=H(a_{j-1}||b_{j-1})}$. Wenn ${\displaystyle A_{n}}$ dem öffentlichen Schlüssel ${\displaystyle pub}$ des Merkle-Signaturverfahrens entspricht, so ist die Signatur gültig.

Weiterentwicklungen

Im Zuge d​er Suche n​ach quantencomputerresistenten Signaturverfahren i​st das Verfahren i​n der letzten Zeit wieder stärker i​n den Fokus gerückt. Inzwischen wurden verbesserte Varianten d​es Merkle-Signaturverfahrens veröffentlicht, u. a.

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

Quellen

• 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-Datei; 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-Datei; 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. (PDF)
• Silvio Micali, M. Jakobsson, T. Leighton, M. Szydlo: Fractal merkle tree representation and traversal. RSA-CT 03, 2003

Einzelnachweise

1. 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.
2. D. McGrew, M. Curcio, S. Fluhrer: Leighton-Micali Hash-Based Signatures. RFC8554. RFC Editor, April 2019, S. RFC8554, doi:10.17487/rfc8554 (rfc-editor.org [abgerufen am 20. Februar 2021]).
3. 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.
4. SPHINCS: Introduction. Abgerufen am 25. Januar 2019 (englisch).