Merkles puzzle

Merkle's Puzzle is the first key exchange protocol in which the two parties do not already have to share a secret key with the other or a third party. It was discovered by Ralph Merkle in 1974 but was not released until 1978. The existence of such a protocol has long been considered impossible, and its discovery can be seen as the beginning of public key cryptography .

description

When Alice wants to exchange a key with Bob , she first creates a table with random keys of the desired length. For a given symmetrical encryption method, it now selects random keys with a length of bits that is not too long and uses each of these keys to encrypt a table entry together with its index in the table. She sends the ciphers to Bob in a random order. ${\ displaystyle m}$ ${\ displaystyle K_ {i}}$ ${\ displaystyle E}$ ${\ displaystyle m}$ ${\ displaystyle k_ {i}}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle E_ {k_ {i}} (i, K_ {i})}$

Bob selects a random cipher and deciphers it by trying all possible keys. For that he needs at most attempts. He makes a note of the key and sends the index back to Alice. The two have thus agreed on the common key with which they can now e.g. B. can exchange messages via symmetric encryption . ${\ displaystyle 2 ^ {n}}$ ${\ displaystyle K_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle K_ {i}}$

In practice, the ciphers would also have to contain redundant information so that Bob can recognize the correct decipher. Alice could, for example, choose a text of sufficient length and append it to all table entries. is sent to Bob in clear text along with the . ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ displaystyle E_ {k_ {i}} (i, K_ {i}, T)}$

safety

An attacker who eavesdrop on the communication between the two sees first the ciphers that Alice sends to Bob, then the index that Bob sends back, which is independent of the order in which the ciphers were sent. So he has no choice but to decipher ciphers until he finds the one that contains the index . For this he needs up to attempts, on average . In his life is so square in the Alice and Bob. ${\ displaystyle m}$ ${\ displaystyle i}$ ${\ displaystyle m \ cdot 2 ^ {n}}$ ${\ displaystyle m \ cdot 2 ^ {n} / 4}$ ${\ displaystyle m = 2 ^ {n}}$

Suppose Bob can try keys every second . Then it takes a maximum of one, on average 1/2 second, to decipher a cipher. However, an attacker with the same computing power would take an average of three months. However, with luck, an attacker can guess the key much earlier. ${\ displaystyle 2 ^ {25}}$ ${\ displaystyle n = 25}$ ${\ displaystyle m = 2 ^ {25}}$

In theoretical cryptology nowadays it is generally assumed that the attacker's runtime is polynomial in a security parameter. According to this definition, a quadratic difference in the runtime between the user and the attacker is not sufficient; the attacker could try out all ciphers. The procedure is therefore not safe in such a model.

Individual evidence

↑ Ralph Merkle: Secure Communications over Insecure Channels . In: Communications of the ACM . tape 21 , no. 4 , April 1978, p. 294-299 , doi : 10.1145 / 359460.359473 .

Web links

Ralph Merkle, Secure Communications over Insecure Channels (1974) : Paper and interview with Ralph Merkle

Ralph Merkle, 1974 project Publishing a new idea History of the discovery and scan of the idea sketch

[Merkle78-1] Ralph Merkle: Secure Communications over Insecure Channels . In: Communications of the ACM . tape 21 , no. 4 , April 1978, p. 294-299 , doi : 10.1145 / 359460.359473 .