[messaging] Reliable Security Estimates for Key Stretching

Daniel Kahn Gillmor dkg at fifthhorseman.net
Tue Jun 2 09:56:25 PDT 2015

On Tue 2015-06-02 11:03:28 -0400, Nadim Kobeissi wrote:
> What are reliable methods to estimate relative added bits of security via
> key stretching algorithms such as scrypt?
> This is fundamentally a shaky question, because the slowdowns given by key
> stretching are relative and measures in "seconds" depend on hardware. There
> is, however, some existing literature on the subject:
> "With simple iterated password hashing, a modern CPU
> can compute a hash function like SHA-256 at around
> 10 MHz [1] (10 million SHA-256 computations per sec-
> ond), meaning that if we slow down legitimate users by
> ≈ 2 ms we can add 14 bits to the effective strength of
> a password, and we can add 24 bits at a cost of ≈ 2 s." [0]

This is just a linear numbers game, right?

    ≈2ms :: ≈2s is a ratio of ≈1000

14 bits → 24 bits is a difference of 10 bits, and 2^10 ≈ 1000

So it looks like it's saying "if we slow down the user by a factor of X,
then we slow down an attacker by the same factor."

The assumption here appears to be that there is no speedup for an
attacker that is better than brute force.  If an attacker has some
clever precomputation, or a way to reuse intermediate results
efficiently, it seems like the slowdown for the attacker may be a
smaller factor than the slowdown for the user, unfortunately.


More information about the Messaging mailing list