Merkle Puzzle

Merkles Puzzle ist der Name des ersten Schlüsselaustauschprotokolls, bei dem die Übertragung des geheimen Schlüssels zur Entschlüsselung eines symmetrischen Verschlüsselungsverfahrens nicht direkt erfolgen muss. Eine solche Übertragung birgt immer das Risiko des Abgehört-Werdens, was einem Angreifer möglich machen würde, die Nachricht unberechtigterweise zu dechiffrieren. Es wurde im Jahr 1974 von Ralph Merkle entdeckt, aber erst 1978 veröffentlicht. Die Existenz eines solchen Protokolls wurde lange für unmöglich gehalten, und seine Entdeckung kann als Beginn der Public-Key-Kryptografie gesehen werden.

Wenn Alice mit Bob einen Schlüssel austauschen möchte, legt Alice zuerst eine Tabelle mit m zufälligen Schlüsseln Ki der gewünschten Länge an. Für ein gegebenes symmetrisches Verschlüsselungsverfahren E wählt sie nun m zufällige Schlüssel Ki mit einer nicht zu großen Länge von n Bit und verschlüsselt mit jedem dieser Schlüssel einen Tabelleneintrag zusammen mit seinem Index in der Tabelle. Die m Chiffrate Eki ( i,Ki ) sendet Alice in zufälliger Reihenfolge an Bob. Bob wählt ein zufälliges Chiffrat aus und probiert alle möglichen Schlüssel aus, bis er richtig rät und das Chiffrat entschlüsseln kann. Dafür braucht er höchstens 2n Versuche. Er merkt sich den Schlüssel K und sendet den Index i zurück an Alice, die damit weiß, welchen Schlüssel Bob benutzt.

Ein Angreifer, der die Kommunikation der beiden belauscht, sieht zuerst die 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 knacken, bis er dasjenige findet, das den Index i enthält. Dafür braucht er bis zu m * 2n Versuche, bei m = 2n ist seine Laufzeit also quadratisch zu der von Alice und Bob.

Angenommen, Bob kann pro Sekunde 225 Schlüssel durchprobieren. Dann braucht er bei m = 225 und n = 25 maximal eine, im Mittel 1/2 Sekunde, um ein Chiffrat zu knacken, ein Angreifer mit derselben Rechenleistung jedoch im Durchschnitt ein halbes Jahr. Allerdings kann ein Angreifer den Schlüssel durch 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.



Quellen, Literaturverweise und weiterführende Links

Ertel, Wolfgang: Angewandte Kryptographie, Hanser Verlag 2012, S. 78