Puzles de Merkle

En criptografía, el método de los puzles de Merkle (del inglés, Merkle's puzzles) constituye un protocolo de intercambio de claves, es decir, un protocolo para intercambiar claves criptográficas de manera segura. Se basa en la elaboración de «puzles», problemas computacionales de complejidad moderada, que dificultan que un tercero que intercepte la comunicación obtenga la clave.

Los puzles de Merkle utilizan exclusivamente criptografía simétrica, a diferencia de la mayoría de protocolos de intercambio de claves actuales. Sin embargo son menos eficientes que estos y no se usan en la práctica. El método de Merkle constituye el primer protocolo de intercambio de claves de la historia, y debe su nombre a Ralph Merkle, quien lo desarrolló en 1974.

Descripción

Partiendo de dos partes interesadas en comunicarse, Alicia y Bob, una de ellas, por ejemplo Alicia, debe comenzar por elaborar una gran cantidad de «puzles» y enviárselas a la otra parte, Bernardo. Un puzle es un problema computacional que requiere una cantidad moderada de esfuerzo computacional para resolverse. Una vez resuelto un puzle se obtiene una posible clave lista para ser usada, así como un identificador que lo distingue del resto de puzles.

Cuando Bernardo recibe todos estos puzles elige uno al azar, lo resuelve y posteriormente envía el identificador de la clave seleccionada de vuelta a Alicia para que ésta sepa que clave se va a usar. De este modo acuerdan una clave secreta común, pues ambos conocen la que corresponde a dicho identificador. Si un tercero, Trudy, intercepta las comunicaciones entre Alicia y Bernardo y quiere obtener la clave, debe resolver todos los puzles hasta encontrarse con el identificador en cuestión. El método se considera seguro en la medida en que el esfuerzo total necesario para resolver una gran cantidad de puzles sea muy grande.

Para la elaboración de cada puzle, según la idea original de Ralph Merkle, pueden generarse una clave e identificador aleatorios, para después codificarlos mediante un cifrado simétrico con una clave relativamente corta. De este modo, el puzle puede resolverse mediante una dosis moderada de fuerza bruta.

Seguridad

El intercambio de la clave requiere la elaboración de los puzles por Alicia, así como de la resolución de uno de ellos por Bernardo. Si el número de puzles es n, y cada uno requiere hasta m intentos para ser resuelto, el tiempo para el intercambio de la clave es O(m + n). El tiempo medio que necesita Eva para descifrar puzles hasta encontrar la clave es O(n · m). Si el número de puzles es similar a la complejidad de los mismos, m ≈ n, la complejidad para Eva es cuadrática, O(n²) comparada con la de Alicia y Bernardo.

Esta complejidad polinomial no ofrece tanta seguridad como otros sistemas de clave pública que llegan a tener complejidad exponencial, en los que el esfuerzo computacional que requiere el atacante crece de forma exponencial respecto al que realiza el usuario autorizado. Además, existen resultados que sugieren que los puzles de Merkle son óptimos, en el sentido de que ningún otro protocolo de intercambio de claves basado en criptografía simétrica ofrece más dificultad a un atacante.

Referencias

• Barak, Boaz; Mahmoody-Ghidary, Mohammad (2009). «Merkle Puzzles Are Optimal — An O(n²)-Query Attack on Any Key Exchange from a Random Oracle». En Shai Halevi, ed. Advances in Cryptology - CRYPTO 2009 (en inglés). doi:10.1007/978-3-642-03356-8_22. 
• Boneh, Dan. Introduction to Cryptography — Merkle's Puzzles. Coursera. Consultado el 28 de julio de 2013. 
• Garfinkel, Simson (1995). PGP: Pretty Good Privacy (en inglés). O'Reilly Media. p. 69. ISBN 9781565920989. 

Enlaces externos

• Merkle, R. C. (abril de 1978). «Secure Communications over Insecure Channels». Communications of the ACM (en inglés) 21 (4): 294-299. doi:10.1145/359460.359473.  El artículo original de Merkle.

• Datos: Q1888605