Chrome generated passwords not high entropy?

Question

On Chrome, if you open a sign up page, it will offer to fill and remember the password field. I did this and got the following sequence of passwords offered as generated:

suCipAytAyswed0
LUnhefcerAnAcg2
it2drosharkEweo
UndosnAiHigcir0
AKDySwaybficMi5
DorrIfewfAidty5
MeecradGosdovl9
KasEsacHuhyflo4
OngouHemNikEyd0

In all of these, there is only one digit, and in all of them except the third the digit is at the end. The chance of me getting that many with this exact pattern is extremely low, and I've seen it in other passwords generated by Chrome, so I'm confident it would continue if I generated some more.

This just seems weird, wouldn't it be easier to generate the password as a random collection of letters and numbers than to enforce some strange pattern; given that these are not supposed to be remembered? Why would Chrome do something else?

Answer 1

Conor's answer is a good starting point, but if you dig into Chromium's source the situation starts to look a little bleaker (but still better than not using a password manager at all).

Chrome 68 (current version as of August 1st, 2018)

Up through version 68 Chrome follows FIPS 181 to generate a 15 character pronounceable password allowing uppercase letters, lowercase letters, and numbers. If the result doesn't contain both an uppercase letter and a number, it changes the first lowercase letter to uppercase, and changes the last lowercase character to a random digit.

Unfortunately the entropy of a FIPS 181 password is pretty hard to calculate, as it generates variable length syllables rather than characters, and there are a bunch of rules dictating whether or not a syllable is allowed.

The non-uniformity has severe implications. A 1994 paper (page 192) estimated that to break into 1 out of 100 accounts with 8 character passwords, an attacker would only have to try 1.6 million passwords. Even if increasing the length from 8 to 15 doubles the entropy, that's still probably under 60 bits of entropy on average¹, though this is improved slightly due to capitalization.

The original standard doesn't appear to support uppercase letters or numbers, and the implementation² only capitalizes the first letter of a syllable with a 50% chance (interestingly y is replaced with w in the array of characters checked, so y will never be capitalized). This means that rather than adding about 1 bit of entropy per letter, capitalization only adds 1 bit per syllable. The number of syllables isn't constant, so it's hard to determine how much entropy this actually adds, but given the scarcity of single letter syllables it almost certainly adds less than 8 bits on average.

Numbers and symbols are supported by turning each single letter syllable alternately into a digit or symbol with 50% chance (though the symbol feature isn't used). Unfortunately, as you have noticed, single letter syllables are uncommon³, so ForceFixPassword usually ends up swapping out the last lowercase letter for a digit.

There may be more issues, but I'm getting a bit tired of looking at it. In short, this isn't a very good method of generating passwords, and the entropy is significantly less than one would expect for the length. In practice this is still probably ok for the average user, as it means they won't be using their favorite low entropy password in 20 different places, but breaking it is definitely possible for a determined and funded attacker with a fast hash (ie not a good password hash) of the password.

Chrome 69 (scheduled for release in September)

Things are looking much better in Chrome 69. The character set is upper and lowercase letters, numbers, and the symbols -_.:! with the following removed for readability:

• l (lowercase letter L)
• I (capital letter i)
• 1 (digit one)
• O (capital letter o)
• 0 (digit zero)
• o (lowercase letter O)

The generation works by adding a random character from each class until the minimum count for said class is met. By default and as currently used this is one lowercase character, one uppercase character, and one digit.

Then the rest of the password is filled with random characters evenly chosen from all character classes (respecting a maximum count for each class, currently unused).

Finally, since characters were added to the beginning of the password from predictable classes in order to satisfy requirements, the string is randomly shuffled. The shuffling happens up to 5 times if two dashes or underscores are adjacent in order to improve readability, so this will very slightly reduce the entropy, but the reduction is so slight as to be unnoticeable (and removing dash or underscore from the allowed symbols would be worse).

With 61 possible characters a fully random password would have log₂(61¹⁵) = 88.96 bits of entropy. Using inclusion-exclusion to account for the required characters, I come up with 88.77 bits of entropy:

61^15          all possible passwords
-53^15         passwords without digits 2-9 (0 and 1 are excluded)
-37^15         passwords without lowercase letters (l and o excluded)
-37^15         passwords without uppercase letters (I and O excluded)
+29^15         add back passwords excluded twice for lack of digit and lowercase
+29^15         add back passwords excluded twice for lack of digit and uppercase
+13^15         add back passwords excluded twice for lack of lowercase and uppercase
-5^15          remove all-symbol passwords that were excluded then added back

The extra shuffling will shave off a fraction of a bit as well, but I don't have time to calculate it right now. In the end, the password should have over 88 bits of entropy, which is pretty good.

The old generator still exists in version 69, but when I tested the dev build it was using the new one. Whether or not there's any way to use the old generator I don't know.

---

_{1. Average entropy isn't necessarily useful with non-uniform distributions, the original 1975 paper gives an example (pages 29-30) of a generator that produces a single password (e.g. "password") with a 50% chance, and a high entropy password otherwise. The average entropy may be high, but there's still a 50% chance the password will be guessed immediately. Even so, extrapolating from the 1994 analysis, I believe it should still have well over 40 bits in the worst case.}

_{2. The implementation isn't actually Chrome's, but is taken from the APG program, with minor modifications for compatibility}

_{3. Testing with apg reveals that single letter syllables actually occur in about 33% of passwords, but 70-75% of those only have a single letter syllable at the end.}

Answer 2

Let me start with an important and accurate caveat:

http://dilbert.com/strip/2001-10-25

The math

Looking at the actual odds, there are 62 possible characters (a-zA-Z0-9) and therefore assuming all are equally distributed that means that any given character has a ~16% chance of being a digit.

You have shown us 136 characters in total which means that on average there should be ~21 digits instead of the 9 you have shown. Running through 1000 random trials I get a mean of 21.5 digits in such a run with a standard deviation of 4.3. That means that your 136 character string with only 9 digits is about a 3sigma outlier (only a 0.3% change of being due to random chance). Of course, this presumes that you didn't have any examples with more numbers that you left out of your example.

The conclusion

This suggests that the lack of numbers is not just random. That could mean a couple things: either the password generation algorithm google is using just sticks a digit on the end or there is something wrong with their password generation algorithm or source of entropy. Without looking at their source it is hard to say which of those cases is more likely. Of course, it isn't so simple as just sticking a digit on the end, because you have an example with a digit towards the beginning. So if this is an intentional result of their password generation algorithm, then their algorithm is very strange, which makes me think something else is going on.

Update Per Androl's answer above, chrome's password generation algorithm is indeed doing something very strange.

The answer

Of course none of this answers your actual question: do these passwords have enough entropy? Ignoring the digit of unknown randomness, we can think of this at least as a string of random letters of length 14. Such a string (presuming they are using a good CSPRNG) would have 1.06e24 possible values, or ~80 bits of entropy. For comparison, a 15 character long string composed of letters or digits would have ~90 bits of entropy. Is that "enough" entropy? Well, that is a much harder question to answer. It depends - is that password then stored on a website that uses md5 and leaks their database for offline cracking rigs? Is it stored on a website that stores passwords in plain text (in which case no amount of entropy matters)? How about for a website that secures your password with modern best-practices? This answer gives a useful comparison and suggests that for plain sha256 a password with 80 bits of entropy is effectively uncrackable (with lots of caveats):

https://security.stackexchange.com/a/168511/149676

As a result, I would say that even if they aren't properly randomizing digits the password is long enough that there is more than enough entropy for the foreseeable future.

Answer 3

You have two wrong assumptions in your question that lead to the answer of why Chrome generates passwords like this and not, say, p^&7+4+{ZgfnP#P/.

First, you assume that the passwords are not supposed to be remembered and should thus be completely random. They are not. Chrome, like many random password generators, creates pronouncable passwords, as outlined in detail in AndrolGenhald's answer.

Using pronouncable passwords instead of gibberish reduces input errors, allows the password to be passed on to another person on the phone, for example, and makes it easier to remember them. Why do you assume that the Chrome passwords are not supposed to be remembered? Very few people these days visit the Internet with only one device.

Secondly, you assume that passwords need to be complicated. This is a common misconception that has been falsified many times, the most official one being the withdrawl of the complexity recommendations in NIST SP-800 (see, e.g. https://www.passwordping.com/surprising-new-password-guidelines-nist/).

Passwords should, most of all, be long. Chrome satisfies that condition nicely (12 characters is a current recommendet minimum for non-critical web applications).

In light of these facts, the passwords generated by Chrome satisfy good, modern password standards. Improvements can be discussed and are certainly possible, but they are certainly on the right track there.

Answer 4

Note that this is only a guess on my part, but it's possible that this is an attempt to make the passwords easier to remember and/or transcribe into a password input box. In addition to the odd number placement, I notice that the provided examples seem to be mostly pronounceable, and I've seen other password generators do something similar (e.g. LastPass has an option to make a generated password "Easy to say"). There are public algorithms to do this (e.g. https://exyr.org/2011/random-pronounceable-passwords/ ).

Making them pronounceable and having seemingly non-random number placement obviously lessens the entropy, but without knowing the actual algorithm in use, it's impossible to say by how much. It's possible that the Chrome developers have assessed the generated entropy and decided that the usability benefits outweigh the lost entropy, and that the remaining entropy is still relatively secure.