Re: [Cfrg] Memory-efficient evaluation of data-independent memory-hard functions

[Joel Alwen <[e-mail]>]

> I would stick to Argon2id, which offers some protection against 
> certain cache-timing attacks, but still leaks meta-data such as 
> whether or not the user who is authenticating has been seen before.

Which type of timing attacks does Argon2id protect against? (Is there
any where I can read more about timing attacks on Argon2 or other
dynamic MHFs?)

> AFAIK, Argon2id has the same memory*time defense as Argon2d, so it 
> seems like a no-brainer to use Argon2id rather than Argon2d, IMO.

I think for the same memory-cost parameter and passes over memory
Argon2d would actually be (at least somewhat) more memory-hard than
Argon2id. In particular the first pass over memory of Argon2id would
still be susceptible to the Argon2i TMTO attack. So "Argon2d level
security" only holds for subsequent passes. In contrast for Argon2d it
holds from the get-go.

There is a trade-off here. The more passes over memory the smaller the
security gap between Argon2id and Argon2d. However this also decreases
any added cache-timing attack resistance Argon2id has over Argon2d.
Moreover it makes the MHF less efficient in terms of
memory-hardness/computational-cost.

Put differently for memory-cost m and number of passes t the runtime
(i.e. computational cost) is about m*t. But the cumulative memory
complexity is (ideally) m^2*t. So to maximise
memory-hardness/computational-cost we really want t=1. However if t=1
then Argon2id collapses to Argon2i so we would only get about m^{7/4}
memory-hardness. In contrast, with Argon2d I believe we would get much
closer to m^2 memory-hardness.

So basically I would only recommend Argon2id over Argon2d for
applications that are willing to tolerate a low through-put MHF.

TBH, I don't yet see a great solution when timing-attacks are a concern
but we also want large memory-hardness for minimal computation.

- Joel