Password generation - too primitive?

Question

A while ago (12 years old), I recognized my passwords weren't safe at all. Because I used the very same password everywhere, some grumpy admin could easily take over all my accounts (he got mail and password).

The obvious thing to do is to change all passwords to unique new passwords. However, remembering these is cumbersome. There had to be a better way...

Leading to: Yet another password generator (Java >= 6).

Non-storing password generation (no file containing all passwords)
Easy recover of lost passwords
Master password used only locally, therefore totally safe (I thought)
Consistency across platforms (Android, Desktop, etc.)
Configurable length of generated password

It works like this:

Input master password and use of the password (e.g. google.com)
Create a Sha1 SecureRandom object
Seed it with the UTF-8 bytes of the master password and the use of the password
Generate as many random alphanumeric characters as specified by the length slider

Questions:

How might this method of generating passwords be attacked (else than bruteforce)?
How safe is this method of generating passwords?
1. If it is unsafe, what causes this unsafety and how to improve it?
Is there something entirely wrong with this approach?

Either use an implicitly seeded `SecureRandom` for unreproducible random numbers, or a stream cipher if you need reproducibility. If you have a master password, you most likely need a proper password based key derivation function (PBKDF2, bcrypt, scrypt,...) — CodesInChaos, Feb 12 '14 at 18:12

score 13 · Accepted Answer · edited Mar 17 '17 at 13:14

For security, one important thing to take into account is that an exhaustive search on the master password is feasible. Schematically, an attacker who got a site-specific password (e.g. an evil admin on that site) can run your Java application (or some code of his own which applies the same algorithm) and "try" potential master passwords, to see if it yields the known site-specific password.

If your master password is fat and random (say, at least 70 bits of entropy), then this won't be an issue. However, if your master password is more "normal" (a "strong" password is, say, 45 bits of entropy), then this is a weakness. The situation can be improved by using proper password hashing:

You need the transformation from master password to site-specific password to be slow through the use of many iteration.
You need a salt. In this case, imagine that 10000 people use your system and all have an account on, say, google.com (a fictitious example). They will all use "google.com" as "password use". Correspondingly, an evil admin at google.com could attack all the 10000 master passwords in parallel, with a lot of cost sharing. You could use your own name as salt; names are not utterly good salts, but this would still significantly improve this situation.

This is "brute force", but with human-remembered passwords, brute force tends to work.

For usability, there can be some issues:

You have to remember what password length you used on each site.
Some sites have special requirements, and there is no "one size fits all" set of rules which works everywhere (e.g. some sites make it mandatory to use punctuation signs, while some others prohibit punctuation signs).
Some sites may mandate password changes. By definition, your applet cannot tolerate a password change, unless you use a new "use" string, and then you have to remember it.
In addition to being suboptimal for password hashing, Sun/Oracle's default implementation of SecureRandom is not well specified, and not guaranteed never to change. If Oracle decides to modify it at some point, all your passwords will be lost. You really should rely on some algorithm which is not subject to such changes.
Good luck running your Java code on your iPhone or iPad. For real portability (including making your code run on the machine you will own 5 years from now), you may need to implement your algorithm in several languages, because there is no such thing as One Language To Rule Them All. This again implies using a well-defined standard, and not "what Java appears to use for now as a PRNG algorithm".

For all the reasons above, making a "password wallet" which does not need storage space is challenging. This concept has been proposed and even implemented many times, and that may work for most sites, so you may tolerate it for your own usage. Depending on your own context (which site you use, what kind of hardware and OS you own...).

Excellent answer, but note that I isolated the Sha1 PRNG implementation, so it will never change. Porting to other languages should be (fairly) easy then. I did not think of the need to change a password though... — tilpner, Feb 12 '14 at 18:45
Agreed that a password wallet without storage space is "challenging". If you still insist on it, the salt is required; that's one place you can use to be able to change the password generated - a counter at the end, a phrase for each change you can remember, etc. If you can, try something that stored purely random passwords. — Anti-weakpasswords, Feb 13 '14 at 14:21
"One Language To Rule Them All" - I think you mean C and/or C++ :) — Timotei, Feb 22 '14 at 10:52
Just curious: does a salt provide more security than a longer master password? — bers, Sep 03 '16 at 19:16
Salts do not provide more or less security than a longer master password; they ensure protection against cost sharing between attacks (and attackers). This is not directly comparable (but you need both). Also, it is not _length_ that really matters, but _entropy_; extra length merely gives more room for entropy. — Tom Leek, Sep 07 '16 at 00:48

score 3 · Answer 2 · edited Mar 17 '17 at 13:14

Tom Leek's answer is an excellent review of your password diversification scheme, so I won't attempt to repeat what he wrote in my own inferior words. In this answer I'll focus on a comparison with unique passwords.

Security wise, unique passwords (generated independently) have the advantage that a breach of one password does not reveal anything about the other passwords.

In terms of usability, your scheme requires a computing device to generate the site password from the master password. (I assume you can't reproduce the SecureRandom computation in your head.) This computing device has to be trusted, since you'll be typing the master password there.

With unique passwords, you can have an encrypted password archive, and use the master password to decrypt it. In order to achieve the same level of security, you need to avoid brute force attacks from the master password, and that's all. In particular, if your encrypted password archive is public, this scheme achieves the same level of security as yours — a breach of the master password reveals everything. So you only need security for the decryption phase, not of the storage of the encrypted password archive. (Storage security would improve the security of the scheme however.)

Therefore the only requirement to have independent passwords is an untrusted storage facility that can be accessed by a device that is trusted for computation. In practice, this requirement is easily met: either the device you're using for computation has storage, or you trust it enough to download your password archive.

The requirement to back up and synchronize the password archive is not onerous; given today's ubiquituous connectivity, it is in fact less constraining than your password generation scheme. There are services to synchronize files seamlessly on every common platform. You can synchronize the password archive, protected with a strong passphrase, to services with a medium level of trust. If some of your devices are more trusted than others, you can keep the full archive on the most trusted devices and a subset consisting of some less important passwords on less-trusted devices.

While your approach is not fundamentally wrong, it does not have a practical benefit over the more secure approach of unique passwords, and it is less flexible. So use unique passwords.

Password generation - too primitive?

2 Answers2