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