How to generate many passwords from one passphrase, so that knowledge of one password does not compromise the others?

Question

The limitations are:

1. it should be a function.
2. passphrase is so weak, that if hash of it is known (or big part of hash), then it can be brute forced.

I want to get N passwords from one passphrase. Lets imagine, that N hackers have web sites with login pages, and I want to use my N passwords as passwords for accounts on their web sites. I don't want one hacker to be able to find my password for another hacker's web site.

First what comes to mind is to divide passphrase to N parts, and use each part as a key. Like

f("MyWeakPassphrase") = {"My", "Weak", "Passphrase" }

(It satisfies restrictions)

But are there better ways?

update Most of answers suggest to use kdf with salt + counter or something similar. It is still a hash, and if broken, all other passwords revealed. I thought there might be an algorithm, so that brute forcing passphrase will reveal only part of a passphrase if only one password is known. Like function above, but better.

Answer 1

I have considered your requirements to be these:

1. it should be a function
2. passphrase is so weak, that if hash of it is known (or big part of hash), then it can be brute forced.
3. many passwords can be generated as output.

There exists various kinds of key derivation functions, which derive cryptographic keys from other cryptographic keys or passwords. The solutions builds of these components. The general idea is to to apply password-based key derivation to get one key (the master key), derive keys from the master key, and represent those keys as passwords.

PASSWORD-BASED KEY DERIVATION

The password-based key derivation functions are good for deriving key from a password. These are good to deal with problem 2: i.e., they've been intended to produce (as good as possible) cryptographic key from password or passphrase.

Key-derivation function is used as follows:

$K = PBKDF(passphrase, salt, 1000000)$

In addition to passphrase, they usually need salt and iteration count. Iteration count shall be selected to as large value as possible without the operation taking too long for the user. Depending on context, the user is most likely wiling to wait 0.1 seconds, 1 seconds or maybe even 5 seconds. Some of most popular choices for password-based key derivation currently include bcrypt, scrypt and PKCS #5's PBKDF2 also known as NIST SP 800-132 Part 1.

In essence, password-based key derivation function is typically based on iterative execution of hash function or pseudo-random function, i.e. something like:

$PRF(...(PRF(PRF(salt, password)))...)$

[Substitute PRF with a function of your choice, that is works like PRF, such as HMAC-SHA256.] But to get all details implemented correctly, please, use one of above standards to implement the solution.

KEY-DERIVATION

Once you have cryptographic key, it is possible to derive other keys from this key using key derivation functions. These derived keys (assuming good key derivation function) are independent in sense that it is not possible to derive original key from these keys.

Some of good key derivation functions are found in HKDF (RFC 5869) and NIST SP 800-108: Recommendation for Key Derivation Using Pseudorandom Functions.

In the simplest case, key derivation is something like:

$K_x = PRF(K, x)$

where x is purpose or label or index of the key, and K is the master key. But to get all details implemented correctly, please, use one of above standards to implement the solution.

PASSWORD FROM KEY

Now you have arbitrary amount of cryptographic keys. But you wanted passwords. There are various ways to convert cryptographic key to password. One simple approach is to use base 16 (hex), base 32 or base 64 encoding to represent the key in ASCII characters. Alternative approach is to have a template of password and apply FPE (Format Preserving Encryption) to template with the derived key. One standard for FPE is NIST SP 800-38G. Anyway, in essence, what you will need is a function that will represent a key as a password. Thus:

${PASS}_x = ENCODE(K_x)$

Last, but not least, I would recommend to use pre-existing password manager software rather than inventing your new solution if possible.

Answer 2

You can just use a counter along with a key derivation function (https://en.wikipedia.org/wiki/Key_derivation_function) such as a hash, and do something such as:

for(int i = 0; i < numberOfPasswordsToGenerate; i++){
   aNewPassword = hash(MyWeakPassphrase + i);
}

The counter makes sure you get a new password, for each iteration of the loop, and they will never know the hash of the original passphrase without the counter.

Of course this can be brute forced, given a large enough dictionary for a dictionary attack or a good rainbow-table, so use a as well salt to prevent that... Actually, just always use a salt.

Edit: To be clear on what I mean, this will make it more akin to this:

for(int i = 0; i < numberOfPasswordsToGenerate; i++){
   aNewPassword = hash(MyWeakPassphrase + i + salt);
}

The salt is just a large enough randomly generated number for each password you store next to the encrypted/hashed password in your database. If you just use a single identical salt for all the passwords, it is called a pepper instead, if I remember correctly.

Note: If you want to go further on security, you could use an IV (initialization vector) that contains the beginning number of the loop, so that the attacker has no idea which numbers you used, unless he gains knowledge of your IV as well.

This would look sort of like:

void generatePasswords(int IV) {
   for(int i = IV; i < IV + numberOfPasswordsToGenerate; i++){
      aNewPassword = hash(MyWeakPassphrase + i + salt);
   }
}

I'm bad at writing pseudo-code, sorry! It always get C-like, but yet not quite C.

Hope it helps!

NOTE: Please read Krystian's comment. We all suggest that you make different passwords by adding a counter and salt to it. This prevents precomputed attacks, but if someone learns the salt and counter (which can be expected, these are considered "public" knowledge security-wise), then they can bruteforce your primary password. The fundamental problem here is that, you want to map a password to multiple unrelated values. In order to be able to recreate this mapping later on (which I assume you would want to, since you derive the passwords from the same passphrase), you need to make the passphrase different and still unique for each new password you make. We do this by adding a salt and counter. Since you need to store the salt and counter to recreate the mapping, they are considered public and thus anyone can still bruteforce your password, since it is weak.

Answer 3

Here is another very simple scheme (not fully secure but it should be enough for your needs).

1. Chose a strong password $pwd$.

2. Let's say you want a password for the website $xyz$. Compute: $PWD = \text{AES}(pwd,xyz)$ where $pwd$ is the key for your encryption.

$PWD$ can then be used as a password to access to the $xyz$ website. Should you want to have another password for another website. Redo the process (keep $pwd$).

About a security point of view.

Lets say you use this method for N compromised website and for your bank website. Should the N hacker try to find the main password would require to break the AES/bruteforce... Hence you have a nice security margin.

Remark: I used AES here for simplicity, a HMAC function could be used or any key derivation function.

My advice: DO NOT IMPLEMENT OR DO WHAT I SAID, stick to the standards. If this is really what you want then I would highly recommend you to go and have a loot at Keepass. It allows you to, generate random password, manage them and also helps with a policy such as change your password every years