Re: Time Invariant String Comparison

[William Ahern <william@...>]

On Sat, Jan 25, 2014 at 01:15:26PM -0430, Andres Perera wrote:
> On Sat, Jan 25, 2014 at 7:18 AM, David Given <dg@cowlark.com> wrote:
> > On 25/01/14 11:06, Rob Kendrick wrote:
> >> On Fri, Jan 24, 2014 at 10:12:02PM -0800, William Ahern wrote:
> > [...]
> >>> Who in their right mind would allow their website authentication system to
> >>> spend 5 seconds (an eternity!) hogging a CPU? Especially when you could
> >>> instead mandate passwords just three or four characters longer for the same
> >>> benefit and without crippling your throughput?
> >>
> >> Because verifying with a correct password is much faster than verifying
> >> with an incorrect one.  Plus, that 5 seconds is tunable.  Want it to be
> >> only a milisecond?  Fine.  You can do that, and make sure it's always a
> >> milisecond, regardless of how fast computers get.
> >
> > Woah, woah, you're talking about two different things.
> >
> > William's talking about it taking 5 CPU-seconds verifying passwords.
> > This is very bad because it makes the web server trivially DOSable (a
> > couple of thousand simultaneous access attempts will cause the server to
> > implode).
> 
> For the comparison to be fruitful, all other factors have to be equal,
> that means throttling max concurrent auths.
> 
> The comment could then be, serverside KDF reduces maximum concurrent
> auths in proportion to the increase of time over a single pass of the
> underlying hash.

Server-side doesn't just reduce concurrent auths, it reduces concurrent
requests overall, because a single hash operation consumes 100% CPU. But
client-side, admittedly, wouldn't be nearly as much of an issue.

I still think the value of these schemes are exagerrated. But if I were to
use one, it'd definitely be scrypt. PBKDF2 is not nearly as useful at this
point. And I'd probably add code to automatically step up the difficulty for
new passwords over time, and maybe to even automatically rehash passwords on
authentication--although adding code in the update path for an
authentication database is risky.

Even though I haven't changed my basic opinion, I appreciate the back and
forth. And I've been forced to read some interesting material.

I'm going to bow out now because for this thread to be useful I feel like
I'd need to commit time to putting together some experiments to validate or
invalidate my assumptions*. The value of these schemes is very much rooted in
practicality. But I don't have the time or motivation for that right now.


* For example, acquiring a list of the N-thousand most common passwords,
assembling an EC2 cluster, and cataloging cracking times.