Un ataque de cumpleaños es un tipo de ataque criptográfico que explota las matemáticas detrás del problema de cumpleaños en la teoría de la probabilidad . Este ataque se puede utilizar para abusar de la comunicación entre dos o más partes. El ataque depende de la mayor probabilidad de colisiones encontradas entre los intentos de ataque aleatorios y un grado fijo de permutaciones ( casilleros ). Con un ataque de cumpleaños, es posible encontrar una colisión de una función hash en, con siendo la seguridad de resistencia clásica de preimagen . Hay un resultado general (aunque discutido [1] ) de que las computadoras cuánticas pueden realizar ataques de cumpleaños, rompiendo así la resistencia a las colisiones, en. [2]
Entendiendo el problema
Como ejemplo, considere el escenario en el que un maestro con una clase de 30 estudiantes (n = 30) pide el cumpleaños de todos (para simplificar, ignore los años bisiestos ) para determinar si dos estudiantes tienen el mismo cumpleaños (correspondiente a una colisión hash como se describe más adelante). Intuitivamente, esta posibilidad puede parecer pequeña. Contrariamente a la intuición, la probabilidad de que al menos un estudiante tenga el mismo cumpleaños que cualquier otro estudiante en cualquier día es de alrededor del 70% (para n = 30), de la fórmula. [3]
Si el maestro había elegido un día específico (digamos, 16 de septiembre), entonces la probabilidad de que al menos un estudiante haya nacido en ese día específico es, alrededor del 7,9%.
En un ataque de cumpleaños, el atacante prepara muchas variantes diferentes de contratos benignos y maliciosos, cada uno con una firma digital . Se busca un par de contratos benignos y maliciosos con la misma firma. En este ejemplo ficticio, suponga que la firma digital de una cadena es el primer byte de su hash SHA-256 . El par encontrado se indica en verde; tenga en cuenta que encontrar un par de contratos benignos (azul) o un par de contratos maliciosos (rojo) es inútil. Una vez que la víctima acepta el contrato benigno, el atacante lo sustituye por el malicioso y afirma que la víctima lo firmó, como lo demuestra la firma digital.
Matemáticas
Dada una función , el objetivo del ataque es encontrar dos entradas diferentes tal que . Tal parse llama colisión. El método utilizado para encontrar una colisión es simplemente evaluar la funciónpara diferentes valores de entrada que pueden elegirse aleatoriamente o pseudoaleatoriamente hasta que se encuentre el mismo resultado más de una vez. Debido al problema del cumpleaños, este método puede resultar bastante eficaz. Específicamente, si una función produce cualquiera de diferentes salidas con igual probabilidad y es suficientemente grande, entonces esperamos obtener un par de argumentos diferentes y con después de evaluar la función durante aproximadamente diferentes argumentos en promedio.
Consideramos el siguiente experimento. De un conjunto de valores H , elegimos n valores uniformemente al azar, lo que permite repeticiones. Sea p ( n ; H ) la probabilidad de que durante este experimento se elija al menos un valor más de una vez. Esta probabilidad se puede aproximar como
Sea n ( p ; H ) el menor número de valores que tenemos que elegir, de modo que la probabilidad de encontrar una colisión sea al menos p . Al invertir esta expresión anterior, encontramos la siguiente aproximación
y asignando una probabilidad de colisión de 0.5 llegamos a
Sea Q ( H ) el número esperado de valores que tenemos que elegir antes de encontrar la primera colisión. Este número se puede aproximar mediante
Por ejemplo, si se utiliza un hash de 64 bits, hay aproximadamente 1,8 × 10 19 salidas diferentes. Si todos estos son igualmente probables (el mejor de los casos), entonces se necesitarían 'solo' aproximadamente 5 mil millones de intentos (5.38 × 10 9 ) para generar una colisión usando la fuerza bruta. [5] Este valor se denomina límite de cumpleaños [6] y para códigos de n bits podría calcularse como 2 n / 2 . [7] Otros ejemplos son los siguientes:
Bits Posibles salidas (H) Probabilidad deseada de colisión aleatoria
(2 sf) (p)10 −18 10 -15 10 -12 10 −9 10 −6 0,1% 1% 25% 50% 75% dieciséis 2 16 (~ 6,5 x 10 4 ) <2 <2 <2 <2 <2 11 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 × 10 8 6,1 × 10 8 3,3 × 10 9 5,1 × 10 9 7,2 × 10 9 128 2 128 (~ 3,4 × 10 38 ) 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 2 256 (~ 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 2 384 (~ 3,9 × 10 115 ) 8,9 × 10 48 2,8 × 10 50 8,9 × 10 51 2,8 × 10 53 8,9 × 10 54 2,8 × 10 56 8,9 × 10 56 4,8 × 10 57 7,4 × 10 57 1,0 × 10 58 512 2 512 (~ 1,3 × 10 154 ) 1,6 × 10 68 5,2 × 10 69 1,6 × 10 71 5,2 × 10 72 1,6 × 10 74 5,2 × 10 75 1,6 × 10 76 8,8 × 10 76 1,4 × 10 77 1,9 × 10 77
- La tabla muestra el número de hashes n ( p ) necesarios para lograr la probabilidad de éxito dada, asumiendo que todos los hashes son igualmente probables. A modo de comparación, 10 −18 a 10 −15 es la tasa de error de bits incorregible de un disco duro típico. [8] En teoría, los hash MD5 o UUID , que son de 128 bits, deberían permanecer dentro de ese rango hasta aproximadamente 820 mil millones de documentos, incluso si sus posibles resultados son muchos más.
Es fácil ver que si las salidas de la función se distribuyen de manera desigual, entonces se podría encontrar una colisión aún más rápido. La noción de 'equilibrio' de una función hash cuantifica la resistencia de la función a los ataques de cumpleaños (aprovechando la distribución desigual de claves). Sin embargo, determinar el equilibrio de una función hash normalmente requerirá que se calculen todas las entradas posibles y por lo tanto no es factible funciones hash como las familias MD y SHA. [9] La subexpresión en la ecuación para no se calcula con precisión para pequeños cuando se traduce directamente a lenguajes de programación comunes log(1/(1-p))
debido a la pérdida de importancia . Cuando log1p
esté disponible (como en C99 ), por ejemplo, se -log1p(-p)
debe usar la expresión equivalente en su lugar. [10] Si esto no se hace, la primera columna de la tabla anterior se calcula como cero y varios elementos de la segunda columna no tienen ni siquiera un dígito significativo correcto.
Aproximación simple
Una buena regla empírica que se puede utilizar para el cálculo mental es la relación
que también se puede escribir como
- .
o
- .
Esto 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 exponentes. Por ejemplo, suponga que está creando hashes de 32 bits () y desea que la probabilidad de una colisión sea como máximo de una en un millón (), ¿cuántos documentos podríamos tener como máximo?
que está cerca de la respuesta correcta de 93.
Susceptibilidad de firma digital
Las firmas digitales pueden ser susceptibles a un ataque de cumpleaños. Un mensaje típicamente está firmado por primera computación , dónde es una función hash criptográfica , y luego usa alguna clave secreta para firmar. Supongamos que Mallory quiere engañar a Bob para que firme un contrato fraudulento . Mallory prepara un contrato justo y una fraudulenta . Luego encuentra una serie de posiciones donde se puede cambiar sin cambiar el significado, como insertar comas, líneas vacías, uno o dos espacios después de una oración, reemplazar sinónimos, etc. Al combinar estos cambios, puede crear una gran cantidad de variaciones en que son todos contratos justos.
De manera similar, Mallory también crea una gran cantidad de variaciones en el contrato fraudulento. . Luego aplica la función hash a todas estas variaciones hasta que encuentra una versión del contrato justo y una versión del contrato fraudulento que tienen el mismo valor hash.. Ella le presenta la versión justa a Bob para que la firme. Una vez que Bob ha firmado, Mallory toma la firma y la adjunta al contrato fraudulento. Esta firma luego "prueba" que Bob firmó el contrato fraudulento.
Las probabilidades difieren ligeramente del problema de cumpleaños original, ya que Mallory no gana nada al encontrar dos contratos justos o dos fraudulentos con el mismo hash. La estrategia de Mallory es generar pares de un contrato justo y uno fraudulento. Las ecuaciones del problema de cumpleaños se aplican dondees el número de pares. El número de hashes que Mallory genera realmente es.
Para evitar este ataque, la longitud de salida de la función hash utilizada para un esquema de firma se puede elegir lo suficientemente grande como para que el ataque de cumpleaños sea computacionalmente inviable, es decir, aproximadamente el doble de bits de los necesarios para prevenir un ataque ordinario de fuerza bruta .
Además de utilizar una longitud de bits más grande, el firmante (Bob) puede protegerse haciendo algunos cambios aleatorios e inofensivos en el documento antes de firmarlo, y manteniendo una copia del contrato que firmó en su poder, para que al menos pueda demostrar en la corte que su firma coincide con ese contrato, no solo con el fraudulento.
El algoritmo rho de Pollard para logaritmos es un ejemplo de un algoritmo que utiliza un ataque de cumpleaños para el cálculo de logaritmos discretos .
Ver también
Notas
- ^ Daniel J. Bernstein. "Análisis de costes de las colisiones hash: ¿las computadoras cuánticas harán que SHARCS sea obsoleto?" (PDF) . Cr.yp.to . Consultado el 29 de octubre de 2017 .
- ^ Brassard, Gilles; HØyer, Peter; Tapp, Alain (20 de abril de 1998). LATIN'98: Informática Teórica . Apuntes de conferencias en Ciencias de la Computación. 1380 . Springer, Berlín, Heidelberg. págs. 163-169. arXiv : quant-ph / 9705002 . doi : 10.1007 / BFb0054319 . ISBN 978-3-540-64275-6. S2CID 118940551 .
- ^ "Foro de matemáticas: Pregunte al Dr. Math FAQ: El problema del cumpleaños" . Mathforum.org . Consultado el 29 de octubre de 2017 .
- ^ Gupta, Ganesh (2015). "¿Qué es el ataque de cumpleaños?" . doi : 10.13140 / 2.1.4915.7443 . Cite journal requiere
|journal=
( ayuda ) - ^ Flajolet, Philippe; Odlyzko, Andrew M. (1990). Quisquater, Jean-Jacques; Vandewalle, Joos (eds.). "Estadísticas de mapeo aleatorio" . Avances en Criptología - EUROCRYPT '89 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 434 : 329–354. doi : 10.1007 / 3-540-46885-4_34 . ISBN 978-3-540-46885-1.
- ^ Consulte los límites superior e inferior .
- ^ Jacques Patarin, Audrey Montreuil (2005). "Esquemas de Benes y Butterfly revisitados" ( PostScript , PDF ) . Université de Versailles . Consultado el 15 de marzo de 2007 . Cite journal requiere
|journal=
( ayuda ) - ^ Gray, Jim; van Ingen, Catharine (25 de enero de 2007). "Medidas empíricas de las tasas de falla y error de disco". arXiv : cs / 0701166 .
- ^ "CiteSeerX" . Archivado desde el original el 23 de febrero de 2008 . Consultado el 2 de mayo de 2006 .
- ^ "Calcule log (1 + x) con precisión para valores pequeños de x" . Mathworks.com . Consultado el 29 de octubre de 2017 .
Referencias
- Mihir Bellare , Tadayoshi Kohno: Equilibrio de la función hash y su impacto en los ataques de cumpleaños. EUROCRYPT 2004: págs. 401–418
- Criptografía aplicada, 2ª ed. por Bruce Schneier
enlaces externos
- "¿Qué es una firma digital y qué es autenticación?" de las preguntas frecuentes sobre criptografía de RSA Security .
- Preguntas frecuentes sobre criptografía de "Birthday Attack" X5 Networks