Re: [Cfrg] Security analysis of scrypt

[Stefano Tessaro <[e-mail]>]

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

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