[cryptography] Digest comparison algorithm

Marsh Ray marsh at extendedsubset.com
Fri Dec 2 00:16:14 EST 2011


On 12/01/2011 10:15 PM, Solar Designer wrote:
> On Thu, Dec 01, 2011 at 09:15:05PM -0600, Marsh Ray wrote:
>> When you can evaluate MD5 at 5.6 GH/s, accessing even a straight lookup
>> table in main memory is probably a slowdown.
>
> Yes, but those very high speeds are throughput for large numbers of
> hashes to compute in parallel.  If you don't yet have a large enough
> number of inputs to hash (that is, if you have an algorithm with
> conditional branching), then you'd achieve a lower speed.

Either way, it's overkill for finding candidate passwords for H[1], 
H[2], and probably H[3] and H[4]. (If the password even holds out that 
long).

> http://whitepixel.zorinaq.com is probably the fastest single MD5 hash
> cracker.  This one tests 33.1 billion of passwords per second against a
> raw MD5 hash on 4 x AMD Radeon HD 5970 (8 GPUs).  Of course, the
> passwords being tested are not arbitrary (e.g., you can't just feed a
> wordlist to such a cracker), although the character set is configurable.

Where would you find a wordlist to keep it busy for more than a 
millisecond anyway?

> 1. Already discussed: implement constant-time comparisons by using XORs
> and ORs.

Talking with people who work closely with code generation convinced me 
that it's essential to examine the generated code. A compiler might 
recognize and exploit the opportunity for early loop termination.

> 2. Pass both strings to compare through an HMAC with a secret.  If one
> of the strings is a secret, then that secret may be reused for this HMAC
> as well.

http://www.isecpartners.com/blog/2011/2/18/double-hmac-verification.html

It may be relevant that in this case it isn't specified which of the two 
parameters 'digest' and 'secret' are unknown to the attacker.

> It'd be curious to explore how much entropy in the salt is needed for
> this.  Are 12-bit salts of traditional DES-based crypt(3) sufficient
> against remote timing attacks or not?

Let's assume crypt(3) returns a string which is compared against the 
expected value using strcmp(), and the salted hash is formed of hex 
digits like:

         %crypt(3)%SSS%HHHHHHHHHHHHHHHH%

SSS - 12 bit salt
HHH - 64 bit value from DES-like function

(I know it uses $ and some form of base-64 in practice, but the relevant 
factor is that the salt comes before the hash value, and everything else 
before H[0] is fixed and known to the attacker.)

The attacker generates, say, 4096 random passwords and accurately times 
their evaluation. If there isn't too much jitter on the network (or the 
local machine), and his timing measurements are accurate enough, he will 
observe the timings grouping into two clusters:

1. The largest cluster will represent the case where H[0] fails the 
comparison in strcmp().

2. The second cluster will be on the order of a few machine cycles 
longer,  representing times that H[0] compared successfully. This 
cluster will be approximately 256 times smaller than the first. With 
4096 trials the expectation is that this cluster will contain about 16 
members.

Now that he has a fuzzy idea of which passwords succeed in matching 
H[0], he evaluates this set for all 4096 possible salt values. There 
will be only one salt value that produces the same H[0] for all of these 
passwords. It's possible that some of his values crept into the wrong 
cluster, but these can be readily ignored if, say, 10 of the 16 produce 
a match. 16*4096 is not very much work at all, and most of it can be 
skipped.

So if his timing data is any good, he has learned the salt and can 
quickly verify it with some confirming tests. The attacker proceeds to 
work out the remainder of the password hash as before.

Conclusion: Salts placed at the beginning of the password string must 
contain sufficient entropy to resist offline brute-force in order to 
provide mitigation against timing attacks. It may be better to place 
them at the end of the password hash string.

>  (Assuming that these salts are
> otherwise perfect.)  They appear to have been sufficient in practice so
> far (I haven't heard of anyone mounting such an attack), but there's
> room for some research and testing here (likely proving that slightly
> larger salts or constant-time comparisons are desirable for this).

(*_*);;;

- Marsh



More information about the cryptography mailing list