Ataque de cumpleaños


Ataque de cumpleaños

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 x1 y x2 diferentes de manera tal que f(x1) = f(x2), hecho conocido como una colisión.

Contenido

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 × 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 continució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 frudulento. 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 resulve 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 xr para varios enteros r elegidos aleatoriamente y computa yx s para varios enteros s elegidos aleatoriamente. Pasado un tiempo, se encontrará un par xr = yx s, lo que significa que y = xr + 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 estamos escribiendo}
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

Referencias

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

Enlaces externos

Obtenido de "Ataque de cumplea%C3%B1os"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Ataque Meet-in-the-middle — Saltar a navegación, búsqueda El ataque por encuentro a medio camino o meet in the middle es un ataque similar al ataque de cumpleaños, que utiliza un compromiso entre tiempo y espacio. Mientras que el ataque de cumpleaños trata de encontrar dos… …   Wikipedia Español

  • El Ataque de los Caimanes — Saltar a navegación, búsqueda El Ataque de los Caimanes Episodio de Thunderbirds Episodio nº Temporada 1 Episodio 23 Escrito por Alan Pattillo Dirigido por David Lane …   Wikipedia Español

  • Criptoanálisis — Saltar a navegación, búsqueda Criptoanálisis (del griego kryptós, escondido y analýein, desatar ) es el estudio de los métodos para obtener el sentido de una información cifrada, sin acceso a la información secreta requerida para obtener este… …   Wikipedia Español

  • Colisión (hash) — En informática, una colisión de hash es una situación que se produce cuando dos entradas distintas a una función de hash producen la misma salida. Es matemáticamente imposible que una función de hash carezca de colisiones, ya que el número… …   Wikipedia Español

  • DNS Poisoning — Saltar a navegación, búsqueda DNS cache poisoning / DNS Poisoning / Pharming es una situación creada de manera maliciosa o no deseada que provee datos de un Servidor de Nombres de Dominio (DNS) que no se origina de fuentes autoritativas DNS. Esto …   Wikipedia Español

  • Anexo:Episodios de Detective Conan — A continuación se presenta un listado de episodios de la serie Detective Conan, con su título original japonés (romanji y kanji), su traducción en español a partir del título original y el título del doblaje en España y en Hispanoamérica. Como… …   Wikipedia Español

  • Anexo:Todos los Personajes de Harry Potter — Se ha sugerido que este artículo o sección sea fusionado en Anexo:Personajes de Harry Potter (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí …   Wikipedia Español

  • Aldea Oculta de la Hoja — Aldea de Naruto Símbolo de la Aldea Oculta de la Hoja. Información Significado del nombre Aldea Oculta de la Hoja Otros nombres Konoha …   Wikipedia Español

  • Personajes de la Aldea Oculta de la Hoja — Anexo:Personajes de la Aldea Oculta de la Hoja Saltar a navegación, búsqueda En el manga y anime Naruto, la Aldea Oculta de la Hoja posee a los siguientes ninjas: Contenido 1 Rango Genin 1.1 Inaho 1.2 …   Wikipedia Español

  • Todos los Personajes de Harry Potter — Anexo:Todos los Personajes de Harry Potter Saltar a navegación, búsqueda J.K. Rowling es la autora de la saga de Harry Potter. En la serie Harry Potter , escrita por J.K. Rowling, Hay mas de 600 personajes, acontinucacion estan todos. Esta lista… …   Wikipedia Español