[messaging] Reliable Security Estimates for Key Stretching

[Taylor R Campbell]

   Date: Tue, 2 Jun 2015 17:03:28 +0200
   From: Nadim Kobeissi <nadim at nadim.computer>

   What are reliable methods to estimate relative added bits of
   security via key stretching algorithms such as scrypt?

A reasonable metric to begin with is area-time complexity.  See, e.g.,
<http://cr.yp.to/nonuniform/nonuniform-20130914.pdf>, particularly
Appendix A and its citations.

Each guess has a certain AT cost to check:
- if it is memcmp(MD5(pw), hash, 16), the AT cost is very low;
- if it is memcmp(MD5(MD5(MD5(pw))), hash, 16), the AT cost is a bit more;
- if it is memcmp(scrypt(pw, n=2^20, r=8, p=1), hash, 32), the AT cost is
much higher.

If the AT cost for a probability of success p in an attack is about
p*2^(n + k), where there are 2^n possibilities for the password each
with equal probability, then you might say the key-stretching provided
k additional bits of security.  (Beware password spaces with non-
uniform distribution: here n is really the min-entropy of the password
space, and if humans are choosing the passwords in their heads, it's
usually very, very small.)

The AT cost is a pretty good approximation to energy and dollar
requirements of attacks.  But there's another dimension, which is how
much advantage different kinds of hardware can have.

Memory-hard algorithms such as scrypt are designed to make the
computation on high-memory general-purpose computers -- as defenders
typically have -- closer to the optimal AT, and make the computation
on high-parallelism computers -- e.g., clusters of GPUs or FPGAs, as
attackers typically have -- farther from it.

The usual way to quantify this is to identify the equivalent cost of a
unit of memory in units of time on a single core for an algorithm.
For scrypt, if I recall correctly, it is something like M ~ T^2 --
that is, a unit increment in memory is equivalent to spending twice as
much time on a single core, or to using twice as many cores in the
same time.  For lyra, it's more like M ~ 2^T -- that is, a unit
increment in memory is equivalent to spending the square of the time
on a single core.

I'm not aware of any formal literature on the subject, though, outside
the scrypt and lyra papers themselves.