Algoritmos de cifrado explicados con ejemplos

La criptografía, en su forma más básica, es la ciencia del uso de códigos y cifrados para proteger los mensajes.

La encriptación consiste en codificar mensajes con la intención de que solo el destinatario deseado comprenda el significado del mensaje. Es una función bidireccional (debe poder deshacer cualquier codificación que haya hecho en el mensaje). Está diseñado para proteger los datos en tránsito.

Si está buscando una base general sobre la diferencia entre algoritmos simétricos y asimétricos y una descripción general de lo que es el cifrado, comience aquí. Este artículo cubrirá principalmente dos de los algoritmos de cifrado más utilizados.

Como descripción general, hubo un problema importante con los algoritmos simétricos cuando se crearon por primera vez: solo funcionaban de manera efectiva si ambas partes ya conocían el secreto compartido. Si no lo hicieron, intercambiar una clave de forma segura sin que un tercero lo viera fue extremadamente difícil.

Y si un tercero obtenía la clave, era muy fácil para ellos romper el cifrado, frustrando el propósito de la comunicación segura.

Diffie-Hellman resolvió este problema al permitir que extraños intercambiaran información a través de canales públicos que pueden usarse para formar una clave compartida. Una clave compartida es difícil de descifrar, incluso si se controlan todas las comunicaciones.

¿Cómo actúa Diffie-Hellman?

Diffie-Hellman es lo que se llama protocolo de intercambio de claves. Este es el uso principal de Diffie-Hellman, aunque también podría usarse para el cifrado (normalmente no lo es, porque es más eficiente usar DH para intercambiar claves y luego cambiar a un cifrado simétrico (significativamente más rápido) para la transmisión de datos ).

La forma en que esto funciona es la siguiente:

Básicamente, hay dos partes, Alice y Bob, que acuerdan un color de inicio (arbitrario pero tiene que ser diferente cada vez). También tienen un color secreto que guardan para sí mismos. Luego mezclan este color con el color compartido, lo que da como resultado dos colores diferentes. Luego pasan este color a la otra parte, quien lo mezcla con su color secreto, resultando en el mismo color secreto final.

Esto se basa en la idea de que es relativamente fácil mezclar dos colores, pero es muy difícil separarlos para encontrar el color secreto. En la práctica, esto se hace con matemáticas.

Por ejemplo:

  1. Bob y Alice están de acuerdo en dos números, un primo grande, p = 29 y base g = 5
  2. Ahora Bob elige un número secreto, x (x = 4) y hace lo siguiente: X = g ^ x% p (en este caso% indica el resto. Por ejemplo, 3% 2 es 3/2, donde el resto es 1) . X = 5 ^ 4% 29 = 625% 29 = 16
  3. Alice también elige un número secreto, y (y = 8) y hace lo siguiente: Y = g ^ y% p. Y = 5 ^ 8% 29 = 390,625% 29 = 24
  4. Bob envía X a Alice y Alice envía Y a Bob.
  5. Entonces Bob hace lo siguiente: K = Y ^ x% p, K = 24 ^ 4% 29 = 331,776% 29 = 16
  6. Alice entonces hace lo siguiente: K = X ^ y% p, K = 16 ^ 8% 29 = 4,294,967,296% 29 = 16

Lo bueno (* posiblemente mágico *) de esto es que tanto Bob como Alice tienen el mismo número, K, y ahora pueden usarlo para hablar en secreto, porque nadie más conoce a K.

La seguridad de este protocolo se basa en algunas cosas:

  1. (Hecho) Es relativamente fácil generar números primos, incluso números primos grandes (como p).
  2. (Hecho) La exponenciación modular es fácil. En otras palabras, es relativamente fácil calcular X = g ^ x% p.
  3. (Supuesto basado en la potencia informática y las matemáticas actuales) La extracción de raíz modular sin los factores primos es muy difícil. Esencialmente, es muy difícil encontrar K sin saber xey, incluso si ha fisgoneado en el tráfico y puede ver p, g, X e Y.

Por lo tanto, asumiendo que esto se implementó correctamente, es relativamente fácil hacer los cálculos necesarios para crear la clave, pero es extremadamente difícil y lleva mucho tiempo hacer los cálculos necesarios para intentar romper la clave mediante la fuerza bruta.

Incluso si un atacante pudiera comprometer esta clave, Diffie-Hellman permite un perfecto secreto hacia adelante.

¿Qué es el secreto directo perfecto?

Esta es la idea de que si descifras el cifrado que el servidor está usando para comunicarse ahora, no significa que todas las comunicaciones que el servidor haya realizado puedan ser leídas.

En otras palabras, solo le permite ver las comunicaciones que se están utilizando ahora (es decir, con esta clave secreta). Dado que cada conjunto de comunicaciones tiene una clave secreta diferente, debería descifrarlas todas por separado.

Esto es posible si cada sesión tiene una clave efímera diferente para cada sesión. Debido a que Diffie-Hellman siempre usa nuevos valores aleatorios para cada sesión, (por lo tanto, genera nuevas claves para cada sesión) se llama Efímero Diffie Hellman (EDH o DHE). Muchas suites de cifrado utilizan esto para lograr un secreto directo perfecto.

Como Diffie-Hellman le permite intercambiar material clave en texto plano sin preocuparse por comprometer el secreto compartido, y las matemáticas son demasiado complicadas para que un atacante la fuerza bruta, el atacante no puede derivar la clave de sesión (e incluso si pudiera, usando claves diferentes y efímeras para cada sesión significa que solo pueden espiar esta sesión, no ninguna en el pasado o el futuro)

El secreto directo está habilitado con cualquier intercambio de claves Diffie-Hellman, pero solo el intercambio de claves efímeras (una clave diferente para cada sesión) proporciona un secreto directo perfecto.

Aquí hay una publicación de Scott Helme que habla de esto con más profundidad y explica cómo habilitar esto en sus servidores.

¿Cuáles son las limitaciones de Diffie-Hellman?

La mayor limitación de DH es que no verifica la identidad. En otras palabras, cualquiera puede afirmar ser Alice o Bob y no existe un mecanismo incorporado para verificar que su afirmación sea verdadera.

Además, si la implementación no se lleva a cabo de manera segura, el algoritmo podría descifrarse con suficientes recursos dedicados (poco probable, pero posible para equipos académicos o actores del estado-nación).

Por ejemplo, esto podría ocurrir si el generador de números aleatorios no cuenta con la entropía adecuada para soportar la fuerza deseada; en otras palabras, debido a que los números generados por computadora nunca son verdaderamente aleatorios, el grado en el que ha inyectado artificialmente la incertidumbre es importante para la fuerza. de su implementación.

Además, se demostró un ataque en 2015 que mostró que cuando muchos servidores utilizaron los mismos números primos al comienzo del intercambio de claves, la seguridad general de Diffie-Hellman fue menor de lo esperado.

Esencialmente, un atacante podría simplemente calcular previamente el ataque contra ese número primo, lo que facilitaría comprometer las sesiones de cualquier servidor que haya utilizado ese número primo.

Esto ocurrió porque millones de servidores usaban los mismos números primos para intercambios de claves. La precomputación de este tipo de ataque aún requiere recursos académicos o de nivel estatal y es poco probable que afecte a la gran mayoría de las personas.

Sin embargo, afortunadamente para aquellos que tienen que preocuparse por los atacantes del estado-nación, existe una forma diferente de lograr el intercambio de claves DH utilizando criptografía de curva elíptica (ECDHE). Esto está fuera del alcance de este artículo, pero si está interesado en aprender más sobre las matemáticas detrás de este intercambio, consulte este artículo.

Para obtener una visión más detallada de las debilidades de DH, consulte este documento técnico y este sitio web.

RSA

RSA lleva el nombre de los creadores (Rivest, Shamir, Adleman) y es una forma de generar claves públicas y privadas.

Técnicamente, hay dos algoritmos RSA (uno que se usa para firmas digitales y otro que se usa para el cifrado asimétrico). Este artículo cubre el algoritmo de cifrado asimétrico.

Esto permite el intercambio de claves: primero asigna a cada parte las claves públicas / privadas de la transacción, luego genera una clave simétrica y, finalmente, utiliza los pares de claves pública / privada para comunicar de forma segura la clave simétrica compartida.

Debido a que el cifrado asimétrico es generalmente más lento que el cifrado simétrico y no se escala tan bien, es muy común utilizar el cifrado asimétrico para intercambiar claves simétricas de forma segura.

¿Entonces, cómo funciona?

  1. Elija 2 números primos muy grandes (al menos 512 bits o 155 dígitos decimales cada uno), xey (estos números deben ser secretos y elegidos al azar)
  2. Encuentre el producto, es decir, z = x * y
  3. Seleccione un número entero público impar, e, entre 3 y n - 1, y no tenga factores comunes (distintos de 1) con (x-1) (y-1) (por lo que es primo relativo ax - 1 e y - 1 ).
  4. Encuentra el mínimo común múltiplo de x - 1 e y - 1, y llámalo L.
  5. Calcule el exponente privado, d, a partir de x, y y e. de = 1% L. d es la inversa de e% L (sabes que existe una inversa porque e es primo relativo a z - 1 e y - 1). Este sistema funciona porque p = (p ^ e) ^ d% z.
  6. Salida (z, e) como clave pública y (z, d) como clave privada.

Ahora, si Bob quisiera enviar un mensaje a Alice, genera el texto cifrado (C) a partir del texto plano (P) usando esta fórmula:

C = P ^ e% z

Para descifrar este mensaje, Alice calcula lo siguiente:

P = C ^ d% z

La relación entre dye asegura que las funciones de cifrado y descifrado sean inversas. Eso significa que la función de descifrado puede recuperar con éxito el mensaje original y que es bastante difícil recuperar el mensaje original sin la clave privada (z, d) (o los factores primos xey).

Esto también significa que puede hacer públicos zye sin comprometer la seguridad del sistema, lo que facilita la comunicación con otras personas con las que aún no tiene una clave secreta compartida.

También puede utilizar las operaciones a la inversa para obtener una firma digital del mensaje. Primero, usa la operación de descifrado en el texto sin formato. Por ejemplo, s = FIRMA (p) = p ^ d% z.

Luego, el destinatario puede verificar la firma digital aplicando la función de encriptación y comparando el resultado con el mensaje. Por ejemplo, m = VERIFY (s) = S ^ e% z.

A menudo, cuando se hace esto, el texto sin formato es un hash del mensaje, lo que significa que puede firmar el mensaje (independientemente de su longitud) con solo una exponenciación.

La seguridad del sistema se basa en algunas cosas:

  1. (Hecho) Es relativamente fácil generar números primos, incluso números primos grandes (como xey).
  2. (Hecho) La multiplicación es fácil. Es muy fácil encontrar z.
  3. (Supuesto basado en matemáticas actuales) Factorizar es difícil. Dado z, es relativamente difícil recuperar xey. Es factible, pero lleva un tiempo y es caro.

    Una estimación dice que recuperar los factores primos de un número de 1024 bits llevaría un año en una máquina que cuesta $ 10 millones. Duplicar el tamaño aumentaría exponencialmente la cantidad de trabajo necesario (varios miles de millones de veces más trabajo).

    A medida que la tecnología continúe avanzando, estos costos (y el trabajo requerido) disminuirán, pero en este punto, este tipo de cifrado, implementado correctamente, es una fuente poco probable de compromiso.

    Generalmente, los únicos hackers con este tipo de dinero y dedicación a un solo objetivo son los estados-nación. Además, si existe una forma más fácil de comprometer un sistema (ver más abajo), probablemente sea una mejor opción.

4. (Hecho) La exponenciación modular es fácil. En otras palabras, es relativamente fácil calcular c = p ^ e% z.

5. (Hecho) La extracción de raíz modular, revertir el proceso anterior, es fácil si tiene los factores primos (si tiene z, c, e y los factores primos xey, es fácil encontrar p tal que c = p ^ e% z).

6. (Supuesto basado en la potencia informática y las matemáticas actuales) La extracción de raíz modular sin los factores primos es muy difícil (si tiene z, c, e, pero no xey, es relativamente difícil encontrar p tal que c = p ^ e% z, particularmente si a es suficientemente grande).

¿Quieres aprender más sobre matemáticas de personas mucho más inteligentes? Mira este artículo.

Genial, ¿cuál es mejor?

Depende de su caso de uso. Hay algunas diferencias entre los dos algoritmos: primero, el secreto directo perfecto (PFS), del que hablamos anteriormente en el contexto de Diffie-Hellman. Si bien técnicamente podría generar pares de claves RSA efímeros y proporcionar un secreto directo perfecto con RSA, el costo computacional es mucho más alto que para Diffie-Hellman, lo que significa que Diffie-Hellman es una mejor opción para implementaciones de SSL / TLS en las que desea un secreto directo perfecto. .  

Si bien existen algunas diferencias de rendimiento entre los dos algoritmos (en términos de trabajo requerido del servidor), las diferencias de rendimiento generalmente no son lo suficientemente grandes como para marcar la diferencia al elegir uno sobre el otro.

En cambio, en general, la consideración principal al determinar cuál es mejor depende de cuál es más compatible para su caso de uso (por ejemplo, al implementar SSL, querrá Diffie Hellman debido al secreto directo perfecto) o cuál es más popular o aceptado como el estándar en la industria.

Por ejemplo, aunque Diffie-Hellman fue aprobado por el gobierno de EE. UU. Y respaldado por un organismo institucional, el estándar no se publicó, mientras que RSA (estandarizado por una organización privada) proporcionó un estándar gratuito, lo que significa que RSA se volvió muy popular entre las organizaciones privadas.

Si está interesado en leer más, aquí hay un gran hilo sobre las diferencias.

¿Está interesado en aprender cómo los piratas informáticos utilizan los ataques criptográficos? Prueba este conjunto de desafíos de Cryptopals.

Cuanto más aprendo sobre criptografía, más creo que Alice y Bob probablemente deberían hablar en persona.

- Paul Reinheimer (@preinheimer) 13 de marzo de 2017