Cómo probarlo

El requisito previo es tener instalados gcc y una versión vulnerable de OpenSSL.

Para el error en BN_mod_sqrt(): compila con gcc -o my_bad_sqrt my_bad_sqrt.c -lcrypto, ejecuta ./my_bad_sqrt y observa cómo se cuelga para siempre. :D

Con un certificado: ejecuta openssl x509 -in certs/cert.der.new -inform DER -text -noout en la línea de comandos; esto también se cuelga.

Entrando en el bucle

La función BN_mod_sqrt() implementa el algoritmo de Tonelli-Shanks para encontrar una raíz cuadrada modular, es decir, dado un entero a y un número primo p, devuelve un valor r tal que r^2 == a (mod p).

Al analizar el commit que parchea la vulnerabilidad, vemos que el culpable es el bucle que encuentra el índice más pequeño i para el cual b^(2^i)==1 (mod p), donde b se define antes en el algoritmo.

El bucle se cambia de

a

En el segundo caso, hay un bucle for limitado por la variable e; en el código original, sin embargo, solo hay una comprobación del caso i==e dentro de un bucle while.

Dado que estos bucles están dentro de un bucle mayor que en cada iteración establece el nuevo valor de e al valor actual de i, probamos la siguiente estrategia de ataque:

1. en la primera ejecución del bucle externo, hacer que i=1 al final; para ello, necesitamos que b^2=1 (mod p).
2. de esta manera, durante la segunda ejecución tendremos e=1, y si podemos entrar en el bucle interno, la comprobación i==e siempre fallará
3. si conseguimos tener siempre t != 1 (mod p), entonces permaneceremos en el bucle para siempre

Observa que los dos primeros pasos pueden ocurrir en una ejecución "normal", es decir, con un primo p. Sin embargo, si p es compuesto, ¡también podemos satisfacer el tercer paso!

Un poco de matemáticas

El algoritmo de Tonelli-Shanks funciona escribiendo p - 1 = 2^e * q, con q impar. Este es también el orden del grupo multiplicativo de los enteros módulo p, y los valores e y q se usarán muchas veces durante la ejecución; sin embargo, si p no es primo, el orden del grupo multiplicativo no será p-1, y esto nos ayudará a entrar en el bucle infinito.

En particular, b se inicializa como b = a^q (mod p), lo que significa que si p fuera primo, entonces b tendría orden una potencia de 2, que luego encontraremos usando el bucle.

Pero si establecemos p = r * s, el orden del grupo multiplicativo es (r-1)*(s-1) = r*s - r - s + 1 en lugar de r*s-1. El algoritmo usa el valor de q para obtener un elemento y de orden exactamente 2^e; sin embargo, cuando p no es primo, el valor de q no tendrá un significado especial para el orden, por lo que el elemento y no tendrá orden una potencia de dos módulo p=r*s.

Dado que al final del primer bucle externo b se establece como b = b*y^(e-i) (mod p), en su segunda iteración el bucle interno intentará encontrar un valor i para el cual b^(2^i) == 1 (mod p), pero fallará dado que y ya no está garantizado que tenga orden una potencia de dos.

El exploit

Los números en el exploit son muy simples: tomamos r=17,s=41, lo que da p=r*s=697. Esto significa que los valores calculados de e y q serán p-1 = 2^3 * 87.

Luego elegimos a=696, lo que significa que a == -1 (mod p) y también b == -1 (mod p) cuando se inicializa. Esto satisfará el paso 1 estableciendo e=1 para el siguiente bucle externo.

Entonces b se establecerá como un elemento con orden que no es una potencia de 2, y el bucle interno se quedará atascado tratando de encontrar un i para el cual b^(2^i)==1 (mod p).

Creando un certificado peligroso

Bien, ahora vamos a construir un certificado peligroso que contenga parámetros de curva explícitos no válidos con un punto base codificado en formato comprimido.

Los archivos de esta sección están en la carpeta certs.

Creando un certificado normal con parámetros de curva explícitos

Primero, necesitamos crear una clave privada EC. Como queremos un certificado objetivo con parámetros de curva explícitos, la clave también debe contener parámetros de curva explícitos.

Luego, por conveniencia, firmamos automáticamente un certificado y lo generamos en formato DER.

Veamos la información del certificado. Contiene parámetros de curva explícitos como se esperaba.

Construyendo un certificado no válido

Ahora necesitamos modificar los valores de estos parámetros: Prime, A, B, Generator. Satisfacen la ecuación siguiente

donde p es el Prime, a es el parámetro A, y b es el parámetro B. p, a, b juntos determinan una curva. Descomprimir un punto significa calcular la coordenada Y a partir de la coordenada X correspondiente.

Obviamente, se debe utilizar la operación de raíz cuadrada modular, que llamará a BN_mod_sqrt().

Basándonos en el trabajo de drago-96, tomamos p=697, x^3+ax+b=696. Y entonces solo necesitamos elegir a, b, x apropiados que satisfagan la segunda ecuación. Aquí tomamos x=8, a=23, b=0.

Bien, ahora podemos empezar a abordar el certificado. Editar la estructura ASN.1 manualmente es realmente terrible. Usé la herramienta xxd para transformar el certificado a formato hexadecimal, y luego lo edité con vim. Después de completar la edición, lo transformé de vuelta con xxd -r.

No encontré una herramienta más cómoda. Si alguien conoce una, por favor, que la comparta en los comentarios.

Los pasos para construirlo son aproximadamente los siguientes:

1. Cambiar los valores de Prime, A, B, Generator
   1. Cambiar Prime a 697, es decir, 0x2b9 en hexadecimal
   2. Cambiar A a 23, es decir, 0x17 en hexadecimal
   3. Cambiar B a 0
   4. Cambiar la coordenada X del Generator a 8, es decir, 0x020008 (o 0x030008) cuando se codifica en formato comprimido
2. Como OpenSSL comprobará el formato de relleno de ASN1_INTEGER, el Prime no debe contener bytes 0 a la izquierda, por lo que tenemos que cambiar la longitud del Prime
3. Del mismo modo, OpenSSL comparará la longitud del Prime con la longitud de la cadena del punto, por lo que la longitud de la coordenada X del Generator debe ser la misma que la del Prime. Por eso establecemos el Generator como 030008, y no como 0308.
4. Debido a que la estructura ASN.1 del certificado está anidada, todas las longitudes de los objetos externos también deben corregirse.
5. Ten en cuenta que puede haber un salto de línea final no deseado (0x0a) al final del archivo después de ejecutar xxd -r. Elimínalo.

Ahora, echemos un vistazo a la estructura ASN.1 del certificado normal. Las partes marcadas con la línea roja son las que deben cambiarse.

Las longitudes antes y después de la modificación son las siguientes:

Uso de plantillas ASN1

Actualizado el 2020-03-21:

Una forma mucho más fácil es usar la herramienta asn1template escrita por wllm-rbnt.

Clona el repositorio:

Genera una plantilla DER a partir de este certificado:

Luego cambia los parámetros que acabamos de mencionar arriba:

Conviértelo de nuevo a ASN1 codificado en DER con ASN1_generate_nconf(3):

El resultado cert_new.der es equivalente a la versión editada manualmente.

Así que ahora hemos construido con éxito un certificado no válido. Veamos la nueva estructura ASN.1

Todas las partes rojas han sido modificadas, y el certificado puede decodificarse correctamente en DER.

Prueba con el certificado no válido

Ahora intentemos analizar el certificado. El proceso entrará en el bucle infinito si todo es como se espera.

Como se muestra, el %CPU del proceso openssl es 100, y la pila de llamadas está dentro de BN_mod_sqrt().

Si un atacante malicioso envía un certificado manipulado de este tipo durante el handshake SSL con el servidor, el servidor entrará en el bucle infinito, lo que provoca un ataque DoS.

Creando un certificado, método alternativo

Intentaremos construir un certificado usando la biblioteca C libcrypto de OpenSSL.

Como hemos visto, necesitamos usar una curva con campo base no primo y codificar los puntos en formato comprimido, de modo que al analizarla encontremos el error en BN_mod_sqrt().

Esto se puede hacer estableciendo y^2 = x^3 + 1*x + 694 (mod 697) como la curva, con (1, 132) como generador; esto llamará a BN_mod_sqrt() con exactamente los mismos parámetros que my_bad_sqrt.

Ejecutar gcc -o my_bad_group my_bad_group.c -lcrypto && ./my_bad_group generará el archivo my_bad_group.der que contiene los ECparams en formato DER.

Intentar analizar esos parámetros con OpenSSL dará como resultado el bucle infinito: openssl ecparam -in my_bad_group.der -inform der.

... WIP ...