Subject: [Cfrg] Security analysis of scrypt

From: Stefano Tessaro <[email-masked]>
Date: Wed, 10 Feb 2016 10:45:17 -0800

Dear CFRG,

We have just posted on eprint a preliminary version of our upcoming
EUROCRYPT paper analyzing the security of scrypt:

http://eprint.iacr.org/2016/100.pdf

We believe this may be of interest in a few ongoing CFRG discussions.

Best,
Stefano

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

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 10 Feb 2016 18:52:53 +0000

> http://eprint.iacr.org/2016/100.pdf

Got a one-paragraph summary that uses little words and small numbers? :)

---

From: Paul Grubbs <[email-masked]>
Date: Wed, 10 Feb 2016 13:59:23 -0500

Can your results be extended to Argon2d and/or Argon2i? If so, are you
planning on doing it?

On Wed, Feb 10, 2016 at 1:52 PM, Salz, Rich <[email-masked]> wrote:

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

---

From: Stefano Tessaro <[email-masked]>
Date: Wed, 10 Feb 2016 11:11:33 -0800

> Got a one-paragraph summary that uses little words and small numbers? :)

The main message is positive: We prove that Scrypt (in fact, more
precisely, its technical core, ROMix) guarantees a near-optimal
memory-time tradeoff in the strongest possible model in which such
proofs have been considered (this is the model recently introduced by
Alwen and Serbinenko). In particular, this model takes into account
parallelism and amortization (i.e., the fact that it should remain
hard to evaluate scrypt many times in a row, rather than just once).
Note that this is a stronger model (and hence, comes with stronger
guarantees) than the one used in the recent Balloon Hashing paper.

Slightly more technical caveats: The absolute statement is true only
for a restricted class of attackers (which however includes the
typical attacks one would think of, and beyond), and the full
statement requires a combinatorial conjecture.

Stefano

---

From: Stefano Tessaro <[email-masked]>
Date: Wed, 10 Feb 2016 11:21:21 -0800

> Can your results be extended to Argon2d and/or Argon2i? If so, are you

Given the analysis is essentially about ROMix, it should extend to
Argon2d. There are syntactical differences -- so we have been a bit
cautious about making a final statement about Argon2d in the current
preliminary version, beyond a footnote stating essentially what I am
writing here -- but we are planning to make explicit what is the
strongest statement about Argon2d we can get out of our techniques.

However, what is clear is that the results do not extend to Argon2i.
The point of this work was to focus on data-dependent designs, which
were not covered by the techniques from the paper of Alwen and
Serbinenko. The lower bound proof inherently relies on the
construction being data dependent, and there is no obvious way to
adapt it to something like Argon2i.

Stefano

---

From: Paul Grubbs <[email-masked]>
Date: Wed, 10 Feb 2016 14:36:06 -0500

Interesting. Thanks for the explanation.

Just out of curiosity, can you explain in a little more detail *why* the
proof relies on data-dependency, and in what step your techniques would
fail if applied to something like Argon2i?
(This is mostly for my own interest, so feel free not to answer if it would
take too long)

---

From: Bill Cox <[email-masked]>
Date: Wed, 10 Feb 2016 11:36:28 -0800

> Got a one-paragraph summary that uses little words and small numbers? :)

I read through the results, but skipped the mathematical proofs.  The
results are very cool.  Basically, the "cost" we typically use to rate
memory-hard functions is "memory*time", where an attacker must use M memory
for T time steps.  We generally assume Scrypt and related functions may
have a time-memory tradeoff, but that the memory*time security remains
intact regardless of the TMTO (though an attacker can gain a small constant
improvement: 4X in the case of Scrypt, smaller in the case of Argon2d).
IIUC, with some reasonable assumptions, they claim to prove that the
"cc(G)", which is the optimal "cumulative memory complexity" possible by
any attacker algorithm has a lower bound proportional to n^2/log^2(n).
Since cc(G) is a lower bound on memory*time, this fits closely with the
common belief that memory*time security goes as the square of the memory
for a data-dependent memory-hard algorithm, such as Scrypt and Argon2d.

This is why I prefer algorithms like Argon2d in applications where
side-channel resistance is not critical.  In the PHC, we were not able to
present compelling security proofs for the memory*time improvement in
data-dependent algorithms vs side-channel resistant algorithms, and in the
end, the judges were split, which is one reason Argon2 won, as it provides
both.  I found that generally, we see around 3X better memory*time defense
in data dependent algorithms when comparing one-pass algorithms, but
without a proof of the memory*time hardness of data-dependent algorithms, I
think there were a lot of doubters.

This is an excellent result, IMO.

Bill

---

From: Stefano Tessaro <[email-masked]>
Date: Wed, 10 Feb 2016 12:11:52 -0800

To be fair, to give credits where they are due, the idea to use cc in
the first place was proposed by Alwen and Serbinenko in their STOC '15
paper. They show memory-independent constructions in there that have
provably high cumulative complexity (cc). From a practical standpoint,
the issue is that those constructions are not as efficient as Argon2i
(and it's open whether Argon2i has a proof in that model). I know Joel
reads along, so he should feel free to go deeper into this.

To answer another question asked by Paul, briefly. The best
abstraction for the problem of evaluating memory-hard functions are
pebbling games on graphs. In essence, you can place a pebble on a node
if and only if all predecessors have a pebble on them -- this
corresponds to being able to compute a hash when you know all of the
preceding hash values you need. And you can remove pebbles at any
time. Alwen and Serbinenko show a very elegant connection between
finding the right graphs with high pebbling complexity and finding
good data-independent constructions that are secure in the parallel
random-oracle model. And they define good complexity metrics.

Now, the advantage you get with data-dependent constructions is that
you can think of the corresponding pebbling game as revealing the
graph little by little to you, and predecessors you need to pebble are
revealed to you as the game proceeds in a "randomized" fashion. The
point is that you can't prepare yourself for these in advance, and
this is instrumental in showing that evaluating something as simple as
scrypt or Argon2d is hard. Argon2i does not give you this benefit, and
you are back to the original framework of Alwen and Serbinenko, where
you know the whole graph to start with.

This makes finding provable data-dependent construction seemingly
easier. Technically, the price that we pay is that the connection
between such "randomized" pebbling games and an actual lower bound in
the parallel random-oracle model is less understood. That is where we
need our combinatorial conjecture. But one should also note that we
prove a lower bound in an extended model of pebbling games (we call
these "entangled pebbling games") which is probably enough to cover
"natural" adversarial evaluation strategies.

Stefano