"Complexidade computacional" é uma medida do esforço de CPU / RAM envolvido na execução de um algoritmo. No caso de um ataque a um algoritmo criptográfico (por exemplo, MD5), a complexidade é medida em relação ao algoritmo atacado. O MD5 processa dados por blocos de 512 bits, portanto tem um "custo elementar" que é a quantidade de CPU necessária para fazer o hash de uma pequena mensagem (de 0 a 447 bits, para ser mais preciso). Como o MD5 oferece uma saída de 128 bits, portanto, para um ataque de pré-imagem (encontrando m tal que MD5 ( m ) = x , onde x é fornecido), o ataque genérico de "sorte" tem um custo médio 2 ¹²⁸ vezes o custo de hash de uma pequena mensagem. Na verdade, o ataque de "sorte" consiste em escolher m aleatórios até que uma correspondência seja encontrada, o que, para uma função hash "perfeita" (um oráculo aleatório) funciona com probabilidade 2 ^-128 para cada tentativa.

Portanto, expressamos "esforço da CPU" como o número de vezes que a função atacada poderia ser avaliada com tantos ciclos de clock investidos. Esta unidade de medida tem a boa propriedade de mostrar facilmente se uma função está "academicamente quebrada" ou não. O ataque de "sorte" é genérico: funciona para todas as funções hash, independentemente de sua perfeição. O custo médio desse ataque é 2 ⁿ para uma função hash com uma saída de n bits. Portanto, qualquer ataque que tenha um desempenho melhor, mesmo que ligeiramente, conta como uma "pausa". No caso do MD5, o ataque apresentado custou 2 ^123,4 , o que significa que é cerca de 20 vezes mais rápido do que o ataque de "sorte". Mas ainda é completamente inviável na prática. O limite realista para um invasor poderoso (digamos, alguém com o orçamento do Google) é de cerca de 2 ⁸⁰ invocações de MD5.