¿Cuál es la debilidad del relleno específico que aborda OAEP en RSA?

La operación en el núcleo de RSA es una exponenciación modular: dada la entrada m , computar m^e módulo n . Aunque en general esta es una permutación unidireccional de enteros modulo n , no cumple todas las características necesarias para el cifrado asimétrico genérico:

• Si e es pequeño y m es pequeño, entonces m^e podría ser más pequeño que n , en cuyo punto la exponenciación modular ya no es modular y se puede revertir de manera eficiente.

• La operación es determinista, lo que permite una búsqueda exhaustiva en el mensaje : el atacante cifra los mensajes posibles hasta que se encuentra una coincidencia con el mensaje cifrado real.

• La exponenciación modular es maleable: dado el "cifrado" de m₁ y m ₂ , una simple multiplicación produce el cifrado de m₁m₂ . Esto es similar a cifrado homomorfo , que puede ser una buena propiedad, o no, según el contexto.

Por este motivo, el entero m que está sujeto a RSA no debe ser el dato para cifrar solo, sino que debe ser el resultado de una transformación que garantice que m es "no pequeño", contiene algunos bytes aleatorios y disuade a la maleabilidad.

El relleno "v1.5" en PKCS # 1 hace el trabajo razonablemente bien, sujeto a dos advertencias (conocidas):

• Un motor de descifrado se puede convertir en un oráculo de relleno si el atacante puede enviar mensajes maliciosos para descifrar, y observe si el motor de descifrado encontró una estructura de relleno correcta o no. Este es el ataque de Bleichenbacher, que podría funcionar contra el servidor SSL, requiriendo alrededor de un millón de apretones de manos abortados para recuperar la clave simétrica de SSL. Desde entonces, los servidores SSL han sido parcheados (si el descifrado no encuentra un relleno, el motor continúa con un blob aleatorio en lugar del "secreto maestro previo"), pero esto resalta un problema potencial con PKCS # 1 v1.5.

• Este esquema de relleno nunca fue "probado". Las pruebas de seguridad son una buena cosa para tener. En mi opinión, este relleno tiene algo mejor, que es que se ha implementado en el campo y se ha utilizado ampliamente durante casi 20 años; pero muchas personas lo prefieren cuando hay algunas matemáticas que corroboran la experiencia.

OAEP tiene como objetivo mejorar las cosas en estos dos puntos. Resultó que para los oráculos de relleno, las cosas no están tan claras ; y la primera prueba se mostró algo equivocada por Shoup. La prueba fue "reparada" por Fujisaki, Okamoto, Pointcheval y Stern en el caso de RSA (OAEP se diseñó como un esquema de relleno genérico, pero ahora tenemos una prueba de seguridad solo cuando se utiliza con RSA).

Para resumir , OAEP intenta mejorar sobre el relleno anterior para la resistencia contra ataques de texto cifrado elegidos (no ataque de texto simple elegido : desde la clave pública es pública, cualquiera puede cifrar cualquier cosa a voluntad), pero el relleno v1.5 ya era heurísticamente bueno en eso, hasta un millón o más de descifrado, lo cual es suficiente para muchos propósitos, y puede ser parcheado para otros (como se hizo para SSL). OAEP funciona mejor si se implementó correctamente , lo cual no es tan fácil como se suele creer.

Quería profundizar, así que terminé leyendo Ataques de texto cifrado elegidos contra protocolos Basado en el RSA Encryption Standard PKCS # 1 por Daniel Bleichenbacher.

La principal debilidad se debe a que el relleno PKCS # 1 permitió realizar algunas suposiciones. Esas suposiciones entonces pueden ser explotadas para diseñar un ataque. Revisa el papel, es un ataque inteligente! El ataque se construye en 4 etapas, cada etapa extrae progresivamente más información que la anterior. Es altamente iterativo pero dentro del alcance de la practicidad (1 día para la clave de sesión SSL típica).

• Etapa 1: intenta ciegamente un texto cifrado que simplemente pasa la verificación de relleno en el lado remoto después del descifrado
• Etapa 2-4: Aproveche los resultados de lo anterior y reduzca progresivamente el espacio de búsqueda.

El bloqueo / estrechamiento para la etapa 2-4 es posible debido a dos razones:

1. La exponencia se puede manipular muy cómodamente, especialmente con inversos de enteros en un campo finito. Esta es una propiedad de la propia RSA / exponenciación modular, no del relleno per se. Por ejemplo, una cita en el documento:

     

   Un atacante que desea encontrar el descifrado m = c ^ d (mod n) de un   el texto cifrado c puede elegir un entero aleatorio s y solicitar el descifrado   del mensaje de aspecto inocente c '= (s ^ e) * c mod n. De la respuesta   m '= (c') ^ d, es fácil recuperar el mensaje original, porque m =   m's ^ −1 (mod n).

2. Uno puede asignar relaciones matemáticas directas entre el texto cifrado elegido y el resultado de descifrado en el lado remoto. Esto es homomorphism donde una operación en la entrada produce la misma operación en la salida. No sabe el resultado exacto, pero puede deducir que "No sé cuál es el valor, pero ahora es 2 veces su valor anterior". El valor real en sí se encuentra dibujando un rango y luego reduciéndolo iterativamente.

OAEP cambia las cosas un poco porque agrega algo de hashing (hashing feistel desequilibrado) entre el descifrado RSA (exponenciación modular) y la verificación de relleno. Básicamente, esto interrumpe el punto # 2 anterior y el ataque no puede pasar a la etapa 2-4 porque no se puede pasar por alto el conocimiento de la etapa 1;="http://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding"> decodificación OAEP . La única forma posible sería si puede invertir de manera determinista la función hash para continuar con las etapas de recopilación de información. Pero entonces eso significa que el hash está roto.

Entonces, RSA es maleable, lo que significa que un atacante puede modificar los mensajes de forma controlada, es decir, multiplicarlos por constantes conocidas. Como resultado, necesitamos algún tipo de relleno para prevenir esto: no queremos que nos pregunte el atacante "¿Qué es este mensaje?" y darle la información que necesita para descifrar otro mensaje. (Hay otros ataques: una encuesta es enlace )

Se requiere relleno Ergo. El primer esquema de relleno coloca primero un byte constante, luego bytes aleatorios distintos de cero, luego un byte cero, y el resto del número es el mensaje. Esto parecía que estaba bien.

Lamentablemente, esto implica que un atacante puede aprender si el primer byte de rM, M cualquier mensaje, r cualquier número es una constante dada. Esto resulta suficiente para factorizar la clave, como se muestra a finales de los 90. www.bell-labs.com/user/bleichen/papers/pkcs.ps es el documento.

SSL v3.0 era inseguro, al igual que otros protocolos implementados, lo que hace que este sea un problema bastante serio.