resultados diferentes igualmente probables y
es lo suficientemente grande, entonces, después de evaluar la función sobre
diferentes de manera tal que
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,
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: 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.
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.
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
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.
(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.
son elementos de un grupo y que
elementos, el método más simple de probar todos los exponentes toma alrededor
El ataque de cumpleaños es considerablemente más rápido e implica menos de
Existen técnicas basadas en repetición iterativa que pueden reducir considerablemente los requerimientos de almacenamiento de los ataques de cumpleaños.
El siguiente es un ejemplo de como crear variaciones de una carta sin alterar el contenido.
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.