Tiempo de ataque

En criptografía , un ataque de sincronización es un ataque de canal lateral en el que un atacante intenta comprometer un sistema criptográfico analizando el tiempo que lleva ejecutar algoritmos criptográficos. Cada operación lógica toma tiempo para ejecutarse en la computadora, y este tiempo puede variar dependiendo de los datos de entrada. Con mediciones de tiempo precisas para diferentes operaciones, un atacante puede recuperar los datos de entrada.

Los criptosistemas a menudo pasan cantidades de tiempo ligeramente diferentes procesando diferentes entradas. Las razones de esto pueden ser optimizaciones de rendimiento que omiten operaciones innecesarias, bifurcaciones , lectura de datos de la memoria caché , instrucciones del procesador (como multiplicación y división) que se ejecutan en un tiempo no determinista, y otras. Las características de rendimiento suelen depender tanto de la clave de cifrado como de los datos de entrada. Al mismo tiempo, el tiempo dedicado a la ejecución de determinadas solicitudes puede convertirse en una fuente de fuga de información sobre el sistema. La cantidad de información que puede ayudar a un atacante depende de muchos parámetros, como: el diseño del criptosistema, el procesador que sirve al sistema, los algoritmos utilizados, los detalles de implementación relevantes, las contramedidas tomadas contra el ataque de sincronización, la precisión de la demora. medidas tomadas.

Un ataque al algoritmo de exponenciación rápida

El algoritmo de exponenciación rápida utilizado por los algoritmos Diffie-Hellman y RSA realiza la siguiente operación en la clave secreta , donde n es parte de la clave pública (RSA) o una constante (Diffie-Hellman) e y puede escucharse. El objetivo del atacante es obtener la clave secreta x . La víctima calcula múltiples valores de y . w es la longitud en bits de la clave x . $R=y^{x}{\bmod {n))$ $y^{x}{\bmod{n))$

Vamos~s_{{0}}~=~1

Para~k=0~hasta~w-1:

Si~(bit~k~de~x)~es~1~entonces

LetR_{k}=(s_{k}\cdot y){\bmod {n))

{\ estilo de visualización más}

Vamos~R_{{k}}~=~s_{{k}}

Let~s_{k+1}=R_{k}^{2}{\bmod {n))

EndFor

Regresar~(R_{{w-1}})

El ataque permite, conociendo los bits 0..(b-1) , encontrar el bit b . Para obtener el exponente completo, se puede comenzar con b=0 y continuar hasta conocer el exponente completo.

Conociendo los primeros b bits de x , el atacante puede calcular las primeras iteraciones del ciclo y encontrar el valor de . La siguiente iteración usa el primer bit desconocido de x . Si es igual a 1, se realizará el cálculo , si es 0, entonces se omitirá la operación. $Para$ $s_{{b}}$ $R_{b}=(s_{b}\cdot y){\bmod {n))$

Usando el Teorema Chino del Resto

Para optimizar las operaciones de clave secreta en RSA , a menudo se utiliza el teorema chino del resto . Primero, se calculan y , donde y es el mensaje. El ataque más simple es elegir y cerca de p o q . Si y es menor que p , no hará nada, y si , deberá restar p de y al menos una vez. Además, si y es ligeramente mayor que p , entonces tendrá los bits más significativos iguales a cero, lo que puede reducir el tiempo de la primera multiplicación. El tiempo específico depende de la implementación. $y{\bmod {p}}$ $y{\bmod {q}}$ $y{\bmod {p}}$ $y>p$ $y{\bmod {p}}$

Ejemplos de ataques a RSA: Ataques de tiempo a RSA y Ataques de tiempo a RSA

Criptoanálisis temporal DSS

El algoritmo del estándar de firma digital calcula , donde p y q son conocidos por el atacante y calculados de antemano, H(m) es el hash del mensaje, x es la clave secreta. En la práctica, primero se calcula y luego se multiplica por . El atacante puede calcular H(m) y corregir en consecuencia. Dado que H(m) tiene aproximadamente el mismo tamaño que q , la suma tiene poco efecto en la operación de reducción en el método de exponenciación de Montgomery ( en ). Los bits más altos serán los más significativos . El valor de r es conocido. Existe una relación entre los bits altos de x y el tiempo de ejecución de la operación de reducción de Montgomery. Si se calcula de antemano, la firma del mensaje requiere solo dos multiplicaciones de módulo, por lo que la cantidad de ruido agregado se vuelve relativamente pequeña. $s=(k^{-1}(H(m)+x\cdot r)){\bmod {q))$ $k^{{-1}}$ $(H(m)+x\cdot r){\bmod {q))$ $k^{-1}{\bmod {q))$ $x\cdot r$ $k^{{-1}}$

Enmascaramiento de tiempo

La forma más obvia de prevenir ataques de sincronización es asegurarse de que todas las operaciones tomen la misma cantidad de tiempo. Sin embargo, es difícil implementar una solución de este tipo, especialmente si es independiente de la plataforma, ya que las optimizaciones realizadas por el compilador, los accesos a la memoria caché, los tiempos de instrucción y otros factores pueden introducir desviaciones de tiempo imprevistas. Si se utiliza un temporizador para retrasar la salida del resultado, la capacidad de respuesta del sistema sigue siendo observable. Además, algunos sistemas operativos brindan niveles de carga del procesador y consumo de energía.

Otro enfoque es hacer que las mediciones de tiempo sean tan inexactas que el ataque se vuelva insoportable. Se agregan demoras aleatorias al tiempo de ejecución, lo que aumenta la cantidad de textos cifrados necesarios para un atacante.

Prevención de ataques

Las técnicas utilizadas para crear firmas ciegas (ver también Cegamiento ) se pueden adaptar para evitar que un atacante exponga la entrada a una operación de exponenciación de módulo. Antes de calcular el exponente modular, elegimos un par aleatorio tal que . Para Diffie-Hellman, es más fácil elegir primero uno al azar y luego calcular . Para RSA, es más rápido elegir un coprimo aleatorio con n y luego calcular , donde e es parte de la clave pública. Antes de realizar el módulo de exponenciación, el mensaje de entrada debe multiplicarse por , y luego el resultado debe corregirse multiplicando por . El sistema debe descartar mensajes iguales a . $(v_{{i}},v_{{f}})$ $v_{f}^{-1}=v_{i}^{x}{\bmod {n))$ $v_{{yo}}$ $v_{f}={(v_{i}^{-1})^{x}}{\bmod {n}}$ $v_{{f}}$ $v_{i}={(v_{f}^{-1})}^{e}{\bmod {n))$ $v_{i}{\pmod {n))$ $v_{f}{\pmod {n))$ ${\ estilo de visualización 0 {\ pmod {n}}}$

Calcular el módulo inverso se considera una operación lenta, por lo que a menudo no es práctico generar un nuevo par para cada operación de exponenciación. Sin embargo, no se pueden reutilizar, ya que ellos mismos pueden ser atacados por el tiempo. Hay una solución: actualizar y antes de cada operación de exponenciación calculando y . $(v_{{i}},v_{{f}})$ $v_{{yo}}$ $v_{{f}}$ $v_{{i}}^{{'}}=v_{{i}}^{{2}}$ $v_{{f}}^{{'}}=v_{{f}}^{{2}}$

Enlaces

Paul C. Kocher. Ataques de sincronización en implementaciones de Diffie-Hellman, RSA, DSS y otros sistemas . CRIPTO 1996: 104-113.
David Brumley, Dan Boneh. Los ataques de sincronización remota son prácticos . Simposio de seguridad de USENIX , agosto de 2003.