imported>Heronils: /* Sicherheit des Protokolls */ Wort hinzugefügt um klarzumachen dass es eine Alternative ist.

2026-03-13T18:12:17Z

Sicherheit des Protokolls: Wort hinzugefügt um klarzumachen dass es eine Alternative ist.

Neue Seite

'''Merkles Puzzle''' ist ein [[Kryptographie|kryptografisches]] [[Schlüsselaustauschprotokoll]]. Es ist das erste derartige [[Kommunikationsprotokoll|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.<ref name="Merkle78" /> Ein solches Protokoll wurde lange Zeit für unmöglich gehalten, und seine Entdeckung kann als Beginn der [[Public-Key-Kryptographie]] gesehen werden.

== Funktionsweise ==

=== Übersicht ===
[[Alice und Bob|Alice]] erzeugt eine große Zahl von Geheimnissen ([[Geheimtext]]en) und schickt sie an [[Alice und Bob|Bob]]. Bob wählt zufällig eines davon aus und [[Entzifferung|entziffert]] es. Er erhält daraus einen Schlüssel und einen zugeordneten, eindeutigen Index. Er schickt den Index zurück an Alice, die nun weiß, welchen Schlüssel Bob verwendet. Ein geheimer Beobachter weiß das allerdings nicht und muss so lange Geheimnisse entziffern, bis er den Index und den zugeordneten Schlüssel findet. Dafür braucht er im Allgemeinen viel mehr Zeit als Bob, da er viele der Geheimnisse entziffern muss statt nur eines.

=== Detaillierte Beschreibung ===
Alice und Bob einigen sich zunächst auf ein [[Symmetrisches Kryptosystem|symmetrisches Verschlüsselungsverfahren]] <math>E</math>, beispielsweise [[Advanced Encryption Standard|AES]]. Ferner auf die Parameter <math>m</math> und <math>n</math>. Diese sind [[natürliche Zahl]]en. <math>m</math> könnte etwa 1 Million<ref>{{Internetquelle |url=https://manchestersiam.wordpress.com/2016/01/29/public-key-cryptography-merkles-puzzles/ |titel=Public Key Cryptography: Merkle’s Puzzles |werk=Manchester SIAM-IMA Student Chapter Blog |datum=2016-01-29 |sprache=en |abruf=2025-05-30}}</ref> sein und <math>n</math> etwa 64.

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

Bob wählt nun zufällig einen der Geheimtexte aus und entziffert ihn, indem er alle möglichen Schlüssel der Länge <math>n</math> durchprobiert, bis er den richtigen <math>s_i</math> gefunden hat. Dafür braucht er höchstens <math>2^n</math> Versuche, im Mittel <math>2^n/2</math>. Er merkt sich den Schlüssel <math>K_i</math> und sendet den Index <math>i</math> zurück an Alice. Damit haben die beiden den gemeinsamen Schlüssel <math>K_i</math> vereinbart, mit dem sie nun z. B. mit AES Nachrichten austauschen können.

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

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

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

== Sicherheit des Protokolls ==
Ein Angreifer, der die Kommunikation der beiden belauscht, sieht zuerst die <math>m</math> Chiffrate, die Alice an Bob schickt, dann den entzifferten Index <math>i</math>, 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 <math>K_i</math> nicht unmittelbar ableiten. Es bleibt ihm also nichts anderes übrig, als so lange Chiffrate zu entziffern, bis er dasjenige findet, das den Index <math>i</math> und den zugeordneten Schlüssel <math>K_i</math> enthält. Dafür muss er im Mittel <math>m / 2</math> Chiffrate entziffern. Bei jeweils <math>2^n/2</math> Versuchen, den richtigen Schlüssel <math>s_i</math> zu finden, braucht er insgesamt im Mittel <math>m \cdot 2^n / 4</math> Versuche. Wenn <math>m = 2^n</math> gewählt wurde, ist seine Laufzeit also quadratisch in der von Alice und Bob.

Angenommen, Bob kann pro Sekunde <math>2^{25}</math> Schlüssel durchprobieren. Dann braucht er bei <math>n = 25</math> maximal eine, im Mittel 1/2 Sekunde, um ein Chiffrat zu entziffern. Ein Angreifer mit derselben Rechenleistung bräuchte bei <math>m=2^{25}</math> 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. In der Praxis kommt daher stattdessen etwa [[Diffie-Hellman-Schlüsselaustausch|Diffie-Hellman]] zum Einsatz, welches auf dem [[Diskreter Logarithmus|diskreten Logarithmus]] basiert, was eine höhere Komplexität bietet. Für Geheimnisse, die auch nach Jahren noch brisant sind, sollte man Merkles Puzzle sowieso nicht einsetzen, denn ein Angreifer kann die übermittelten Nachrichten speichern und dann in Ruhe daran arbeiten, den Schlüssel zu finden. Hier empfehlen sich stattdessen [[Einmalkennwort|Einmalkennwörter]].

Zuletzt ist festzuhalten, dass das Protokoll, wie alle anderen auch, nicht funktioniert, wenn der Angreifer ein [[Man-in-the-Middle-Angriff|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 [[Digitale Signatur|digital signieren]].

== Einzelnachweise ==
<references>
<ref name="Merkle78">{{Literatur |Autor=Ralph Merkle |Titel=Secure Communications over Insecure Channels |Sammelwerk=Communications of the ACM |Band=21 |Nummer=4 |Datum=1978-04 |Seiten=294–299 |DOI=10.1145/359460.359473}}</ref>
</references>

== Weblinks ==
* Ralph Merkle, [http://www.selmer.uib.no/researchcourse2004/program/RonRivest/Merkle-SecureCommunicationOverInsecureChannels.htm Secure Communications over Insecure Channels (1974)]: Paper und Interview mit Ralph Merkle
* Ralph Merkle, 1974 [http://www.merkle.com/1974 project Publishing a new idea] Geschichte der Entdeckung und Scan der Ideenskizze

[[Kategorie:Schlüsselaustauschprotokoll]]

Merkles Puzzle - Versionsgeschichte

imported>Heronils: /* Sicherheit des Protokolls */ Wort hinzugefügt um klarzumachen dass es eine Alternative ist.