"Merkle's Puzzles" is an early key exchange protocol where Alice sends Bob a large batch of "puzzles" (messages containing a unique ID and a secret key) each encrypted with a weak breakable cipher. Bob chooses and brute forces just one puzzle to reveal the key and then publicly tells Alice which ID he solved — as shown in the diagram below (https://www.youtube.com/watch?v=e3VxAM2oqYI). While an eavesdropper can see every puzzle and the final ID, they are at a massive mathematical disadvantage. Bob only has to solve one puzzle (linear task) whereas the attacker would need to solve a significant portion of the entire batch (quadratic task) to find the specific key Bob chose. This creates a shared secret that allows both parties to transition to secure symmetric encryption for the rest of their conversation (https://manchestersiam.wordpress.com/2016/01/29/public-key-cryptography-merkles-puzzles/).
Overall, Merkle's puzzles possess two major limitations: efficiency and security. In terms of efficiency, the protocol only offers a quadratic advantage; if Alice and Bob spend O(n + m) effort to establish a key, an attacker can break it in O(n x m) time. To make this secure against modern computing "n" and "m" would have to be so large that the process becomes too slow for practical use. Furthermore, the protocol lacks authentication, making it highly susceptible to MitM (Man in the Middle) attacks. In this scenario, an attacker intercepts the exchange and establishes separate encrypted sessions with both Alice and Bob. Thus, allowing them to transparently read or modify messages while both parties believe they are speaking directly to one another (http://www.crypto-it.net/eng/asymmetric/merkle-puzzles.html).
Lastly, Merkle's puzzles are fundamentally insecure for modern use because they rely on a linear security gap rather than an exponential one. While a million fold increase in effort sounded robust in the 1970s, modern hardware has rendered it trivial. To achieve even a basic level of security today, Alice would have to transmit terabytes of "puzzles" just to agree on a single key (creating a massive communication bottleneck). Unlike modern algorithms Merkle's puzzles scale poorly. Hence, offering no protection against high speed brute forcing and providing zero "forward secrecy" against attackers who record data to crack later (https://backdrifting.net/post/013_puzzle_box_key_exchange).
See you in my next writeup ;-) You can follow me on twitter — @boutnaru (https://twitter.com/boutnaru). Also, you can read my other writeups on medium — https://medium.com/@boutnaru. You can find my free eBooks at https://TheLearningJourneyEbooks.com.
