Re: Time Invariant String Comparison

[Andres Perera <andres.p@...>]

On Sun, Jan 26, 2014 at 9:13 PM, William Ahern
<william@25thandclement.com> wrote:
> 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.

http://eprint.iacr.org/2013/525

"Moreover, Catena supports (1)~client-independent updates (the server
can increase the security parameters and update the password hash
without user interaction or knowing the password), (2)~a server relief
protocol (saving the server's resources at the cost of the client),
and (3)~a variant Catena-KG for secure key derivation (to securely
generate many cryptographic keys of arbitrary lengths such that
compromising some keys does not help to break others)."

this kdf is fairly recent, heard about it today

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