Date: Thu, 3 Apr 2014 17:02:08 +0200 (CEST)
From: Stefan.Lucks@...-weimar.de
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Deliberately GPU-friendly password hashes?

On Thu, 3 Apr 2014, Bill Cox wrote:

[...]
> Speed not mattering in a memory hard password hashing scheme seems to
> me to be an attitude from academia. In the real world, time always
> matters (did that login take 0.1 seconds or 10s?), [...]

Being from academia myself, I have to point out that this is definitively 
not an "attitude from academia"!. Who on earth would dispute that it 
matters if a log-in takes 0.1 or 10.0 seconds?

Most likely, the defender has certain budgets for time and memory, any you
need two tunable parameters (like "pepper" and "garlic") to make sure that
your password hash uses the budgets, without exhausting them.

> Finally, I am saddened to be the only submitter to use a cryptographic
> primitive like SHA256 for securely deriving an initial key, but then
> filling memory with non-cryptographically pseudo-random data.  The
> guys using the new AES instructions might be fast enough, but every
> other memory hard entry is speed limited due to their reliance on a
> strong hash function for deriving data to fill memory.

Well, this raises the workload (=time) for both the attacker and the 
defender, so this should be OK. At worst --I guess, this is your concern-- 
you cannot use the full memory budget, since you would otherwise exhaust
the time budget.

But usually, filling the memory takes a fraction of the time (one half, or 
1/4 or so) for the full password hash, so alternative ways of filling the 
memory don't give you that much of an advantage -- hardly worth the 
security assurance you loose that way, see below.

> However, a lot of these entries have trivial tests for non-randomness 
> that easily prove the memory is the result of their PHS, and not random.

Interesting point! So if the data are left in the memory, rather than 
deleted at the end of the password hashing, some adversary can check if a 
certain password hash function has been applied or not.

Academically, this is a cool new attack scenario! I have doubts, though, 
that this has much practical relevance in the context of PHC -- who would 
really want to hide the fact that (s)he is using a certain password hash, 
or hashing a password at all? And the executable is in memory, also.

What I (yes, I am an academic) consider a lot more relevant is what we 
called the "garbage collector attack" in the Catena submission:

     If, after executing the password hash function, the memory has been
     released, how much can the adversary, who is searching for the
     password, benefit from reading that memory?

This ought to be a concern for every memory-hard password hash.

Of course, you should whipe the memory, before you release it ... but this 
is forgotten so often, even when the memory actually holds cryptographic 
keys.

> The only benefit of using a slow cryptographic primitive in this case is 
> that there is little need to worry that the whole thing can be reversed, 
> revealing the password or initial derived key.

Agreed! This is one benefit, though not the only one.

> I suppose it also makes it simple to prove that there are no short-cuts 
> an attacker can take.

Agreed! This is another benefit.

> However, simply applying a strong hash function now and then should be 
> enough to gain similar confidence [...]

Now, this is the point where we disagree!

When using a strong primitive everywhere, you can make a strong argument 
(mathematically: a "proof") that your password hash function is secure if 
the underlying primitive is secure. (Of course, this also depends on a 
carefully designed structure, that supports such a "proof".)

Then, if the primitive you are using has been analysed well, you inherit 
that primitive's security assurance. You are even free to switch to 
another primitive, if you would trust that primitive more.

Otherwise, in the "here and there" case, you have invented your own 
cryptographic primitive. This is a cool thing, there is nothing wrong with 
doing so!

But in spite of calling some other primitive "here and there" you don't 
inherit the security assurance from that other primitive. Your password 
hash function might turn out as weak, regardless of the strength of the 
other primitive.

Any new primitive has a low security assurance, initially. If it is 
intensively analysed, and nobody finds a flaw, then over the years, people 
gain confidence in the primitive -- i.e., it collects security assurance. 
But that takes years, at best -- why, do you think, did the AES- and the 
SHA-3 process take so long? (And note that these two where extremely 
prominent and did attract the top cryptographers -- I am not quite so 
optimistic for PHC candidates, especially with the ongoing CAESAR 
competition ...)

> Anyway, I think applicability for GPU password strengthening should be
> one of the criteria used by the PHS judges.

Definitively!

So long

Stefan

------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
     <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
--Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--

Powered by blists - more mailing lists