Password Generator

Most advice about passwords is about how a password looks. Add a capital. Add a digit. Swap a letter for a symbol. The trouble is that a guesser does not care how a password looks. A guesser cares how many candidates must be tried before the right one turns up, and that number depends on the method that made the password, not on its appearance.

That is the whole idea behind entropy, and it is less mysterious than its reputation. If a method can produce N different results and every one of them is equally likely, its entropy is the base-2 logarithm of N, measured in bits. Uniform choice is the case that gives the most entropy for a given N; any lean towards some results lowers it. Each extra bit doubles the number of guesses that someone who knows the method exactly would need in the worst case.

Counting, not decorating

For a random password the count is easy. Pick L symbols, each independently and uniformly from a set of N symbols, and there are N to the power L possible passwords. The entropy is L times log2 N. Sixteen characters from the 62 letters and digits give 95.27 bits. Eight small letters give 37.60. Fifteen characters from all 94 printable ASCII symbols give 98.32.

Notice which lever moves the number. Going from 62 symbols to 94 adds about 0.6 bits per character. Adding one character adds about six. That arithmetic is why the current NIST guidance on digital identity, SP 800-63B-4, describes password length as a primary factor in strength and builds its rules around it. A service must require at least 15 characters for a password used as the only factor, and at least 8 when the password is one factor among several. It should allow at least 64, so that people can use passphrases.

The same document is blunt about the decorations. Services shall not impose other composition rules, such as demanding a mix of character types. Its appendix explains why: people respond to such rules in predictable ways, so a person who would have chosen “password” tends to choose “Password1” when told to add a capital and a digit, and “Password1!” when a symbol is required as well. The rule changes the look and barely changes the count.

NIST also drops forced periodic changes. A service shall not require people to change passwords on a schedule, only when there is evidence of compromise. What it asks instead is a blocklist check: a new password is compared with a list of commonly used, expected or compromised values, and rejected if it is on it.

None of this is aimed at generated passwords, which is the point. Human choices are predictable, so rules push them around. A generator needs only an honest source of randomness and an honest way of turning bits into symbols.

The bias trap in naive random code

The honest source is the easy part. In a browser it is crypto.getRandomValues, which the Web Cryptography specification defines as a source of cryptographically strong random values. MDN describes the implementation as a pseudo-random generator seeded with enough entropy, suitable for cryptographic purposes, and notes that one call will fill at most 65,536 bytes. The language’s ordinary Math.random is a different thing altogether: MDN says plainly that it does not provide cryptographically secure numbers and must not be used for anything related to security.

The subtle part is the step that comes after. A random byte is a number from 0 to 255, and an alphabet has, say, 62 symbols. The tempting line of code takes the byte modulo 62. But 256 is not a multiple of 62. It leaves a remainder of 8, so the first 8 symbols each receive five of the 256 byte values and the other 54 receive four. Those 8 symbols come up 25 percent more often than the rest. The same trick with an 88-symbol alphabet is worse: 80 symbols get three byte values and 8 get two, a 50 percent tilt.

Bias like that is not subtle in data. The NIST/SEMATECH e-Handbook describes the chi-square goodness-of-fit test, which compares observed counts with the counts a fair process would give, and tabulates the critical values. For 62 symbols there are 61 degrees of freedom, and the value a fair process exceeds only once in a thousand runs is 100.888. In this tool’s own tests, a million bytes reduced modulo 62 gave a statistic of 6,572.5. The fair sampler, fed the same kind of stream, stayed below the bound at every one of 16 character positions for six different alphabets.

The fix is old and simple. Throw away the byte values that do not fit evenly and draw again. For 62 symbols, keep bytes 0 to 247, which is four complete rounds of the alphabet, and discard 248 to 255. Every symbol now owns exactly four byte values, and the cost is a redraw about 3 percent of the time. When the alphabet is larger than 256, as a word list is, the same rule works on two bytes at a time.

Rules such as “at least one digit” hide a second version of the trap. One common shortcut forces a digit into a random position, which makes digits more common than they should be and makes the count hard to state. The clean way is to generate a whole candidate fairly and throw it away if it misses a required kind. Every valid password is then exactly as likely as every other, and the count is the number of valid strings.

That count is not N to the power L any more, and it can be computed exactly by inclusion and exclusion: start with every string, subtract those that miss each kind, add back those that miss two kinds, and so on.

Here is a worked example you can reproduce in the tool above. Take 16 characters from 88 symbols: 26 capitals, 26 small letters, 10 digits and the 26 common symbols, with one of each kind required. Without the rule the entropy would be 103.35 bits. With it the exact figure is 103.11 bits, so the rule costs 0.24 bits, and 84.45 percent of fair candidates pass. Under the rule each digit appears at a given position with a chance of 1.325 percent instead of 1.136.

A quarter of a bit is a small price, and it shrinks as length grows. The point is not that the rule is ruinous. The point is that a page which prints 103.35 bits for that setting is overstating its own result, and one that forces characters into place cannot say what its result is at all. The Wikipedia article on password strength makes the general case: requiring every character class is itself a pattern, and patterns reduce the work an attacker must do.

Passphrases and word lists

A passphrase is the same idea with a bigger alphabet. Instead of one symbol out of 88, each step picks one word out of a list. Arnold Reinhold’s Diceware list, first published in 1995, holds 7,776 words because that is six to the power five, the number of ordered rolls of five ordinary dice. In 2016 the Electronic Frontier Foundation published a long list of the same size, built from words that English speakers are most likely to recognise, with rare, vulgar and hard-to-spell entries left out.

The EFF is careful to say that the change is about usability, not security. Every word on a 7,776-word list carries 12.9 bits when it is picked fairly, whichever list it is. The EFF recommends six words, about 77 bits; the exact figure is 77.55 bits. Six fair dice rolls per word would give the same number, which is why the tool’s 3D view shows the strength of any result as a count of dice: a 16-character password from 88 symbols is worth about 40 dice.

The UK National Cyber Security Centre recommends a smaller version of the idea, three random words, as long enough and strong enough for most purposes. Three words from the EFF list give 38.77 bits. That is fine for an account where the service limits guesses, and thin for anything that might be attacked offline. Decorations behave as before. Capitalising every word adds nothing, because every result gets it. Adding one random digit to one random word of six adds log2 of 60, about 5.9 bits.

What a generator cannot do

Entropy describes the method, not the string. A guesser who does not know the method may waste time, but a careful one assumes the worst, so the number shown is a floor on the work, not a promise of safety. It also says nothing about how the password is stored. NIST notes that an attacker who steals a database of hashed passwords can compute many billions of hashes per second, which is why offline attacks need far more strength than online ones, and why NIST expects stored passwords to be salted and prefers a deliberately slow hash.

A generator also cannot check a result against breached lists without either holding such a list or sending something away to ask. This one does neither, and says so. That check belongs to the service that stores the password.

PINs are a special case: four digits allow 10,000 values, so a hundred guesses find a fair four-digit PIN one time in a hundred. A PIN is safe only where the device or service stops the guessing.

Which leads to the part that matters more than any generator. A random 16-character password is excellent and impossible to remember, and reusing it across sites hands it to anyone who breaks into the weakest one. NIST says services shall allow password managers and autofill, notes that managers make stronger passwords more likely, and calls distinct passwords important for avoiding password stuffing. CISA puts the same advice in plain words: make passwords long, random and unique, at least 16 characters, and let a password manager create, store and fill them.

So the generator is the easy half. It should use the system’s cryptographic source, reject rather than reduce, count exactly what its rules allow, and show that count without flattering it. The other half is a place to keep the result that is not your memory and not a note on the monitor. Pick a long passphrase for the manager itself, let it hold everything else, and the arithmetic finally works in your favour.