Re: [Cfrg] Balloon-Hashing or Argon2i.

[Stefano Tessaro <[e-mail]>]

Hi Jean-Philippe,

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

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/