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 $H$ resultados diferentes igualmente probables y $H$ es lo suficientemente grande, entonces, después de evaluar la función sobre $1.2{\sqrt {H}}$ argumentos distintos, se espera encontrar un par de argumentos $x_{1}$ y $x_{2}$ diferentes de manera tal que $f(x_{1})=f(x_{2})$, 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, $H$:

$p(n)=1-{\bar {p}}(n)\approx 1-e^{-(n(n-1))/2\cdot H}\approx 1-e^{-n^{2}/{2\cdot H}},$

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

$n(p)\approx {\sqrt {2\cdot H\cdot \ln \left({1 \over 1-p}\right)}},$

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

$n(0.5)=1.1774{\sqrt {H}}$.

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

Bits	Salidas posibles	Probabilidad deseada de colisiones aleatorias
		10-12	10-9	10-6	0.1%	1%	25%	50%	75%
64	1.8 × 1019	6.1 × 103	1.9 × 105	6.1 × 106	1.9 × 108	6.1 × 108	3.3 × 109	5.1 × 109	7.2 × 109
128	3.4 × 1038	2.6 × 1013	8.2 × 1014	2.6 × 1016	8.3 × 1017	2.6 × 1018	1.4 × 1019	2.2 × 1019	3.1 × 1019
256	1.2 × 1077	4.8 × 1032	1.5 × 1034	4.8 × 1035	1.5 × 1037	4.8 × 1037	2.6 × 1038	4.0 × 1038	5.7 × 1038
384	3.9 × 10115	8.9 × 1051	2.8 × 1053	8.9 × 1054	2.8 × 1056	8.9 × 1056	4.8 × 1057	7.4 × 1057	1.0 × 1058
512	1.3 × 10154	1.6 × 1071	5.2 × 1072	1.6 × 1074	5.2 × 1075	1.6 × 1076	8.8 × 1076	1.4 × 1077	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 $m$ típicamente se firma computando primero $f(m)$, donde $f$ es una función de hash criptográfica y luego se usa alguna clave secreta para firmar $f(m)$. Supongamos que Alice quiere engañar a Bob para que firme un contrato fraudulento. Alice prepara un contrato bueno $m$ y uno malo $m'$. Así, ella busca un número de posiciones donde $m$ 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 $m$, todas ellas contratos buenos. De manera similar, podría crear un número inmenso de contratos fraudulentos $m'$. 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, $f(m)=f(m')$. 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 $x$ e $y$ son elementos de un grupo y que $y$ es una potencia de $x$. Queremos encontrar el exponente de $x$ que da $y$. Un ataque de cumpleaños computa $x^{r}$ para varios enteros $r$ elegidos aleatoriamente y computa $yx^{-s}$ para varios enteros $s$ elegidos aleatoriamente. Pasado un tiempo, se encontrará un par $x^{r}=yx^{-s}$, lo que significa que $y=x^{r+s}$.

Si el grupo tiene $n$ elementos, el método más simple de probar todos los exponentes toma alrededor $n/2$ intentos en promedio. El ataque de cumpleaños es considerablemente más rápido e implica menos de $2{\sqrt {n}}$ 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 2²⁴ 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 Archivado el 30 de diciembre de 2008 en Wayback Machine., 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.

• Datos: Q615485