Are there key-derivation functions that are safe to use in parallel on the same secret?

Question

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.

Answer 1

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.

Answer 2

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).