[messaging] Reliable Security Estimates for Key Stretching
Taylor R Campbell
campbell+moderncrypto at mumble.net
Tue Jun 2 12:36:27 PDT 2015
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.,
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
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.
More information about the Messaging