Password generation determinism

"Unless a password generator is just taking raw output from /dev/random, it's using programming logic to determine the password. Programming is deterministic, so password generators are deterministic, and so are the passwords they generate.

Therefore, password generators do not produce good passwords. Q.E.D."

I saw a statement much like that one a while back. The questioner was concerned that programatic password generators were not yielding good passwords, since they were designed with deterministic logic and only took a restricted set of inputs to generate that password.

This is true to a point, but there are limits.

If you have perfect knowledge of how a password generation program works and what it uses for inputs, it is possible to derive correct passwords much faster than true random guessing would suggest. The only entropy in the system is introduced by the inputs. If that input size is (for example) only 8 bits regardless of how large a password is generated, the final password will have no more than 8 bits of entropy. You can create a table of all possible passwords this program can generate.

However, if you don't have perfect knowledge of how the password generation program works, the effective entropy can be much higher for an attacker. The effective entropy will be somewhere between the supplied entropy and the entropy implied by the password length.

So, turn this on it's head.

Take password stores. They take a user-supplied password which can have very bad entropy, perform a generally well known computation on it to get a string (frequently called a hash) that is actually stored. This is seen as effective security, so long as the computation is sufficiently robust and non-reversible. But, robustness is a moving target. MD5 is broken, WEP hashes are so broken as to be nearly cleartext these days, Windows LanMan hashes are very broken, SHA-1 is showing some weaknesses but is still pretty strong.

Password-derivation attacks focusing on automatically generated passwords are perhaps most effective when used against systems known to use generated passwords that users will actually keep. Unless they have something like OnePassword end-users will immediately change passwords that are 16 characters of random typeable-ASCII, but may keep something like, "shoes376emotional". The techniques for defending against password-guessing attacks are well known:

• Limit the rate the system will accept login attempts for user accounts (increase the time required to guess the password)
  
• Limit the number of times a login can fail before locking the account from further login attempts (increase the time required to guess the password)
  
• Force periodic password changes (move the target faster than password-guessing could find the password)
• Prevent stations with lots of bad login attempts from further access to the login process (force the attackers to use multiple stations)

No matter how you slice it, even with perfect knowledge of the password-generator an attacker is still going to have to grind through a lot of passwords to find the one that works. They'll be able to find it faster than the char-sets used in the password would suggest, but still need to plow through thousands of attempts. Most of the above methods have been baked into things like Active Directory for a very long time. The same can't be said for bespoke website authentication services.

Using a well known poorly designed password generation system that spits out passwords end-users are likely to continue using means that you need to move the goal-posts (force regular password changes) more often in order to prevent brute-force intrusions. Unless you're also supplying generated passwords for those changed passwords (I've never heard of such a system, but I suppose they could exist) the changed passwords are likely to be something slightly different ("shoes#&^emotional") to completely different than the ones the generator would spit out, which further reduces the likelihood of a successful password-guessing attack.

The biggest vulnerability presented by poorly designed password generation systems are for systems that:

• Don't rate-limit login attempts
• Don't lock-out accounts after a certain number of bad login attempts
• Don't force password changes
• Don't do any kind of IP-reputation lockouts after repeated bad logins

A lot of built-from-scratch web authentication systems don't do any of the above four points, instead they focus on keeping the password hashes secure and having a password-recovery option for people who forget their passwords. Putting an insufficiently entropic password generator on top of it compounds the bad idea.

Can password-generators produce good passwords?

They absolutely can produce cryptographically good ones (a simple one: draw 8 bytes from /dev/random, get the sha1 hash of those bytes, convert the first 16 bytes of the hash to UTF-8, rerun bytes that don't translate, bam! Good 16-character password). Producing good passwords that users will be able to remember is another much more complex problem.

Are bad password generators unusable?

Since bad is relative, it depends. Such poor generators could be sufficient for producing short-term temporary passwords, which limits their vulnerability window. Usable, but only intelligently.