Ataque de cumpleaños en Criptografía – Part 1

Requisito previo: paradoja de  
cumpleaños El ataque de cumpleaños es un tipo de ataque criptográfico que pertenece a una clase de ataques de fuerza bruta. Explota las matemáticas detrás del problema del cumpleaños en la teoría de la probabilidad. El éxito de este ataque depende en gran medida de la mayor probabilidad de colisiones encontradas entre intentos de ataque aleatorios y un grado fijo de permutaciones, como se describe en el problema de la paradoja del cumpleaños . 

Problema de paradoja de cumpleaños: 
consideremos el ejemplo de un salón de clases de 30 estudiantes y un maestro. El maestro desea encontrar parejas de estudiantes que tengan el mismo cumpleaños. Por lo tanto, el maestro pide el cumpleaños de todos para encontrar tales parejas. Intuitivamente este valor puede parecer pequeño. Por ejemplo, si el maestro fija una fecha en particular, digamos el 10 de octubre , entonces la probabilidad de que al menos un estudiante nazca ese día es 1 – (364/365) ³⁰ , que es aproximadamente 7.9 % . Sin embargo, la probabilidad de que al menos un estudiante tenga el mismo cumpleaños que cualquier otro estudiante es de alrededor del 70% usando la siguiente fórmula: 
 

1 - 365!/((365 - n!) * (365n))  (substituting n = 30 here) 

Derivación del término anterior: 

Supuestos: 
1. Suponiendo un año no bisiesto (por lo tanto, 365 días). 
2. Asumir que una persona tiene la misma posibilidad de nacer en cualquier día del año. 
Consideremos n = 2. 
P(Dos personas tienen el mismo cumpleaños) = 1 – P(Dos personas tienen diferente cumpleaños) 
                                                              = 1 – (365/365)*(364/365) 
                                                              = 1 – 1*(364/365 ) 
                                                              = 1 – 364/365 
                                                              = 1/365. 
Entonces, para n personas, la probabilidad de que todas tengan cumpleaños diferentes es: 
P(N personas con cumpleaños diferentes) = (365/365)*(365-1/365)*(365-2/365)*….(365-n+1)/365. 
                                                              = 365!/((365-n)! * 365 ⁿ ) 

Función hash: 
una función hash H es una transformación que toma una entrada m de tamaño variable y devuelve una string de tamaño fijo llamada valor hash (h = H (m)) . Las funciones hash elegidas en criptografía deben cumplir los siguientes requisitos: 
 

• La entrada es de longitud variable,
• La salida tiene una longitud fija,
• H(x) es relativamente fácil de calcular para cualquier x dado,
• H(x) es unidireccional,
• H(x) no tiene colisiones. 
   

Se dice que una función hash H es unidireccional si es difícil de invertir, donde «difícil de invertir» significa que dado un valor hash h, es computacionalmente inviable encontrar alguna entrada x tal que H(x) = h . 

Si, dado un mensaje x, no es computacionalmente factible encontrar un mensaje y que no sea igual a x tal que H(x) = H(y) , entonces se dice que H es una función hash débilmente libre de colisiones. 

Una función hash fuertemente libre de colisiones H es aquella para la cual no es factible computacionalmente encontrar dos mensajes x e y tales que H(x) = H(y) . 

Sea H: M => {0, 1} ⁿ una función hash ( |M| >> 2 ⁿ ) 

El siguiente es un algoritmo genérico para encontrar una colisión en el tiempo O(2 ^n/2 ) hashes. 

Algoritmo: 
 

1. Elige 2 ^n/2 mensajes aleatorios en M: m ₁ , m ₂ , …., m _n/2
2. Para i = 1, 2, …, 2 ^n/2 calcular t _i = H(m _i ) => {0, 1} ⁿ
3. Busque una colisión (t _i = t _j ​​). Si no lo encuentra, vuelva al paso 1 
    

Consideremos el siguiente experimento. De un conjunto de valores H, elegimos n valores uniformemente al azar, lo que permite 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: 

p(n; H) = 1 - ( (365-1)/365) * (365-2)/365) * ...(365-n+1/365))
p(n; H) = e-n(n-1)/(2H) = e-n2/(2H) 

Susceptibilidad 
de la firma digital: las firmas digitales pueden ser susceptibles a los ataques de cumpleaños. Un mensaje m normalmente se firma calculando primero H(m) , donde H es una función hash criptográfica, y luego usando alguna clave secreta para firmar H(m) . Supongamos que Alice quiere engañar a Bob para que firme un contrato fraudulento. Alicia prepara un contrato justo m y fraudulento m’ . A continuación, encuentra una serie de posiciones donde mse puede cambiar sin cambiar el significado, como insertar comas, líneas vacías, uno contra dos espacios después de una oración, reemplazar sinónimos, etc. Al combinar estos cambios, puede crear una gran cantidad de variaciones en m, que son todos contratos justos. 

De manera similar, Alice también puede hacer algunos de estos cambios en m’ para llevarlo, aún más, más cerca de m , es decir, H(m) = H(m’) . Por lo tanto, Alice ahora puede presentar la versión justa m a Bob para que la firme. Después de que Bob haya firmado, Alice toma la firma y le adjunta el contrato fraudulento. Esta firma prueba que Bob ha firmado el contrato fraudulento. 

Para evitar tal ataque, la salida de la función hash debe ser una secuencia de bits muy larga, de modo que el ataque de cumpleaños ahora se vuelva computacionalmente inviable.