"Complejidad computacional" es una medida del esfuerzo de CPU / RAM involucrado en la ejecución de un algoritmo. En el caso de un ataque sobre un algoritmo criptográfico (por ejemplo, MD5), la complejidad se mide en relación con el algoritmo atacado. MD5 procesa los datos por fragmentos de 512 bits, por lo que tiene un "costo elemental", que es la cantidad de CPU que se necesita para enviar un pequeño mensaje (de 0 a 447 bits, para ser precisos). Dado que MD5 ofrece una salida de 128 bits, entonces, para un ataque de preimagen (encontrar m tal que MD5 ( m ) = x , donde < em> x se da), el ataque genérico "tener suerte" tiene un costo promedio de 2 128 veces el costo de hashing en un mensaje pequeño. De hecho, el ataque "tener suerte" consiste en elegir m al azar hasta que se encuentre una coincidencia, que, para una función hash "perfecta" (un random oracle ) funciona con probabilidad 2 -128 para cada intento.
Por lo tanto, expresamos "esfuerzo de CPU" como el número de veces que la función atacada podría evaluarse con tantos ciclos de reloj invertidos. Esta unidad de medición tiene la agradable propiedad de mostrar fácilmente si una función está "rota académicamente" o no. El ataque "tener suerte" es genérico: funciona para todas las funciones hash, independientemente de su perfección. El costo promedio de ese ataque es 2 n para una función hash con una salida de n -bit. Así que cualquier ataque que haga mejor, incluso un poco, cuenta como un "descanso". En el caso de MD5, el ataque presentado ha costado 2 123.4 , lo que significa que es aproximadamente 20 veces más rápido que el ataque "tener suerte". Pero sigue siendo completamente inviable en la práctica. El límite realista para un atacante poderoso (por ejemplo, alguien con el presupuesto de Google) es alrededor de 2 80 invocaciones de MD5.