I would like to prompt users for a single passphrase to establish trust with separate, normally (but not always) complementary systems from one password input.

I'm essentially looking for a box where one password enters and two leave, where maximum of entropy is maintained and the ability of an attacker using either output password to derive the other is minimized.

There are some constraints:

  • The algorithm must be public knowledge.
  • No other secret keys can be involved.
  • Output passwords must be deterministic for any given input password.

A simple answer seems to be:

  • $\rm pass1 = HMAC(password, \text{ "Magic One"})$
  • $\rm pass2 = HMAC(password, \text{ "Magic Two"})$

With this method, it should be as difficult for someone who knows $\rm pass1$ to derive $\rm pass2$ as it would be for them to guess $\rm password$.

Are there better existing algorithms? The only reference I have been able to find is Steve Bellovin's Hashed Password Exchange Internet-Draft using the same basic method.

Specifically, is it practically possible to increase the difficulty of someone with knowledge of $\rm pass1$ to derive $\rm pass2$ to be more than the difficulty of guessing $\rm password$ itself, even if it requires spending portions of available $\rm password$ entropy?

For example, let's assume that $\rm pass2$ is exposed in an environment where it is being attacked "offline", while $\rm pass1$ is less vulnerable. In this case, $\rm pass1$ is effectively also exposed to the "offline" risk as much as $\rm pass2$.

  • 3
    $\begingroup$ Have you considered using a slow KDF like PBKDF2 or Scrypt to compensate for the low entropy of the password, and then simply split the output into two keys? $\endgroup$
    – hunter
    Nov 5 '13 at 21:11
  • $\begingroup$ Thank you, I'm looking for basic understanding of best that can be done with a given effective input entropy (amplified or not, good or bad) $\endgroup$
    – disk eater
    Nov 5 '13 at 23:59
  • $\begingroup$ They are different questions. If I derive an input yielding 'pass1' by brute forcing 'pass1' this input also reveals 'pass2'. I am asking about ways to construct outputs such that difficulty of deriving 'pass2' exceeds the simple entropy of the input. For example $\endgroup$
    – disk eater
    Nov 6 '13 at 3:17
  • $\begingroup$ if an all knowing algorithm cut input password "box fish" into separate passwords assigned pass1 = "box", pass2 = "fish" knowledge of 'pass1' is more or less useless to derive 'pass2'. Whereas splitting "puffer fish" into "puffer" and "fish" yields disaster. $\endgroup$
    – disk eater
    Nov 6 '13 at 3:24
  • 3
    $\begingroup$ disk eater, try separating the concept of "password" from "key". The password is what the human remembers, the key is what the algorithm needs. Algorithms like PBKDF2 translate a password into a pile of key material. So instead of splitting the password, you divide the key material. Knowing half the pile reveals nothing about the other half. Of course, guessing the password now has two independent systems that can test your guesses, and if you guess right, you can generate both keys, but that's a risk inherent to your requirements - not to the technology. $\endgroup$ Nov 6 '13 at 14:44

You want a pair of functions $(f_1,f_2)$ from a set $S$ of possible passphrases to a key set $K$, that is $f_1,f_2: S \rightarrow K$. The functions are public, in the sense that they can be computed by anyone.

Your security goal is that the cost of finding $f_2(pw)$, knowing $f_1(pw)$, should be roughly as expensive as finding $f_2(pw)$ by searching for $pw$, using $f_1(pw)$ to confirm a correct guess, then simply computing $f_2(pw)$.

In this setting, using a sensible KDF is the best you can hope for. You compute a long bit string $s = \mathit{KDF}(pw)$. The string splits into two parts, $s = s_1 || s_2$, and $f_1(pw) = s_1$, $f_2(pw) = s_2$.

It is good because: Under reasonable assumptions (the KDF looks like a random function). If the KDF looks like a random function, then unless you know the input to the function, you cannot use part of the function value to say something about any other part of the function value.

It cannot be improved upon because: The requirement that $f_1(pw)$ should contain as much entropy as $pw$ means that the function value $f_1(pw)$ more or less uniquely determines $pw$, which means that exhaustive search will work.

Trivial remark on the proposed solution: We could have said that $f_i = \mathit{KDF}(pw, i)$, in line with your HMAC proposal, but then in practice the workload for someone trying to confirm a guess is half that of the legitimate user. With the above proposal, the workloads are equal.

  • $\begingroup$ Thanks for taking the time to respond from my question Entropy tradeoffs to increase isolation between results IS a price I'm willing to pay. Impossible is an acceptable answer I am just exploring ways to increase the distance between output passwords such that compromise of one of the output passwords exposes the other password to less risk than the entropy of the input password. Obviously while keeping as much entropy in each result as possible. $\endgroup$
    – disk eater
    Nov 6 '13 at 19:09
  • $\begingroup$ If you relax the requirement that $f_1(pw)$ should have the same entropy as $pw$, then simple truncation will be your best bet. Split the string so that $s_1$ is short, so that many distinct passwords produce the same $s_1$. But even if they produce the same $s_1$, they won't produce the same $s_2$. This seems a bit risky, though. Typically, for passwords, you don't have a lot of entropy. $\endgroup$
    – K.G.
    Nov 7 '13 at 8:59

To answer your literal question:

"Specifically, is it practically possible to increase the difficulty of someone with knowledge of $\rm pass1$ to derive $\rm pass2$ to be more than the difficulty of guessing $\rm password$ itself, even if it requires spending portions of available $\rm password$ entropy?"

The answer is "no".

To see why, observe that, if an attacker knows (or can correctly guess) the original master password, they will be able to compute all the derived passwords. Thus, the ability to guess the master password implies the ability to derive all the other passwords.

What you could, however, do is make each of the derive password independent of some parts of the master password, which would make it impossible for an attacker to fully confirm whether or not they've correctly guessed the master password based on knowledge of only one derived password. However, if the master password is intended to be human-memorizable, I would strongly suggest against it, since it would reduce the entropy in each derived password.

Indeed, arguably the best way to do this would be to first choose each derived password to be a suitably long sequence of random words, and then let the master password simply be the concatenation of the "derived" passwords. While this would accomplish your goal, and could be practical if the number of derived passwords was not too high, it would also make the whole scheme trivial and rather pointless, since users could just as easily memorize the derived passwords directly.

Instead, for practical use, I would recommend deriving each derived password from the entire master password using a suitable KDF, and accept that guessing the master password will compromise the system. If this is not acceptable, the best alternative solution would be to simply use two separate and independent passwords.


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