Diffie-Hellman: el algoritmo genial detrás de la comunicación de red segura

Comencemos con un experimento mental rápido.

Tienes una red de 3 computadoras, utilizadas por Alice, Bob y Charlie. Los 3 participantes pueden enviar mensajes, pero solo de una manera que todos los demás clientes que se conectaron a la red puedan leerlos. Ésta es la única forma de comunicación posible entre los participantes.

Si Alice envía un mensaje a través de los cables, tanto Bob como Charlie lo reciben. En otras palabras, Alice no puede enviar un mensaje directo a Bob sin que Charlie lo reciba también.

Pero Alice quiere enviar un mensaje confidencial a Bob y no quiere que Charlie pueda leerlo.

Parece imposible con estas estrictas reglas, ¿verdad? Lo hermoso que este problema se resuelve en 1976 por Whitfield Diffie y Martin Hellman.

Esta es una versión simplificada del mundo real, pero enfrentamos el mismo problema cuando nos comunicamos a través de la red más grande que jamás haya existido.

Por lo general, no está conectado directamente a Internet, pero forma parte de una red local más pequeña, llamada Ethernet.

Esta red más pequeña puede ser cableada o inalámbrica (Wi-Fi), pero el concepto básico permanece. Si envía una señal a través de la red, esta señal puede ser leída por todos los demás clientes conectados a la misma red.

Una vez que emita un mensaje al servidor de su banco con la información de su tarjeta de crédito, todos los demás clientes de la red local recibirán el mensaje, incluido el enrutador. Luego lo reenviará al servidor real del banco. Todos los demás clientes ignorarán el mensaje.

Pero, ¿qué pasa si hay un cliente malintencionado en la red que no ignora sus mensajes confidenciales, sino que los lee? ¿Cómo es posible que aún tenga dinero en su cuenta bancaria?

Cifrado

En este punto, está claro que necesitamos usar algún tipo de cifrado para asegurarnos de que el mensaje sea legible para Alice y Bob, pero un galimatías completo para Charlie.

El cifrado de la información se realiza mediante un algoritmo de cifrado, que toma una clave (por ejemplo, una cadena) y devuelve un valor cifrado, llamado texto cifrado. El texto cifrado es simplemente una cadena de aspecto completamente aleatorio.

Es importante que el valor cifrado (texto cifrado) se pueda descifrar solo con la clave original. Esto se llama algoritmo de clave simétrica porque necesita la misma clave para descifrar el mensaje con la que se cifró. También hay algoritmos de clave asimétrica, pero no los necesitamos en este momento.

Para que sea más fácil de entender esto, aquí hay un algoritmo de cifrado ficticio implementado en JavaScript:

function encrypt(message, key) { return message.split("").map(character => { const characterAsciiCode = character.charCodeAt(0) return String.fromCharCode(characterAsciiCode+key.length) }).join(""); }

En esta función, asigné cada carácter a otro carácter según la longitud de la clave dada.

Cada carácter tiene una representación entera, llamada código ASCII. Hay un diccionario que contiene todos los caracteres con su código, llamado tabla ASCII. Así que incrementamos este número entero por la longitud de la clave:

Descifrar el texto cifrado es bastante similar. Pero en lugar de sumar, restamos la longitud de la clave de cada carácter en el texto cifrado, por lo que recuperamos el mensaje original.

function decrypt(cipher, key) { return cipher.split("").map(character => { const characterAsciiCode = character.charCodeAt(0) return String.fromCharCode(characterAsciiCode-key.length) }).join(""); }

Finalmente, aquí está el cifrado ficticio en acción:

const message = "Hi Bob, here is a confidential message!"; const key = "password"; const cipher = encrypt(message, key); console.log("Encrypted message:", cipher); // Encrypted message: Pq(Jwj4(pmzm(q{(i(kwvnqlmv|qit(um{{iom) const decryptedMessage = decrypt(cipher, key); console.log("Decrypted message:", decryptedMessage); // Decrypted message: Hi Bob, here is a confidential message!

Aplicamos cierto grado de cifrado al mensaje, pero este algoritmo solo fue útil para fines de demostración, para tener una idea de cómo se comportan los algoritmos de cifrado de clave simétrica.

Hay un par de problemas con esta implementación además de manejar mal los casos de esquina y los tipos de parámetros.

En primer lugar, cada clave de 8 caracteres puede descifrar el mensaje que se cifró con la clave "contraseña". Queremos que un algoritmo de cifrado solo pueda descifrar un mensaje si le damos la misma clave con la que se cifró el mensaje. Una cerradura de puerta que se puede abrir con cualquier otra llave no es tan útil.

En segundo lugar, la lógica es demasiado simple: cada carácter se desplaza la misma cantidad en la tabla ASCII, lo cual es demasiado predecible. Necesitamos algo más complejo para que sea más difícil encontrar el mensaje sin la clave.

En tercer lugar, no hay una longitud mínima de clave. Los algoritmos modernos funcionan con claves de al menos 128 bits (~ 16 caracteres). Esto aumenta significativamente el número de claves posibles y, con ello, la seguridad del cifrado.

Por último, se necesita muy poco tiempo para cifrar o descifrar el mensaje. Esto es un problema porque no lleva demasiado tiempo probar todas las claves posibles y descifrar el mensaje cifrado.

Esto va de la mano con la longitud de la clave: un algoritmo es seguro si yo, como atacante, quiero encontrar la clave, entonces necesito probar una gran cantidad de combinaciones de teclas y se necesita un tiempo relativamente largo para probar una sola combinación.

Existe una amplia gama de algoritmos de cifrado simétrico que abordan todas estas afirmaciones, que a menudo se utilizan juntos para encontrar una buena relación de velocidad y seguridad para cada situación.

Los algoritmos de clave simétrica más populares son Twofish, Serpent, AES (Rijndael), Blowfish, CAST5, RC4, TDES e IDEA.

Si desea obtener más información sobre la criptografía en general, consulte esta charla.

Intercambio de llaves

Parece que redujimos el espacio del problema original. Con el cifrado, podemos crear un mensaje significativo para las partes que son elegibles para leer la información, pero que es ilegible para otros.

Cuando Alice quiere escribir un mensaje confidencial, elige una clave y encripta su mensaje con ella y envía el texto cifrado a través de los cables. Tanto Bob como Charlie recibirían el mensaje encriptado, pero ninguno de ellos podría interpretarlo sin la clave de Alice.

Ahora, la única pregunta que hay que responder es cómo Alice y Bob pueden encontrar una clave común simplemente comunicándose a través de la red y evitar que Charlie descubra esa misma clave.

Si Alice envía su clave directamente a través de los cables, Charlie la interceptaría y podría descifrar todos los mensajes de Alice. Entonces esta no es una solución. A esto se le llama el problema del intercambio de claves en informática.

Intercambio de claves Diffie-Hellman

Este genial algoritmo proporciona una forma de generar una clave compartida entre dos personas de tal manera que la clave no se puede ver al observar la comunicación.

Como primer paso, diremos que hay un número primo enorme, conocido por todos los participantes, es información pública. Lo llamamos "p" o módulo .

También hay otro número público llamado "g" o base ,que es menor que p .

No se preocupe por cómo se generan estos números. En aras de la simplicidad, digamos que Alice elige un número primo muy grande ( p ) y un número que es considerablemente menor que p . Luego los envía a través de los cables sin ningún cifrado, para que todos los participantes conozcan estos números.

Ejemplo: para entender esto a través de un ejemplo, usaremos números pequeños. Digamos p = 23 y g = 5 .

Como segundo paso, tanto Alice ( a ) como Bob ( b ) elegirán un número secreto, que no le dirán a nadie, simplemente vive localmente en sus computadoras.

Ejemplo:Digamos que Alice eligió 4 ( a = 4 ) y Bob eligió 3 ( b = 3 ).

Como siguiente paso, harán algunos cálculos matemáticos con sus números secretos, calcularán:

  1. la base ( g ) en el poder de su número secreto,
  2. y lleve el módulo del número calculado a p .
  3. Llame al resultado A (para Alice) y B (para Bob).

Modulo is a simple mathematical statement, and we use it to find the remainder after dividing one number by another. Here is an example: 23 mod 4 = 3, because 23/4 is 5 and 3 remains.

Maybe it's easier to see all of this in code:

// base const g = 5; // modulus const p = 23; // Alice's randomly picked number const a = 4; // Alice's calculated value const A = Math.pow(g, a)%p; // Do the same for Bob const b = 3; const B = Math.pow(g, b)%p; console.log("Alice's calculated value (A):", A); // Alice's calculated value (A): 4 console.log("Bob's calculated value (B):", B); // Bob's calculated value (B): 10

Now both Alice and Bob will send their calculated values (A, B) through the network, so all participants will know them.

As a last step Alice and Bob will take each other's calculated values and do the following:

  1. Alice will take Bob's calculated value (B) in the power of his secret number (a),
  2. and calculate this number's modulo to p and will call the result s (secret).
  3. Bob will do the same but with Alice's calculated value (A), and his secret number (b).

At this point, they successfully generated a common secret (s), even if it's hard to see right now. We will explore this in more detail in a second.

In code:

// Alice calculate the common secret const secretOfAlice = Math.pow(B, a)%p; console.log("Alice's calculated secret:", secretOfAlice); // Alice's calculated secret: 18 // Bob will calculate const secretOfBob = Math.pow(A, b)%p; console.log("Bob's calculated secret:", secretOfBob); // Bob's calculated secret: 18

As you can see both Alice and Bob got the number 18, which they can use as a key to encrypt messages. It seems magic at this point, but it's just some math.

Let's see why they got the same number by splitting up the calculations into elementary pieces:

In the last step, we used a modulo arithmetic identity and its distributive properties to simplify nested modulo statements.

So Alice and Bob have the same key, but let's see what Charlie saw from all of this. We know that p and g are public numbers, available for everyone.

We also know that Alice and Bob sent their calculated values (A, B) through the network, so that can be also caught by Charlie.

Charlie knows almost all parameters of this equation, just a and b remain hidden. To stay with the example, if he knows that A is 4 and p is 23, g to the power of a can be 4, 27, 50, 73, ... and infinite other numbers which result in 4 in the modulo space.

He also knows that only the subset of these numbers are possible options because not all numbers are an exponent of 5 (g), but this is still an infinite number of options to try.

This doesn't seem too secure with small numbers. But at the beginning I said that p is a really large number, often 2000 or 4000 bits long. This makes it almost impossible to guess the value of a or b in the real world.

The common key Alice and Bob both possess only can be generated by knowing a or b, besides the information that traveled through the network.

If you're more visual, here is a great diagram shows this whole process by mixing buckets of paint instead of numbers.

Here p and g shared constants represented by the yellow "Common paint". Secret numbers of Alice and Bob (a, b) is "Secret colours", and "Common secret" is what we called s.

This is a great analogy because it's representing the irreversibility of the modulo operation. As mixed paints can't be unmixed to their original components, the result of a modulo operation can't be reversed.

Summary

Now the original problem can be solved by encrypting messages using a shared key, which was exchanged with the Diffie-Hellman algorithm.

With this Alice and Bob can communicate securely, and Charlie cannot read their messages even if he is part of the same network.

Thanks for reading this far! I hope you got some value from this post and understood some parts of this interesting communication flow.

If it was hard to follow the math of this explanation, here is a great video to help you understand the algorithm without math, from a higher level.

If you liked this post, you may want to follow me on Twitter to find some more exciting resources about programming and software development.