Merkles Puzzle

Merkles Puzzle ist ein kryptografisches Schlüsselaustauschprotokoll. Es ist das erste derartige Protokoll, bei dem nicht vorausgesetzt wird, dass die Kommunizierenden bereits einen geheimen Schlüssel teilen. Es wurde im Jahr 1974 von Ralph Merkle entdeckt, aber erst 1978 veröffentlicht.^[1] Die Existenz eines solchen Protokolls wurde lange für unmöglich gehalten, und seine Entdeckung kann als Beginn der Public-Key-Kryptographie gesehen werden.

Alice und Bob einigen sich zunächst auf ein symmetrisches Verschlüsselungsverfahren ${\displaystyle E}$, beispielsweise AES. Ferner auf die Parameter ${\displaystyle m}$ und ${\displaystyle n}$. Diese sind natürliche Zahlen. ${\displaystyle m}$ könnte etwa 1 Million^[2] sein und ${\displaystyle n}$ etwa 64.

Alice erzeugt dann eine Tabelle mit ${\displaystyle m}$ Einträgen, bestehend jeweils aus einem zufällig gewählten Schlüssel ${\displaystyle K_{i}}$ und dem Index ${\displaystyle i}$, mit ${\displaystyle i=0,1,\cdots ,m-1}$. Im Folgenden werden Alice und Bob ihre Nachrichten mit einem dieser Schlüssel ${\displaystyle K_{i}}$ verschlüsseln, daher muss dessen Länge ausreichend für eine sichere Verschlüsselung sein, typisch 128 Bit. Als Nächstes erstellt Alice ${\displaystyle m}$ weitere zufällige Schlüssel ${\displaystyle k_{i}}$, diesmal der Länge ${\displaystyle n}$ Bit. Der Parameter ${\displaystyle n}$ wurde absichtlich so gewählt, dass eine mit einem ${\displaystyle n}$ Bit langen Schlüssel verschlüsselte Nachricht mit realistischem, aber nicht zu kleinem Aufwand entziffert werden kann, etwa im Bereich ${\displaystyle 40\leq n\leq 64}$. Alice verschlüsselt nun jeden Tabelleneintrag ${\displaystyle (K_{i},i)}$ mit dem entsprechenden Schlüssel ${\displaystyle k_{i}}$. Die so erzeugten Chiffrate ${\displaystyle E_{k_{i}}(K_{i},i)}$ mit ${\displaystyle i=0,1,\cdots ,m-1}$ sendet sie in zufälliger Reihenfolge an Bob.

Bob wählt nun zufällig einen der verschlüsselten Tabelleneinträge aus und entziffert ihn, indem er alle möglichen Schlüssel der Länge ${\displaystyle n}$ durchprobiert, bis er den richtigen ${\displaystyle k_{i}}$ gefunden hat. Dafür braucht er höchstens ${\displaystyle 2^{n}}$ Versuche, im Mittel ${\displaystyle 2^{n}/2}$. Er merkt sich den Schlüssel ${\displaystyle K_{i}}$ und sendet den Index ${\displaystyle i}$ zurück an Alice. Damit haben die beiden den gemeinsamen Schlüssel ${\displaystyle K_{i}}$ vereinbart, mit dem sie nun z. B. mit einer symmetrischen Verschlüsselung Nachrichten austauschen können. Das kann das gleiche Verfahren ${\displaystyle E}$ wie oben sein, oder auch ein anderes.

In der Praxis müssen die Chiffrate noch zusätzliche Information enthalten, damit Bob das richtige Dechiffrat erkennen kann:

Alice könnte beispielsweise einen Text ${\displaystyle T}$ ausreichender Länge wählen, der an alle Tabelleneinträge angefügt und zusammen mit diesen verschlüsselt wird. ${\displaystyle T}$ wird außerdem im Klartext zusammen mit den Chiffraten ${\displaystyle E_{k_{i}}(K_{i},i,T)}$ an Bob gesendet. Bob kann dann den richtigen Schlüssel ${\displaystyle k_{i}}$ daran erkennen, dass ${\displaystyle T}$ im Dechiffrat richtig herauskommt. Das Dechiffrat könnte zwar rein zufällig plausibel sein, aber durch eine genügende Länge von ${\displaystyle T}$ macht man diesen Fall unwahrscheinlich. In diesem Fall ist auch darauf zu achten, dass ${\displaystyle E}$ ein modernes Verschlüsselungsverfahren wie etwa AES ist, welches gegen einen Angriff mit bekanntem Klartext sicher ist. Damit wird sichergestellt, dass ein Angreifer nicht mithilfe von ${\displaystyle T}$ die notwendige Anzahl von übersendeten Geheimnissen in vertretbarer Zeit entziffern kann.

Eine andere Möglichkeit ist, das Feld für den Index ${\displaystyle i}$ so groß zu machen, dass es für Zahlen bis deutlich über ${\displaystyle m\cdot 2^{n}}$ ausreicht. Dann wird mit hoher Wahrscheinlichkeit bei jedem falschen Schlüssel ein Index größer als ${\displaystyle m-1}$ herauskommen.

Ein Angreifer, der die Kommunikation der beiden belauscht, sieht zuerst die ${\displaystyle m}$ Chiffrate, die Alice an Bob schickt, dann den Index, den Bob zurückschickt, der aber von der Reihenfolge, in der die Chiffrate gesendet wurden, unabhängig ist. Daraus kann er den zwischen den beiden vereinbarten Schlüssel ${\displaystyle K_{i}}$ nicht unmittelbar ableiten. Es bleibt ihm also nichts anderes übrig, als so lange Chiffrate zu entziffern, bis er dasjenige findet, das den Index ${\displaystyle i}$ und den zugeordneten Schlüssel ${\displaystyle K_{i}}$ enthält. Dafür muss er im Mittel ${\displaystyle m/2}$ Chiffrate entziffern. Bei jeweils ${\displaystyle 2^{n}/2}$ Versuchen, den richtigen Schlüssel ${\displaystyle k_{i}}$ zu finden, braucht er insgesamt im Mittel ${\displaystyle m\cdot 2^{n}/4}$ Versuche. Wenn ${\displaystyle m=2^{n}}$ gewählt wurde, ist seine Laufzeit also quadratisch in der von Alice und Bob.

Angenommen, Bob kann pro Sekunde ${\displaystyle 2^{25}}$ Schlüssel durchprobieren. Dann braucht er bei ${\displaystyle n=25}$ maximal eine, im Mittel 1/2 Sekunde, um ein Chiffrat zu entziffern. Ein Angreifer mit derselben Rechenleistung bräuchte bei ${\displaystyle m=2^{25}}$ jedoch im Durchschnitt drei Monate. Allerdings kann ein Angreifer den Schlüssel mit Glück auch deutlich früher erraten.

In der theoretischen Kryptologie wird heutzutage in der Regel angenommen, dass die Laufzeit des Angreifers polynomial in einem Sicherheitsparameter ist. Nach dieser Definition reicht ein quadratischer Unterschied in der Laufzeit zwischen den Benutzern und dem Angreifer nicht aus, der Angreifer könnte alle Chiffrate durchprobieren. Das Verfahren ist in einem solchen Modell also nicht sicher.

Für die praktische Anwendung ist Merkles Puzzle sowieso weniger geeignet, weil die Sicherheitsreserve gering ist. Man muss es so abstimmen, dass Bob zum Entziffern nicht zu lange braucht, und keine übermäßig große Datenmenge zu übermitteln ist, aber ein Angreifer andererseits nur mit geringer Wahrscheinlichkeit den richtigen Tabelleneintrag rechtzeitig findet. Und was „rechtzeitig“ ist, kommt wieder darauf an, wie lange die Geheimhaltung bestehen soll. Für Geheimnisse, die auch nach Jahren noch brisant sind, sollte man es sowieso nicht einsetzen, denn ein Angreifer kann die übermittelten Nachrichten speichern und dann in Ruhe daran arbeiten, den Schlüssel zu finden. In der Praxis kommt daher etwa Diffie-Hellman zum Einsatz, welches auf dem diskreten Logarithmus basiert, was eine höhere Komplexität bietet.

Zuletzt ist festzuhalten, dass das Protokoll, wie alle anderen auch, nicht funktioniert, wenn der Angreifer ein Man-in-the-Middle ist, der die Nachrichten nicht nur belauscht, sondern auch verändert. Er ersetzt dann einfach die Chiffrate von Alice durch seine eigenen und sendet die an Bob. Dasselbe macht er mit Bobs an Alice zurückgesendeten Index. Diesem Problem wird entgegengewirkt, indem Alice und Bob ihre Nachrichten digital signieren.

1. ↑ Ralph Merkle: Secure Communications over Insecure Channels. In: Communications of the ACM. Band 21, Nr. 4, April 1978, S. 294–299, doi:10.1145/359460.359473. 
2. ↑ Public Key Cryptography: Merkle’s Puzzles. In: Manchester SIAM-IMA Student Chapter Blog. 29. Januar 2016, abgerufen am 30. Mai 2025 (englisch). 

• Ralph Merkle, Secure Communications over Insecure Channels (1974): Paper und Interview mit Ralph Merkle
• Ralph Merkle, 1974 project Publishing a new idea Geschichte der Entdeckung und Scan der Ideenskizze