Message-ID: <20150430155505.GA25385@openwall.com>
Date: Thu, 30 Apr 2015 18:55:05 +0300
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Maximising Pseudo-Entropy versus resistance to Side-Channel Attacks

On Thu, Apr 30, 2015 at 02:43:45PM +0200, Stefan.Lucks@...-weimar.de wrote:
> Except that there is no law that requires defenders to publish their 
> password files. Given past experience, it would be unwise for the defender 
> to assume the password file will never be compromised. For this reason, the 
> defender must use a good password hash function. On the other hand, is 
> would be just as unwise to assume that the password file will actually be 
> compromised. Without knowing the password file, Mallory would be back to 
> on-line attacking the defender's system. The point I am trying to make is 
> that in such a situation, a password hashing function being vulnerable to 
> side-channel attacks would be a terrible choice.

While you're mostly correct, you're somehow omitting important detail.
As discussed before, salting may defeat side-channel attacks on password
hashes, as long as the salts are not known/predictable by the attacker.
In your example, "without knowing the password file, Mallory would"
typically also not know the salts, so would not be able to mount a
side-channel attack.

A notable exception, as pointed out by Krisztian before, is what happens
when you offload hash computation to the client.  In that case, you'd
usually reveal the salt of the target user to the client system.
Another user of the client system could then mount a side-channel attack
there (by also obtaining the salt from the server via the same means).

Similarly, if full hashing is sometimes performed on the server (e.g.,
for clients that lack the custom software), then support for client-side
hash computation could be used to retrieve salts for mounting side-channel
attacks from another (pseudo-)user account or VM on the server.

It's primarily this special case that warrants use of side-channel
resistant password hashing schemes.  Indeed, it may be safer to use them
unconditionally, e.g. in case client-side hash computation would be
added to a given setup later.

> Even if the defender does not really understand how Mallory might mount a 
> side-channel attack against H1, choosing H1 for the marginal gain of a ten 
> times better performance could be a fatal move, if H2 is resistant to 
> side-channel attacks. The most serious issue are cache-timing attacks, 
> but one should also consider garbage collector attacks, and possibly other 
> attacks as well.

This is right.  However, a relevant question is: are we focusing on
avoiding unlikely yet potentially fatal special cases, or are we trying
to reduce the percentage of passwords that will get cracked in a more
likely case?  I expect that answers will vary.

> (Note that the situation for password-based key derivation, is different. 
> There, can hardly exclude Mallory from performing off-line attacks. Except 
> when Mallory doesn't have the ciphertext -- but then, why should Mallory 
> care for the key or the password at all?)

Right.  However, garbage collector attacks do matter for KDF use,
perhaps more so than for password hashing use.

> The consequence for PHC?
> 
> If PHC selects a single winner from one of the finalists, it should either 
> be Argon2i or Catena. If PHC selects more than one winner, the set of 
> winners should include at least one of Argon2i and Catena.

This appears to be the case.  I think it was understood by most (or at
least by many) panel members at finalists selection that unless a fatal
flaw is found in Catena, it will most likely be a winner.  (We didn't
expect a tweak to the extent of Argon2i, and it's still not accepted.
But it might be accepted soon.)

Personally, I would probably not recommend a side-channel resistant PHC
winner for most use cases at least in the nearest future.  I think I'm
not alone at that.  So if it's the only winner, then we should expect
greater use of non-PHC schemes.  (Argon2 has advantage here: it's two
complementary schemes at once.  OTOH, it is in need of further tweaks.)

BTW, it might be more than a 10x difference in GPU attack resistance at
low defensive running times (such as for achieving high request rate
capacity on a server).  First, there's a 3x difference in running time
for same memory usage (for Argon2d vs. Argon2i recommended minimum
t_cost).  Then, there's exclusion of anti-GPU measures such as rapid
secret-dependent S-box lookups, which potentially means up to the peak
GPU/CPU performance ratio (if the defensive running time is limited such
that the memory usage is very low).  Maybe a hashing scheme could
introduce rapid secret-independent S-box lookups, which maybe would
nevertheless be of some anti-GPU effectiveness.  But the confidence in
that would be lower, and we don't have it in PHC currently.

For Litecoin, which is scrypt at 128 KB and thus does include
secret-dependent lookups (just not good enough ones), the GPU/CPU
performance ratio is more like 20x.  Yes, scrypt is susceptible to
efficient TMTO, whereas Catena and Argon2i try not to be, but those
Litecoin GPU miners use a low TMTO factor - typically 1/2.  It just
happens to be optimal for them.  So Catena and Argon2i may be just as
susceptible to the ~20x attack performance ratio at low m_cost.
Frankly, Argon2d too, which is why I proposed a tweak to it.

Alexander

Powered by blists - more mailing lists