# Does it make sense to stretch non-keys?

I was thinking about stretching salt.

Key-stretching is good against brute force guessing and assumes your system isn't compromised.

Salting a one-way makes it so you have to compute * n for each password and assumes your system is compromised.

Assuming the system is compromised, derived salts are found, static keys are found, would it make sense to stretch anything at that point?

-

When using a salted, key-stretching KDF, like PBKDF2 or scrypt, you are in effect stretching both the salt and the password. That is to say, what you're calculating is

$$\rm key = KDF(password, salt)$$

where changing either of $\rm password$ or $\rm salt$ requires the slow $\rm KDF$ function to be entirely recomputed.

In fact, if changing the salt did not require repeating the entire key derivation process, this would significantly reduce the effectiveness of the salt: instead of requiring $t \times n \times m \times k$ time to test $n$ passwords against $m$ hashes with a KDF iteration count of $k$ (with one iteration taking about $t$ time), the ability to easily change the salt would allow an attacker to carry the same attack out using only about $t \times n \times (m + k)$ time.

In particular, contrast this with extract-then-expand style KDFs like HKDF, used for deriving multiple keys from a single original key or password, which have the general form:

\begin{aligned} \rm PRK &= \rm KDF_{extract}(password, salt) \\ \rm key_{\it i} &= \rm KDF_{expand}(PRK, info_{\it i}) \\ \end{aligned}

where ${\rm info}_i$ is a unique string identifying the purpose for which ${\rm key}_i$ is being derived. One of the advantages of this kind of KDF is that, whereas $\rm KDF_{extract}$ needs to be slow if used with password inputs*, the $\rm KDF_{expand}$ function can be fast, allowing many keys to be efficiently derived from one password.

The important thing to note here is that, as a consequence, the salt and info strings play very different roles: the salt can and should be varied to reduce the effectiveness of parallel brute force attacks on multiple passwords, whereas varying the info strings offers no such protection, since changing the info string does not require recomputation of the slow extract phase.

(*: Note that the extract function defined in the HKDF standard is not slow, and should not be used for password-based key derivation. However, the standard does include a provision for effectively replacing the extract function with any other source of uniformly distributed pseudorandom keys, such as PBKDF2.)

-
Thanks Ilmari, what does PRK stand for? –  Andrew Hoffman Dec 5 '13 at 18:41
@Andrew: "pseudorandom key". It's basically what the HKDF standard calls the output of the first KDF stage. It's not a particularly informative name, but I figured I'd follow their example, since I couldn't think of anything better either. –  Ilmari Karonen Dec 5 '13 at 19:20