[cryptography] Digest comparison algorithm

[Solar Designer]

On Thu, Dec 01, 2011 at 11:16:14PM -0600, Marsh Ray wrote:
> On 12/01/2011 10:15 PM, Solar Designer wrote:
> >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?

Not a plain wordlist, but wordlist + thousands or millions of rules.
In fact, another tool implements that and achieves just slightly slower
speeds: http://hashcat.net/oclhashcat-plus/

> >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.

That's correct.

> >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

Yes, Nate had pointed me at this one too.

> >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

OK, let's assume this.

> (I know it uses $ and some form of base-64 in practice,

For traditional DES-based crypt(3), it is 13 characters:

sshhhhhhhhhhh

There's no fixed part, just two characters of salt and 11 of hash (using
a base-64 character set).

But let's continue to assume your format for the string for now:

> 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.

Yes.

> This cluster will be approximately 256 times smaller than the first.

Why not 16 times, if we use hex digits and assume a char-by-char strcmp()?

> With 
> 4096 trials the expectation is that this cluster will contain about 16 
> members.

256 with the above correction.

> 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.

Did you mean there will _likely_ (but not necessarily) be only one such
salt value?

> So if his timing data is any good, he has learned the salt

Yes, well done.

> 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.

I don't see how placement of the salt in the encoded salt+hash string
matters.  With either placement, the salt characters in the string will
always match because crypt(3) is called with that stored salt.  The fact
that with salt placement at the beginning strcmp() actually does compare
those characters before it gets to comparing H[0] doesn't affect
anything, as far as I can see, assuming a char-by-char strcmp().

Am I missing something?

Alexander
_______________________________________________
cryptography mailing list
cryptography at randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE