Merkles Puzzle

Merkles Puzzle ist das erste Schlüsselaustauschprotokoll, bei dem die beiden Parteien nicht bereits einen geheimen Schlüssel mit der jeweils anderen oder einer dritten Partei teilen müssen. 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.

BeschreibungBearbeiten

Wenn Alice mit Bob einen Schlüssel austauschen möchte, legt sie zuerst eine Tabelle mit   zufälligen Schlüsseln   der gewünschten Länge an. Für ein gegebenes symmetrisches Verschlüsselungsverfahren   wählt sie nun   zufällige Schlüssel   mit einer nicht zu großen Länge von   Bit und verschlüsselt mit jedem dieser Schlüssel einen Tabelleneintrag zusammen mit seinem Index in der Tabelle. Die   Chiffrate   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   Versuche. Er merkt sich den Schlüssel   und sendet den Index   zurück an Alice. Damit haben die beiden den gemeinsamen Schlüssel   vereinbart, mit dem sie nun z. B. über eine symmetrische Verschlüsselung Nachrichten austauschen können.

In der Praxis müssten die Chiffrate auch redundante Information enthalten, damit Bob das richtige Dechiffrat erkennen kann. Alice könnte beispielsweise einen Text   ausreichender Länge wählen und an alle Tabelleneinträge anhängen.   wird im Klartext zusammen mit den   an Bob gesendet.

SicherheitBearbeiten

Ein Angreifer, der die Kommunikation der beiden belauscht, sieht zuerst die   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   enthält. Dafür braucht er bis zu   Versuche, im Mittel  . Bei   ist seine Laufzeit also quadratisch in der von Alice und Bob.

Angenommen, Bob kann pro Sekunde   Schlüssel durchprobieren. Dann braucht er bei   maximal eine, im Mittel 1/2 Sekunde, um ein Chiffrat zu entziffern. Ein Angreifer mit derselben Rechenleistung bräuchte bei   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.

EinzelnachweiseBearbeiten

  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.

WeblinksBearbeiten