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

[Bill Cox <[e-mail]>]

I think the CFRG should feel free to move forward with Agon2i and Argon2d,
once the authors address the recent TMTO against Argon2i.  You have
convinced me that bringing up alternatives like Argon2id muddies the
waters, and should be avoided for now.

On Mon, Feb 15, 2016 at 8:06 AM, Joel Alwen <[e-mail]> wrote:

> > 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?)


I think the recent paper on Scrypt <http://eprint.iacr.org/2016/100.pdf> is
applicable to both Argon2d and Argon2id in terms of off-line defense
without side-channel data.  AFAIK, there has been no formal analysis of
hybrid-MHFs like Argon2id.


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

Actually, with t=1, Argon2id fills the first half of memory in a
side-channel resistant manner, and the second half in an unpredictable
data-dependent manner.  The CC metric when attacking Argon2id would be
somewhat lower than Argon2d, since less memory could be used in the first
1/2 of memory, but the difference is a small constant factor, since the
second half of memory is required just the same as Argon2d.

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

I agree.  Generally I prefer a single-pass algorithm when using
data-dependent MHFs, though Yescrypt has an interesting mode where only a
partial second pass is done.


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


In most applications, I agree t should be 1 for data-dependent MHFs.


> However if t=1
> then Argon2id collapses to Argon2i


This isn't quite right, since both iMHF and dMHF are done in one pass.


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

I agree.  In particular, I would be surprised to hear that someone finds an
attack on 1-pass Argon2d or Argon2id that is better than O(m^2) CC
complexity.  Lowering memory by more than about 8X results in having to
recompute a significant fraction of all prior memory for each new block
computed, so I do not see how to avoid O(m^2) memory*time.


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

There is clearly still work to be done here.  I have yet to see a
compelling iMHF that combines both high TMTO resistance and high
performance.  However, I would be surprised to see more than a constant
factor improvement vs Argon2i, assuming it is changed to XOR over memory in
later passes.

I wrote an automated pebbler
<https://github.com/waywardgeek/twocats/tree/master/tools/pebble> to
guesstimate the hardness of the different iMHFs.  It might be due to flaws
in my pebbling algorithm, but Gambit's simple memory access pattern worked
best to defeat my pebbler, and it already XORs over memory.  I would swap
out the Keccak sponge for the much faster one used in Lyra2, but once
that's done, Gambit seems both simple and resistant to TMTOs, though I have
no proof of it's superior resistance.  It seems like a good algorithm, but
I would not recommend it without more analysis that has been done to date.

Bill