[cryptography] Digest comparison algorithm

Marsh Ray marsh at extendedsubset.com
Thu Dec 1 22:15:05 EST 2011

On 12/01/2011 06:15 PM, Jerrie Union wrote:
> How should the attacker mount the attack after hash[0] has been recovered?

He tests passwords that yield the identified H[0].

> I guess for a given digest D if the attacker guess the character at position 1 (D[1])
>   by supplying the secret S there’s no easy way to recover D[2] because the md5
> function will introduce noise in every single bit of the output as you change a single
> bit in the input.

He could generate random passwords and discard 254/255 of them. This 
should not be a limitation as MD5s can be generated by the millions per 
second (said to be giga/s with GPGPU rigs).

He only needs to find 256 of them to probe for the next value.

> Maybe, by having a huge precomputed table the attacker can attempt to mount a timing attack
> in this way:
> 1. guess the first byte of the digest by exploiting the timing attack
> 2. for every digest in the rainbow table starting with the previously guessed byte:
> 3. try to send the plaintext and time the response to recover the second byte
> The same process could be iterated until the fully string is recovered.
> Does it make sense?

Except that the rainbow table is unnecessary and the precomputed table 
doesn't need to be very big.

When you can evaluate MD5 at 5.6 GH/s, accessing even a straight lookup 
table in main memory is probably a slowdown.

Solar might have hard numbers.

- Marsh

More information about the cryptography mailing list