Ataque de cumpleaños

Un ataque de cumpleaños (o, en inglés, birthday attack) es un tipo de ataque criptográfico que se basa en la matemática detrás de la paradoja del cumpleaños, haciendo uso de una situación de compromiso espacio-tiempo informática. Concretamente, si una función matemática produce  resultados diferentes igualmente probables y  es lo suficientemente grande, entonces, después de evaluar la función sobre  argumentos distintos, se espera encontrar un par de argumentos  y  diferentes de manera tal que , hecho conocido como una colisión.

La matemática 
Para demostrar el resultado anterior, comenzamos con el desarrollo en series de Taylor de la probabilidad de que dos personas cumplan los años en el mismo día. En este caso, reemplazamos el número de días en un año con el número de resultados únicos, :

donde  es el número de intentos para una colisión. Invirtiendo esta expresión,

y asignando una probabilidad de colisión de 0.5 (condición de que sea tan posible como imposible), llegamos a

.

Como ejemplo, si se usa un hash de 64 bits, habrá aproximadamente 1.8 × 1019 resultados distintos. Si todas son igualmente probables (el mejor de los casos), entonces tomaría solamente unos 5.1 × 109 intentos aproximadamente generar una colisión usando fuerza bruta. Otros ejemplos son como se muestra a continuación:

{| border="1" cellpadding="3" cellspacing="0"
|- align="center" bgcolor="lightgrey"
| nowrap rowspan="2" | Bits
| nowrap rowspan="2" | Salidasposibles
| nowrap colspan="8" | Probabilidad deseada de colisiones aleatorias
|- align="center" bgcolor="lightgrey"
| nowrap | 10-12
| nowrap | 10-9
| nowrap | 10-6
| nowrap | 0.1%
| nowrap | 1%
| nowrap | 25%
| nowrap | 50%
| nowrap | 75%
|- align="center"
| nowrap bgcolor="lightgrey" | 64
| nowrap bgcolor="lightgrey" | 1.8 × 1019
| nowrap | 6.1 × 103
| nowrap | 1.9 × 105
| nowrap | 6.1 × 106
| nowrap | 1.9 × 108
| nowrap | 6.1 × 108
| nowrap | 3.3 × 109
| nowrap | 5.1 × 109
| nowrap | 7.2 × 109
|- align="center"
| nowrap bgcolor="lightgrey" | 128
| nowrap bgcolor="lightgrey" | 3.4 × 1038
| nowrap | 2.6 × 1013
| nowrap | 8.2 × 1014
| nowrap | 2.6 × 1016
| nowrap | 8.3 × 1017
| nowrap | 2.6 × 1018
| nowrap | 1.4 × 1019
| nowrap | 2.2 × 1019
| nowrap | 3.1 × 1019
|- align="center"
| nowrap bgcolor="lightgrey" | 256
| nowrap bgcolor="lightgrey" | 1.2 × 1077
| nowrap | 4.8 × 1032
| nowrap | 1.5 × 1034
| nowrap | 4.8 × 1035
| nowrap | 1.5 × 1037
| nowrap | 4.8 × 1037
| nowrap | 2.6 × 1038
| nowrap | 4.0 × 1038
| nowrap | 5.7 × 1038
|- align="center"
| nowrap bgcolor="lightgrey" | 384
| nowrap bgcolor="lightgrey" | 3.9 × 10115
| nowrap | 8.9 × 1051
| nowrap | 2.8 × 1053
| nowrap | 8.9 × 1054
| nowrap | 2.8 × 1056
| nowrap | 8.9 × 1056
| nowrap | 4.8 × 1057
| nowrap | 7.4 × 1057
| nowrap | 1.0 × 1058
|- align="center"
| nowrap bgcolor="lightgrey" | 512
| nowrap bgcolor="lightgrey" | 1.3 × 10154
| nowrap | 1.6 × 1071
| nowrap | 5.2 × 1072
| nowrap | 1.6 × 1074
| nowrap | 5.2 × 1075
| nowrap | 1.6 × 1076
| nowrap | 8.8 × 1076
| nowrap | 1.4 × 1077
| nowrap | 1.9 × 1077
|}

Esta tabla muestra el número de hashes que son necesarios para alcanzar la probabilidad de éxito dada, asumiendo que todos los hashes son igualmente probables

Es fácil ver que si los resultados de la función no están distribuidas uniformemente (es decir, si no son igualmente probables), entonces las colisiones pueden ser halladas mucho más rápidamente. La noción de 'balance' de una función de hash cuantifica la resistencia de la función a ataques de cumpleaños y permite que se estime la vulnerabilidad de funciones de hash populares, tales como MD5 y SHA (Bellare y Kohno, 2004).

Las firmas digitales pueden ser susceptibles de un ataque de cumpleaños. Un mensaje  típicamente se firma computando primero , donde  es una función de hash criptográfica y luego se usa alguna clave secreta para firmar . Supongamos que Alice quiere engañar a Bob para que firme un contrato fraudulento. Alice prepara un contrato bueno  y uno malo . Así, ella busca un número de posiciones donde  pueda ser modificado sin cambiar el significado, como por ejemplo insertando comas, líneas en blanco, cambiando el espaciado entre oraciones, usando sinónimos, etc. Combinando estos cambios, Alice podría crear un número inmenso de variaciones de , todas ellas contratos buenos. De manera similar, podría crear un número inmenso de contratos fraudulentos . Entonces, ella aplica una función de hash a todas esas variaciones hasta que encuentre una versión del contrato bueno y otra del malo que posean el mismo valor hash, . Luego, le presenta la versión buena a Bob para que la firme. Una vez que Bob la firma, Alice toma la firma y se la adjunta al contrato fraudulento. Las firma digital "prueba" entonces que Bob firmó el contrato fraudulento. (Nota: este esquema difiere levemente del problema original del cumpleaños, pues Alice no gana nada por encontrar dos contratos buenos o dos contratos fraudulentos que producen el mismo hash; sin embargo, en este esquema las probabilidades son sorprendentemente altas.)

Para impedir este ataque, la longitud de los resultados de la función hash deben ser lo suficientemente grandes de manera que el ataque de cumpleaños se torne computacionalmente imposible, por ejemplo, unas dos veces más grande de lo que se requeriría para prevenir un ataque de fuerza bruta. También se ha recomendado que Bob realice cambios menores en cualquier documento que le sea presentado para ser firmado. Sin embargo, esto no resuelve el problema, porque ahora Alice sospecha que Bob intenta usar un ataque de cumpleaños.

El ataque de cumpleaños puede ser usado para acelerar el cómputo de logaritmos discretos. Supongamos que  e  son elementos de un grupo y que  es una potencia de . Queremos encontrar el exponente de  que da . Un ataque de cumpleaños computa  para varios enteros  elegidos aleatoriamente y computa  para varios enteros  elegidos aleatoriamente. Pasado un tiempo, se encontrará un par , lo que significa que .

Si el grupo tiene  elementos, el método más simple de probar todos los exponentes toma alrededor  intentos en promedio. El ataque de cumpleaños es considerablemente más rápido e implica menos de  intentos en promedio.

Existen técnicas basadas en repetición iterativa que pueden reducir considerablemente los requerimientos de almacenamiento de los ataques de cumpleaños.

Ejemplo 
El siguiente es un ejemplo de como crear variaciones de una carta sin alterar el contenido. 

{Estimado|Querido} cliente,

{Nos ponemos en contacto con usted|Le escribimos}
para {anunciarle|informarle} sobre la {charla|conferencia}
que se {realizará|llevará a cabo} el día 1 de enero de 2007,
a las 12 horas en {nuestro auditórium|nuestras premisas},
{que brindará|a cargo de} un {reconocido|prestigioso}
{autor|escritor} de {varios|numerosos} {libros|documentos}
sobre ciencia y tecnología.

{La charla|El encuentro} {consistirá en|comprenderá} los
siguientes {tópicos|contenidos}: {Internet, |Web 2.0, }
{E-learning y VoIP|VoIP y E-learning}.

{Esta|La presente} invitación es {sólo|únicamente} para
nuestros {más exclusivos clientes|clientes más exclusivos} y
es por {ello|esta razón}, que {esperamos|deseamos} contar con
su presencia.

Sin {más|otro particular}, {le saludamos|nos despedimos de
usted} {atentamente|cordialmente}.

Seleccionando entre una de las dos opciones que se presentan, se puede crear 224 mensajes distintos. Normalmente los procesadores de texto pueden configurarse para generar documentos de esta manera.

Véase también 
 Ataque Meet-in-the-middle

Referencias 
 Mihir Bellare, Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks. EUROCRYPT 2004: pp. 401-418.

Enlaces externos 
 "What is a digital signature and what is authentication?" del FAQ de RSA. (en inglés)
 "Parallel collision search with cryptanalytic applications , Michael Wiener and Paul C. van Oorschot (en inglés)
 Artículo sobre funciones hash y los ataques de cumpleaños en Netmedia.
 Debilidad del SHA-1 por D. Fernando Acero Martín, militar español experto en seguridad informática.

Ataques criptográficos

de:Kollisionsangriff#Geburtstagsangriff