5
$\begingroup$

The scenario is like this: I need 2 keys for different purposes (encryption + encryption, encryption + mac, or whatever). Because it is not good practice to reuse the same key, I'd like the 2 keys to be independent. But remembering 2 different keys are cumbersome (don't question this please), so I think there should be some way to generate these keys from one common master key.

The closest crypto tool for this job I can find is a KDF. However, the KDF usually takes as an additional input: the salt. Should I randomly generate and remember a salt, or simply use a hash function such as SHA512 and divide its output into 2 keys?

I think in this scenario, there's no need to worry about the possible recovery of the master key from the derived keys, because the derived keys are no less important than the master key. The compromise of the derived keys is just as bad as that of the master key. The importance is instead focused on the independence between the 2 derived keys, since at least there are some encryption and mac schemes such that, when used together, would become totally broken if keys are not independent.

Improve this question
$\endgroup$
2
  • $\begingroup$ Is your master key a near uniform random string of bits, or at least does it have a distribution with high, ≫128-bit entropy? Or is your master key a password, which is likely to have a highly structured distribution in bit strings and perhaps to be chosen from a distribution with much ≤128-bit entropy? $\endgroup$
    – Squeamish Ossifrage
    Jul 14, 2018 at 1:24
  • $\begingroup$ @SqueamishOssifrage Currently we assume the master key is a randomly generated 128-bit. I think a block cipher in CTR mode should be good for key derivation if so. However, for usability reasons the master key may be changed to a master password, possibly shorter in length, with less entropy, and non-uniform. So I'd also like to know what should we do to enhance the key derivation in this case. $\endgroup$
    – Cyker
    Jul 14, 2018 at 4:51

3 Answers 3

Reset to default
9
$\begingroup$

  • The purpose of the salt is to limit the cost that an adversary can share between multiple targets. The salt need not be random. It need only be unique per user.

    If two users share a salt (possibly an empty salt), then the work to find at least one of their keys can be shared with Oechslin's rainbow tables on a parallel machine so that the expected cost to find at least one of their keys in a batch multi-target attack is about half the expected cost of a single-target attack, and the expected time to find at least one of their keys is at most one eighth the expected time of a single-target attack.

    In general, if there are $n$ possible keys, and $t$ targets, and you parallelize the computation about $p \geq t^2$, then the expected cost to find at least one is $n/t$ and the expected time to find the first one is $n/pt$, at most about $n/t^3$.

    If you use 256-bit keys, then the number of users necessary to make this significant is impossibly high, so you can safely use an empty salt in that case. The salt is important only for ≤128-bit keys. (This is why AES-128 should already be considered to have a <128-bit security level, and why you should use AES-256 anyway.)

    If you have a notion of a user id unique to a key, you could just concatenate it with the name of your application as the salt, with no need for storage. If you don't have a notion of a unique user id, using a random salt reduces the probability that the adversary can share work between two attack targets. The longer the salt, the lower the probability of a collision enabling the adversary can share work. Use a 256-bit salt, and there will never be a collision unless your implementation is broken.

  • A secondary purpose of a KDF is to map a high-entropy but possibly nonuniform secret into a uniform secret. If your master key came from a Diffie–Hellman key agreement and is the bit string encoding of some unique representative of a residue class modulo a large safe prime, or is the byte string encoding of a point on an elliptic curve, then the master key is not uniformly distributed among bit strings, but does have high entropy. A KDF smooths out the distribution on bit strings so it is effectively uniform.

  • The purpose of a password hash (scrypt, argon2, etc.) is to use all your available resources to drive up the cost of a single evaluation of the hash, which a brute force attack must do repeatedly. Willing to spend 1sec on hashing? Force the adversary to compute two million (say) HMAC-SHA256 computations instead of one for each guess. Willing to spend 1 GB RAM on hashing? Force the adversary to commit the area of 1 GB RAM in each parallel hashing circuit—which otherwise could have been dedicated to many more parallel hashing circuits if it were not memory-hard, like PBKDF2—or spend double the time hashing if they can only fit 512 MB RAM, etc. If you can't raise the number of possibilities for the secret, e.g. if your secret was chosen by a human, you can at least raise the cost of testing each possibility in a brute force attack.

These considerations apply independently:

  • Have a human-chosen password? Probably has ≪128 bits entropy. Use a password hash like argon2id with a salt to (a) drive up the cost of each guess, (b) map a nonuniform bit string into a uniform bit string, and (b) prevent the adversary from sharing work between multiple targets. Make sure if the user ever changes the password, the salt changes too, so if it's deterministically chosen, it can't just be an application name and user id—it must also include, say, a revision number.

  • Have a machine-generated memorable diceware password chosen from ${\sim}2^{128}$ possibilities? Use a KDF like HKDF with a salt to (a) turn a nonuniform bit string of 128 bits entropy into a uniform bit string, and (b) prevent the adversary from sharing work between multiple targets. Using a password hash to drive up the cost of each guess doesn't hurt if this is only ever used in an interactive application, but it's not necessary.

  • Have a shared secret encoding of an $x$ coordinate on Curve25519 from an X25519 key agreement, so that $x^3 + 486662 x^2 + x$ is a quadratic residue modulo $2^{255} - 19$? Use a KDF like HKDF to turn it into a uniform random bit string. Salting doesn't hurt in this case, but it's not necessary.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For map a high-entropy but possibly nonuniform secret into a uniform secret: Any chance we can do this without a salt? $\endgroup$
    – Cyker
    Jul 14, 2018 at 9:08
  • $\begingroup$ @Cyker I edited to elaborate. Does that answer your question? $\endgroup$
    – Squeamish Ossifrage
    Jul 14, 2018 at 14:13
3
$\begingroup$

Edit to add: (comment from SEJPM) $mk$ needs to be high-entropy (128 bit+ in practice).

If you believe in the random oracle model, then you don't need to remember any salt. Let $H$ be you KDF (modelled as a random oracle) and your master key be $mk$, then you can generate two keys $k_1=H(1\mathbin\|mk),k_2=H(2\mathbin\|mk)$.

If you don't like random oracle model, and assuming your master key is of the right size, you can use a block cipher as a pseudorandom function (PRF) and generate two keys $k_1=\mathit{PRF}_{mk}(1), k_2=\mathit{PRF}_{mk}(2)$.

As you have assumed the master key is private, then both methods should be fine. Both will give you independent keys (at least independent to the eyes of all computationally bounded adversaries).

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ One may want to note that for $k_1,k_2$ to be secure obviously $mk$ needs to be high-entropy (128 bit+) which is non-trivial for a human to remember. $\endgroup$
    – SEJPM
    Jul 13, 2018 at 14:25
  • $\begingroup$ @SEJPM Yes, you are right. I might have taken it for granted. Whenever I saw ``key'', it means to me a uniformly random string of enough length. But it might mean different things to others. $\endgroup$
    – Changyu Dong
    Jul 13, 2018 at 14:44
  • $\begingroup$ I actually prefer using a block cipher in counter mode. But as pointed out by Squeamish, if the master key doesn't have enough entropy or may not even be uniform, can we address this concern? $\endgroup$
    – Cyker
    Jul 14, 2018 at 4:37
  • $\begingroup$ @Cyker It is difficult. Anything derived deterministically from the master key cannot have higher entropy than it. What you can do though is to use some low entropy secret and interactive protocols to protect and retrieve a high entropy master key. For example, password protected secret sharing (see eprint.iacr.org/2010/561). $\endgroup$
    – Changyu Dong
    Jul 14, 2018 at 6:19
  • $\begingroup$ @ChangyuDong I think in this use case it'd be good enough if the derived keys are as secure as the master key. Put it another way, we only expect the derived keys offer the same level of protection as the master key, not more. However, I'm not sure whether the quality of KDF such constructed will severely degrade when not given enough entropy. $\endgroup$
    – Cyker
    Jul 14, 2018 at 6:24
2
$\begingroup$

Remembering one key is cumbersome, never mind two. A cryptographic key should consist of about 128 bits to be considered secure. Remembering a password or passphrase is hard enough. A password is not a secret / symmetric key as it doesn't consist of randomized bits.

There are basically two types of KDF. One is a KDF that uses a password as principal input material called a PBKDF: a password based key derivation function. The second is one that takes a key as principal input, called a KBKDF: a key based key derivation function.

Both a PBKDF and a KBKDF may take a salt, but a salt is much more important for a PBKDF. This is because otherwise the output of two identical passwords may be easily identified. Furthermore, without the salt, rainbow tables can be used to try and find the password. The strength of a key will also be weakened, especially if it is used many times, but the initial strength of a key is much higher than that of a regular password so the weakening will be less pronounced or not applicable for larger key sizes of 192 bits or higher.

A KBKDF may also take a salt, but it is mainly used to ease the proof for the KBKDF. If the input key does indeed contain enough entropy then the KDF should be secure without it. HKDF may take a salt as input and the HKDF standard contains a part on how the salt helps secure the output of HKDF-extract in chapter 3.1.

To derive two keys from a password the use of both a PBKDF and a KDF is the least brittle (by which I mean: the least likely to break if something is wrong with the PBKDF or KBKDF).

You'd get:

$$K_m = \text{PBKDF}(\mathit{work}, \mathit{salt}, \mathit{passphrase})$$ $$K_1 = \text{KBKDF}(K_m, \mathit{label}_1)$$ $$K_2 = \text{KBKDF}(K_m, \mathit{label}_2)$$ $$\ldots$$

that way you only require one salt, you perform key strengthening on the password and the keys $K_1$ and $K_2$ are independent. The password may be of any practical size. Of course it must still be relatively strong otherwise it may be brute forced or found using an (enhanced) dictionary attack.

If you want to use two modern implementations you can use one of the Argon2 variants as PBKDF and HKDF or HKDF-expand as KBKDF.

Note that the $\mathit{work}$ parameter may be include elements for the CPU work to be performed, the parallelism and possibly the memory hardness of the function. The $\mathit{label}$ is often part of a structure called $\mathit{OtherInfo}$ or just $\mathit{info}$ which may also contain other data that identifies or sets apart the output keys. Every standard may use slightly different parameter names and notation.

In principle, if you can actually remember a key then you can just use the KBKDF's, but that's highly cumbersome:

17a2ae1904debd903e090d5c7fb0a0e3

is a random key of 128 bits displayed as 32 hexadecimals.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Rainbow tables are not applicable only to password hashes. They are just as much applicable to functions of 128-bit secret keys like $k \mapsto \operatorname{AES128}_k(182378)$ or $k \mapsto \operatorname{HKDF}_k(\text{‘encryption subkey’})$. The cost of breaking the first of a million AES-128 keys is far less than $2^{128}$ AES computations because of this. The difference between password hashes and KDFs is not rainbow tables—it's whether we use additional resources to drive up the cost of a single function evaluation in a brute force attack. (This is why I advise against AES-128.) $\endgroup$
    – Squeamish Ossifrage
    Jul 14, 2018 at 1:19
  • $\begingroup$ Hello assuming the PBKDF function in use is not broken, is it helpful using an additional KBKDF than directly using PBKDF twice with 2 labels? $\endgroup$
    – Cyker
    Jul 14, 2018 at 5:08
  • $\begingroup$ Yes, because when you would use a PBKDF / password hash twice you would perform the key strenthening twice as well. This is basically work that an attacker and the regular user needs to perform. Worse, if the attacker can validate the password using just one of the resulting keys then the attacker has to perform only half of the work. $\endgroup$
    – Maarten Bodewes ♦
    Jul 14, 2018 at 10:57
  • $\begingroup$ @SqueamishOssifrage You are right of course, but with passwords the strength is supposed to be under 70 bits. I'm not directly remembering the algorithm (it is close but not quite the key size - 20 bits as 2^20 = 1Mi, lets assume 28 bits of security are lost), but for AES keys you would still need around $2^{100}$ tries right? That's still rather far out of the ball park. $\endgroup$
    – Maarten Bodewes ♦
    Jul 14, 2018 at 11:02
  • $\begingroup$ @MaartenBodewes Feasible today, probably not, but within the realm of possibility for human engineering? I think it is: crypto.stackexchange.com/a/58669/49826 But whether it's feasible or not, my point is that rainbow tables apply to the structure of AES just as much as to the structure of password hashes. The difference is in scale, not in applicability. $\endgroup$
    – Squeamish Ossifrage
    Jul 14, 2018 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.