Re: Time Invariant String Comparison

[William Ahern <william@...>]

On Mon, Jan 20, 2014 at 12:08:20AM -0430, Andres Perera wrote:
> On Sun, Jan 19, 2014 at 7:37 PM, William Ahern
> <william@25thandclement.com> wrote:
> 
> [...]
> 
> > The marginal security is so low, that's the kind of thing you need to on a
> > regular basis to make them worthwhile. That's not the kind of thing you need
> > to do with traditional cryptographic primitives. My 2048-bit RSA key from
> > 2000 is in real-terms just as safe today as it was 14 years ago. But a
> > PBKDF2 round variable would be laughable after 14 years.
> 
> You could even encrypt files with your RSA key! You wouldn't do that
> with bcrypt output, however, because you negate the whole benefit of
> recursive hashing: the attacker only needs to find the n-1th
> intermediate form to crack the file.
> 
> Would you consider, then, login authentication distinct from general
> decryption?
> 
> It's almost as if bcrypt and the like were designed for distinct purposes.

I think the fundamental problem is human-useable passwords. Solutions like
bcrypt or scrypt are trying to salvage a doomed situation; namely, improving
the real-world survivability of inherently weak passwords, whether used for
authentication or encryption. bcrypt and especially scrypt are smart in
trying to prevent any shortcuts with brute force implementations, but ASIC
shortcuts aren't the real problem.

The amount of entropy in human-useable 6-character or 8-character passwords
is so low that it doesn't really matter if something like scrypt makes it a
million times harder to compute each hash--although if I understand the
original description from the scrypt paper, it's more like roughly only
260000 times harder than SHA-2 based on the original parameters.

Note that there purportedly already are scrypt machines (for litecoin) which
can do 25 million scrypt hashes per second (albeit with an r parameter value
of 1, so knock it down by some small'ish fixed constant).

A weak password will still be a weak password with or without scrypt.

If you move to something like HOTP systems, the exponential increase in
search space far exceeds the linear (by comparison) attack cost that scrypt
buys you.

Solutions like scrypt do make you less vulnerable than the next guy. And
there's something to be said for that. But that's perilously close to the
cryptographic equivalent of bike shedding. Or even "you can never go wrong
by choosing Microsoft" as a contingent defense for when things break.