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 _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
