What are the pros and cons of deterministic site-specific password generation from a master pass?

Question

I've been reading up a bit on deterministic password generators. All the ones I can find basically do something like this:

1. Pick a master username and a master passphrase. The username could be your email, or a PIN, or something else. The master passphrase can be subject to stringent requirements to ensure sufficient entropy. The combination of these two factors needs to be ultra-secure and something you're reasonably certain that nobody's ever used before.

2. Enter the site name that you want a password for.

3. Generate the string $H^n\text{(passphrase||username||sitename})$, where $H^n(\cdots)$ is an n-fold iteration of SHA256 or some other sufficiently secure hashing algorithm and $||$ is string concatenation.

4. Make sure that n is sufficiently large such that n iterations of the hash generates a substantial amount of work and protects against brute-forcing.

5. Do a final deterministic mapping from this last string down to an n-character string where the individual chars of the string are in some set of "valid" characters (alphanumeric, alphanumeric+symbols, etc).

There are variations on the above, but that seems to be the basic idea.

Now, I'm curious how secure and trustworthy an algorithm like this really is compared to existing password managers.

For existing password managers, you have the same basic weakness - if your user+master pass is compromised, all of your passwords are also compromised. But does this system have any additional weakness on top of that?

It seems as though it'd be fairly resistant to the obvious things: - If your plaintext pass for one site is compromised, it'd be very difficult to work out your pass for another site.

• Furthermore, due to the fact that the hash function is iterated a sufficient number of times, it'd be difficult to brute force.

• The best way to attack this seems to be a rainbow table approach with a bunch of common master usernames, master passphrases, and site names, but so long as your username+passphrase is of sufficient entropy, that'd be difficult to pull off.

• Furthermore, if you want extra security for a certain site, you can increase the entropy of the sitename field a bit (example: eBay becomes 3b4Y@!#$% or something).

Seems reasonably secure, but I don't know if I'm missing something. Is there some well-known weakness with this system?

Answer 1

The above scheme does have a very important drawback against schemes that encrypt a password store. If you randomly generate the site specific passwords then there is no relation to the master password. You would need the complete password store to perform e.g. dictionary attacks to find the master password. This is not true for the deterministic password generator you've described; one single leaked site specific password would enable an attacker to launch an attack on the master password. In the following two paragraphs I'll focus on the security without regard of this observation.

It seems that the scheme above is just an application of a Password Based Key Derivation Scheme (PBKDF), coupled with a deterministic method of mapping the result to a new password in step 5. As long as step 5 only maps to an array of characters in a specific alphabet without loosing entropy, the security of the scheme depends on the PBKDF used. KDF's commonly already include parameters specific to the secret that is to be generated (in this case that would be the site name).

So for the security of the scheme you should simply study security of PBKDF's and - if possible - the security of the specific PBKDF that is being used. Maybe you can compare the scheme against well known variants like PBKDF1, PBKDF2, bcrypt, scrypt or e.g. the proprietary OpenSSL PBKDF.

Answer 2

This scheme is similar to bitcoin HD wallets (bip32) which have now been in use for several years, and holding millions of dollars worth of funds, ie. they have come under attack, by determined and resourceful attackers, but to this day, they are still considered one of the most secure solutions, and all high security hardware wallets us that approach. So the basic scheme is pretty secure and has been battle-tested in the field.

Now an important thing of note is that those bitcoin HD wallets do not leave the master password/key generation into the user's hand, as that is the obvious point of weakness. If the attacker knows a single derived key an attacker cannot brute force the master key if the master key has high enough entropy, instead the master key needs to know at least 2 derived keys, and then has to break through pkbdf... But with enough entropy bits, unless the hash function has been badly broken, this is not considered feasible (or rather, it would be more complex than breaking AES)

Security-wise the approach can have higher security than encrypted vaults approaches, because there is no vault to be brute forced. Also since passwords are derived through a well defined cryptoencrypted amdean, there is no risk of a weak password getting generated (generating high quality random is complex, and if the generator is running in a VM or relying on OS functions that are later proved vulnerable, there is a not so negligible risk of weak randomness).

The main roadblock is that the master key needs to be long and complex to ensure security (think 128 bits of entropy or more). Which means it is long to type, and hard to memorize, so it is not directly usable (that said AES encrypted vaults protected by weak passwords are equally insecure, and actually more insecure because AES is much less computationally intensive than even a basic pkbdf, and more susceptible to brute force).

The solutions thus revolve around storing that master key in a secure storage. If it is a secure hardware storage (like what hardware bitcoin wallets use), then the security is as high as that of the hardware storage.

If using a password protected encrypted vault, then security is marginally above that of encrypted password databases (as there is less data to be encrypted and it is of fixed length, so all attacks based on a high amount of encrypted data, or variable data length are moot).

Finally, the last downside is one of convenience: the scheme does not provide user names, website names, number of password renewals, etc. Which users may expect, and if they are to be provided, you will need an encrypted vault of some kind. Granted that vault mostly is a privacy risk, rather than a security risk, but it still means you cannot entirely do away with a vault...