Subject: [Cfrg] Tight security proofs for practical memory-hard password-hashing

From: Joel Alwen <[email-masked]>
Date: Tue, 20 Sep 2016 15:02:29 +0200

Hi,

Recently Jeremiah, Krzysztof and I put some new results on eprint which
have some relevance to the push for a new memory-hard password-hashing
function.

https://eprint.iacr.org/2016/875

To help put the results in context I wanted to clarify what my take on
the concrete relevance is to the CFRG efforts in this direction are.

The paper, in general, concentrates on fleshing out / improving on some
of the theory in this area so that stuff is maybe not of direct interest
here (for the curious: see bottom of email for more info on those results).

However one contribution that I hope is more directly relevant to the
CFRG's concerns are a pair of new proof techniques for getting (certain
types of) provable memory-hardness for iMHFs. These techniques are FAR
easier to understand, work with, and easier to adapt to different
constructions, hardness notions and computational models than the
techniques used in the AS15 paper. The techniques are also tight enough
that they (can) give us really exact (non-asymptotic) security
statements. Basically they are both easy and powerful enough to use that
we can directly analyse very practical constructions (even ones not
designed with these proof techniques in mind).

As evidence we used these two techniques to show provable
memory-hardness for Argon2i-A (the PHC winning version of Argon2i.),
Balloon Hashing and Catena. Unfortunately, (though unsurprisingly given
AB16 and the new attacks in this work) the statements we prove are
really not anywhere close the memory-hardness we've been hoping for up
till now. But they do show how these techniques can be used for
algorithms we care about in practice.

Another way to think about this paper is that we now have two new simple
design criterion for an iMHF either of which automatically gives us
(certain types of) provable security. I'm willing to wager we will soon
see otherwise practically competitive iMHF constructions enjoying
security proofs using one of these techniques.

As usual, feedback, questions and criticism are very welcome. I'm all
ears people. :-)

- Joel

PS. For those who are interested what the new techniques are: in a
nutshell the most important one can be understood like this. We show
that analysing the "depth-robustness" of an underlying (graph
characterizing the) mode of operation of an iMHF automatically gives
very tight lower bounds on the memory hardness of that mode of operation
in an ideal compression function model. By "tight" I mean whatever we
know about the depth-robustness of the mode of operation translates
exactly (not asymptotically) and with a very small loss in constants
into a proof of memory hardness in the ideal compression function model.
So to get a security proof for say Argon2i-A we now only needed to
understand its (say expected) depth-robustness.

PPS. For those interested what theory results we have. I'd say at least
two are worth highlighting as they relate to what we're doing in the CFRG.

1) We present a new class of attacks on memory-hard functions
generalizing AB16. We show that they get lower asymptotic memory
complexity for Argon2i (version 1.3 from the PHC), Balloon Hashing and
Catena when compared to AB16. But, in contrast to the AB16 attack, I'm
personally less clear on whether:
 - the hidden constants & low-order-terms can be made small
 - that the attack can be made to behave well using only moderate
(rather than unbounded) amounts of parallelism on random instances.
 - Nor have we had time to address recent great questions brought up on
this mailing-list about how routing overhead in the ASIC and memory
chips will affect the attack.
So for now I'd consider these new attacks to be a theoretical result
lacking solid evidence (one-way or another) for how they behave in
practice. Understanding their practically (be it to refute or assert)
would take a fair bit more work that just hasn't been done. Still, just
to be clear though: asymptotically the new attacks are pretty severe.

2) We give a new mode of operation over a compression function with
provable asymptotically optimal memory-hardness. However, at this point
its definitely still a theoretical result because a key component we use
in the construction is a particular graph (by Erdos, Graham and
Szemeredi) which just wasn't designed for ever actually being used in
practice. Its way too complicated and has horrible constants giving us
crappy exact security (at least using our current proof techniques). So
for now I'd say that result isn't per se interesting for the CFRG's
purposes. Still, I pretty convinced this is a step in the right
direction for us.
---------------------------------Snip--------------------------------

---

From: Joel Alwen <[email-masked]>
Date: Wed, 21 Sep 2016 18:05:01 +0200

> The very last open question on this paper says that it is not known
> whether scrypt is optimally memory hard. But in the introduction it
> is claimed, citing an unpublished manuscript, that this is indeed the
> case. So which is it? Is the open question referring strictly to the
> \pi_cc value which is not used in the "direct" proof of the
> manuscript?

Good catch, that part of the intro needs some fixing.

AFAIK here is what we do and don't know about provable security of
scrypt. First, by "full security" in this context I mean having
amortized-AT = Theta(n^2) amortized per instance even when given
arbitrary parallelism. (Notice that CC =< AT so lower-bounding
amortized-CC would be good enough.)

The two main results right now are the proof in the original scrypt
paper by Colin and proof in the Eurocrypt 2015 paper(eprint/2016/100) on
scrypt. Here's my take on why both fall short of full security in
several ways.
 - Both consider only a one-off cost, i.e. the memory-hardness of
computing a single instance; i.e. non-amortized. But when brute-forcing
passwords or solving a proof-of-work we compute many, even highly
correlated, instances. So ultimately an adversary does care about
amortized, not one-off cost.
 - The former proof is for AT complexity instead of CC like the later.
Unfortunately one-off AT really implies very little about amortized AT.
In contrast, (for these types of functions) one-off CC is probably a
better indicator for amortized-AT since intermediary hash values when
computing scrypt on distinct inputs are likely not compressible.
 - The former also assumes an upper bound on the amount of memory (and
parallelism) used by an adversary.
 - Both papers also assume that the next position in the memory array
needed by ROMix is chosen uniformly and independently of all previous
computation. This simplifies the proofs but in reality its actually
totally deterministic since it is fixed by the inputs and the choice of
hash function.
 - The former also (implicitly) assumes that the adversary does nothing
other then read and write intermediary hash values to memory. (No
encoding, storing partial values, XORing, etc.)
 - Finally the proof in the latter is based on an unproven conjecture
and only gets Omega((n/log(n))^2) instead of n^2 like the former.

So basically as far as I know scrypt is *not* known to be provably fully
secure. And, to be sure, I think it's a great (if surprisingly
difficult) open problem.

> A second question is whether the results on scrypt easily transfer to
> Argon2d, which is also up for standardization, along with Argon2i. A
> footnote on 2016/100 suggests that this is the case.

Actually this is probably the biggest reason I am personally interested
in proofs for scrypt. My intuition for why Argon2d should be memory hard
follows very much the same lines as to why I think scrypt is memory
hard. So whatever techniques we do develop for scrypt will hopefully be
easy enough to adapt to Argon2d (and other data-dependent MHFs). And
that would be awesome because there are other reasons to prefer Argon2d
over scrypt. At least for the Eurocrypt 2015 proof technique I think
this hope does play out. It's just that I don't see how to use that
technique to prove the type of "full security" I'd been hoping for. Thus
the explicit open problem for scrypt.

Why not go straight for Argon2d (or another dMHF)? If we can prove
something directly then great! It's just that ROMix is the simplest
algorithm I know of which tries to get memory-hardness via the
"unpredictable pointer chasing" technique also used in Argon2d so
(besides its comparatively wide deployment) I think this makes
scrypt/ROMix a good candidate to study.

> Also, somewhat of a nitpick, why refer to Argon2-A and -B instead of
> v1.0 and v1.3, which is (in my opinion, anyway) easier to
> unambiguously refer to the distinct Argon2 versions under study?

Yes, in retrospect you're right. I think we first introduced the -A / -B
notation as a quick & easy way to clarify amongst ourselves what we were
talking about. Those were the two versions we were most concerned with.
Of course, at the end we probably should have gone back and changed this
to something more like what you suggested. TBH, we just didn't think
about it. For any more formal (i.e. published / not eprint) version
we'll probably do this though.

- Joel