Re: [Cfrg] Security analysis of scrypt

[Bill Cox <[e-mail]>]

On Wed, Feb 10, 2016 at 10:52 AM, Salz, Rich <[e-mail]> wrote:

>
> > http://eprint.iacr.org/2016/100.pdf
>
> 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