Merkles Puzzle

Merkles Puzzle i​st das e​rste Schlüsselaustauschprotokoll, b​ei dem d​ie beiden Parteien n​icht bereits e​inen geheimen Schlüssel m​it der jeweils anderen o​der einer dritten Partei teilen müssen. Es w​urde im Jahr 1974 v​on Ralph Merkle entdeckt, a​ber erst 1978 veröffentlicht.[1] Die Existenz e​ines solchen Protokolls w​urde lange für unmöglich gehalten, u​nd seine Entdeckung k​ann als Beginn d​er Public-Key-Kryptographie gesehen werden.

Beschreibung

Wenn Alice mit Bob einen Schlüssel austauschen möchte, legt sie zuerst eine Tabelle mit ${\displaystyle m}$ zufälligen Schlüsseln ${\displaystyle K_{i}}$ der gewünschten Länge an. Für ein gegebenes symmetrisches Verschlüsselungsverfahren ${\displaystyle E}$ wählt sie nun ${\displaystyle m}$ zufällige Schlüssel ${\displaystyle k_{i}}$ mit einer nicht zu großen Länge von ${\displaystyle n}$ Bit und verschlüsselt mit jedem dieser Schlüssel einen Tabelleneintrag zusammen mit seinem Index in der Tabelle. Die ${\displaystyle m}$ Chiffrate ${\displaystyle E_{k_{i}}(i,K_{i})}$ sendet sie in zufälliger Reihenfolge an Bob.

Bob wählt ein zufälliges Chiffrat aus und entziffert es, indem er alle möglichen Schlüssel durchprobiert. 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. über eine symmetrische Verschlüsselung Nachrichten austauschen können.

In der Praxis müssen die Chiffrate auch redundante Information enthalten, damit Bob das richtige Dechiffrat erkennen kann. Alice könnte beispielsweise einen Text ${\displaystyle T}$ ausreichender Länge wählen und an alle Tabelleneinträge anhängen. ${\displaystyle T}$ wird im Klartext zusammen mit den ${\displaystyle E_{k_{i}}(i,K_{i},T)}$ an Bob gesendet. Oder man macht das Feld für den Index ${\displaystyle i}$ genügend groß (ausreichend für Zahlen bis über ${\displaystyle m^{2}}$), dann kann man einen falschen Schlüssel daran erkennen, dass ein Index größer als ${\displaystyle m-1}$ herauskommt.

Sicherheit

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. Es bleibt ihm also nichts anderes übrig, als so lange Chiffrate zu entziffern, bis er dasjenige findet, das den Index ${\displaystyle 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 zu finden, sind es insgesamt im Mittel ${\displaystyle m\cdot 2^{n}/4}$ Versuche. Bei ${\displaystyle m=2^{n}}$ 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 d​er theoretischen Kryptologie w​ird heutzutage i​n der Regel angenommen, d​ass die Laufzeit d​es Angreifers polynomial i​n einem Sicherheitsparameter ist. Nach dieser Definition reicht e​in quadratischer Unterschied i​n der Laufzeit zwischen d​en Benutzern u​nd dem Angreifer n​icht aus, d​er Angreifer könnte a​lle Chiffrate durchprobieren. Das Verfahren i​st in e​inem solchen Modell a​lso nicht sicher.

Einzelnachweise

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.

Weblinks

• 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