I'm considering using a key-derivation scheme for generating multiple keys from the same user secret. It is important that given all but one of these derived keys, it is not feasible to calculate the last one. Tunable difficulty would be a big plus.

Is there such a function, or set of functions, that are safe to use in parallel on the same secret?

This is not a duplicate of this question because I do not have any way to store a client-side salt between different devices. Using a constant would work, since that can be stored in the source code, e.g. sha256(user_secret + "first_static_salt"), but I have no idea if such a scheme would be secure. I also don't have the same parameters and same key derivation function requirements of that question. Using three different functions would work fine for me.

EDIT: I only have the user password for entropy. Any user-specific salt used would have to be stored on a server, which means that it would be known for all parties involved (unless you encrypt it with the user password...).

The goal here is to hide sensitive data from the servers; they only need metadata to function properly, so there's no reason to send sensitive data through them. The current setup would use two different keys, one for authenticating with the servers, and one for encrypting/decrypting the actual data. Most servers would just push around uuid's, and these uuid's would be used to access a separate system where the actual sensitive encrypted data is stored. The client would then interact with these two separate systems.

  • 3
  • 2
    $\begingroup$ The trivial answer would be: Use HKDF with appropriate (constant) personalization strings, this is the standard solution if you have a high-entropy master secret. If you don't then use your preferred PBKDF (-> Argon2) and use a constant (different) salt for all derivations. So, for an answer we need this info: Do you have a high-entropy master secret or not?. To be clear: A high-entropy MS would be 16 bytes from a true random number generator, a low-entropy MS would be a password or something along those lines. $\endgroup$
    – SEJPM
    Jun 23 '16 at 11:34
  • $\begingroup$ @SEJPM clarified. The only secret is the user password. Any salt would be known to the server (unless we encrypt it, with the user password...). $\endgroup$ Jun 23 '16 at 11:54
  • 1
    $\begingroup$ Two more questions: a) would you prefer not to store salts (16 bytes per user + overhead) on the server (for cost reasons) with marginally weakened security? and b) does each user have a unique identifier (e.g. user name, log-in name or something) which he is aware of? $\endgroup$
    – SEJPM
    Jun 23 '16 at 12:04
  • $\begingroup$ a) I would prefer not storing salt on the server because of the extra round trip time required to fetch it; each login attempt would require a double round trip. b) Good catch, each user has their userid/email when logging in. That could be used as a user-specific salt, if I only allow a single userid per user (that is, no email/phone/username combination login like facebook). $\endgroup$ Jun 23 '16 at 12:13

You need to split this up into two separate problems:

  1. you may have a low entropy password (as you indicate you want to have "tunable difficulty");
  2. you need the keys of a specific user not to reveal any information about the password or the other keys.

Lets solve this in two steps:

First you need a salt and a work factor or iteration count. You can do this by choosing a secure password hash or Password Based Key Derivation Function (PBKDF). Passable options include PBKDF2, bcrypt, scrypt and Argon2 (ordered from standardized/available to secure).

You've indicated that you worry that the server knows the salt. This is however not a problem as a salt may be a publicly known value. The salt is mainly used to assure that:

  1. you cannot search all the password hash results of the separate users using a single salt until you find a match;
  2. you cannot find indications of duplicate passwords by looking at the password hash results.

OK, so now you should have a secret that depends on the password and the publicly available salt. It is possible to simply create create a large secret and split that up into multiple keys. The output of the PBKDF should be indistinguishable from random so as long as you don't mistakenly have an overlap between keys the keys should be independent of each other.

It is however much nicer to use a Key Based Key Derivation Function (KBKDF) such as HKDF for this step. You would then use the result of the PBKDF as key for the KBKDF. In that case you can use a label for each key, e.g. Authentication_key and Data_encryption_key. Those keys would both depend on the master key, but they would otherwise be independent of each other.

  • $\begingroup$ a) may I ask you to swap the order of your PBKDFs, because atm it's from worst to best? b) The gripe with the server-stored salt is not about publicness but about another needed round trip to fetch it at log-in $\endgroup$
    – SEJPM
    Jun 23 '16 at 12:50
  • $\begingroup$ Hmm. That doesn't feel like terribly good reason (it was given as comment after I created the answer, my save button didn't work). I'll fix the order of the PBKDFs. $\endgroup$
    – Maarten Bodewes
    Jun 23 '16 at 12:52

I'll quickly summarize your situation as a TL;DR:
You provide a service, using your server, which requires users to get a key, which is identical across devices, without wanting the user to fetch a salt from the server for each log-in and you're only given a low entropy secret to derive a (somewhat) secure key.

Safely deriving keys from passwords requires a few things: A unique salt, a password / passphrase (don't block those!), an implementation of a good PBKDF and (finally) a specific amount of work you're willing to spend for derivation.

  • The password is supplied by the user.
  • The salt is more difficult here, but you could use a fancy combination of the user's log-in name (e.g. his e-mail, his username or something like that) and a hardcoded constant for each derived key. So you'd essentially run the PBKDF with the password, the workload, and the same identifier but with different constants for all the keys you need. You'd have to ensure though that the log-in name is unique (but you need to ensure that anyways to create a usable log-in system).
  • The password-based key derivation function (PBKDF) should be one of the well-established ones, e.g. Argon2, bcrypt or scrypt and if everything else fails PBKDF2.
  • Finding the appropriate workload is also difficult. Ideally you want to put it as high as you can afford, but as you seem to operate on a multitude of platforms this may prove rather difficult and you should do wide-ranged testing if possible (especially on the lower end of your target market of devices) to ensure it runs reasonably well everywhere while not being "too cheap". If you can store the parameters on a per-user basis (I assume you can't) then you could also do some measurements on a per-user basis and use this.

As Maarten proposed in his answer, chaining a PBKDF using the unique identifier and HKDF using an appropriate hard-coded constant for each different key would be a good instantation of "fancy combination" and woul allow you to tune security parameters even higher.

Additionally, please note that using any of the mentioned KBKDFs / PBKDFs, it is completely impossible to find anything out about other keys or the master key without brute-forcing it (which the PBKDF makes significantly harder).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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