ataque de cumpleaños

Un ataque de cumpleaños es un ataque de colisión por fuerza bruta que explota las matemáticas detrás del problema del cumpleaños en la teoría de la probabilidad . Este ataque puede usarse 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 ( palomas ). Sea${\textstyle H}$sea ​​el número de valores posibles de una función hash, con${\textstyle H=2^{l}}$. Con un ataque de cumpleaños, es posible encontrar una colisión de una función hash con${\textstyle 50\%}$oportunidad en${\estilo de texto {\sqrt {2^{l}}}=2^{l/2},}$ dónde${\textstyle l}$es la longitud en bits de la salida hash, ^{[ 1 ] [ 2 ]} y con${\textstyle 2^{l-1}}$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 colisiones, en${\estilo de texto {\sqrt[{3}]{2^{l}}}=2^{l/3}}$. ^{[ 4 ]}

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

Como ejemplo, consideremos el escenario en el que un profesor con una clase de 30 alumnos (n = 30) pregunta la fecha de nacimiento de cada uno (para simplificar, ignoremos los años bisiestos ) para determinar si dos alumnos tienen la misma fecha de nacimiento (lo que corresponde a una colisión de hash, como se describe más adelante). Intuitivamente, esta probabilidad puede parecer pequeña. Contrariamente a la intuición, la probabilidad de que al menos un alumno tenga la misma fecha de nacimiento que cualquier otro alumno en cualquier día es de alrededor del 70 % (para n = 30), según la fórmula${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$. ^{[ 6 ]}

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

En un ataque de cumpleaños, el atacante prepara varias variantes de contratos, tanto benignos como maliciosos, cada uno con su firma digital . Se busca un par de contratos, uno benigno y otro malicioso, 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 ; cabe destacar 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.

Dada una función${\displaystyle f}$El objetivo del ataque es encontrar dos entradas diferentes.${\displaystyle x_{1},x_{2}}$de tal manera que${\displaystyle f(x_{1})=f(x_{2})}$Una pareja así${\displaystyle x_{1},x_{2}}$Se denomina colisión. El método utilizado para encontrar una colisión consiste simplemente en evaluar la función.${\displaystyle f}$para diferentes valores de entrada que pueden ser elegidos 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${\displaystyle f(x)}$produce cualquiera de${\displaystyle H}$diferentes resultados con igual probabilidad y${\displaystyle H}$Si es suficientemente grande, entonces esperamos obtener un par de argumentos diferentes.${\displaystyle x_{1}}$y${\displaystyle x_{2}}$con${\displaystyle f(x_{1})=f(x_{2})}$después de evaluar la función durante aproximadamente${\displaystyle 1.25{\sqrt {H}}}$diferentes argumentos en promedio.

Consideremos el siguiente experimento. De un conjunto de H valores, 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 ]}

dónde${\displaystyle n}$es el número de valores elegidos (entradas) y${\displaystyle H}$es el número de resultados posibles (salidas hash posibles).

Sea n ( p ; H ) el número más pequeño de valores que debemos 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 debemos 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 ¹⁹ resultados diferentes. Si todos son igualmente probables (el mejor caso), entonces se necesitarían 'solo' aproximadamente 5 mil millones de intentos (5,38 × 10 ⁹ ) para generar una colisión usando fuerza bruta. ^{[ 8 ]} Este valor se llama límite de cumpleaños ^{[ 9 ]} y podría aproximarse como 2 ^{l /2} , donde l es el número de bits en H. ^{[ 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 son igualmente probables. Para comparar,10 ⁻¹⁸ a10 ⁻¹⁵ es la tasa de error de bits no corregible de un disco duro típico. ^{[ 11 ]} En teoría, los hashes MD5 o UUID , que son aproximadamente 128 bits, deberían mantenerse dentro de ese rango hasta unos 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 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 (que explotan 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, es inviable para funciones hash populares como las familias MD y SHA. ^{[ 12 ]} La subexpresión${\displaystyle \ln {\frac {1}{1-p}}}$en la ecuación para${\displaystyle n(p;H)}$no se calcula con precisión para tamaños pequeños${\displaystyle p}$cuando se traduce directamente a lenguajes de programación comunes log(1/(1-p))debido a la pérdida de significado . Cuando log1pestá disponible (como en C99 ), por ejemplo, -log1p(-p)se debe usar la expresión equivalente en su lugar. ^{[ 13 ]} Si no se hace esto, la primera columna de la tabla anterior se calcula como cero, y varios elementos en la segunda columna no tienen ni siquiera un dígito significativo correcto.

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. Un mensaje${\displaystyle m}$Normalmente se firma mediante el primer cálculo${\displaystyle f(m)}$, dónde${\displaystyle f}$es una función hash criptográfica y luego se utiliza alguna clave secreta para firmar${\displaystyle f(m)}$Supongamos que Mallory quiere engañar a Bob para que firme un contrato fraudulento . Mallory prepara un contrato justo.${\displaystyle m}$y uno fraudulento${\displaystyle m'}$Luego encuentra una serie de puestos donde${\displaystyle m}$se pueden cambiar sin cambiar el significado, como insertar comas, líneas en blanco, 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${\displaystyle m}$que son todos contratos justos.

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

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${\displaystyle 2^{l}}$es el número de hashes posibles, donde${\displaystyle l}$es la longitud en bits de la salida 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${\displaystyle 2^{(l/2)+1}}$hashes, que es el doble del número requerido para una colisión simple bajo el problema clásico del cumpleaños.

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 que los necesarios para prevenir un ataque de fuerza bruta ordinario .

Además de utilizar una longitud de bits mayor, el firmante (Bob) puede protegerse realizando algunos cambios aleatorios e inofensivos en el documento antes de firmarlo, y conservando una copia del contrato que firmó, para que al menos pueda demostrar ante el tribunal que su firma coincide con ese contrato, y 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 por colisión
• Ataque de encuentro en el medio
• Algoritmo BHT

• Mihir Bellare , Tadayoshi Kohno: Equilibrio de la función hash y su impacto en los ataques de cumpleaños. EUROCRYPT 2004: pp . 401-418
• Criptografía aplicada, 2.ª ed., por Bruce Schneier

• "¿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"