Splitting a password for dual roles 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$.
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.