Subject: Re: [Cfrg] Balloon-Hashing or Argon2i.

From: krzysztof pietrzak <[email-masked]>
Date: Sun, 14 Aug 2016 19:36:13 +0200

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 <[email-masked]>
> To:     Dmitry Khovratovich <[email-masked]>
> CC:     [email-masked] <[email-masked]>
>
>
>
> 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.

---

From: Andy Lutomirski <[email-masked]>
Date: Sun, 14 Aug 2016 12:08:47 -0700

> become a moving target changing its specification constantly doesn't

I agree.  The IRTF should recommend the use of an algorithm with strong
provable security, especially when such an algorithm seems to be imminently
available.

--Andy

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Mon, 15 Aug 2016 05:20:17 +0000

IMHO when saying "all PHC candidates are broken" (and Balloon too) this
post confuses two things

- a made-up theoretical asymptotic security notion

- security notions that make sense in the real world (I hate this term
though)

A suboptimal performance wrt the former doesn't mean "broken" wrt the
latter.

Some people crack passwords for a living. Ask them what they think of the
first notion :)

And wrt the second notion, none of the PHC candidates are broken, as will
tell you any security engineer that had to develop real systems that work
and are used.

In the same spirit, I've often heard members of the theoretical crypto
community arguing "I don't understand why AES is used, there's no security
proof and it's only heuristical security." Well then.

On Sun, 14 Aug 2016 at 19:43, krzysztof pietrzak <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Stefano Tessaro <[email-masked]>
Date: Sun, 14 Aug 2016 23:17:53 -0700

Hi Jean-Philippe,

> proof and it's only heuristical security." Well then.

I don't want to be nitpicking too much, but this is different. There
may be no security proofs for AES, but there are well-defined security
notions (concrete, not asymptotic) for which AES is not broken, and
these notions are pleasing both for applied and (practice-oriented)
theoretical cryptographers. One should probably differentiate between
different types of theoretical cryptographers --many of us here on
CFRG are completely comfortable with assuming AES satisfies a wide
range of properties.

Rather, an analogous situation to the AB16 attacks in this context
would be if we (hypothetically, for the sake of example) had a
O(2^{3/4n}) key-recovery attack against a generalized parameterized
version of AES with key and block length n, and we were debating
whether the hidden constant is smaller than 2^{40} for n = 128 on a
realistic real-world parallel architecture. It is not the type of
question with an easy answer.

Concretely, for memory hardness, I think there are two questions:

= Are the metrics in the [AB16] attacks realistic or not? If not
(which seems to be the claim), can we state precise metrics that would
be appealing to practitioners and that theoreticians can work with? I
don't think the issue is asymptotic vs concrete (every number can be
interpreted as a function of n or as a concrete value), but rather
*what* is being measured.

= Given a concrete metric we can all be happy with, can we translate
the [AB16] attacks into these metrics, and can they be optimized for
appropriate concrete parameters?

Note that I have no stakes in the attacks here, even though I do work
on proofs for memory-hard functions. Still, I would just prefer
important ideas (on both fronts) not to get lost in translation, as
progress seems to be constantly happening on both fronts, and the
theory community is gaining increasing interest in memory hardness.

If we end up with constructions as simple as Argon2i, but with
provable security in a meaningful metric, I don't quite see the harm.
(And we do have proofs for scrypt/Argon2d already.) It would be great
however to agree on such metric.

Best,
Stefano

-- 
Stefano Tessaro
Assistant Professor of Computer Science
University of California, Santa Barbara
http://cs.ucsb.edu/~tessaro/

---

From: Bill Cox <[email-masked]>
Date: Mon, 15 Aug 2016 07:34:53 -0700

On Sun, Aug 14, 2016 at 11:17 PM, Stefano Tessaro <[email-masked]>
wrote:

> be appealing to practitioners and that theoreticians can work with?

Correct, I do claim they are unrealistic.  I like their quality measure:
total energy.  The problem is their model was simplified too much.  In
particular:

1) The energy in DRAM is dominated by the high-speed interface
<http://people.duke.edu/~bcl15/documents/malladi2012-micro.pdf>.  Adding
additional size to the DRAM increases power slightly, and not at all
proportionally.  Storing data in a tiny capacitor continues to be super
efficient in terms of power in general.

2) There was no model for the power required for parallel cores to
communicate between them, and as a die gets large (they assumed up to
500mm^2), this power will dominate in their attack.

The right approach to analyzing ASIC attacks is to iterate with the ASIC
design community.  Every new model is an advance, but to make them more
effective we need to adapt them to make them more realistic.

I strongly agree with Jean-Philippe Aumasson above.  Any theoretical notion
of security needs to be tested fleshed out and tested in more realistic
attacks.  Any realistic ASIC attack will have to specify H.  We'll hear
about how the attacker takes advantage of deep pipelining and interleaving
to do multiple attacks in parallel more efficiently.  We'll hear about
custom cache architectures.  We'll also hear about exactly how data will
get routed between cores, and all of these various components will have
size and power estimates.

I have worked with ASICs for many years, but I do not consider myself a
world-class expert in ASIC design, nor am I familiar with changes in ASIC
design in the age of fin-fets.  However, I would be happy to help flesh out
more realistic attacks for anyone who wants to see how their model might
work in a real ASIC attack.

Bill