Message-ID: <20140118172126.GA15352@openwall.com>
Date: Sat, 18 Jan 2014 21:21:26 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] cost upgrades (Re: [PHC] Scripting memory (not so) high vs Catena in PHP (with optimizations))

On Sat, Jan 18, 2014 at 11:27:32AM -0500, Bill Cox wrote:
> I totally stole Catena's update scheme.  All we have to do is add an
> outer loop that iterates "garlic" number of times, computing the hash
> with the user's password.  Inside the loop, at the end, we double the
> memory.  This makes the scheme take 2X longer for the same memory
> usage (for garlic == 3, it does 8*m_cost + 4*m_cost + 2*m_cost +
> m_cost), so it's not ideal, but it is trivial to take the hash for
> garlic = g, and compute the hash for garlic = g+1.  The input to each
> loop iteration is just the output from the previous.
> 
> So, for brand spanking new hashes, set garlic = 0, so the user has no
> penalty at all.  As the password hash ages, incrementing the garlic
> can help.

Thank you for explaining this so concisely and so clearly!  In my terms,
this corresponds to 2x granularity and good design (so never-upgraded
hashes have their full AT cost).

In "2X longer for the same memory usage", you're referring to memory
usage at the end.  I think it is more relevant to consider the AT cost
of the entire hash computation, and (as I had mentioned) with 2x
granularity and many upgrades it converges to 1/3 of AT cost of
never-upgraded hashes.  In your example above, it is about 37.8%:

(1+2^2+4^2+8^2) / 15^2 = ~37.8%

> If the user ever does log in again, maybe the server can
> recompute a hash for a higher m_cost, and set garlic back to 0.

This brings us to another issue with cost upgrades: timing leaks
allowing a remote attacker to determine valid usernames and/or users
with differently upgraded (or non-upgraded) hashes.  This is actually a
reason in favor of supporting hash upgrades without requiring plaintext
passwords, so that all hashes can be upgraded in the exact same way at
once (rather than as users log in).  The ability to do as you describe
is very nice, where such timing attacks are deemed relatively
unimportant.

> I've shamelessly stolen other good ideas, too, such as Blakerypt's use
> of a session key when available,

I haven't looked, but from the mentions in here it sounds like
Blakerypt's session key is what I call a local parameter.  Is it that,
or is it something different?

In current escrypt, the builtin local parameter support is currently
only present when there's a ROM (it is used to initialize the ROM);
maybe we should add such builtin support for ROM-less uses as well.

> and a few of your ideas.  Maybe if,
> in the very unlikely even that NoelKDF is chosen, I can add those who
> contributed ideas as official-ish authors if they allow?  This sharing
> of ideas in a competition is super cool, but also very unusual.  My
> 13-year-old daughter says we must all be terrible competitors.

Yeah, we're terrible.  It's about advancing the field and having better
tools to use, regardless of which one(s) is/are chosen as "winners".

> By the way, I'm quite interested in access to your high-end machines,
> but I have enough on my plate now that I'm back to my real job that I
> wont need access for some time.  I'll email you when I need it, and
> thank you for the offer!

Sounds good.

Alexander

Powered by blists - more mailing lists