elikaski/ecc_attacksAtaques conocidos contra la criptografía de curva elíptica
En los últimos años, el enfoque de la criptografía de curvas elípticas se ha vuelto popular debido a su alta eficiencia y fuerte seguridad. El propósito de este artículo es presentar este tema de una manera relativamente más clara de lo que existe hoy en internet.
En este artículo presentaré qué son las curvas elípticas, las operaciones básicas que se pueden realizar sobre ellas y cómo se pueden utilizar en el contexto criptográfico. La mayor parte de este artículo consiste en ejemplos de ataques conocidos a implementaciones incorrectas o usos indebidos de las mismas. A lo largo del artículo intento separar la explicación en una parte intuitiva y de alto nivel, y una parte matemática que entra en más detalle. Se invita al lector a centrarse en la parte que le interese en cada lugar y a omitir las partes que le interesen menos.
¡Feliz lectura!
En general, una curva elíptica es un tipo de línea curva. Un ejemplo de ello es la parábola, cuya ecuación es de la forma $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ y se ve así:
En el contexto de la criptografía, es habitual usar curvas elípticas cuya ecuación es de la forma
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
Por ejemplo, una curva elíptica correspondiente a la ecuación $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ se ve así:
La ecuación de la curva define la relación entre la coordenada 𝑥 de un punto de la curva y su coordenada 𝑦. En un contexto criptográfico, restringimos 𝑥, 𝑦, 𝑎, 𝑏 a números enteros y restringimos los cálculos al módulo de algún número primo grande. Así, la ecuación de la curva elíptica es:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Esto significa que tenemos un número finito de puntos en la curva. En lenguaje matemático, se dice que la curva está definida sobre un cuerpo finito de orden 𝑝. Como resultado, ahora no necesariamente toda coordenada 𝑥 tendrá un punto correspondiente en la curva, porque puede que la coordenada 𝑦 correspondiente no sea un número entero.
El conjunto de puntos de la curva consiste en pares de enteros (𝑥, 𝑦) que satisfacen la ecuación de la curva. Además de estos puntos, se define otro punto especial llamado "Infinito", denotado por 𝒪. En lenguaje matemático, este punto es el elemento neutro del conjunto de puntos de la curva respecto a la operación de suma, que definiremos en la siguiente sección. El número de puntos de la curva (incluido el punto 𝒪) se denomina "orden de la curva".
Otra observación es que las curvas elípticas son simétricas respecto al eje X. Esto significa que si el punto 𝑃 = (𝑥, 𝑦) está en la curva, entonces el punto −𝑃 = (𝑥, −𝑦) también está en la curva. De hecho, se considera que estos puntos son "inversos" entre sí (de ahí la notación −𝑃 para el segundo punto), y el resultado de la operación de suma entre ellos se define como el elemento neutro 𝒪.
Un teorema llamado teorema de Hasse proporciona una estimación de #𝐸, el orden de la curva, y es del orden de magnitud de Θ(𝑝). Más precisamente:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Dados dos puntos de la curva, es posible definir una operación de suma entre ellos, cuyo resultado es un tercer punto que también está en la curva. Para encontrar este punto geométricamente, trazamos una línea entre los dos puntos dados y la continuamos hasta que interseque la curva en un tercer punto. Este punto se refleja con respecto al eje 𝑋, y el punto resultante se define como el resultado de la suma.
Aquí hay un diagrama que muestra cómo, dados los puntos 𝑃 y 𝑄, se puede encontrar el punto 𝑃 + 𝑄:
Una pregunta que puede surgir de esta descripción es: ¿qué ocurre si la línea trazada entre los dos puntos no vuelve a intersecar la curva? En este caso se dice que la línea interseca la curva en el "infinito", y el resultado de la suma es el punto 𝒪. Nótese que este caso ocurre si la línea trazada es vertical, es decir, estamos intentando sumar un punto 𝑃 con su punto inverso, −𝑃:
De esto se derivan dos identidades básicas. Para todo punto 𝑃 se cumple que:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Otra pregunta que surge de la descripción geométrica es: ¿cómo sumamos un punto consigo mismo? Vimos que para sumar dos puntos distintos 𝑃 y 𝑄, trazamos una línea entre ellos y observamos el punto de intersección de su prolongación con la curva. Intuitivamente, dejaremos 𝑃 constante y observaremos la línea que se crea a medida que movemos 𝑄 "cada vez más cerca" de 𝑃, hasta que 𝑄 se fusione con 𝑃. Lo que obtendremos es una línea cada vez más "tangente" a la curva en el punto 𝑃, y esa es exactamente la línea que consideraremos cuando queramos sumar 𝑃 consigo mismo:
Para sumar un punto 𝑃 consigo mismo, trazamos una tangente a la curva en el punto 𝑃 y la continuamos hasta que interseque la curva en un segundo punto. Este punto se refleja con respecto al eje 𝑋, y el punto resultante se define como el resultado de la suma. Es habitual denotar el resultado de la suma como 𝑃 + 𝑃 = 2𝑃. Nuevamente, si la tangente no interseca la curva en un segundo punto, se dice que interseca la curva en el "infinito", y el resultado de la suma en este caso es el punto 𝒪.
Estas descripciones geométricas visuales ilustran muy bien y nos ayudan a entender cómo funciona la suma de puntos. Pero, ¿cómo la calculamos realmente? ¡Ecuaciones matemáticas, por supuesto!
Dados los puntos $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ y $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$, el resultado de su suma es el punto $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ tal que:
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
Donde 𝜆 se define como la pendiente de la recta que conecta los puntos, si son distintos, y la pendiente de la tangente a la curva en el punto, si el punto se suma a sí mismo. Formalmente:
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
Los cálculos matemáticos detrás de la suma de puntos no son críticos para el resto del artículo. En ese sentido, podemos ver la suma de puntos como una caja negra que recibe dos puntos de la curva y devuelve un tercer punto que también está en la curva.
Vimos que es posible sumar un punto 𝑃 consigo mismo, y denotamos el punto resultante como 2𝑃. Si volvemos a sumar el punto 𝑃 a este resultado, alcanzaremos un punto denotado como 3𝑃, y así sucesivamente. De esta manera es posible definir la "multiplicación" de un punto por una constante, sumando repetidamente el punto a sí mismo (de manera similar a la multiplicación entre números):
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
Aparentemente, para multiplicar un punto por un número 𝑛 necesitamos realizar 𝑛 operaciones de suma entre puntos. Esto se debe a que, dado un punto inicial, es difícil saber de antemano dónde caerá el "último" punto, sin llegar a él "paso a paso". Semejante cálculo sería muy ineficiente, porque 𝑛 podría ser muy grande.
Para este propósito existe el algoritmo Double And Add, en el que partimos del punto 𝑃; luego, por cada bit en la representación binaria de 𝑛, el punto actual se multiplica por 2 (es decir, se suma a sí mismo) y se añade al resultado si el valor del bit es 1. La complejidad temporal de este algoritmo es 𝑂(log 𝑛), y permite multiplicar puntos por números muy grandes de manera eficiente.
Una propiedad importante de la multiplicación de puntos que usaremos más adelante es que para todo punto 𝑃 y todo par de números 𝑎, 𝑏 se cumple:
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
Intuitivamente, supongamos que partimos del punto 𝑃, damos 𝑎 pasos desde él y alcanzamos el punto 𝑎𝑃. Desde este punto, damos 𝑏 pasos de "tamaño" 𝑎 y alcanzamos el punto 𝑏(𝑎𝑃). Alternativamente, en otro escenario, podríamos partir del punto 𝑃, dar 𝑏 pasos con él y alcanzar el punto 𝑏𝑃. Desde este punto, dar 𝑎 pasos de "tamaño" 𝑏 y alcanzar el punto 𝑎(𝑏𝑃).
En ambos escenarios dimos en total la misma cantidad de 𝑎𝑏 pasos desde el punto 𝑃, así que en ambos escenarios alcanzamos el mismo punto final. Matemáticamente, multiplicar un punto por una constante es asociativo.
Si partimos de un punto 𝑃 y lo sumamos a sí mismo una y otra vez, en cada paso alcanzaremos algún punto nuevo de la curva. Debido a que hay un número finito de puntos en la curva, en algún momento volveremos a alcanzar puntos que ya habíamos alcanzado antes, y estaremos en una especie de bucle, o "círculo". Más precisamente, en algún momento alcanzaremos el punto -𝑃, en el siguiente paso alcanzaremos el punto 𝒪, y en el paso posterior volveremos a alcanzar el punto 𝑃 del que partimos.
El punto que crea ese "círculo" se llama generador, porque todo el "círculo" puede generarse a partir de él, y es habitual denotarlo con la letra 𝐺. El número de puntos del "círculo" (incluido el punto 𝒪) se denomina "orden del generador 𝐺" y suele denotarse por 𝑛. Cada punto de la curva forma un "círculo" de algún tipo. Matemáticamente, el conjunto de puntos de este "círculo" es un grupo cíclico.
Una propiedad interesante que se deriva de esto es que multiplicar un punto 𝐺 por su orden 𝑛 nos da el punto del infinito:
𝑛𝐺 = 𝒪
“Dados los puntos 𝑃 y 𝑄 tales que 𝑄 = 𝑥𝑃 para algún 𝑥, es difícil encontrar 𝑥.”
Y en palabras, supongamos que alguien partió de un punto inicial, dio un cierto número de pasos desde él y llegó a un punto final. Dados el punto inicial y el punto final, ¿cómo sabemos cuántos pasos dio?
La respuesta a esta pregunta no es tan intuitiva, porque es difícil predecir de antemano, a partir de un punto inicial, qué puntos se alcanzarán dando pasos desde él. Una solución ingenua podría ser partir nosotros mismos de 𝑃, avanzar desde allí un paso a la vez y contar los pasos que damos, hasta llegar a 𝑄. La complejidad de esta solución es 𝑂(𝑥), y no es factible si se sabe que 𝑥 es un número grande, por ejemplo si 𝑥 es de 256 bit.
Este problema se denomina Problema del Logaritmo Discreto en Curvas Elípticas (ECDLP), y es un problema difícil. Pero, ¿qué tan difícil es?
En un contexto criptográfico, es habitual medir la "dificultad de los problemas", o la "fortaleza de un sistema criptográfico", con una métrica llamada Security Level. En esta métrica, se dice que un problema tiene "seguridad de 𝑛 bits" si el mejor ataque conocido resuelve el problema en $𝑂(2^𝑛)$ pasos.
Actualmente, el mejor algoritmo que resuelve el problema ECDLP lo hace con una complejidad de $𝑂(\sqrt n)$, donde 𝑛 es el orden del punto 𝑃, y lo hace mediante un ataque Meet In The Middle. Cuando se selecciona un punto con un orden suficientemente grande, resolverlo no es factible; de ahí la fortaleza del problema.
Por ejemplo, si elegimos un 𝑛 de tamaño 256 bit, obtenemos que el problema ECDLP tiene un nivel de seguridad de 128 bit. En comparación, para alcanzar el mismo nivel de seguridad de 128 bit en el cifrado RSA, que se basa en el problema de la factorización de enteros, se requiere una clave pública de 3072 bit. Esto hace que el uso de curvas elípticas sea relativamente más eficiente computacionalmente.
Después de toda esta introducción al mundo de las curvas elípticas, pasaremos a ver qué se puede hacer con ellas en un contexto criptográfico. Como sabemos, los sistemas criptográficos suelen basarse en un "problema difícil" que es difícil de resolver. Por ejemplo, RSA con el problema de factorizar un número que mencionamos, o el protocolo Diffie-Hellman con el problema del logaritmo discreto. Un sistema criptográfico basado en el problema ECDLP en una curva elíptica pertenece a la familia de la criptografía de curvas elípticas, o ECC para abreviar.
Comencemos con una historia. Imagina que estás en una fiesta: una sala llena de gente, donde todos pueden hablar con todos y todos escuchan a todos. En esta sala también están Alice y Bob, que nunca se han conocido antes. Alice siente atracción por Bob y quiere invitarlo a salir. Alice es un poco tímida, por lo que quiere contarle a Bob este mensaje secreto sin que los demás invitados la oigan. Alice y Bob no han coordinado nada de antemano, y todo lo que Alice le diga a Bob será oído por todos los demás invitados de la fiesta. ¿Cómo puede Alice contarle el mensaje a Bob sin que nadie más lo oiga?
Si respondiste "curvas elípticas", ¡estás en lo cierto!
Alice seleccionará alguna curva elíptica y un generador en ella, y se los comunicará a Bob. Concretamente, Alice le pasará a Bob (y a todos los demás en la sala) los dos parámetros de la curva 𝑎, 𝑏, el módulo 𝑝 y el generador 𝐺. Además, Alice seleccionará algún valor $𝑑_𝐴$ en el rango $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$, donde 𝑛 es el orden de 𝐺. Ese valor $𝑑_𝐴$ se denomina clave privada de Alice. Alice calculará el punto $𝐴 = 𝑑_𝐴𝐺$, que se denomina clave pública de Alice, y se lo comunicará a Bob. De manera similar, Bob seleccionará una clave privada $𝑑_𝐵$, calculará el punto $𝐵 = 𝑑_𝐵𝐺$, que se denomina clave pública de Bob, y se la comunicará a Alice.
Alice tomará la clave pública de Bob, multiplicará ese punto por su clave privada y llegará a un tercer punto $𝑃_𝐴 = 𝑑_𝐴𝐵$. De manera similar, Bob tomará la clave pública de Alice, la multiplicará por su clave privada y llegará a un tercer punto propio $𝑃_𝐵 = 𝑑_𝐵𝐴$. Si examinamos los puntos a los que llegaron Alice y Bob por separado, descubrimos que llegaron al mismo punto. Este hecho proviene de la propiedad de asociatividad de multiplicar un punto por una constante que vimos antes:
$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$
Al final de todo el proceso, Alice y Bob lograron ponerse de acuerdo en algún punto de la curva, y en ninguna etapa ninguno de los dos transmitió ese punto a la otra persona. La información que todos han oído es: 𝑎, 𝑏, 𝑝, 𝐺, 𝐴, 𝐵. Una persona que esté en la sala escuchando esta información no puede encontrar, a partir de ella, el punto en el que Alice y Bob se pusieron de acuerdo.
Esto se debe a que si otra persona en la sala quisiera encontrar ese punto, necesitaría conocer la clave privada de Alice o la de Bob para multiplicar 𝐵 o 𝐴 por ellas. Para encontrar la clave privada de Alice, por ejemplo, observará $𝐴 = 𝑑_𝐴𝐺$, porque esta es la única información que se envió y que "contiene" la clave privada de Alice. Dados 𝐺 y $𝑑_𝐴𝐺$, encontrar $𝑑_𝐴$ equivale a resolver el problema del logaritmo discreto en curvas elípticas, que, como se mencionó, es un problema difícil.
Este hermoso protocolo se llama: Diffie-Hellman de Curva Elíptica (ECDH).
No hemos terminado nuestra historia. Aunque Alice y Bob se pusieron de acuerdo en un punto secreto compartido, Alice todavía no le había pedido a Bob la cita que tanto deseaba.
Una vez que las partes se han puesto de acuerdo en un punto secreto compartido, pueden usarlo como clave de cifrado de cualquier método de cifrado, por ejemplo AES, y a partir de ese momento comunicarse de forma segura mediante cifrado.
Es habitual tomar una de las coordenadas 𝑥 o 𝑦 del punto y usarla. Para mantener la seguridad, se recomienda aplicar un hash al valor seleccionado y usar solo el resultado del hash como clave de cifrado. En la práctica, a veces el valor es demasiado grande para usarse como clave de cifrado. Por ejemplo, si la función hash utilizada es SHA-1, su longitud de salida es de 160 bit, mientras que el cifrado AES solo requiere 128 bit. En tal caso, es habitual usar solo 128 bits de los 160 y descartar el resto.
En cualquier caso, en este punto Alice y Bob se ponen de acuerdo en una clave de cifrado, y son los únicos que la conocen. A partir de este momento se comunican mediante cifrado, y cualquiera que escuche en la sala no puede entender lo que dicen.
Aquí hay un diagrama del protocolo:
Usando la clave acordada, Alice cifra el mensaje "Hey Bob, ¿te gustaría salir a tomar un café mañana por la tarde?" y le pasa el mensaje cifrado a Bob. Bob descifra el mensaje con la clave que él también conoce. Alice espera que Bob diga que sí, pero eso no forma parte del protocolo.
En el conocido protocolo Diffie-Hellman (DH), las partes transmiten abiertamente un número primo 𝑝 y un generador 𝑔 que está en el grupo correspondiente al valor 𝑝. Alice genera aleatoriamente una clave privada 𝑎 y difunde abiertamente su clave pública $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$. De manera similar, Bob genera aleatoriamente una clave privada 𝑏 y difunde abiertamente su clave pública $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$. Alice toma entonces la clave pública de Bob y la eleva a la potencia de su clave privada, calculando así el valor $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. Del mismo modo, Bob calcula el valor $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. Al final del proceso, Alice y Bob pudieron ponerse de acuerdo en un valor común 𝐾, sin transmitirlo entre ellos.
Un atacante que los escuche no puede encontrar 𝐾 dados los valores difundidos 𝑝, 𝑔, 𝐴, 𝐵. Para ello, tendrá que encontrar la clave privada de Alice o la de Bob. Para calcular la clave privada de Alice, por ejemplo, tendría que encontrar 𝑎 dados 𝑔 y $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$, lo cual es un problema difícil. Este problema se denomina Problema del Logaritmo Discreto (DLP).
Hay una similitud muy clara entre DH, que se basa en DLP, y ECDH, que se basa en ECDLP (básicamente son lo mismo, solo que con el prefijo EC). En ambos protocolos, dos partes que se comunican entre sí pueden ponerse de acuerdo en algún valor secreto compartido, sin que coordinen nada de antemano. Cualquiera que escuche los mensajes entre las partes estará expuesto a la información pública que intercambian, pero no podrá alcanzar el valor secreto compartido entre ellas.### Segundo uso de las curvas elípticas: firmar un mensaje Continuando con nuestra historia, digamos que Alice y Bob salieron a una cita y pasaron una agradable velada juntos. Al día siguiente, Alice recibe un mensaje que dice: "Hola Alice, soy Bob, lo pasé genial contigo ayer y me encantaría volver a verte este fin de semana". Alice sospecha que no es Bob quien envió el mensaje, porque sabe que Bob se divirtió tanto con ella ayer que no esperará hasta el fin de semana para verla, ¡sino que querrá verla mañana! ¿Cómo puede Alice verificar que fue Bob quien escribió el mensaje?
Si respondiste "curvas elípticas", ¡vuelves a tener razón!
La dificultad del problema ECDLP también se puede utilizar para firmar mensajes. Durante su cita, Alice y Bob acordaron una curva elíptica y un generador 𝐺 en ella. Bob generó un valor $𝑑_𝐵$, llamado clave privada de Bob, y calculó el punto $𝑃_𝐵 = 𝑑_𝐵𝐺$, llamado clave pública de Bob. Bob le dio a Alice su clave pública para que ella pudiera usarla más tarde para verificar si un mensaje que recibe fue realmente firmado por él.
Digamos que Bob quiere firmar un determinado mensaje 𝑚. Calculará el valor $z = hash(m)$ usando alguna función hash segura, y conservará una cantidad de bits del resultado igual a la longitud de bits de n, el orden del generador 𝐺. Bob generará algún valor aleatorio 𝑘 en el rango $1 ≤ 𝑘 ≤ 𝑛 − 1$. Luego Bob calculará el punto $𝑘𝐺 = (𝑥_1, 𝑦_1)$, tomará su coordenada 𝑥, y calculará $𝑟 = 𝑥1\ \ \ \ (mod\ n)$. Finalmente, Bob calculará el valor $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$.
La firma del mensaje 𝑚 se define como el par de valores calculados 𝑟 y 𝑠.
Supongamos que Alice recibió un determinado mensaje 𝑚, y su firma consiste en un par de valores 𝑟 y 𝑠. Alice quiere asegurarse de que es efectivamente Bob quien firmó el mensaje. Alice calculará el valor $z = hash(m)$ de la misma manera que Bob. Luego, Alice calculará los valores $𝑢_1 = 𝑧𝑠^{−1}$ y $𝑢_2 = 𝑟𝑠^{−1}$. Finalmente, Alice usará la clave pública de Bob $𝑃_𝐵$ y calculará el punto $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$. La firma se considerará válida si se cumple que $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$. La razón por la que esto es correcto es que se cumple:
$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$
Si la firma es válida, la coordenada 𝑥 de este punto debería ser efectivamente 𝑟, tal como se define en la firma del mensaje. Cabe señalar que el orden del generador 𝐺, que se denota con la letra 𝑛, debe ser un número primo, y esto es para que sea posible calcular los números inversos en los algoritmos de firma y verificación.
Se puede ver que solo la persona que posee la clave privada $𝑑_𝐵$ puede crear una firma válida para la clave pública $𝑃_𝐵$. Un atacante que no tenga el valor $𝑑_𝐵$ no puede calcular el valor 𝑠 correspondiente a $𝑃_𝐵$ en la firma. Si el atacante quiere crear una firma que coincida con un determinado mensaje, tendrá que resolver el problema ECDLP, es decir, encontrar la clave privada $𝑑_𝐵$ dados $𝐺$ y $𝑃_𝐵 = 𝑑_𝐵𝐺$, lo cual es un problema difícil.
Este protocolo de firma se llama Algoritmo de Firma Digital de Curva Elíptica, o ECDSA para abreviar. El protocolo garantiza que los mensajes firmados no han sido alterados ni falsificados, y además garantiza que la persona que firmó el mensaje no puede negar haberlo creado.
A diferencia del protocolo ECDH, donde las partes no tenían que coordinar nada de antemano, en el protocolo ECDSA las partes deben acordar de antemano una clave pública. Solo después de que cada parte sepa con certeza que la clave pública que posee pertenece realmente a la persona con la que quiere comunicarse, el protocolo puede utilizarse. De lo contrario, no tiene sentido verificar la firma con la clave pública que posee cada parte.
Volvamos a nuestra historia. Alice sabe con certeza que la clave pública $𝑃_𝐵$ en su poder pertenece a Bob, porque Bob se la dio explícitamente durante su cita. Alice intenta verificar el mensaje con ella y descubre que no hay coincidencia. ¡Por supuesto! Otra persona creó el mensaje y lo firmó, tal como Alice sospechaba.
Aquí hay un diagrama del protocolo:
En el protocolo ElGamal para firmar mensajes, las partes acuerdan un número primo grande 𝑝 y un número generador 𝑔. La parte firmante genera un valor 𝑑 en el rango $1 ≤ 𝑑 < 𝑝 − 1$, llamado clave privada, calcula el valor $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$, llamado clave pública, y lo publica.
Para firmar un determinado mensaje, calculan el valor $z = hash(m)$ y generan un valor aleatorio 𝑘 en el rango $1 ≤ 𝑘 < 𝑝 − 1$ que sea coprimo con $(p-1)$. Calculan $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ y $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$. La firma del mensaje m se define como el par de valores calculados 𝑟 y 𝑠.
La parte que ha recibido un determinado mensaje 𝑚, y cuya firma consiste en un par de valores 𝑟 y 𝑠, utiliza la clave pública 𝑦 para verificar la firma calculando los valores $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ y $𝑢_2 = 𝑔^𝑧$. La firma se considerará válida si $𝑢_1 = 𝑢_2$. Esto se debe a que, según la definición de 𝑠, se denota:
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$, por lo tanto $𝑘𝑠 = 𝑧 − 𝑑𝑟$, de ahí que $𝑧 = 𝑘𝑠 + 𝑑𝑟$. Por lo tanto:
$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$
Un atacante no puede crear una firma válida para la clave pública 𝑦 sin conocer la clave privada 𝑑. Para obtener la clave privada dada la clave pública, el atacante tendría que resolver el problema DLP, que es un problema difícil.
Aquí también hay una clara similitud entre ECDSA, que se basa en ECDLP, y ElGamal, que se basa en DLP. En ambos casos, las partes tienen que coordinar una clave pública de antemano, y se requiere generar un valor aleatorio 𝑘 cada vez que queramos firmar un nuevo mensaje. Además, en ambos casos, un atacante que escuche los mensajes entre las partes no puede deducir información útil que le permita falsificar firmas.
Vimos cómo se pueden usar las curvas elípticas en sistemas criptográficos para acordar un valor secreto y para firmar mensajes. Como todo en la vida, cuando se trata de poner algo en práctica, las cosas no siempre salen como estaba previsto. En el resto del artículo presentaré diferentes formas de atacar sistemas criptográficos basados en ECC que han sido mal utilizados por el usuario o implementados de manera insegura.
Naturalmente, divido esta parte en ataques a ECDH y ataques a ECDSA. En ambos casos diremos que "tuvimos éxito" en el ataque si encontramos la clave privada de una de las partes, y nos detendremos ahí. En el caso de ECDH, es suficiente porque a partir de la clave privada es posible llegar al valor secreto compartido y a toda la información cifrada con él posteriormente. En el caso de ECDSA, es suficiente porque la clave privada se puede usar para firmar mensajes como queramos.
SageMath es un software matemático libre y de código abierto. Se puede escribir con casi la misma sintaxis que Python, y también se puede usar como una biblioteca de Python. Esta biblioteca implementa funciones útiles relacionadas con las curvas elípticas y, por lo tanto, es muy útil para los cálculos que necesitamos hacer en el contexto de ECC. Como parte de este artículo, proporciono fragmentos de código escritos en esta biblioteca. Encontré que es más fácil instalarla en el sistema operativo Ubuntu, específicamente en la versión 22.04. Para instalarla, simplemente ejecuta el comando: sudo apt install sagemath.
Para ejecutar un archivo que contiene código, guarda el archivo con la extensión .sage y ejecuta el comando: sage file.sage.
Además, se puede usar un intérprete, de manera similar al intérprete de Python, ejecutando el comando: sage. También es posible crear archivos .py en los que se importe la biblioteca sage.all, y ejecutarlos con el comando python3 file.py. Ten en cuenta que al ejecutar un archivo con el comando sage, la notación ^ se interpreta como potencia, mientras que al ejecutarlo con python3, esta notación se interpreta como xor.
En este artículo utilizo principalmente las siguientes funciones en SageMath:
E.gens() - encontrar generadores en la curva EG.order() - calcular el orden del generador Gn*G - multiplicación del generador G por el número nn.factor() - factorizar el número n en sus factores - la función devuelve una lista de pares (𝑝, 𝑒) tal que 𝑝 es un factor primo, y 𝑒 es su exponente, es decir, el número de veces que 𝑝 aparece en la descomposición de ncrt - resolver un sistema de ecuaciones del teorema chino del restoQuizás el uso incorrecto de ECDH que es más fácil de atacar sea elegir un generador con un orden n demasiado pequeño.
Como se mencionó, es posible resolver el problema ECDLP con una complejidad de $O(\sqrt{n})$. Cuando 𝑛 es demasiado pequeño, por ejemplo de 32 bits, entonces se vuelve factible resolver este problema. Hay varios algoritmos que resuelven el problema, incluidos Baby-Step Giant-Step, Pollard's Rho y Pollard's Lambda. Estos algoritmos se pueden ejecutar como una caja negra con la ayuda de SageMath, usando la función discrete_log:```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
En este fragmento de código elegimos los parámetros de la curva de forma aleatoria bajo la limitación de que `𝑝` tiene una longitud de 32 bits. Esta limitación nos garantiza que el número de puntos en la curva es $O(2^{32})$ y, por lo tanto, el orden de cada punto en ella es como máximo $O(2^{32})$ también. Después de eso, creamos la curva, elegimos algún generador en ella, generamos una clave privada aleatoria y calculamos la clave pública. Finalmente, a partir del generador y de la clave pública, calculamos el logaritmo discreto para encontrar la clave privada y verificamos que la clave encontrada sea efectivamente correcta. Este código tarda, como mucho, unos pocos segundos en encontrar la clave privada.
## El orden del generador es un número suave
Como se mencionó, el orden de un generador se define como el número de puntos en el "círculo" que se forma cuando sumamos el punto generador consigo mismo una y otra vez, y se denota por `𝑛`. Si `𝑛` es un número compuesto que puede factorizarse en factores primos más pequeños, entonces es posible resolver ECDLP de manera eficiente. Tal número se llama Número Suave y, a los efectos de este artículo, es un número que puede factorizarse en suficientes factores primos, cada uno de los cuales es lo bastante pequeño para que nuestro ataque funcione. La definición formal de Número Suave es un poco diferente y no es relevante para nosotros.
De forma intuitiva, esto se hace "atacando" cada uno de los factores primos por separado. Dado un punto generador `𝐺` que forma un "círculo" muy grande, y algún punto `𝑃` en el "círculo" tal que `𝑃 = 𝑘𝐺`. El "círculo" grande puede desmantelarse en varios "círculos" pequeños, cada uno del tamaño de un factor primo de `𝑛`. En cada "círculo" pequeño podemos mapear `G` y `P` a otros puntos correspondientes `G'` y `P'` que se encuentran en el "círculo" pequeño y satisfacen `𝑃′ = 𝑘′𝐺′`. Debido a que el "círculo" es pequeño, es relativamente fácil resolver el problema y encontrar `𝑘′`. Finalmente, podemos combinar todos los pequeños `𝑘′` que encontramos en el `𝑘` deseado en el "círculo" original.
El algoritmo que realiza lo que he descrito se llama Algoritmo de Pohlig-Hellman. Su complejidad temporal es $O(\sqrt{p_{max}})$ donde $p_{max}$ es el factor primo más grande en la descomposición de `𝑛`. Esto también tiene sentido, porque la parte más "pesada" del algoritmo es resolver el problema ECDLP en el "círculo" más grande entre los "círculos" más pequeños. Por ejemplo, `n` podría ser un número de 128 bits y se descompone en factores primos de modo que el mayor de ellos sea un número de 30 bits. El algoritmo reduce la complejidad de resolver el problema de $2^{64}$ a $2^{15}$, convirtiéndolo así de inviable a viable.
Afortunadamente, la función `discrete_log` de SageMath realiza este algoritmo en su implementación. Para ejecutar el ataque, simplemente puedes llamar a la función:```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
En este fragmento de código definimos una curva elíptica y un generador en ella, e imprimimos los factores primos de su orden. La salida es:``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!
Se puede ver que, aunque el orden del generador es de 128 bits, se descompone en factores primos de modo que el mayor factor primo es de 32 bits.
Después, igual que en el ataque anterior - elegimos una clave privada aleatoria, calculamos una clave pública a partir de ella y, dados el generador y la clave pública, calculamos la clave privada y verificamos que es correcta.
Aunque ya hemos terminado, no hemos visto cómo se definen los «círculos» pequeños, cómo mapear los puntos `𝐺` y `𝑃` a sus correspondientes puntos `𝐺′` y `𝑃′`, y cómo combinar todas las soluciones pequeñas en una solución grande. Intentaré explicarlo aquí de forma intuitiva, porque el siguiente ataque también se basa en esta parte.
Supongamos que tenemos un «círculo» de orden `3𝑥5𝑥7 = 105`, y su generador es `𝐺`. Definiremos un punto `𝐺′ = (5𝑥7)𝐺 = 35𝐺`, y observaremos el «círculo» generado a partir de él. Si desde `𝐺′` avanzamos un «paso», es decir, sumamos `𝐺′` a sí mismo, será como avanzar 35 pasos desde el punto `35𝐺` en el «círculo» original, y llegaremos al punto `2𝐺′ = 70𝐺`. Si avanzamos un «paso» más, llegaremos al punto `3𝐺′ = 105𝐺 = 𝒪`, y si avanzamos otro «paso» desde allí, llegaremos al punto `4𝐺′ = 35𝐺 = 𝐺′`, es decir, de vuelta al punto inicial. El «círculo» formado por `G′` es de orden `3`, y no es casualidad, porque en un «círculo» de orden `105` es posible dar exactamente `3` «pasos» de tamaño `35`. De manera similar, podríamos crear un «círculo» de orden `5` definiendo el punto `𝐺′ = (3𝑥7)𝐺 = 21𝐺`, y un círculo de orden `5` definiendo `𝐺′ = (3𝑥5)𝐺 = 15𝐺`.
Cuando lo miramos al revés, resulta más interesante. Supongamos que en el «círculo» original tomamos `𝑛` pasos desde el punto `G` y llegamos al punto `𝑛𝐺`. Si también en el «círculo» pequeño tomamos `𝑛` pasos desde el punto `𝐺′`, llegaríamos al punto `𝑛′𝐺′` tal que `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`. ¿Y por qué es interesante? Porque el orden de `𝐺′` es mucho menor que el orden de `𝐺` y, por lo tanto, dados `𝐺′` y `𝑛′𝐺′`, podemos encontrar `𝑛′` con relativa facilidad. Si lo hacemos, y lo hacemos también para los otros dos factores primos del orden del «círculo», que son `5` y `7`, tendríamos los siguientes valores:
𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)
A partir de estos tres valores, `𝑛` se puede encontrar fácilmente mediante el Teorema Chino del Resto, y así resolver el problema original.
## El orden del generador es casi un número suave, y la clave privada es pequeña
Supongamos que, de manera similar al ataque anterior, obtenemos una curva en la que el orden del generador se descompone en factores primos, pero esta vez, el factor primo más grande es demasiado grande para que sea práctico resolver su ECDLP. Por ejemplo, si el orden del generador es `256 bit`, pero el factor primo más grande es `128 bit`.
El algoritmo de Pohlig-Hellman requerirá alrededor de $O(2^{64})$ operaciones para encontrar la clave privada, lo cual es inviable.
Si sabemos que la clave privada utilizada es relativamente pequeña, aún se puede encontrar de manera eficiente.
Supongamos que la clave privada es de `64 bit` (en lugar de `256 bit`). Cuando se crea la clave pública, el generador se multiplica por la clave privada y se obtiene algún punto en el «círculo» que crea el generador. Aunque el «círculo» tiene un tamaño de aproximadamente $2^{256}$ puntos, este punto «caerá» en algún lugar de los «primeros» $2^{64}$ puntos. No hay «interacción» entre la clave privada y los puntos del «círculo» que corresponden a valores más grandes.
Es posible ejecutar el algoritmo de Pohlig-Hellman, pero «descartar» los «círculos» demasiado grandes, siempre que el producto de los órdenes de los «círculos» restantes sea al menos la longitud de la clave privada. Si se encuentran suficientes factores primos pequeños, cuyo producto sea al menos `64 bit`, entonces los «círculos» correspondientes serán suficientes para realizar el mismo ataque que vimos anteriormente.
Si antes teníamos una vida fácil en cuanto a escribir código, esta vez tendremos que implementar las cosas nosotros mismos, porque la función `discrete_log` de SageMath no sabe que queremos «descartar» algunos de los factores primos. El siguiente fragmento de código hace esto:```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()
print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)
PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G
print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
new_order *= p^e
count_factors_needed += 1
if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
print("Found enough factors! The rest are not needed")
break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)
print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
quotient_n = (n // p ^ e)
G0 = quotient_n * G # G0's order is p^e
P0 = quotient_n * P
k = G0.discrete_log(P0)
subsolutions.append(k)
subgroup.append(p ^ e) # k the order of G0
print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
En este fragmento de código definimos una curva elíptica y un generador en ella, e imprimimos los factores primos de su orden. La salida es:``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271
El orden del generador es de `256 bit`, y se descompone en varios factores primos, de modo que los dos más grandes son de `77 bit` y `107 bit`. Son lo suficientemente grandes como para que sea poco práctico resolver ECDLP. Luego, se genera aleatoriamente una clave privada de `64 bit`, y se calcula una clave pública. En el siguiente paso, "recolectamos" suficientes factores primos hasta obtener un orden con una longitud de al menos `64 bit`. La salida es:```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
Se puede ver que los dos factores más grandes son redundantes, y el factor más grande que nos queda es de 40 bit. En el siguiente paso, para cada uno de los factores que nos quedan, calculamos los puntos 𝐺′ y 𝑃′ como expliqué antes, y para cada uno de ellos resolvemos el ECDLP. Los resultados y los factores primos se guardan en las listas subsolutions y subgroups respectivamente. Finalmente, todos los resultados se combinan mediante el Teorema Chino del Resto en la clave privada, y verificamos que efectivamente es correcta.
Al examinar la definición de la suma de puntos en curvas elípticas, notamos una propiedad interesante: en la suma de puntos no se utiliza el valor 𝑏, sino solo los valores 𝑎 y 𝑝. Esto significa que sumar puntos que se encuentran en una curva también puede tener sentido para otra curva que difiere de ella solo en ese valor de 𝑏. Esto es, por supuesto, también cierto al multiplicar un punto por un número. Si el usuario no verifica que el punto que recibe de la otra parte como clave pública realmente se encuentra en su curva, entonces se expone a un ataque de curva inválida.
Supongamos que dos partes acuerdan alguna curva elíptica $E_1$. Un atacante puede crear una curva maliciosa $𝐸_2$, que tiene los mismos valores de 𝑎 y 𝑝 que $𝐸_1$ pero un valor de 𝑏 diferente. En la curva $𝐸_2$, el atacante elegirá un punto 𝑃 cuyo orden sea pequeño, por ejemplo 3. Por supuesto, el punto 𝑃 no estará en $𝐸_1$, porque satisface una ecuación con un valor de 𝑏 distinto al de $𝐸_1$. El atacante enviará el punto 𝑃 como su clave pública al usuario. Digamos que al usuario no le importa verificar que el punto que recibe esté realmente en la curva $𝐸_1$ acordada por las partes. El usuario tomará la clave pública que recibió del atacante, la multiplicará por su clave privada y llegará a un punto que debería ser el punto secreto compartido, como vimos en la definición del protocolo ECDH. Desde el punto de vista del usuario, calculará la operación de multiplicación en la curva $𝐸_1$. Pero debido a que el punto 𝑃 no está en absoluto en esa curva, sino en $𝐸_2$, el usuario en realidad calculará la operación de multiplicación en la curva $𝐸_2$. Luego, el usuario utilizará el punto secreto compartido para continuar la comunicación con el atacante. Supongamos que las partes usan la coordenada 𝑥 del punto como clave de cifrado AES. En este caso, el usuario cifrará algún mensaje y lo enviará al atacante.
Dado que el orden de 𝑃 es 3, solo hay 3 posibilidades para el punto compartido que el usuario puede calcular. El atacante revisará estos posibles puntos y encontrará cuál de ellos corresponde a la clave que descifra con éxito el mensaje cifrado que envió el usuario. Dado este punto y el punto inicial 𝑃, el atacante puede deducir el resto de dividir la clave privada del usuario por el número 3. El atacante puede enviar al usuario puntos 𝑃 maliciosos adicionales, con órdenes crecientes, por ejemplo 5, 7, y así sucesivamente. De esta manera, el atacante puede recolectar suficientes valores que representen restos de divisiones de la clave privada del usuario entre números pequeños. Finalmente, el atacante puede usar el Teorema Chino del Resto para calcular la clave privada del usuario, de la misma manera que vimos en el ataque anterior.
Aquí hay una explicación más intuitiva: un atacante puede proporcionar al usuario un punto en un "círculo" muy pequeño, por ejemplo de longitud 2. El usuario avanzará en este "círculo" cualquier número de pasos y llegará al punto de destino. El atacante conoce el punto de destino del usuario, que puede ser una de 2 posibilidades. Por lo tanto, el atacante puede saber si el usuario ha dado un número par o impar de pasos en el círculo. El atacante puede proporcionar al usuario puntos adicionales en "círculos" de longitudes 3, 5, 7, y así sucesivamente. Hasta que el atacante tenga suficientes de esos factores, cada uno de los cuales contiene poca información sobre el número de pasos que ha dado el usuario. Finalmente, el atacante puede combinar todos estos valores en el número exacto de pasos que ha dado el usuario, que es su clave privada.
El siguiente código demuestra el ataque:```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random
curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()
private_key = random.randrange(n)
def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
message = pad(message.encode(), 16)
return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)
def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key
# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)
def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")
def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue
E = EllipticCurve(GF(p), [a, b])
for _ in range(100):
R = E.random_point()
n = R.order()
for f, e in n.factor():
if f in orders_found:
continue
if f > max_order:
break
# Create a point with order f
orders_found.add(f)
P = (n // f) * R
assert P.order() == f
yield (f, P)
subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)
# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)
# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)
# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)
# Found enough values to calculate private key
if upto >= n:
break
print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")
En este fragmento de código, se seleccionan una curva y un generador, el usuario genera aleatoriamente una clave privada y la usa en todos los usos del protocolo ECDH. La función `find_curves_with_small_subgroup` encuentra pares de puntos y órdenes, de modo que el orden de cada punto es relativamente pequeño, y el punto está en alguna curva que difiere de la curva original solo en el valor de `𝑏`. El código genera tales pares hasta que encuentra suficientes. Para cada par, se envía la clave pública al usuario y se recibe de él un mensaje cifrado.
Se realiza una fuerza bruta sobre el mensaje cifrado para encontrar el valor de la clave privada del usuario, módulo el orden actual. Todos estos resultados se guardan y, finalmente, usamos el Teorema Chino del Resto para calcular la clave privada del usuario y verificar que es correcta. En este caso, las partes acordaron que la comunicación se hará en AES, con la clave de cifrado que es la coordenada `x` del punto secreto compartido, y el IV que es su coordenada `𝑦`.
La complejidad del ataque es $𝑂(𝑛_{𝑚𝑎𝑥})$ donde $𝑛_{𝑚𝑎𝑥}$ es el mayor orden entre los órdenes de los puntos maliciosos. Esto se debe a que la parte más "pesada" del ataque es la fuerza bruta sobre el "círculo" más grande entre los "círculos" pequeños, y afortunadamente para el atacante, puede controlar este valor casi por completo. Por lo tanto, este ataque es relativamente eficiente en términos de complejidad. Como se mencionó, la raíz del problema en este caso es que el usuario no comprueba que el punto que recibe esté siquiera en la curva con la que está trabajando. Además, el usuario usa la misma clave privada en cada nuevo uso de ECDH, lo cual no es muy seguro.
## La curva es singular
Una de las propiedades importantes que una curva elíptica debe tener para ser criptográficamente segura es que sea no singular. Una curva no singular es una curva cuyo cierto valor, llamado "discriminante" de la curva, es distinto de cero. Esto se cumple cuando sus parámetros `𝑎` y `𝑏` satisfacen la desigualdad:
$4a^3 + 27b^2 ≠ 0$
Una curva que no satisface esta desigualdad tiene un punto "problemático" llamado `punto singular`. Hay dos tipos de tales puntos: nodo y cúspide. Un punto nodo existe en una curva que tiene una especie de lazo que se interseca a sí mismo en el punto singular, y se pueden trazar dos tangentes diferentes a la curva a través de este punto.
Un punto cúspide es un punto donde la curva es "afilada", como si dos líneas salieran de él, pero solo hay una tangente a la curva en ese punto.
<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves" width="500">
En un punto tipo nodo hay una raíz doble, por lo que la ecuación de la curva se puede escribir como:
$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$
La curva se puede "mover" a la izquierda reemplazando la variable $x$ por la variable $(𝑥 + 𝑥_0)$ y llegar a la forma:
$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$
Así que ahora el punto singular está en el origen de los ejes. El valor numérico de $t = (x_0-x_1)$ se puede usar para crear un mapeo entre los puntos de la curva y los enteros, de modo que la operación de suma entre puntos de la curva sea equivalente a la operación de multiplicación entre números. Para cada punto `(𝑥, 𝑦)` haremos corresponder el número
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$. En particular, a un par de puntos `𝐺` y `𝑄` tal que `𝑄 = 𝑛𝐺` podemos mapear números `𝑔` y `𝑞` tales que $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$, y esto es un problema DLP "normal". Para ilustrar este proceso, he añadido un enlace a un ejemplo con números pequeños en las referencias al final del artículo. En el mapeo que hicimos, usamos la ecuación de las líneas lineales $y+\sqrt{t}x$ y $y-\sqrt{t}x$, y esas son las líneas que corresponden a las dos tangentes que se pueden trazar en el punto singular (después de "mover" la curva), que es básicamente la razón por la que este ataque puede usarse.
Tal problema DLP se puede resolver eficientemente con la ayuda del algoritmo de Pohlig-Hellman, que ya hemos visto antes, porque también se puede usar en enteros en lugar de puntos en la curva. En el contexto de los puntos, vimos que el algoritmo es útil cuando el orden del generador es un número liso. A diferencia de un "círculo" de puntos en una curva, que puede tener cualquier orden, en el campo de los enteros módulo un número primo `𝑝` el orden es `𝑝 − 1`. Si `𝑝 − 1` es un número liso, entonces el algoritmo resolverá el problema DLP eficientemente, encontrando así la clave privada `n`.
El siguiente fragmento de código hace esto:```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0
Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066
x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()
assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
double_root = roots[0][0]
single_root = roots[1][0]
else:
double_root = roots[1][0]
single_root = roots[0][0]
print("double root:", double_root)
print("single root:", single_root)
# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)
# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()
def transform(x, y, t_sqrt):
return (y + t_sqrt * x) / (y - t_sqrt * x)
g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)
# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)
from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
En este fragmento de código, definimos los parámetros de una curva elíptica y verificamos que efectivamente es singular. Encontramos las raíces del polinomio correspondiente a la curva e identificamos cuál de ellas es la raíz doble. Usamos la raíz doble para "mover" la curva y alcanzamos los puntos "movidos" 𝐺 y 𝑄. Luego calculamos $\sqrt{t}$ a partir de las raíces que encontramos y lo usamos para mapear los puntos 𝐺 y 𝑄 a los números 𝑔 y 𝑞. Imprimimos la descomposición de 𝑝 − 1 en sus factores primos (para verificar que el DLP puede resolverse de manera eficiente). Finalmente, calculamos el DLP e interpretamos el resultado como una cadena.
La salida es: ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
Esta vez oculté un mensaje en la propia clave privada. Cabe señalar que, debido a que es una curva singular, no es posible en SageMath crearla de forma normal, definir puntos sobre ella y realizar operaciones con ellos como hicimos antes. En este código definí las coordenadas de los puntos como variables constantes. Para calcular el punto `𝑄`, yo mismo multipliqué la clave privada por el generador usando mi propia implementación del algoritmo Double And Add.
## La curva es supersingular
Dada una curva elíptica módulo `𝑝`, y un generador cuyo orden es `𝑛`, el grado de inmersión de la curva con respecto al generador se define como el número más pequeño `k` que satisface la ecuación $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$. Con ciertas transformaciones, el problema ECDLP puede reducirse a un problema DLP en un cuerpo de orden $𝑝^𝑘$. El valor `𝑘` suele ser un número muy grande (aproximadamente del mismo tamaño que el propio `𝑝`), pero cuando es relativamente pequeño (por ejemplo, menor que `6`), la curva se denomina `supersingular` y resulta factible resolver este problema DLP de forma eficiente. Este ataque se llama ataque MOV, en honor a sus tres inventores (Menezes-Okamoto-Vanstone).
Las transformaciones que mencioné son funciones que reciben dos puntos y devuelven un número en el cuerpo de los números complejos. Las transformaciones que se pueden usar son Weil Pairing o Tate Pairing, y las usaremos como una caja negra. Tal transformación `𝑇` satisface la siguiente propiedad para cada par de puntos `𝑃`, `𝑄`:
$T(mP, nQ)=T(P,Q)^{mn}$
Por lo tanto, dados dos puntos `𝐺` y `𝑄 = 𝑚𝐺`, podemos seleccionar aleatoriamente un tercer punto `𝑅` y calcular los dos valores: \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
Desde aquí podemos resolver el problema DLP para `𝑔` y `𝑞` en un cuerpo de orden $p^k$, encontrando así la clave privada `𝑚`. Incluí un enlace a una explicación más detallada de las matemáticas detrás de este ataque, en las referencias al final del artículo.
El siguiente fragmento de código realiza este ataque:```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052,
524474557735717484100814381066)
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
k += 1
print("Found k:", k)
# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G
# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()
# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY
# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)
# Make sure the pairing did not break anything
assert g ^ private_key == q
print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
En este fragmento de código definimos una curva y su generador, y calculamos su valor de Grado de Inmersión, que en este caso es 2, por lo tanto es práctico realizar el ataque. Definimos una curva idéntica a la curva original, excepto que los cálculos se realizan módulo $𝑝^𝑘$ en lugar de módulo $𝑝$. Los dos puntos 𝐺 y 𝑄 también están en la nueva curva. Luego encontramos un tercer punto cuyo orden divide a 𝑛.
Usando el tercer punto, mapeamos los puntos 𝐺 y 𝑄 a los números 𝑔 y 𝑞 y calculamos el logaritmo discreto para ellos. Finalmente, verificamos que el resultado obtenido es de hecho correcto.
La salida es:``` Found k: 2 Calculating private key... success! The private key is: Festivus
Desde un punto de vista computacional, hoy existen algoritmos de cálculo de índices que pueden resolver el problema DLP de forma relativamente eficiente, y lo hacen con una complejidad de $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$. Esta expresión puede parecer intimidante, pero comparada con los algoritmos ECDLP cuya complejidad es $O(\sqrt{p})=e^{O(log\ p)}$, se puede ver que es más fácil resolver el problema DLP, asumiendo que el Grado de Inmersión (denotado por `𝑘`) es efectivamente pequeño.
## La curva es anómala
Si una curva determinada tiene la propiedad de que el orden de la curva (el número de puntos sobre ella) es exactamente igual al módulo `𝑝`, entonces se la denomina `Anomalous Curve` y es vulnerable a un ataque llamado Smart's Attack. Este ataque utiliza `𝑝-adic numbers`. Un número de este tipo se puede representar como una suma de potencias de `p` (positivas y negativas) con coeficientes. Formalmente, un número `s` de este tipo es una serie de la forma:
$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$
Cuando los coeficientes son enteros en el rango $0 ≤ 𝑎_𝑖 < 𝑝$, y la suma puede ser infinita en la dirección de las potencias positivas de `𝑝`. En estos números, "miramos" los dígitos de derecha a izquierda en lugar de izquierda a derecha, y por lo tanto dicha serie puede converger a algún valor. Estos números pertenecen a un sistema numérico diferente al que estamos acostumbrados, y se comportan de forma muy distinta a las reglas matemáticas "normales". Se podría escribir un artículo completo solo sobre este tema, y para aquellos interesados, he incluido en las referencias al final del artículo un enlace a un video que lo presenta de una manera relativamente clara.
En cualquier caso, en este ataque se crea una nueva curva a partir de la curva dada, definida sobre los números p-ádicos. Dados dos puntos `𝐺` y `𝑄 = 𝑚𝐺` en la curva original, los mapeamos a los puntos correspondientes en la nueva curva. A partir de las coordenadas de los puntos obtenidos es fácil calcular `𝑚`.
El siguiente código realiza el ataque:```python
def lift(P, E, p):
# lift point P from old curve to a new curve
Px, Py = map(ZZ, P.xy())
for point in E.lift_x(Px, all=True):
# take the matching one of the 2 points corresponding to this x on the p-adic curve
_, y = map(ZZ, point.xy())
if y % p == Py:
return point
p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p
private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G
# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37])
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)
# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
En este fragmento de código, se define una función lift, que recibe un punto de la curva original y le hace corresponder un punto en la nueva curva. Luego definimos una curva elíptica y un generador en ella, y verificamos que el orden de la curva es efectivamente p. Elegimos una clave privada y calculamos la correspondiente clave pública. Después realizamos el ataque. Definimos una nueva curva sobre los números p-ádicos, y mapeamos los puntos originales 𝐺 y 𝑃 a los puntos correspondientes en la nueva curva usando la función lift y multiplicándolos por 𝑝.
Para cada nuevo punto, calculamos la razón entre su coordenada 𝑥 y su coordenada 𝑦. El cociente de estos dos valores es la solución ECDLP de los puntos originales.
La salida es:``` success! The private key is: >>>>> Extraordinarily Nice <<<<<
La razón por la que este cálculo funciona está relacionada con el hecho de que el número de puntos en la curva es exactamente `𝑝`. Esta propiedad nos permite realizar varios mapeos, el último de los cuales mapea entre puntos en una curva sobre números 𝑝-ádicos, a números módulo $p^2$. Este mapeo tiene la propiedad de que la razón entre el par de números correspondientes a los dos puntos originales es exactamente el resultado del logaritmo de los dos puntos. Dejaremos todos estos mapeos como una caja negra, pero al final del artículo añadí referencias a las explicaciones matemáticas pertinentes.
# Ataques a ECDSA
## No calcular el hash del mensaje antes de firmarlo
Vimos que en el proceso de firmar un mensaje, primero se calcula el hash del mensaje, y los bits altos del hash se utilizan en el cálculo de la firma. Supongamos que en alguna implementación de firma y verificación, este paso de hash se omite y, en lugar de tomar los bits altos del hash, los bits se toman del mensaje tal cual. En tal implementación, la única parte del mensaje que afecta a su firma es el comienzo del mensaje. En otras palabras, si tenemos un mensaje y su firma, podemos conservar el comienzo del mensaje y cambiar el resto, y la firma seguirá siendo válida. Es un ataque realmente simple.
Supongamos, por ejemplo, que escribes el siguiente mensaje a tu banco y lo firmas sin calcularle el hash:```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"
El banco verificará correctamente este mensaje y realizará la acción. Algún ... atacante ... podría crear el siguiente mensaje:``` "Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"
Y usa la firma que acabas de crear. La firma también será válida para este mensaje, y el banco realizará la acción. No es bueno (bueno, depende de quién).
El siguiente código demuestra el ataque:```python
from ecdsa import SigningKey, NIST256p
signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key
class MyHash:
def __init__(self, data):
self.data = data
def digest(self):
return self.data
# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)
# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")
En este fragmento de código se utiliza la librería ecdsa, junto con una curva conocida. Definimos una clase que debería implementar una función hash pero no lo hace, y en su lugar deja el mensaje tal cual. Por lo tanto, al firmar un mensaje, solo se utilizan los primeros bits del mensaje original, en lugar de los de su hash. Luego el mensaje se firma y se verifica correctamente. A continuación se crea un mensaje malicioso y el código verifica que la firma del mensaje original también coincide con el mensaje malicioso.
En tal escenario, puede que no hayamos obtenido la clave privada para generar nuestras propias firmas nuevas, pero dada una firma, podemos firmar tantos mensajes como queramos, siempre que comiencen con el mismo prefijo.
k En Diferentes FirmasComo parte del proceso de firma de mensajes, se requiere que el usuario genere aleatoriamente un valor 𝑘 y lo use para firmar el mensaje. Es muy importante usar diferentes valores 𝑘 en diferentes firmas. De lo contrario, dados dos mensajes firmados donde el usuario usó el mismo valor 𝑘 en lugar de re-generarlo, un atacante podría calcular la clave privada del usuario.
Como se mencionó, durante la firma de mensajes el usuario envía públicamente $r=x_1\ \ \ \ (mod\ p)$ y $s=k^{-1}(z+rd_A)$. Suponiendo que el usuario firmó dos mensajes diferentes correspondientes a $𝑧_1$ y $𝑧_2$, y envió públicamente dos pares de valores $𝑟, 𝑠_1$ y $𝑟, 𝑠_2$, es decir, usó el mismo valor 𝑘 en estas dos firmas. Observamos que:
$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$
A partir de esto, el atacante puede encontrar el valor de 𝑘 calculando:
$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$
Una vez que el atacante ha encontrado 𝑘, puede calcular la clave privada del usuario a partir de una de las firmas. Nótese que:
$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$
Dados los valores de 𝑟, 𝑠 y 𝑧 de un mensaje y su firma, y el valor de 𝑘 que el atacante encontró, el atacante puede calcular $d_A=r^{-1}(ks-z)$. A partir de este punto, el atacante puede firmar cualquier mensaje que desee, en nombre del usuario cuya clave privada obtuvo.
El siguiente fragmento de código realiza este ataque:```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha256 import random
curve = curve_256 generator = generator_256 n = generator.order()
secret_key = 6743529130774090927928101169617481154782309 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
k = random.randrange(curve.p()) message1 = "Life is like a box of chocolates." message2 = "You never know what you're gonna get." z1 = bytes_to_long(sha256(message1.encode()).digest()) z2 = bytes_to_long(sha256(message2.encode()).digest())
signature1 = private_key.sign(z1, k) signature2 = private_key.sign(z2, k)
found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n assert k == found_k
found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
En este fragmento de código, se utiliza la librería `ecdsa`, junto con una curva conocida. Definimos una clave privada y la usamos para firmar dos mensajes. El valor de `𝑘` se genera aleatoriamente, pero permanece igual para las dos firmas. Dados los dos mensajes y sus firmas, el código realiza el cálculo que vimos para encontrar `𝑘`. Finalmente, usamos el valor de `𝑘` que encontramos para calcular la clave privada como vimos. La salida es:```
Success!
The secret is: Mistakes were made
Es interesante notar que este ataque se utilizó realmente en 2010, cuando Sony implementó de forma insegura su mecanismo de firma en el software de la consola PlayStation. Sony usaba un valor estático de 𝑘 para sus firmas, lo que permitió a los atacantes obtener la clave privada de Sony mediante el cálculo anterior. Esto llevó a la capacidad de firmar cualquier código y hacer que PlayStation aceptara ejecutarlo. Posteriormente, esta capacidad se usó para instalar juegos pirateados y no oficiales en la consola.
k de forma inseguraSi el usuario elige 𝑘 de una manera insuficientemente aleatoria, entonces la clave privada puede ser encontrada. Por ejemplo, si el atacante sabe que 𝑘 está en un rango muy pequeño de valores, o si conoce algunos de los bytes de 𝑘, entonces es posible, mediante una simple fuerza bruta, encontrar la clave privada del usuario a partir de un único mensaje firmado. El atacante ejecutará el cálculo que vimos en el ataque anterior para los diferentes valores de 𝑘, hasta que alcance el valor correcto y obtenga la clave privada a partir de él.
Para superar este problema, a veces los usuarios generan aleatoriamente algún valor, calculan su hash con alguna función hash y usan el resultado como 𝑘. Este método puede causar problemas. Supongamos, por ejemplo, que el orden del generador 𝑛 es de 256 bit, y la función hash seleccionada es SHA-1. La salida de esta función es un número de 160 bit. En cálculos módulo 𝑛, se sabe que el valor de 𝑘 contiene 96 ceros al principio, lo que significa que 𝑘 es un número relativamente pequeño. En tal situación, se dice que los valores de 𝑘 son biased, y dados varios mensajes firmados con la misma clave privada, la clave privada puede ser encontrada.
El ataque se basa en una estructura algebraica llamada reticulado. Informalmente, un reticulado puede pensarse como un conjunto de vectores en un espacio de dimensión 𝑚, que puede expresarse como una combinación lineal de vectores "base" con coeficientes enteros. Matemáticamente, si $\{b_1,\dots,b_d\}$ son los vectores base sobre $ℝ^𝑚$, entonces el reticulado correspondiente a ellos es $L=$ $\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}$. En esta estructura existe el problema conocido: dada la base de un reticulado, encontrar el vector más corto que existe en el reticulado. En este contexto, informalmente, un vector "corto" es un vector cuyos elementos están lo más cerca posible de cero. Este problema se llama el Problema del Vector Más Corto (SVP), y se considera NP-hard. Existen algoritmos que resuelven un problema similar pero más fácil: encontrar algún vector corto, es decir, un vector relativamente "cercano" al vector más corto del reticulado. Este problema se llama el Problema del Vector Más Cercano (CVP), y uno de los algoritmos que lo resuelve se llama algoritmo de Lenstra-Lenstra-Lovász (LLL). En este ataque usaremos este algoritmo como una caja negra.
Dados 𝑑 mensajes firmados, es posible construir un reticulado que contenga el vector $(𝑘_1, \dots , 𝑘_𝑑)$, donde cada elemento del vector es un valor 𝑘 que corresponde a una firma. El algoritmo LLL encontrará una aproximación al vector más corto de este reticulado. Dado que se sabe que los valores de 𝑘 son pequeños, hay una alta probabilidad de que el vector corto que encuentre el algoritmo contenga al menos un elemento k correcto. Una vez que se encuentra un 𝑘 correcto, la clave privada se puede calcular como vimos en el ataque anterior.
Para construir este reticulado, es necesario definir sus vectores base. He incluido en las referencias al final del artículo un enlace a un artículo que explica cómo se definen estos vectores base. Técnicamente, los vectores base del reticulado se pueden representar como una matriz, de modo que cada fila de ella consta de los elementos de un vector base. Para mejorar la precisión del algoritmo LLL, se recomienda añadir a esta matriz dos columnas que contienen información sobre el tamaño esperado de los valores de 𝑘 y la relación entre 𝑘 y 𝑛. Esta mejora también se explica en la referencia que adjunté. El siguiente fragmento de código demuestra este ataque:```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import random
def build_matrix(signatures, bias, q): # M matrix should be: """ [ B 0 m'1 m'2 m'2 ... m'n 0 B/q r'1 r'2 r'3 ... r'n 0 0 0 0 q * I 0 0 ] where: m' = s^-1 * m r' = s^-1 * r """
# Construct the first 2 rows of M:
row1 = [bias, 0]
row2 = [0, bias / q]
for m, r, s in signatures:
row1.append((inverse_mod(s, q) * m) % q)
row2.append((inverse_mod(s, q) * r) % q)
top_rows = Matrix(QQ, [row1, row2])
# Construct the q*I block along with 2 columns of zeros
zero_cols = zero_matrix(QQ, len(signatures), 2)
qI = q * identity_matrix(QQ, len(signatures))
bottom_rows = block_matrix([[zero_cols, qI]])
# Combine all rows into one matrix
M = top_rows.stack(bottom_rows)
return M
def find_private_key(L, signatures, public_key): # Check if any valid k was found in L generator = public_key.generator q = generator.order() for row in L.rows(): for i in range(len(signatures)): m,r,s = signatures[i] # Skip the first two vector components we used to improve LLL possible_k = row[i+2] # LLL might have swapped the sign of the found short vectors for k in [possible_k, -possible_k]: d = inverse_mod(r,q)(ks-m) % q if d*generator == public_key.point: return d
curve = curve_256 generator = generator_256 q = int(generator_256.order())
secret_key = 1793056234309773077862125006843383726029262764680727851636 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
messages_to_sign = [ "And then I go and spoil it all", "By saying somethin' stupid like", "I love you" ]
signatures = [] for message in messages_to_sign: message_hash = bytes_to_long(sha1(message.encode()).digest()) k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest()) signature = private_key.sign(message_hash, k) signatures.append((message_hash, signature.r, signature.s))
bias = 2^160 M = build_matrix(signatures, bias, q)
L = M.LLL()
found_key = find_private_key(L, signatures, public_key) assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
En este fragmento de código se utiliza una curva estándar, se selecciona una clave privada y a partir de ella se calcula la clave pública correspondiente. Se crean 3 mensajes y se firman con 3 valores aleatorios `k` que son el resultado de la función hash SHA-1. Luego creamos la matriz correspondiente a la base del retículo, como se explica en el artículo, y ejecutamos el algoritmo LLL sobre ella. Después, recorremos las filas de la matriz resultante y comprobamos si en alguna de ellas se encuentra un valor correcto de cualquier `𝑘`.
La comprobación se realiza calculando la clave privada a partir del posible `𝑘`, como vimos en el ataque anterior, y verificando si la clave obtenida es realmente correcta. Finalmente, nos aseguramos de que la clave privada encontrada es realmente correcta. La salida es:```
success!
The secret is: I am Jack's broken heart
La complejidad de este ataque es la misma que la del algoritmo LLL, que es $O(d^6\ \log^3B)$, donde 𝐵 indica la longitud del sesgo de 𝑘 ($2^{160}$ en nuestro caso), y 𝑑 indica el número de mensajes firmados (3 en nuestro caso). Surge la pregunta de cuál es el número mínimo de mensajes firmados que debemos utilizar para poder ejecutar el ataque. La respuesta es $\displaystyle d=O(\frac {\log n}{\log n-\log B})$ donde 𝑛 es el orden del generador y 𝐵 es el sesgo. Una explicación de esto aparece en el segundo enlace de las referencias que adjunté a este tema al final del artículo.
En la práctica, también se puede ejecutar una variante de este ataque en casos donde se conocen los bits superiores de 𝑘, o simplemente cualquier bit de 𝑘. El ataque puede ejecutarse incluso si solo se conoce el valor de un bit, o incluso si solo se conoce el valor de un bit con una probabilidad mayor al 50%. Pero, por supuesto, en estos casos se requieren muchos más mensajes firmados para realizar el ataque.
Vimos que en el proceso de verificación de firma, la parte firmante envía el par de valores 𝑟 y 𝑠 a la parte verificadora. En los navegadores que implementan el protocolo HTTPS, por ejemplo, es habitual enviar este par de valores en un certificado, que también puede contener datos sobre la curva que utilizó la parte firmante. La parte verificadora debe asegurarse de que los datos de la curva que se encuentran en el certificado coinciden con la curva acordada previamente. Si no coinciden, puede ser problemático.
Supongamos que en una determinada curva Alicia tiene una clave privada $d_A$ y una clave pública $𝑃_𝐴$ que le corresponde, lo que significa que $𝑃_𝐴 = 𝑑_𝐴𝐺$ para el generador 𝐺 en esta curva. Con la clave privada $𝑑_𝐴$, Alicia puede firmar sus mensajes como vimos en la definición del protocolo ECDSA. Supongamos que la parte que verifica la firma también recibe el generador 𝐺 del usuario, y no verifica que el generador recibido del usuario sea efectivamente el generador acordado. Un atacante puede enviar como generador el punto que es la clave pública de Alicia, $𝐺^′ = 𝑃_𝐴$. El atacante elegirá como clave privada "falsa" el valor $𝑑_𝐴^′ = 1$, y por tanto es evidente que $𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$. Esto significa que el atacante puede "demostrar" que tiene la clave privada que corresponde a la clave pública de Alicia. Así, un atacante puede crear cualquier mensaje que desee y calcular para él un par de valores 𝑟 y 𝑠 de la manera habitual con $𝑑_𝐴^′$, y la firma resultante se verificará con éxito.
Intuitivamente, en el proceso de verificación de firma, la parte firmante demuestra que es efectivamente la "titular" de la clave pública, que en realidad es un punto de "destino" en la curva. Esto se debe a que solo el firmante sabe cuántos pasos dar desde el punto de partida para llegar al punto de destino. Si la parte verificadora no verifica que el punto de partida recibido del usuario sea realmente el punto de partida verdadero, entonces un atacante puede decidir que el punto de partida es el punto de destino, y que el número de pasos a dar desde él es cero. Todas las demás partes de la verificación de firma permanecen igual, y la firma se verificará con éxito. Este ataque se llama Curveball.
Este ataque puede generalizarse con valores adicionales. El atacante elegirá algún valor 𝑥 y calculará $𝐺^′ = 𝑥𝑃_𝐴$. La clave privada falsa será $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$. Entonces es evidente que se cumple $𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$.
El siguiente código demuestra el ataque:```python from ecdsa.ecdsa import generator_256 from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random
def hash_message(message): return bytes_to_long(sha256(message.encode()).digest())
def verify(public_key, G, message, r, s): n = G.order() if r < 1 or r > n - 1 or s < 1 or s > n-1: return False hash = hash_message(message) u1 = (hash * inverse_mod(s, n)) % n u2 = (r * inverse_mod(s, n)) % n P = u1 * G + u2 * public_key return P.x() % n == r
def sign(private_key, G, message): n = G.order() k = random.randrange(n) hash = hash_message(message)
r = (k * G).x() % n
s = inverse_mod(k, n) * (hash + r * private_key) % n
return r, s
G = generator_256 n = G.order() private_key = random.randrange(n) public_key = private_key * G
message = "Let me be the one that shines with you" r, s = sign(private_key, G, message) assert verify(public_key, G, message, r, s)
x = random.randrange(n) fake_G = x * public_key fake_private_key = inverse_mod(x, n) assert fake_private_key != private_key assert fake_G != G
evil_message = "Where did I go wrong?" r, s = sign(fake_private_key, fake_G, evil_message) assert verify(public_key, fake_G, evil_message, r, s)
En este fragmento de código elegimos un generador conocido, una clave privada y una clave pública. Firmamos un mensaje y nos aseguramos de que se verifica correctamente. Luego creamos una clave privada falsa y un generador falso de modo que ambos coincidan con la clave pública original. Un mensaje malicioso se firma con la clave falsa y, finalmente, la firma falsa se verifica correctamente con la clave pública original. El problema con este código es que el algoritmo de verificación no comprueba que el generador `𝐺` coincida con la clave pública. Aunque en este ataque no encontramos la clave privada del usuario, un atacante puede explotar la implementación incorrecta de la verificación de firmas y crear una firma que se verifique correctamente. Sin embargo, el atacante no puede crear firmas "reales" que de hecho se verifiquen correctamente en una implementación correcta de la verificación de firmas.
Es interesante señalar que esta es una vulnerabilidad real que existía en la arquitectura Windows CryptoAPI. En la función responsable de verificar la firma de un certificado, había una verificación insuficiente de los parámetros de la curva, en los casos en que estos se incluían en el propio certificado. En particular, no se comprobaba que el generador fuera efectivamente el generador que corresponde a la clave pública. Un atacante podía crear certificados falsos que se consideraban de confianza porque parecían estar firmados por una Autoridad de Certificación de confianza. Esto se lograba añadiendo campos de curva maliciosos al certificado y eligiendo el generador de la forma que he descrito. La vulnerabilidad fue descubierta por la organización NSA, corregida en 2020 y recibió el número CVE-2020-0601.
# Conclusión
## Resumen de los Ataques ECDH
| Tipo de Problema | El Problema | El Ataque | Cómo Funciona el Ataque | Complejidad del Ataque |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Seleccionar una curva con un generador inseguro | El orden del generador `n` es demasiado pequeño | Baby-Step Giant-Step | Meet In The Middle | $𝑂(\sqrt n)$ |
| Seleccionar una curva con un generador inseguro | El orden del generador `n` es un número liso | Pohlig-Hellman | Descomponer `𝑛` en factores primos, atacar cada uno de ellos por separado y combinar los resultados mediante el Teorema Chino del Resto | $O(\sqrt{p_{max}})$ donde $p_{max}$ es el factor primo más grande en la descomposición de `𝑛` |
| Seleccionar una curva con un generador inseguro + seleccionar una clave privada insegura | El orden del generador `n` es casi un número liso, y la clave privada es pequeña | Pohlig-Hellman mejorado | Descomponer `𝑛` en factores primos, descartar los factores demasiado grandes, atacar cada uno de ellos por separado y combinar los resultados mediante el Teorema Chino del Resto | $O(\sqrt{p_{max}})$ donde $p_{max}$ es el factor primo más grande en la descomposición de `𝑛` |
| Implementación incorrecta de ECDH | No verificar que un punto está en la curva | Ataque de Curva Inválida | Enviar puntos con órdenes pequeños en curvas maliciosas como clave pública, atacar cada uno de ellos por separado y combinar los resultados mediante el Teorema Chino del Resto | $𝑂(𝑛_{𝑚𝑎𝑥})$ donde $𝑛_{𝑚𝑎𝑥}$ es el orden más grande entre los órdenes de los puntos maliciosos |
| Seleccionar parámetros de curva de forma insegura | La curva es singular | Reducir ECDLP a DLP | Mapear puntos a números de una manera que convierte la suma de puntos en multiplicación de enteros | $O(\sqrt{p_{max}})$ donde $p_{max}$ es el factor primo más grande en la descomposición de $(p-1)$ |
| Seleccionar parámetros de curva de forma insegura | La curva es supersingular | Reducir ECDLP a DLP | Mapear puntos a números de una manera que convierte la suma de puntos en multiplicación de enteros | $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$ donde `k` es el grado de inmersión con respecto al generador |
| Seleccionar parámetros de curva de forma insegura | La curva es anómala | Ataque de Smart | Una serie de mapeos entre puntos en una curva y puntos en una curva sobre números `p-adic`, y de vuelta a enteros | $O(1)$ |
## Resumen de los Ataques ECDSA
| Tipo de Problema | El Problema | El Ataque | Cómo Funciona el Ataque | Complejidad del Ataque |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Implementación incorrecta de la firma y la verificación | No aplicar hash al mensaje antes de firmarlo | Dado un mensaje firmado, falsificar mensajes adicionales que corresponden a la misma firma | Mantener el prefijo del mensaje tal cual y modificar el resto | $O(1)$ |
| Uso incorrecto del algoritmo de firma | Reutilizar el mismo valor de `k` en diferentes firmas | Encontrar la clave privada del usuario | Encontrar el valor de `k` y calcular a partir de él la clave privada del usuario | $O(1)$ |
| Uso incorrecto del algoritmo de firma | Generar valores de `k` de forma insegura | Dados varios mensajes firmados, encontrar la clave privada del usuario | Reducir el problema a encontrar un vector corto en un retículo, encontrar el valor de `k` y calcular a partir de él la clave privada del usuario | $O(d^6\ \log^3B)$ donde `B` es el sesgo de `k`, y `d`d es el número de mensajes firmados |
| Implementación incorrecta de la verificación | No verificar que el generador es válido | Falsificar firmas que se verifican correctamente (Curveball) | Seleccionar un generador falso y una clave privada que correspondan a la clave pública de otro usuario | $O(1)$ |
## Protección Contra Estos Ataques
Cabe señalar que en ECDH, ambas partes deben ponerse de acuerdo sobre la curva al inicio del protocolo. Si un usuario se comunica con un atacante, y el atacante es quien proporciona los parámetros de la curva, entonces el atacante puede proporcionar parámetros inseguros. Como resultado, el atacante puede obtener la clave privada del usuario. Si el usuario siempre utiliza la misma clave privada, entonces el atacante puede descifrar todas las conversaciones entre ese usuario y cualquier otro usuario. Por eso es muy importante no permitir que usuarios desconocidos proporcionen los parámetros de la curva si no se puede confiar en ellos. Además, debes asegurarte de que cada punto recibido de un usuario externo esté realmente en la curva acordada. Y, por supuesto, debes asegurarte de que la curva seleccionada en sí no sea vulnerable a uno de los ataques conocidos que hemos visto. También es mejor utilizar una clave privada nueva cada vez que uses el protocolo ECDH.
Del mismo modo, en ECDSA, se debe tener cuidado de implementar correctamente los algoritmos de firma y verificación. No omitas el hash del mensaje, la generación aleatoria y segura del valor `𝑘` cada vez que se use el protocolo y, por supuesto, en la verificación de firmas, si el generador se recibe del usuario - asegúrate de que sea efectivamente el que se acordó anteriormente.
## Referencias
- En este artículo utilicé gráficos del libro Understanding Cryptography de Christof paar:\
https://gnanavelrec.wordpress.com/wp-content/uploads/2019/06/2.understanding-cryptography-by-christof-paar-.pdf
- Un sitio que ilustra cómo se ven las curvas elípticas criptográficas:\
https://graui.de/code/elliptic2/
- Explicación detallada de las operaciones de suma y multiplicación en curvas elípticas:\
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
- Conferencia sobre introducción a las curvas elípticas y suma de puntos - por Christof Paar:\
https://www.youtube.com/watch?v=vnpZXJL6QCQ
- Conferencia sobre generadores, ECDLP, dificultad de los problemas, ECDH, Double And Add - por Christof Paar:\
https://www.youtube.com/watch?v=zTt4gvuQ6sY
- Explicación del Nivel de Seguridad de diferentes algoritmos de cifrado:\
https://en.wikipedia.org/wiki/Security_level
- Explicación de ECDH:\
https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman
- Explicación de ECDSA:\
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
- Explicación de las firmas con ElGamal:\
https://en.wikipedia.org/wiki/ElGamal_signature_scheme
- Explicación del teorema chino del resto:\
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
- Explicación de la relación entre el discriminante de una curva singular y el hecho de que tiene una raíz doble:\
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity
- Un ejemplo con números pequeños del mapeo entre puntos y números en curvas singulares:\
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp/61434#61434
- Explicaciones de los números 𝑝-ádicos:\
https://en.wikipedia.org/wiki/P-adic_number \
https://www.youtube.com/watch?v=3gyHKCDq1YA
- Explicación de las matemáticas detrás del ataque MOV:\
https://risencrypto.github.io/WeilMOV/
- Explicaciones de las matemáticas detrás del ataque de Smart (es bastante complicado, ya estás advertido):\
https://wstein.org/edu/2010/414/projects/novotney.pdf \
http://www.monnerat.info/publications/anomalous.pdf
- Explicación del ataque basado en retículos y del algoritmo LLL:\
https://forum.vac.dev/t/lattice-attacks-on-ecdsa/136 \
\
El ataque se basa en la parte 4 de un artículo de Joachim Breitner y Nadia Heninger:\
https://eprint.iacr.org/2019/023.pdf
- Explicación del problema CVP:\
https://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_(CVP)
- Explicación del algoritmo LLL:\
https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm