Ataque de cumpleaños

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de diciembre de 2015; las comprobaciones requieren 67 ediciones .

Un ataque de cumpleaños es un nombre que se usa en el criptoanálisis para un método para descifrar cifrados o encontrar colisiones de funciones hash basadas en la paradoja del cumpleaños . La esencia del método es reducir significativamente el número de argumentos pasados a la función hash, lo cual es necesario para detectar una colisión, ya que si la función hash genera un valor de n bits, entonces el número de argumentos aleatorios de la función hash para los cuales en se detectará al menos una colisión hash con una función de alta probabilidad (es decir, hay al menos un par de códigos hash iguales obtenidos en diferentes argumentos) no es 2 n , sino solo alrededor de 2 n /2 .

Entendiendo el problema

Considere un ejemplo: ¿Dos personas en un grupo de 23 tendrán el mismo cumpleaños? Un año, excluyendo los años bisiestos, tiene 365 días, por lo que hay 365 cumpleaños diferentes, un número mucho mayor que 23.

Si elegimos un día en particular, entonces la probabilidad de que al menos una persona haya nacido ese día en particular sería de alrededor del 6,1%. Sin embargo, la probabilidad de que al menos una persona tenga el mismo cumpleaños que cualquier otra persona es de alrededor del 50%, según la fórmula [1] . Para n = 70 , la probabilidad de tal coincidencia es del 99,9%. ${\ estilo de visualización 1-(364/365)^{23}}$ $1-365!/((365-n)!\cdot 365^{n})$

Matemáticas

Para una función hash dada, el objetivo del ataque es encontrar una colisión del segundo tipo . Para ello, se calculan valores para bloques de datos de entrada seleccionados aleatoriamente hasta encontrar dos bloques que tengan el mismo hash. $h$ $h$

Sea una función hash . El ataque de cumpleaños tiene éxito si hay un par tal que $h$ $x_{1}\neq x_{2}$ $h(x_{1})=h(x_{2}).$

Por lo tanto, si una función da cualquiera de los diferentes resultados con la misma probabilidad y es lo suficientemente grande, entonces la expectativa matemática del número de pares de argumentos diferentes para los cuales es . La estimación del número de operaciones hash para encontrar una colisión de una función hash criptográfica ideal con un tamaño de salida de bits a menudo se escribe como y no [2] . $h(x)$ $norte$ $norte$ $x_{1}\neq x_{2},$ $h(x_{1})=h(x_{2}),$ $1{,}25{\sqrt {N))$ $norte$ ${\ estilo de visualización 2^{n/2},}$ $2^{{n}}$

Sea la probabilidad de que al menos dos personas en un grupo de personas ( ) tengan el mismo cumpleaños. $P(n)$ $norte$ ${\ estilo de visualización n<N=365}$

P(n)

1-1\cdot \left(1-{\frac {1}{N}}\right)\cdot \left(1-{\frac {2}{N}}\right)\cdot .. .\cdot \left(1-{\frac {n-1}{N}}\right)=1-\prod _{i=0}^{n-1}\ \left(1-{\frac { en la derecha).

De los dos primeros términos de la expansión en la serie de Taylor de la función para , $\displaystyle e^{x}=1+{\dfrac {x}{1!}}+{\dfrac {x^{2}}{2!}}+{\dfrac {x^{3} {3!}}+\cpuntos,$ ${\ estilo de visualización | x | \ ll 1}$ $e^{x}\aprox. 1+x.$ $\left(1-{\frac {i}{N))\right)$ ${e}^{-i/N},$

P(n)\approx 1-\prod_{i=0}^{n-1}\ {e}^{-i/N}=1-\exp \sum_{i=0}^ {n-1}(-i/N)=1-{e}^{-n(n-1)/2N}\aprox. 1-{e}^{-{\frac {n^{2}}{ 2N}}}.

Encontremos un número tal que $norte$ $P(n)\geq {\frac {1}{2)).$

{\frac {1}{2}}\geq {e}^{-{\frac {n^{2}}{2N}}}.

Como consecuencia,

n\geq {\sqrt {2\ln 2\cdot N}}\aprox. 1,177{\sqrt {N}}\aprox. 23

[1] .

Por ejemplo, si se usa un hash de 64 bits, hay aproximadamente 1,8 × 10 19 salidas diferentes. Si todos son igualmente probables (en el mejor de los casos), entonces se necesitarían "solo" alrededor de 5 mil millones de intentos ( 5.38 × 109 ) para crear una colisión usando la fuerza bruta . Otros ejemplos:

pedacitos	Salidas posibles (N)	Probabilidad de colisión aleatoria deseada (P)
pedacitos	Salidas posibles (N)	10 −18	10 −15	10 −12	10 −9	10 −6	0,1%	una %	25%	cincuenta %	75%
dieciséis	2 16 (~6,5 x 10 3 )	<2	<2	<2	<2	<2	once	36	190	300	430
32	2 32 (~4,3 × 10 9 )	<2	<2	<2	3	93	2900	9300	50,000	77 000	110 000
64	2 64 (~1,8 × 10 19 )	6	190	6100	190 000	6,100,000	1,9 × 108	6,1 × 108	3,3 × 109	5,1x109 _	7,2 × 109
128	2128 (~ 3,4 × 1038 )	2,6 × 10 10	8,2 × 10 11	2,6 × 10 13	8,2 × 10 14	2,6 × 10 16	8,3 × 10 17	2,6 × 10 18	1,4 × 10 19	2,2 × 10 19	3,1 × 10 19
256	2256 ( ~ 1,2 × 10 77 )	4,8 × 10 29	1,5 × 10 31	4,8 × 10 32	1.5×10 34	4,8 × 10 35	1,5 × 10 37	4,8 × 10 37	2,6 × 10 38	4.0 × 10 38	5,7 × 10 38
384	2384 (~3,9 × 10115 )	8,9 × 10 48	2,8 × 10 50	8,9 × 1051	2,8 × 1053	8,9 × 1054	2,8 × 1056	8,9 × 1056	4,8 × 1057	7,4 × 1057	1.0 × 10 58
512	2512 (~1,3 × 10154 )	1.6×10 68	5,2 × 10 69	1,6 × 10 71	5,2 × 1072	1,6 × 1074	5,2 × 1075	1,6 × 10 76	8,8 × 1076	1,4 × 10 77	1,9 × 10 77

La tabla muestra el número de hashes necesarios para lograr una determinada probabilidad de éxito, suponiendo que todos los hashes tienen la misma probabilidad. En comparación,

{\ estilo de visualización n (P),}

10 −18 a 10 −15 es la tasa de error de bit incorregible de un disco duro típico [3] . Teóricamente, los hashes MD5 o un UUID de 128 bits deberían permanecer dentro de este rango hasta unos 820 mil millones de documentos, incluso si sus posibles resultados son mucho mayores.

Es fácil ver que si las salidas de una función están distribuidas de manera desigual, las colisiones se pueden encontrar aún más rápido. El concepto de "equilibrio" de una función hash cuantifica la resistencia de la función a un ataque de "cumpleaños" (utilizando una distribución de claves no uniforme). Sin embargo, determinar el equilibrio de una función hash requiere calcular todas las entradas posibles y, por lo tanto, no es factible para las funciones hash populares, como las familias MD y SHA.

Sensibilidad de la firma digital

Una firma digital electrónica , por ejemplo, puede ser vulnerable a este ataque . Digamos que 2 personas, A y B, quieren firmar un contrato, pero A quiere pasarle a B una versión falsa del contrato. Entonces A redacta un contrato genuino y un contrato falso. Además, al realizar cambios válidos que no modifican el significado del texto (disposición de comas, guiones, sangrías), A logra que ambos contratos tengan el mismo hash. Después de eso, A envía a B un contrato genuino, B lo firma y su firma también muestra que también firmó un contrato falso, ya que ambos contratos tienen el mismo hash. Para evitar este tipo de vulnerabilidad, basta con aumentar la longitud del hash para que sea computacionalmente difícil encontrar 2 contratos con los mismos hash. En particular, se requiere el doble de la longitud del hash para proporcionar una complejidad computacional comparable a la de la búsqueda por fuerza bruta. En otras palabras, si un atacante puede calcular valores de hash utilizando la fuerza bruta , comenzará a encontrar colisiones de hash para todos los hash de menos de un poco de longitud. (ver en:Ataque de cumpleaños ) $2^{n}$ $2n$

Para evitar este ataque, la longitud de salida de la función hash utilizada para el esquema de firma se puede elegir lo suficientemente grande como para hacer que el ataque de "cumpleaños" sea computacionalmente inviable, es decir, aproximadamente el doble de bits que los necesarios para evitar un ataque convencional de "fuerza bruta". (enumeración completa) .

Ataque de cumpleaños BIND

DNS es un sistema informático distribuido para obtener información sobre . Se usa más comúnmente para obtener una dirección IP del nombre del host (computadora o dispositivo).

El término "recursión" en DNS se refiere al comportamiento del servidor DNS, en el que el servidor realiza en nombre del cliente una búsqueda completa de la información necesaria en todo el sistema DNS, si es necesario, refiriéndose a otros servidores DNS. En el caso de una consulta "recursiva", el servidor DNS sondea los servidores (en orden descendente del nivel de zona en el nombre) hasta que encuentra una respuesta o descubre que el dominio no existe (en la práctica, la búsqueda comienza desde el servidores DNS más cercanos al deseado, si la información se almacena en caché y está actualizada, es posible que el servidor no consulte a otros servidores DNS).

En 2002, Wagner de Sacramento publicó una recomendación que mostraba un problema con la implementación del protocolo DNS por parte de BIND. Descubrió que BIND estaba enviando múltiples solicitudes recursivas simultáneas para la misma dirección IP.

El atacante envía una consulta al servidor DNS de la víctima. Elige un nombre de dominio que el servidor DNS A no puede encontrar en su caché y se ve obligado a reenviarlo al siguiente servidor DNS B. Cada intercambio de permisos entre A y B se autentica a través de un TID aleatorio. Antes de que el Servidor DNS A pueda recibir paquetes de respuesta del Servidor DNS B, el atacante envía N paquetes de respuesta falsos al Servidor DNS A. Si uno de estos paquetes falsos tiene el mismo TID que el TID del Servidor DNS A, el servidor aceptará los paquetes falsos. A como paquetes válidos. La respuesta real del Servidor DNS B no será procesada por el Servidor DNS A. Por lo tanto, un atacante puede "envenenar" la memoria caché del Servidor DNS A para asignar el dominio comprometido a la dirección IP proporcionada por el atacante.

En un ataque normal, el atacante envía N respuestas falsas para una solicitud, la probabilidad de éxito es (TID - número de 16 bits). ${\frac{N}{65535}}$

El ataque de cumpleaños facilita romper el protocolo BIND. El atacante envía una gran cantidad de N consultas al servidor DNS de la víctima, todas con el mismo nombre de dominio. Enviamos N respuestas falsas para N solicitudes. Por lo tanto, la probabilidad de que el ataque tenga éxito es [4]

P(n)=1-{e}^{-{\frac {n^{2}}{2N}}}.

Aproximación simple

Una buena regla general que se puede usar para una evaluación mental rápida es la proporción

P(n)\approx {n^{2} \over 2N},

que también se puede escribir como

{\displaystyle N\aprox. {n^{2} \sobre 2P(n)))

n\approx {\sqrt {2N\veces P(n))).

Esta aproximación funciona bien para probabilidades menores o iguales a 0,5.

Este esquema de aproximación es especialmente fácil de usar cuando se trabaja con indicadores. Por ejemplo, calculemos cuántos documentos pueden ser procesados por una función hash de 32 bits ( ) para que la probabilidad de una colisión no sea mayor a uno en un millón ( ). Una estimación del mayor número posible de documentos para tales condiciones es ${\ estilo de visualización N = 2 ^ {32}}$ $P=10^{-6}\aproximadamente 2^{-20}$

n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2 ^{13}}}=2^{6{,}5}\aproximadamente 90{,}5,

que está cerca de la respuesta correcta 93.

Ejemplos

Suponga que para atacar un cifrado de bloque de 64 bits, un atacante necesita obtener dos pares de texto sin formato/texto cifrado que difieran solo en el bit menos significativo. La interpretación de este problema en términos de la paradoja del cumpleaños lleva a la conclusión de que el espacio de solo textos claros conocidos contendrá el par requerido con una alta probabilidad [5] . $2^{32}$

Como otro ejemplo, considere el ciclo de un cifrado Feistel de 64 bits . Suponga que el cifrado utiliza una función aleatoria F (32 a 32 bits). Un atacante podría querer saber cuántos textos sin formato necesita obtener para obtener una colisión de la función F . Según la paradoja del cumpleaños, para ello hay que sortear textos abiertos [5] . $2^{16}$

Una consecuencia de la paradoja del cumpleaños es que para un cifrado de bloque de n bits, se pueden esperar ocurrencias repetidas de un bloque de texto cifrado con una probabilidad de aproximadamente 0,63 dados solo textos sin formato aleatorios cifrados en la misma clave (independientemente del tamaño de la clave). Para el modo ECB, si dos bloques de texto cifrado coinciden, los textos sin formato correspondientes también deben coincidir. Esto significa que en un ataque de texto cifrado conocido, la información sobre los textos sin formato puede revelarse a partir de los bloques de texto cifrado. $2^{{n/2}}$

Notas

↑ 1 2 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introducción a los algoritmos, tercera edición, p. 130-133
↑ Bukhantsov A. D., Druzhkova I. V. Sobre la modificación del algoritmo MD5 // Belgorod State National Research University, 2016, p. 176.
↑ Gray, Jim & van Ingen, Catharine (25 de enero de 2007), Mediciones empíricas de tasas de fallas de disco y tasas de error, arΧiv : cs/0701166 .
↑ Joe Stewart , Envenenamiento de caché de DNS, p. 4-5.
↑ 1 2 Babenko L. K., Ischukova E. A. , Análisis de criptosistemas simétricos, p. 146.

Literatura

Mihir Bellare, Tadayoshi Kohno : Equilibrio de la función hash y su impacto en los ataques de cumpleaños. EUROCRIPTA 2004: pp401-418
Don Coppersmith : Otro ataque de cumpleaños, Procediendo a CRYPTO '85 Avances en criptología p. 14-17