Crypto-IT

• without authentication

Merkle's Puzzles protocol allows any two parties to negotiate a shared secret key. The secret key can be later used to protect their further communication.

Merkle's Puzzles is one of the first algorithms for a public-key cryptosystem. It was invented by Ralph Merkle in 1974 and published in 1978.

The Merkle's Puzzles algorithm describes a communication between two parties which allows to create a shared secret key. It is impossible to deduce the key by a potential eavesdropper. The key may be later use during the further communication, protected by the symmetric encryption.

The protocol of the exchange of information between two parties (commonly referred to as Alice and Bob) is presented below. To determine the shared secret key, the following steps should be performed:

1. One of the parties (Alice) prepares a lot of messages, which consist of a unique random id and a unique random key.
2. Then, Alice encrypts each message using a weak cipher (for example a symmetric cipher with a secret 20-bit long key) and send all the encrypted messages to the second party (to Bob).
3. Bob chooses randomly one of the received encrypted messages and breaks its security using a brute force attack.
4. Bob informs Alice, what is the id value in the message selected by him.
5. At this point, both Alice and Bob possess the secret shared key, which was in the message chosen and broken by Bob. They can use it during the further communication.

The main idea of the algorithm of Merkle's Puzzles is that the big number of messages is encrypted using a cipher weak enough to be broken by a brute force attack by the receiver.

The secret unique key is specified by the message id transmitted without encryption. The attacker, who wants to capture the key, can overhear all messages. He would have to break many messages using brute force attacks, hoping to find the message which was chosen randomly. After its decryption, he would have had knowledge about the secret key. Therefore, the key which was used for encryption of the messages must be long enough, that decryption of a large number of messages would be practically impossible.

Assuming that decrypting one message using brute force attack requires n steps and that there are m messages, the establishment of the secret key takes Alice and Bob O(n+m) time. On the other hand, to discover the selected key, an eavesdropping intruder must perform calculations with complexity O(n*m).

Quadratic complexity of decrypting is typically not considered secure enough against an attacker. Too long key (that means too big value of n) causes using the protocol quite inconvenient for its users. At present, there are more efficient and convenient ways to use encryption with public and private keys.

Because the protocol does not provide authentication of the communicating parties, it is vulnerable to man-in-the-middle attacks. The attacker may establish two sessions of the protocol (one with Alice and one with Bob) and pretend to be the opposite side to each of them. He creates two symmetric keys and uses them in the communication with them (still pretending to be the opposite side to each of them).

A lot of messages, which are sent at the beginning of the protocol, must be encrypted by the first person using a symmetric cipher.

To achieve this, one of the common and popular algorithms of symmetric encryption is used. The only difference lies in the intentional weakening of the cipher, by used shorter symmetric keys. Usually, the original random key (let us say 128-bit long) is replaced by the key consisting of 98 bits set to 0 connected with 30 bits of random bits of the real key. The receiver must break those 30 random bits to read the message and get the symmetric key.