Date: Tue, 2 Jun 2015 17:03:28 +0200 From: Nadim Kobeissi <[email protected]>
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. _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
