[cryptography] Digest comparison algorithm

Solar Designer solar at openwall.com
Thu Dec 1 23:15:30 EST 2011


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.

> Solar might have hard numbers.

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.

Anyway, back to the original topic, I think there are two primary ways
of fixing the code:

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

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.  Then compare the HMACs.  So instead of a direct comparison like:

	if (token == secret)

you do:

	if (HMAC(secret, token) == HMAC(secret, secret))

In fact, I think HMAC is an overkill for this - simple concatenation of
inputs to a crypto hash will do as well.  (Length extension attacks do
not apply here when the secret length is constant.)

http://openwall.info/wiki/people/solar/algorithms/challenge-response-authentication#Timing-attacks

Nate Lawson pointed out a few theoretical problems with this to me in a
private e-mail exchange, but none of those apply when the expected_response
length is a constant and is not secret.  (That is, expected_response
value is secret, but its length is e.g. the constant 16.)  Otherwise
this length value may be leaked, and length extension attacks might be
possible as well.

BTW, a similar thing (to what I proposed above) happens when
authenticating with a plaintext password against a salted hash.
As far as I'm aware, historically the salt was never intended to serve
for this purpose, but it happens to mitigate timing attacks on
comparison of the hashes (e.g., crypt(3) output strings) as long as it's
stored along with the hash (not revealed separately) and not guessed by
a remote attacker (who doesn't readily have a copy of the hash anyway).
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?  (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).

Alexander



More information about the cryptography mailing list