Ataque de cumpleaños

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 los intentos de ataque aleatorios y un grado fijo de permutaciones ( casillas ). Sea el número de valores posibles de una función hash, con . Con un ataque de cumpleaños, es posible encontrar una colisión de una función hash con la casualidad en donde es la longitud de bits de la salida hash, ^[1]^[2] y con siendo la seguridad de resistencia de preimagen clásica 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 la colisión, en . ^[4] ${\textstyle H}$ ${\textstyle H=2^{l}}$ ${\textstyle 50\%}$ ${\estilo de texto {\sqrt {2^{l}}}=2^{l/2},}$ ${\textstyle l}$ ${\textstyle 2^{l-1}}$ ${\estilo de texto {\sqrt[{3}]{2^{l}}}=2^{l/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

Como ejemplo, considere el escenario en el que un profesor con una clase de 30 estudiantes (n = 30) pregunta por el cumpleaños de todos (para simplificar, ignore los años bisiestos ) para determinar si dos estudiantes tienen el mismo cumpleaños (que corresponde a una colisión hash como se describe más adelante). Intuitivamente, esta probabilidad puede parecer pequeña. Contra-intuitivamente, 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), a partir de la fórmula . ^[6] $1-{\frac {365!}{(365-n)!\cdot 365^{n}}}$

Si el profesor hubiera elegido un día específico (digamos, el 16 de septiembre), entonces la probabilidad de que al menos un estudiante naciera ese día específico es de aproximadamente 7,9%. $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 el malicioso y afirma que la víctima lo firmó, como lo demuestra la firma digital.

Terminología

En el contexto del ataque de cumpleaños, las variables clave están relacionadas con el conocido problema de las bolas y los contenedores en la teoría de la probabilidad, de la siguiente manera.

norte: Número de entradas (o bolas)

La variable n representa el número de entradas (o intentos) que se realizan. En la analogía del problema de las bolas y los recipientes, n se refiere al número de bolas que se lanzan aleatoriamente en H recipientes. Cada entrada corresponde al lanzamiento de una bola en uno de los recipientes (valores hash).

yo: Número de valores hash (o contenedores)

La variable H representa el número total de posibles salidas de la función hash. Este es el número de "contenedores" únicos en los que pueden caer las bolas. El número total de salidas hash se expresa a menudo como , donde l es la longitud en bits de la salida hash. En la analogía de bolas y contenedores, H representa el número de contenedores, cada uno correspondiente a un valor hash único. $H=2^{l}$

yo:Longitud en bits de la salida de la función hash

La variable l se refiere a la longitud en bits de la salida de la función hash. Dado que una función hash de longitud en bits l puede producir salidas únicas, la cantidad de valores hash posibles (o bins) es . ${\estilo de visualización 2^{l}}$ $H=2^{l}$

pag:Probabilidad de colisión

La variable p representa la probabilidad de que se produzca una colisión, es decir, la probabilidad de que a dos o más entradas (bolas) se les asigne la misma salida (contenedor). En un ataque de cumpleaños, p se suele establecer en 0,5 (50 %) para estimar cuántas entradas se necesitan para tener una probabilidad del 50 % de que se produzca una colisión.

Resumen de la relación con el problema de las bolas y los contenedores

El ataque de cumpleaños se puede modelar como una variación del problema de las pelotas y los contenedores . En este problema:

Las bolas representan entradas a la función hash.
Los contenedores representan posibles salidas de la función hash (valores hash).
Una colisión ocurre cuando dos o más bolas caen en el mismo contenedor (es decir, dos entradas producen la misma salida hash).

Matemáticas

Dada una función , el objetivo del ataque es encontrar dos entradas diferentes tales que . Este par 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 ser bastante eficiente. Específicamente, si una función produce cualquiera de las 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 para aproximadamente diferentes argumentos en promedio. ${\estilo de visualización f}$ $Estilo de visualización x_{1},x_{2}$ $f(x_{1})=f(x_{2})$ $Estilo de visualización x_{1},x_{2}$ ${\estilo de visualización f}$ ${\estilo de visualización f(x)}$ ${\estilo de visualización H}$ ${\estilo de visualización H}$ $estilo de visualización x_{1}}$ $estilo de visualización x_{2}}$ $f(x_{1})=f(x_{2})$ $1.25{\sqrt {H}}$

Consideremos el siguiente experimento. De un conjunto de valores H, elegimos n valores de manera uniforme y aleatoria, 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

p(n;H)\aproximadamente 1-e^{-n(n-1)/(2H)}\aproximadamente 1-e^{-n^{2}/(2H)}

^[7]

donde es el número de valores elegidos (entradas) y es el número de resultados posibles (posibles salidas hash). ${\estilo de visualización n}$ ${\estilo de visualización H}$

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, obtenemos la siguiente aproximación

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

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

n(0,5;H)\aproximadamente 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

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

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

La tabla muestra la cantidad de hashes n ( p ) necesarios para lograr la probabilidad de éxito dada, suponiendo que todos los hashes tienen la misma probabilidad. A modo de comparación,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 , al tener aproximadamente 128 bits, deberían permanecer dentro de ese rango hasta aproximadamente 820 mil millones de documentos, incluso si sus posibles salidas son muchas más.

Es fácil ver que si las salidas de la función se distribuyen de forma desigual, entonces se podría encontrar una colisión incluso 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 (explotando la distribución desigual de la clave). 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 para las funciones hash populares, como las familias MD y SHA. ^[12] La subexpresión en la ecuación para no se calcula con precisión para small cuando se traduce directamente a lenguajes de programación comunes debido a la pérdida de significancia . Cuando está disponible (como en C99 ), por ejemplo, se debe utilizar la expresión equivalente en su lugar. ^[13] Si esto no se hace, la primera columna de la tabla anterior se calcula como cero, y varios elementos en la segunda columna no tienen ni un dígito significativo correcto. $\ln {\frac {1}{1-p}}$ $n(p;H)$ ${\estilo de visualización 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

p(n)\approx {n^{2} \sobre 2H}

que también se puede escribir como

H\approx {n^{2} \sobre 2p(n)}

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 estamos creando hashes de 32 bits ( ) y queremos 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? $Estilo de visualización H=2^{32}}$ $p\aprox 2^{-20}$

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 está cerca de la respuesta correcta de 93.

Pruebas

El ataque de cumpleaños es un método que aprovecha las matemáticas de las colisiones en las funciones hash. A continuación, proporcionamos límites superiores e inferiores para la probabilidad de una colisión, basados en la analogía del problema de las bolas y los contenedores, y derivamos ecuaciones clave.

Ataque de cumpleaños - Límite superior

El ataque de cumpleaños se puede modelar como el lanzamiento de n bolas (entradas) en H contenedores (posibles salidas hash). La probabilidad de una colisión está limitada por la siguiente ecuación:

$p\leq {\frac {n^{2}}{2H}}$

Esta ecuación se deduce del límite de unión, que proporciona un límite superior para la probabilidad de que se produzca al menos una colisión. Denotamos el evento de que la bola i-ésima colisione con una de las bolas anteriores como . La probabilidad de una colisión para la bola i-ésima es: $C_{i}$

$\Pr[C_{i}]\leq {\frac {i-1}{H}}$

Por lo tanto, la probabilidad total de una colisión después de lanzar las n bolas está limitada por:

$p=\Pr[C_{1}\cup C_{2}\cup \cdots \cup C_{n}]\leq {\frac {0}{H}}+{\frac {1}{H}}+\cdots +{\frac {n-1}{H}}={\frac {n(n-1)}{2H}}$

Esto proporciona el límite superior para la probabilidad de una colisión en una función hash.

Ataque de cumpleaños - Límite inferior

El límite inferior de la probabilidad de una colisión se puede derivar suponiendo que no hay colisión después de lanzar i bolas, que deben ocupar todas ellas casillas diferentes. La probabilidad de que no haya colisión después de lanzar la (i+1)-ésima bola es:

$\Pr[D_{i+1}|D_{i}]={\frac {H-i}{H}}=1-{\frac {i}{H}}$

La probabilidad total de que no haya colisión después de lanzar las n bolas es el producto de estos términos:

$\Pr[D_{n}]=\prod _{i=1}^{n-1}\left(1-{\frac {i}{H}}\right)$

Usando la desigualdad , podemos aproximar esto como: $1-x\leq e^{-x}$

$\Pr[D_{n}]\leq \prod _{i=1}^{n-1}e^{-{\frac {i}{H}}}=e^{-{\frac {n(n-1)}{2H}}}$

Por lo tanto, la probabilidad de al menos una colisión está limitada a continuación por:

$p\geq 1-e^{-{\frac {n(n-1)}{2H}}}$

Esto proporciona el límite inferior para la probabilidad de una colisión.

Ataque de cumpleaños y problema de pelotas y contenedores

Del argumento anterior se desprende que la probabilidad de al menos una colisión está limitada entre:

${\frac {n(n-1)}{4H}}\leq p\leq {\frac {n^{2}}{2H}}$

Sea , se produce una colisión casi segura cuando el número de ensayos, n , viene dado por: $p\approx 1$

$n=\Theta ({\sqrt {H}})=\Theta (2^{l/2})$

Esto ilustra cómo el número de entradas necesarias para una colisión crece en función de la longitud de bits de la salida hash.

Susceptibilidad de 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. Normalmente, un mensaje se firma calculando primero , donde es una función hash criptográfica y, a continuación, utilizando una clave secreta para firmar . Supongamos que Mallory quiere engañar a Bob para que firme un contrato fraudulento . Mallory prepara un contrato justo y uno fraudulento . A continuación, encuentra una serie de posiciones en las que 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 los cuales son todos contratos justos. $m$ $f(m)$ $f$ $f(m)$ $m$ $m'$ $m$ $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. 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 entonces "prueba" que Bob firmó el contrato fraudulento. $m'$ $f(m)=f(m')$

Las probabilidades difieren ligeramente del problema original del cumpleaños, 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. Para una función hash dada es el número de hashes posibles, donde es la longitud en bits de la salida del hash. Las ecuaciones del problema del cumpleaños no se aplican exactamente aquí. Para una probabilidad del 50% de una colisión, Mallory necesitaría generar aproximadamente hashes, que es el doble del número requerido para una colisión simple bajo el problema clásico del cumpleaños. $2^{l}$ $l$ $2^{(l/2)+1}$

Para evitar este ataque, la longitud de salida de la función hash utilizada para un esquema de firma puede elegirse lo suficientemente grande como para que el ataque de cumpleaños se vuelva computacionalmente inviable, es decir, aproximadamente el doble de bits de los que se necesitan para prevenir 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 al documento antes de firmarlo, y conservando una copia del contrato que firmó en su poder, de modo que al menos pueda demostrar en 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 a Mallory un contrato para que lo firme. Mallory podría encontrar una versión inofensivamente modificada de este contrato justo que tenga la misma firma que un contrato fraudulento, y Mallory podría proporcionar el contrato justo modificado y la firma a Bob. Más tarde, Mallory podría presentar la copia fraudulenta. Si Bob no tiene la versión inofensivamente modificada del contrato (quizás solo encuentre su propuesta original), el fraude de Mallory es perfecto. Si Bob la tiene, Mallory al menos puede afirmar que es Bob el estafador.

A continuación se ofrecen detalles adicionales:

1. Propuesta de contrato original: Bob le propone a Mallory un contrato justo, esperando que ella lo firme.

2. Los contratos modificados y fraudulentos de Mallory: en lugar de firmar directamente el contrato de Bob, Mallory crea dos versiones del contrato.

Una es una versión ligeramente modificada del contrato de Bob que parece inofensiva o "inofensiva" para Bob.

El otro es un contrato fraudulento que beneficia a Mallory, pero fundamentalmente, tiene la misma firma digital que la versión modificada.

3. Mallory entrega el contrato modificado: Mallory firma la versión modificada y se la entrega a Bob. La firma de esta versión es la misma que aparecería en el contrato fraudulento.

4. El riesgo de Bob: Si Bob no conserva una copia de la versión modificada que firmó Mallory, sino que sólo conserva la propuesta original, no tendrá pruebas de lo que Mallory aceptó. Más tarde, Mallory puede presentar el contrato fraudulento (que lleva la misma firma) y afirmar que fue el que se firmó.

5. Resultados:

Si Bob carece de la versión modificada, el contrato fraudulento de Mallory es indistinguible del documento firmado, lo que permite un fraude perfecto.
Si Bob conserva la versión modificada, Mallory aún podría afirmar que Bob cambió los contratos, creando dudas sobre quién es responsable del fraude.

Véase también

Notas

^ "Cómo evitar colisiones, funciones hash criptográficas" (PDF) . Fundamentos de criptografía, Departamento de Ciencias de la Computación, Wellesley College .
^ ab Dang, QH (2012). Recomendación para aplicaciones que utilizan algoritmos hash aprobados (informe). Gaithersburg, MD: Instituto Nacional de Estándares y Tecnología.
^ Daniel J. Bernstein. "Análisis de costos de colisiones de hash: ¿Las computadoras cuánticas harán que SHARCS quede obsoleto?" (PDF) . Cr.yp.to . Consultado el 29 de octubre de 2017 .
^ Brassard, Gilles; HØyer, Peter; Tapp, Alain (20 de abril de 1998). "Criptoanálisis cuántico de funciones hash y claw-free". LATIN'98: Informática teórica . Apuntes de clase en 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.S2CID118940551 .
^ R. Shirey (agosto de 2007). Glosario de seguridad en Internet, versión 2. Grupo de trabajo de redes. doi : 10.17487/RFC4949 . RFC 4949. Informativo.
^ "Problema de cumpleaños". Brilliant.org . Brilliant_(sitio web) . Consultado el 28 de julio de 2023 .
^ 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 .
^ 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.
^ Ver límites superior e inferior .
^ Jacques Patarin, Audrey Montreuil (2005). "Los esquemas de Benes y Butterfly revisitados" ( PostScript , PDF ) . Universidad de Versalles . Consultado el 15 de marzo de 2007 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
^ Gray, Jim; van Ingen, Catharine (25 de enero de 2007). "Medidas empíricas de tasas de errores y fallos de discos". arXiv : cs/0701166 .
^ "CiteSeerX". Archivado desde el original el 23 de febrero de 2008. Consultado el 2 de mayo de 2006 .
^ "Calcular 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: Balance de funciones hash y su impacto en los ataques de cumpleaños. EUROCRYPT 2004: pp401–418
Criptografía aplicada, 2.ª edición, de 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: "Ataque de cumpleaños"