Re: [Cfrg] Balloon-Hashing or Argon2i.

[krzysztof pietrzak <[e-mail]>]

I'm following the discussion going on here with some astonishment. The
Argon2i iMHF is asymptotically broken, and whether an asymptotic
attack is practical with current parameters/hardware should only be of
interest if a scheme is already widely deployed and we have to live
with it, but pushing for standardisation of a mode that is known to
have structural deficiencies is -- in my opinion -- just irresponsible
and could hurt our field.

This is not to say that the Alwen-Blocki attack [AB16]
https://eprint.iacr.org/2016/115.pdf is not already practical, the
arguments brought forward against the practicality of the attack have
been convincingly refuted in [AB16b]
https://eprint.iacr.org/2016/759.pdf . The fact that Argon2i has
become a moving target changing its specification constantly doesn't
look good either.

Bill Cox writes
"To summarize what I think should happen here: I recommend continuing
with any standardization effort that would have gone forward without
the published TMTO attacks that claim to save power while recomputing
values many times.  Intuitively, it is simply less power to store and
reuse results than recomputing them, which turns out to be true in
real ASIC implementations."
If this was true (i.e., we only must consider adversaries who don't
recompute values), then constructing secure iMHFs with optimal
parallel cumulative memory complexity \Omega(n^2) would be a
triviality (e.g. make 2 passes over memory updating
x[i]=f(x[i],x[i-1])). The entire point of [AB16b] is showing that this
intuition is also wrong for the [AB16] attacks.

At this point it seems all the iMHFs submitted to the password hashing
competition are broken, which maybe is not too surprising given that
the call for submissions didn't even specify a formal security notion
the mode has to satisfy, a property like

"Speed-up or other efficiency improvement (e.g., in terms of area-time
product per password tested) of cracking-optimized ASIC, FPGA, and GPU
implementations (checking multiple sets of inputs in parallel)
compared to CPU implementations intended for password validation
should be minimal."

is not something cryptographers can work with. To me the competition
looked more like a beauty contest, where due to lack of a meaningful
security notion the submissions were focusing on secondary properties
and features, rather than on provable security guarantees their modes
provide.

Only in [AS15] this desirability from the call has been captured by a
formal notion -- cumulative parallel memory-complexity (cpmc) -- a
good MHF should (1) have cpmc close to n^2 (so it is memory hard) and
(2) its sequential space-time complexity (sstc) should be close to its
(cpmc), so paralellism and armortization doesn't make the evaluation
much cheaper.

With a formal security notion at hand, there has been a lot of
progress in understanding MHFs in the last year. For data independent
MHFs we now know that already the first proposed MHF -- Scrypt (or
rather RoMix) -- has optimal \Omega(n^2) cpmc (assuming the underlying
building block is a random function, an assumption like that is
necessary as we can't prove superlinear circuit lower bounds). This
result has been announced recently
https://pariscryptoday.github.io/second.html#LR

The situation for data independent MHFs (iMHF) is even more
interesting: an iMHF has high cpmc if and only if the underlying
evaluation graph is depth-robust (also this result is not published
yet, it has been announced
https://calendar.csail.mit.edu/events/171401 and a manuscript exists).
Thanks to this connection, we understand quite well how the graph
underlying a good iMHF must look like, and already have constructions
with cpmc \Omega(n^2/log(n)) (which is within loglog(n) of the
theoretical maximum). This construction is non-constructive (in the
sense that one has to sample a graph at random, and this graph will
constitute a good iMHF with overwhelming probability). We also have
extremely simple and efficient explicit constructions, but the proven
cpmc is a log(n) factor off the optimum (it is optimal modulo a
combinatorial conjecture which we believe to hold).

I guess it is in everyones interest to come up with a secure proposal
for MHFs, and simply ignoring all the cryptographic knowledge we now
have on how to (not) construct MHFs is just ignorant and dangerous.

Krzysztof

> Subject:        Re: [Cfrg] Balloon-Hashing or Argon2i.
> Date:   Thu, 11 Aug 2016 09:20:28 -0700
> From:   Bill Cox <[e-mail]>
> To:     Dmitry Khovratovich <[e-mail]>
> CC:     [e-mail] <[e-mail]>
>
>
>
> To summarize what I think should happen here: I recommend continuing
> with any standardization effort that would have gone forward without the
> published TMTO attacks that claim to save power while recomputing values
> many times.  Intuitively, it is simply less power to store and reuse
> results than recomputing them, which turns out to be true in real ASIC
> implementations.