Securely generating passwords based on a secret and a public identifier

I'm trying to create a good scheme for generating passwords in my systems management scripts. What I'd like to do is have a secret key (let's say hello123), which I keep only on trusted management machines. I'd then like to combine that with a "password identifier" (for example testing-db-pass), and produce some ASCII text that can be set as the password in the service's config.

I've read about key stretching, PBKDF2 and HMAC, and it seems like using bcrypt and passing hello123, testing-db-pass as the salt and key for those would work - but is that vulnerable to attack? Do I need to do something like HMAC-bcrypt? Is there a better way?

• What are your security goals? – Paŭlo Ebermann Jul 6 '13 at 11:14
• @PaŭloEbermann I'd like that the identifiers (like testing-db-pass above) and the algorithm be public information (i.e. on github). One secret - which I've realised should just be a large key kept in a file on the system administrator's machine - is then used to deterministically derive secure passwords for each identifier. This should be in such a way that compromise of one password doesn't help the attacker find any other password, despite knowing all the identifiers. – George Bashi Jul 6 '13 at 15:33
• I've implemented a deterministic password generator passassin.com which uses master-passphrase (which you could keep on your trusted machine, or in your head) and a site name. It produces passwords with commonly required numbers of capitals, digits, symbols, etc. – fadedbee Jun 13 '19 at 11:16

What I did in one of my password generators is that given a secret key $K$, public data $\text{Pub}$, I first generate a solid "master key" $K_m$ via key-stretching the secret key using PBKDF2 (any other key derivation function would work, I just happened to have that lying around):

$$K_m = PBKDF2(K, \text{salt, iterations, } \cdots)$$

And then derive individual secrets via $HMAC(K_m, \text{Pub})$ (formatting the result as required).

It is pretty straightforward, and secure, but there are a few sticky points that you need to look out for:

1. If your public data $\text{Pub}$ is aggregated from multiple sources (say, an identifier string + time + counter + version + other metadata), you must ensure you do not end up generating duplicate $\text{Pub}$ data from different original inputs (or you'll get the same derived password back, of course). For instance, do not concatenate strings to create $\text{Pub}$. Instead, hash them all, and concatenate the hashes. Formally, the "input data $\to \text{Pub}$" mapping must be collision-free. In practice this easily gotten wrong.

2. Make sure all your security parameters are properly set up (number of PBKDF2 iterations, strong hash functions are being used, all that stuff)

The advantage of using HMAC like this instead of just using PBKDF2 and messing around with the salt is that:

1. It scales - multiple derived secrets can be efficiently computed via a single PBKDF2 invocation, whereas your method would involve invoking the key derivation function for each derived password (which may be very slow, if you use a lot of iterations)

2. It is actually using the underlying cryptographic primitives properly. A key derivation function is not meant to derive a lot of individual passwords from a given secret key by changing the salt. See this question for details. This is not the case for HMAC, which is, in fact, supposed to be used like this, as its main use is to generate fingerprints of arbitrary messages with a cryptographic key (and of course you don't need to change the key at each message) .Of course, you would probably be fine, but PBKDF2 is just not meant to be used that way.

3. It is less susceptible to misuse. Your method has no intermediate steps, only an input and an output. This makes it difficult to reason about security properties that each variable in your algorithm has, as well as any "cryptographic barriers" that your algorithm creates (e.g. "one cannot derive the secret key from a given generated password"). This is important because when you will need to add more features to your derivation process, you will need to redo the entire cryptographic analysis again to make sure you are not fundamentally breaking anything. In the approach I suggest, the intermediate "master key" has some known security properties (for instance, the secret key cannot be compromised by any manipulation done on the master key) which means I can easily tack on additional features without fear of introducing such and such security vulnerability. If you've ever heard the term "structured programming", this is pretty much an instance of it.

Speaking of adding more features, you will probably want a mechanism to verify that you typed in the secret key right (else you will get a garbage password out which won't match what you used before). It's not obvious how to do it using your method. However, with the improved algorithm, this is fairly straightforward - generate and store a random salt $S$ which you feed to PBKDF2 to generate $K_m$, and then store $Hash(K_m)$ somewhere, enabling you to verify if whoever is in charge of the secret key typed in correctly, without compromising it (or any derived password) if this stored information is somehow leaked (this is akin to storing the hash of the key inside the file when encrypting a file, to be able to tell the user if he typed the key in properly instead of complying and decrypting garbage).

Finally, once you have your final bytes, it's fairly easy to convert them to some charset that you can use as a password. The simplest way is to convert it to Base64, which is fairly convenient and efficient. Of course since they are just bits, you can convert them to whatever you want (hexadecimal, raw ascii, a pin number, etc..)

• Thank you for your thorough and detailed answer. Your point about "It is actually using the underlying cryptographic primitives properly" particularly made things click. How does the picture change if I were to use certificates? I'm imagining I could generate a public & private key, use the private key in HMAC as you describe above, but then also use the key pair to do encryption if need be. – George Bashi Jul 5 '13 at 11:33
• @GeorgeBashi I would say that is okay. HMAC is guaranteed not to leak any information about the input, so it should be safe to feed it into HMAC while still using the keypair as usual. This is assuming the private key has enough entropy e.g. is long enough to avoid being brute-forced, which is hopefully the case here. I'm not sure I understand what you mean by "certificates" though. – Thomas Jul 6 '13 at 3:35
• I meant SSL certificates like I'm used to from setting up HTTPS - i.e. public/private key pairs. I was a little confused about terminology, but your reply has answered my question, thank you. – George Bashi Jul 6 '13 at 15:36