Are there significant problems with a password generation pattern using groups of alternating consonants/vowels?

Question

I'm using a password manager to store unique passwords for all my accounts. Most of the passwords are auto-filled, auto-typed or can be copied and pasted, but occasionally, I have to type them manually (e.g. in-game accounts, certain mobile apps/services, etc.).

Since passwords like VeS3XPTUs3w4PN8xGdmN can be a pain to type correctly manually, I have played around with password generator patterns in order to find something that's easier to "buffer" in memory while typing. I find that phrases that can be pronounced are much easier to remember than unpronouncable strings like the above.

For example, pattern that's easier to remember might be punctuation-delimited groups of alternating consonants and vowels:

vudu:ARUD;raxu,URAB:6527
give;ALEZ,jabu.ACUP,4722
kuge.UTUF,xura;EVEG.7334
kiro.AVAJ.vovo:AHAY;4786

I realize that any pattern will make the passwords easier to crack if an attacker figures out the pattern. For the examples above, I would guess that

• all the letter groups could just as well be lowercase, since the number of combinations are the same and whether a group is uppercase or lowercase is explicitly given by the pattern
• the number group at the end would be better as another letter group, since the pattern explicitly states whether it's numbers or letters, and a letter group following the pattern above would have (slightly) more combinations

In other words, the following examples might be a bit harder to crack for an attacker knowing the pattern:

vapu-dapu-fato-sovu-gazi
mipi-rodo-qiba-tiwu-cihe
qana-jeru-hibu-toka-xixu
fuca-kigu-moka-koxu-yopu

At the same time, including both lowercase, uppercase, and numbers will make them more difficult to brute-force. Then again, if the passwords are this long, the last group of examples above might be sufficient anyway.

Is there anything I should know about before using such patterns for generating passwords? Specifically, could (or should) the pattern be improved, and could it be simplified without losing significant security (or alternatively, could one just as well use a nonsense sequence of real words)?

Answer 1

Calculating entropy for the vapu-dapu-fato-sovu-gazi pattern

Let's do some math for the following kind of pattern:

vapu-dapu-fato-sovu-gazi

Assuming there are five vowels, 'a', 'e', 'i', 'o', 'u', and 21 consonants, and you always start with a consonant, you can build 21 * 5 * 21 * 5 (11025) unique four-letter-words. Replacing the last group with a four-digit random number yields 10000 instead of 11025 possibilities for the last group.

If you paste 5 of these words together, you get 11025⁵ possible passwords (I'm ignoring the dashes because if the generator pattern is known, they don't add any security).

This gives you a password search space of size 162889462677744140625. That's equal to 67 bits of entropy, if you choose your consonants and vowels in a completely random fashion.

67 bits are not great, but they're much, much better than your average password entropy. Assuming a well-funded attacker who has the resources (botnets?) of one million computers available which can each check one million passwords a second, it will take four and a half years to exhaustively search the password space, and on average a bit more than 2 years to find the correct password.

If an attacker was ignorant of your password scheme and simply tried every possible string of 24 characters, it would take much longer.

Is 10¹² guesses per second reasonable?

To give a bit of context to the above assumptions about the attacker: One million password guesses a second per machine is easily doable today on GPUs if the password is protected with a very weak hash function, such as MD5 (and the old Windows LM hash is so weak that you can reach a few billion guesses a second - hashcat parlance is 'Megahashes' and 'Gigahashes' per second...) . It's not feasible when the password is protected with strong password hash functions such as bcrypt, scrypt etc. Depending on the configuration, you might get anywhere between one hash up to a few kilohashes per second. Botnet sizes of one million zombies are optimistic for an attacker (the very large Mirai botnet, which enslaved IoT devices which wouldn't work very well as password crackers, consisted of about 100'000 devices), most botnets are smaller. Finally, having a botnet run a million CPUs or GPUs at, say, 20% capacity cracking passwords for two years non-stop would probably get someone's attention sooner or later.

If you're not happy with these assumptions, I'd suggest the following: Imagine the attacker you want to protect against. See what resources he'd need to achieve his goal, and then make an educated guess about whether he can afford these resources. For example, coming up with the resources needed to do 10¹² guesses a second (renting several large botnets for two years or buying and running the hardware yourself) is probably out of the reach of everyone but large corporations, organized crime and nation states.

What if you used real words?

could it be simplified without losing significant security, or alternatively, could one just as well use a nonsense sequence of real words

Let's consider using real words instead of made-up ones. Random words are much harder to memorize, and if you used real words from a lexicon that contained, say, 7000 words, the resulting password would still contain 63 bits of entropy. That's 16 times weaker, but you could easily offset that by adding another word, which would yield 76 bits of entropy and, assuming the same attacker, protect you for over two millenia if technology didn't advance in that time. Again, it is absolutely crucial to choose the words randomly. Just thinking of a few words that come to your mind is not good enough. Also, you'd have to take care not to pick 5 very short words, because then you'd open yourself to a brute-force attack on the resulting short string.

Check out the obligatory xkcd, and Diceware for word lists. Or if you're too lazy, you can buy a password for two bucks from this girl in NYC :-)

Answer 2

If you have a password generation method, the only way to know the strength of your password is to measure the key space and get a number. In your simpler case, if the password were to be 24 characters long with the pattern cvcv-cvcv-cvcv-cvcv-cvcv, and assuming that the entire sequence was generated in a truly random manner, the security would be calculated as follows:

• c has 21 possibilities, and multiplies your key space by 21.
• v has 5 possibilities, and multiplies your key space by 5.
• “-” is a literal and has only 1 possibility (itself). It multiplies your key space by 1, which is to say it adds no security—nothing to the key space and should be ignored in the calculation as if it weren’t there.

The security of cv would be 105 (21×5). The security of cvcv would be 11,025 (21×5×21×5 = 105×105 = 105²). The security of cvcv-cvcv would be 121,550,625 (105×105×105×105 = 105⁴). Continuing the pattern, the security of cvcv-cvcv-cvcv-cvcv-cvcv would be 162,889,462,677,744,140,625 (105¹⁰ ≈ 1.63×10²⁰).

I always “normalize” my results so that I can measure my password’s security by bits. Your last pattern would have the equivalent security of about 67.14 randomly-generated bits (log₂(105¹⁰)), which may be low if you’re encrypting data. There are, however, ways to stretch weak passwords to make them harder to crack by increasing the resources (memory, computation, and/or storage) required to try each combination. It all depends on how the password will be used and what your threat model is.

I have played around with password generator patterns in order to find something that's easier to "buffer" in memory while typing. I find that phrases that can be pronounced are much easier to remember than unpronouncable strings like the above.

At the same time, including both lowercase, uppercase, and numbers will make them more difficult to brute-force.

If you considered a consonant-vowel pattern at the core of your scheme because you thought that it would be easier to remember, then including unpronounceable information like casing and punctuation would be counter to that goal, but each person has his/her own requirements and memory characteristics. For example, I can remember passwords in terms of JavaScript code, allowing me to remember sequences like (for an airline account perhaps):

if(winter){bird[3].fly(south);}else{bird[3].fly(north);}

I remember it simply as an English sentence: If it’s winter, bird number three flies south. Otherwise, it flies north. Measuring its security would be quite a challenge given the open-ended nature of such a password system, but the security is actually less than it appears.

Is there anything I should know about before using such patterns for generating passwords? Specifically, could (or should) the pattern be improved, and could it be simplified without losing significant security (or alternatively, could one just as well use a nonsense sequence of real words)?

Just make sure it meets your requirements: memorability; pronounceability; and security. Come up with different candidate methods of generating passwords and measure the security of each (using log₂(…)).

And remember Kerckhoffs’s principle: you should always assume that the attacker knows everything (including the key space) about your security system except the very bits that make up your key. Given a reasonably secure cryptosystem and good security practices, the easiest attack would be to guess the password itself (asides from finding you and applying rubber-hose cryptanalysis).

Answer 3

The following policy is guaranteed to produce strong passphrases: pick them randomly with equal probability out of a sufficiently large set. The first policy can be achieved by defining a set of rules that given random input—coin flips, dice rolls, a cryptographic random number generator—chooses a passphrase without any bias between the alternatives.

For the second policy—the sufficiently large set—if this is a login (not encryption!) passphrase for a website that's not super-critical to you and that you might have to remember from memory, I would recommend drawing the passphrase from a set with at least 2^64 alternatives. Since the base-2 logarithm of the set of alternatives is the entropy of the passphrase, this means you get a 64-bit security level.

Note that 64-bits might not hold up to a high-powered attacker that's determined to spend months to crack you passphrase specifically. If you can step up to about 2^80 alternatives that's better, but of course that's harder if you actually need to remember them. If you're using a password manager however there's no need to skimp.

---

Now let's consider your scheme. The ASCII character set has 21 consonants and 5 vowels.

Now here's a trick to make the math much simpler. If we take the base-2 logarithm of the number of alternatives we get the entropy of one such random choice. And the entropy of the concatenation of independently chosen strings is the sum of their entropies. This means that your random choices get you:

• log2(21) = 4.4 bits for each consonant;
• log2(5) = 2.3 bits for each vowel;
• log2(21) + log2(5) = 6.7 bits for each syllable;
• 2 * (log2(21) + log2(5)) = 13.4 bits for each group (since the separators are predictable and don't add anything)

This means that the entropy of your passphrases is the number of groups multiplied by 13.4. And that means that you need:

• 5 groups to get to the 64-bit threshold;
• 6 groups to get to the 80-bit threshold.

Which means that your examples, if chosen truly at random, meet the 64-bit threshold because they have 5 groups:

vapu-dapu-fato-sovu-gazi
mipi-rodo-qiba-tiwu-cihe
qana-jeru-hibu-toka-xixu
fuca-kigu-moka-koxu-yopu

So if adding one extra group to your passphrases isn't a big bother, I'd recommend doing so, but your shorter length isn't bad. The one thing I'd caution you is this: use a cryptographically secure random number generator.

Answer 4

Let's assume the worst case that the attacker knows you are using this method. This is not a far-fetched assumptions, because the attacker might obtain some of your passwords from low-security services and notice the pattern.

How high would the entropy of your password scheme be?

You seem to consider Y a consonant, so there are 5 vowels and 21 consonants. That means there are 5 * 21 = 105 possible vowel-consonant pairs.

The latter example has 10 such pairs, so you have 105 ^ 10 possible passwords. This by far exceeds the usual recommendation of 8 mixed-case letters, numbers and typeable special characters (about 80 ^ 8, depending what special characters you account for).

The first example isn't actually that much different from that. You vary capitalization and the order of consonant and vowel, but you do that with a predictable pattern, so it is irrelevant for the worst case mentioned above. You have two character-pairs less, but compensate for that with a 4-digit number and 4 ^ 4 = 256 possible variations of punctuation, which is stronger by about factor 200 (2,560,000 vs. 11,025).