Ataque de cumpleaños

Tipo de ataque criptográfico

Un ataque de cumpleaños es un ataque de colisión de fuerza bruta que explota las matemáticas detrás del problema del 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 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 con probabilidad en , ^{[1] [2]} siendo el clásico valor de resistencia de preimagen con la misma probabilidad. ^[2] Existe un resultado general (aunque controvertido ^[3] ) de que las computadoras cuánticas pueden realizar ataques de cumpleaños, rompiendo así la resistencia a las colisiones, en . ^[4] ${\textstyle 50\%}$ ${\textstyle {\sqrt {2^{n}}}=2^{n/2}}$ ${\textstyle 2^{n-1}}$ ${\textstyle {\sqrt[{3}]{2^{n}}}=2^{n/3}}$

Aunque existen algunas vulnerabilidades de firma digital asociadas con el ataque de cumpleaños, no se puede utilizar para romper un esquema de cifrado más rápido que un ataque de fuerza bruta . ^{[5] : 36}

Entendiendo el problema

Comparación del problema de cumpleaños (1) y el ataque de cumpleaños (2):

En (1), las colisiones se encuentran dentro de un conjunto, en este caso, 3 de 276 parejas de 24 astronautas lunares.

En (2), se encuentran colisiones entre dos conjuntos, en este caso, 1 de 256 pares de solo los primeros bytes de hashes SHA-256 de 16 variantes cada uno de contratos benignos y maliciosos.

Como ejemplo, considere el escenario en el que un maestro con una clase de 30 estudiantes (n = 30) pregunta 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 de 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 alrededor del 70% (para n = 30), según la fórmula . ^[6] ${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$

Si el maestro había elegido un día específico (por ejemplo, el 16 de septiembre), entonces la probabilidad de que al menos un estudiante naciera en ese día específico es aproximadamente del 7,9%. ${\displaystyle 1-(364/365)^{30}}$

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, supongamos 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. Después de que la víctima acepta el contrato benigno, el atacante lo sustituye por uno 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 tales que . Un par así se llama colisión. El método utilizado para encontrar una colisión es simplemente evaluar la función para 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 los resultados diferentes con igual probabilidad y es suficientemente grande, entonces esperamos obtener un par de argumentos diferentes y después de evaluar la función para aproximadamente diferentes argumentos en promedio. ${\displaystyle f}$ ${\displaystyle x_{1},x_{2}}$ ${\displaystyle f(x_{1})=f(x_{2})}$ ${\displaystyle x_{1},x_{2}}$ ${\displaystyle f}$ ${\displaystyle f(x)}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle f(x_{1})=f(x_{2})}$ ${\displaystyle 1.25{\sqrt {H}}}$

Consideremos el siguiente experimento. De un conjunto de valores H elegimos n valores uniformemente al azar, permitiendo así 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

${\displaystyle p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}}$^[7]

Sea n ( p ;  H ) el número más pequeño 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

${\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}}$

y asignando una probabilidad de colisión de 0,5 llegamos a

${\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}}$

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

${\displaystyle Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}}$

Por ejemplo, si se utiliza un hash de 64 bits, hay aproximadamente1,8 × 10 ¹⁹ salidas diferentes. Si todos estos son igualmente probables (el mejor de los casos), entonces se necesitarían "sólo" aproximadamente 5 mil millones de intentos (5,38 × 10 ⁹ ) para generar una colisión usando fuerza bruta. ^[8] Este valor se denomina límite de cumpleaños ^[9] y para códigos de n bits podría aproximarse a 2 ^{n /2} . ^[10] Otros ejemplos son los siguientes:

La tabla muestra el número de hashes n ( p ) necesarios para lograr la probabilidad de éxito dada, suponiendo que todos los hashes sean igualmente probables. Para comparacion,10 ⁻¹⁸ a10 ⁻¹⁵ es la tasa de error de bits incorregible de un disco duro típico. ^[11] En teoría, los hashes MD5 o UUID , que tienen aproximadamente 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 generalmente requerirá que se calculen todas las entradas posibles y, por lo tanto, no es factible para las aplicaciones populares. funciones hash como las familias MD y SHA. ^[12] La subexpresión en la ecuación para no se calcula con precisión para pequeño cuando se traduce directamente a lenguajes de programación comunes debido a una pérdida de importancia . Cuando esté disponible (como lo está en C99 ), por ejemplo, se debe utilizar la expresión equivalente . ^[13] Si no se hace esto, 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. ${\displaystyle \ln {\frac {1}{1-p}}}$ ${\displaystyle n(p;H)}$ ${\displaystyle p}$log(1/(1-p))log1p-log1p(-p)

Aproximación simple

Una buena regla general que se puede utilizar para el cálculo mental es la relación

${\displaystyle p(n)\approx {n^{2} \over 2H}}$

que también se puede escribir como

${\displaystyle H\approx {n^{2} \over 2p(n)}}$.

o

${\displaystyle n\approx {\sqrt {2H\times p(n)}}}$.

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, supongamos que está creando hashes de 32 bits ( ) y desea que la probabilidad de una colisión sea como máximo de una entre un millón ( ), ¿cuántos documentos podríamos tener como máximo? ${\displaystyle H=2^{32}}$ ${\displaystyle p\approx 2^{-20}}$

${\displaystyle n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6.5}\approx 90.5}$

que se acerca a la respuesta correcta de 93.

Susceptibilidad a la firma digital

Las firmas digitales pueden ser susceptibles a un ataque de cumpleaños o, más precisamente, a un ataque de colisión de prefijo elegido. Por lo general, un mensaje se firma primero mediante computación , donde hay una función hash criptográfica , y luego usando 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 otro fraudulento . Luego encuentra una serie de posiciones que se pueden cambiar sin cambiar el significado, como insertar comas, líneas vacías, uno versus dos espacios después de una oración, reemplazar sinónimos, etc. Al combinar estos cambios, puede crear una gran cantidad de variaciones. sobre los cuales se basan todos los contratos justos. ${\displaystyle m}$ ${\displaystyle f(m)}$ ${\displaystyle f}$ ${\displaystyle f(m)}$ ${\displaystyle m}$ ${\displaystyle m'}$ ${\displaystyle m}$ ${\displaystyle m}$

De manera similar, Mallory también crea una gran cantidad de variaciones del 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. Después de que Bob haya firmado, Mallory toma la firma y la adjunta al contrato fraudulento. Esta firma "prueba" que Bob firmó el contrato fraudulento. ${\displaystyle m'}$ ${\displaystyle f(m)=f(m')}$

Las probabilidades difieren ligeramente del problema del 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 otro fraudulento. Para una función hash determinada es el número de hashes posibles. Las ecuaciones del problema del cumpleaños no se aplican exactamente aquí, la cantidad de hashes que Mallory realmente genera para una probabilidad es el doble de lo requerido para una colisión simple que corresponde a . ${\displaystyle 2^{n}}$ ${\displaystyle 50\%}$ ${\displaystyle 2^{n/2}\times 2}$ ${\displaystyle 2^{(n/2)+1}}$

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 se vuelva computacionalmente inviable, es decir, aproximadamente el doble de bits de los necesarios para evitar un ataque de fuerza bruta ordinario .

Además de utilizar una longitud de bits mayor, el firmante (Bob) puede protegerse haciendo algunos cambios aleatorios e inofensivos en el documento antes de firmarlo, y conservando una copia del contrato que firmó en su poder, de modo que al menos pueda demostrar ante el tribunal 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 .

Ataque inverso

El mismo fraude es posible si el firmante es Mallory, no Bob. Bob podría sugerirle un contrato a Mallory para que lo firme. Mallory podría encontrar una versión modificada de manera inofensiva de este contrato justo que tenga la misma firma que un contrato fraudulento, y Mallory podría proporcionarle el contrato justo modificado y la firma a Bob. Más tarde, Mallory pudo presentar la copia fraudulenta. Si Bob no tiene la versión inofensiva del contrato modificada (quizás solo haya encontrado su propuesta original), el fraude de Mallory es perfecto. Si Bob lo tiene, Mallory al menos puede afirmar que es Bob el estafador.

Ver también

• Ataque de colisión
• Ataque de encuentro en el medio
• Algoritmo BHT

Notas

1. "Evitar colisiones, funciones hash criptográficas" (PDF) . Fundamentos de criptografía, Departamento de Ciencias de la Computación, Wellesley College .
2. Dang, QH (2012). Recomendación para aplicaciones que utilizan algoritmos hash aprobados (Informe). Gaithersburg, MD: Instituto Nacional de Estándares y Tecnología.
3. Daniel J. Bernstein. "Análisis de costos de las colisiones de hash: ¿las computadoras cuánticas harán que SHARCS quede obsoleto?" (PDF) . Cr.yp.to. ​Consultado el 29 de octubre de 2017 .
4. Brassard, Gilles; Høyer, Peter; Tapp, Alain (20 de abril de 1998). "Criptoanálisis cuántico de funciones hash y sin garras". LATIN'98: Informática Teórica . Apuntes de conferencias sobre informática. vol. 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.
5. R. Shirey (agosto de 2007). Glosario de seguridad de Internet, versión 2. Grupo de trabajo de redes. doi : 10.17487/RFC4949 . RFC 4949. Informativo.
6. "Problema de cumpleaños". Brillante.org . Brillante_(sitio web) . Consultado el 28 de julio de 2023 .
7. Bellare, Mihir; Rogaway, Phillip (2005). "El problema del cumpleaños". Introducción a la criptografía moderna (PDF) . págs. 273–274 . Consultado el 31 de marzo de 2023 .
8. Flajolet, Philippe; Odlyzko, Andrew M. (1990). "Estadísticas de mapeo aleatorio". En Quisquater, Jean-Jacques; Vandewalle, Joos (eds.). Avances en criptología: EUROCRYPT '89 . Apuntes de conferencias sobre informática. vol. 434. Berlín, Heidelberg: Springer. págs. 329–354. doi :10.1007/3-540-46885-4_34. ISBN 978-3-540-46885-1.
9. Ver límites superior e inferior .
10. Jacques Patarin, Audrey Montreuil (2005). «Revisión de los esquemas de Benes y Butterfly» ( PostScript , PDF ) . Universidad de Versalles . Consultado el 15 de marzo de 2007 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
11. Gris, Jim; van Ingen, Catharine (25 de enero de 2007). "Medidas empíricas de tasas de error y fallas de disco". arXiv : cs/0701166 .
12. "CiteSeerX". Archivado desde el original el 23 de febrero de 2008 . Consultado el 2 de mayo de 2006 .
13. "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 la autenticación?" de las preguntas frecuentes sobre criptografía de RSA Security .
• Preguntas frecuentes sobre criptomonedas de X5 Networks sobre el "ataque de cumpleaños"