- Block diagrams
- Mathematical functions
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:
- One of the parties (Alice) prepares a lot of messages, which consist of a unique random id and a unique random key.
- 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).
- Bob chooses randomly one of the received encrypted messages and breaks its security using a brute force attack.
- Bob informs Alice, what is the id value in the message selected by him.
- 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.
Security of Merkle's Puzzles
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).