26 julio, 2011

The CRC32 of this string is 4A1C449B

Pues si, estaba aburrido y se me ocurrió si sería posible insertar el hash de un texto dentro del propio texto.

Viabilidad
Como no estaba muy seguro primero analicé la viabilidad. Si asumimos un formato de texto fijo, en el que sólo varía la parte del hash, la probabilidad no es baja.

Para un hash n bits, la probabilidad de acertar a la primera es:
1/(2^n)

Por tanto, la probabilidad que exista un resultado válido en todo el espacio es:


Por tanto es probable encontrar algún hash con estas características, y si no apareciera probaríamos con otra cadena base distinta.

Optimización
Lo siguiente que hice fue tomar un código de ejemplo de código de CRC32 basado en tabla de 8 bits, y precomputar una tabla de 24 bits (que debe ocupar unos 96MB en memoria).
Este código es capaz de calcular las 2^32 posibilidades en unos pocos minutos.

Habría estado bien hacer algún análisis que permitiera alguna optimización específica para este problema, pero no llego hasta ahí.

Resultado
Tras 2 minutos obtenemos:
"The CRC32 of this string is 4A1C449B"

Y poco más que decir, se puede verificar (es importante no añadir saltos de línea ni espacios al final) aquí:

Con un poco más de trabajo podemos obtener:
"I killed 56e9dee4 cows and all I got was..."