Good and Bad Passwords How-To

A Review of Some Automated Password Generators

• Automated Password Generators
• State Department Passwords
• U.S. Government Automated Password Generator
• First password.pl

Automated Password Generators

Today, small dictionaries or common password lists get a significant percentage of passwords. Ways to extend and improve the cracking dictionaries were reviewed. When the limits of improving the dictionaries and rules are reached, we've shown how to build front end generators to replace the cracking tools low yield, brute force methods. These build passwords along the lines of standard good password recommendations. The yield should be much better than brute force. As computing power increases, password cracking tools should be able to generate ever larger numbers and variations on what have generally been regarded as strong passwords.

The response to automated cracking methods lies in letting computers create passwords for us. An automated password generator can almost instantaneously create as many strong passwords as we want. If such a tool is properly configurable it should be able to generate passwords with any degree of structure or randomness as is desired. The default control pattern in the current password.pl generates passwords from 147 trillion possibilities. In line with the large set, many of these passwords are more difficult than most users and administrators are used to dealing with. There are alternative control patterns and option settings that create more pseudo word like passwords which will be discussed later.

State Department Passwords

In the early eighties the State Department built an automated password generator as part of their Controlled User Environment. This generator did not generate random passwords but highly structured passwords that were easy to remember. Truly random sequences of the 95 printable ASCII characters become difficult to remember and type even at 4 characters, and beyond 6 characters very few normal humans can remember a truly random sequence, at least not without substantial effort and frequent use.

The State Department analysts realized the problem of truly random passwords and recognized that relatively easy to remember passwords could be built from three small, easy to remember pieces. The State Department passwords conformed to a very specific pattern, CVC99CVC or consonant vowel consonant, digit digit, consonant vowel consonant. Click here to see dynamically generated examples. The letters were all upper case. This looks too simple to have a significant number of passwords but the arithmetic is quite simple: 21 * 5 * 21 * 10 * 10 * 21 * 5 * 21 = 486,202,500. That's nearly 500 million passwords but that's only slightly larger than the word, non letter, word pattern that we worked through in about three hours.This was fine for the mid 80's but not adequate for the twenty first century.

Because of the consonant vowel consonant sequence, the alphabetic sequences are fairly easy to pronounce. Anyone can remember two digits. Most of these eight character passwords are really quite easy to remember which is a significant accomplishment given that the password universe is several hundred times larger than the English language. Of course a user only needs to remember his or her password, not the nearly 500 million that are possible.

U.S. Government Automated Password Generator

Later, the U.S. Government developed a password standard that was specifically designed to create pseudo random letter sequences that were fully pronounceable by those who speak English. The character sequences are tested against pronounceability tables as they are built. As soon as an unpronounceable result is obtained, the password is discarded and the process restarted. The standard excludes the use of mixed case or any characters except letters.

There are supposed to be approximately 1.6 trillion pronounceable ten character sequences. The authors of the standards thought this was adequate for any purpose. Longer passwords would be harder but these are not discussed in the standard. The standard was finalized in late 1993 and was to go into effect March 1994.

1.6 trillion seems marginal when the standard was adopted and simply inadequate today for anything of particular value. It only takes 185 days at 100,000 passwords per second to do all possibilities. This is not likely to be a major problem for anyone with significant resources to apply to the problem. Further, given the nature of the standard, a cracker knows exactly what character set to work with for any site that employs the standard, making such sites perfect targets for brute force attacks. If a site using this standard, experienced a breach in which accounts and password hashes were compromised, it seems almost a forgone conclusion that all passwords will be cracked.

Due to how NT stores password hashes , all alphabetic passwords are a bad joke. If an NT system is compromised so that the password hashes are obtained, a fast desktop system should be able to crack all possible pure alpha passwords in less than half an hour. Increasing the password length to NT's maximum of 14 would make no difference. Though NT hadn't yet been created, the LANMAN hashing scheme that is the source of NT's password storage problems predates the Automated Password Generator by several years. It seems to me, someone put end user, ease of use, way ahead of security here.

The idea behind my first password.pl was the State Department style passwords. I added some configuration options for multiple purposes. I wanted variations that would allow for increased complexity and thus a larger universe of possible passwords. Since I gave the Perl source code away from the very beginning, I wanted sites to be able to make adjustments suitable to their own needs. The generated passwords could be made easier or harder or more or less consistent than the default settings. More important, sites could make adjustments to the algorithm both by changing several constants or even the program logic. Even if a potential intruder knew that a site he or she was attacking, used password.pl and had their own copy, there would be no way of knowing that the passwords the intruder saw, looked like those being generated at a particular site.

If just the first consonant of each alpha sequence (in the State Department default pattern) is randomly allowed to be upper case, the number of passwords jumps to just under 2 billion. If the upper casing is truly random then approximately one fourth of the generated passwords will still be all lower case. If program logic discards the all lowercase passwords and regenerates a new password until there is one upper case letter, then the password population is actually reduced by one fourth even though the resulting passwords look more complex (and are better passwords).

If an attacker knows the exact algorithm being used and that it forces at least one upper case character, then they know that if the first generated character is lower case, the first character of the second alpha sequence must be upper case. If the all lower case passwords are allowed to display, then the attacker needs to generate a larger population to cover all possibilities. The danger of displaying the all lower case passwords, is that users are likely to pick the easier of the options presented to them. Users who pick all lower case, will have their passwords found by a cracker creating dictionaries from matching patterns but using only lower case letters. If nearly all users pick the all lower case and the attacker anticipates this behavior, they won't bother to include the upper case in their generated passwords and will get most passwords with a quarter of the effort. If the ordinary users pick all lower case but the system administrators pick mixed case, the attacker may get most accounts but miss the really desirable administrator accounts.

Password.pl's first letter upper option forced at least one of the leading alpha characters to be upper case. Both could be; there were always lower case letters in other positions.

There is no right or wrong choice as making the best choice depends on correctly anticipating human behavior (selection from among the displayed passwords, assuming more than one is shown at a time). It also depends on anticipating an attacker's potential reactions based on the attacker's assessment of the types of passwords users will choose.

Though there is no right or wrong, a weaker password is a weaker password regardless of the size of the set of passwords it was drawn from or how it was created. A seven character password with six same case letters and a digit will always be a weaker password than a loosely similar password with nine characters including mixed case letters, a digit and a symbol. No plausible algorithm or approach to building a custom dictionary will get the nine character password before the seven. I used loosely similar because !!!!!!1Aa is a poor password. Still, it's hard to describe a rational way to find it before finding rud7gek which looks semi-decent for a seven character password.

An additional variation on the original State Department password pattern is to open up the digit positions to symbols. If all are allowed in either position, then the number of possible passwords with the pattern CvcnnCvc, where the n's are any non letter, is over 34 billion.

With any password generator that pseudo randomly builds passwords to match defined patters, there will be instances where limiting the displayed passwords by forcing a more complex appearance reduces the possible number of passwords. Here we are looking at two character positions that can be a digit or symbol. If all possibilities are allowed, there will be more possible passwords but there will be combinations that are all numbers or all symbols. Users are likely to pick the easier all numeric combinations. This is identical to the choice discussed when two words were being combined with two non letter characters. The issue is still the same with longer character sequences but the forced diversity is more clearly the better choice as the sequences get longer.

The original password.pl actually did something quite different. There was a variable called symbolOdds. At 0, two digits were always output. At 1 there would nearly always be only a single digit. As it increased to 10 there was an increasing chance that there would be two digits or a digit and a symbol. At 10 there were always 2 non alphabetic characters. At least one was always a digit with about a 50% chance the other would be a symbol. When there was both a digit and a symbol they could occur in either order. When I wrote the original, I thought two symbols was just too difficult, so I created a deliberate bias toward the easier passwords. The current version has no such biases.

An additional option, randomly added an extra consonant following each consonant but more than two were never added in the whole password. The resulting character pattern could be represented by "Cc0vcc0nn0Cc0vcc0" where "c" is a consonant and "C" is an optionally upper case consonant, "v" is a vowel and "n" is a non alphabetic character. A "0" indicates the preceding character may or may not be present. Finally a mixed case option could override the first upper behavior and pseudo randomly forced all characters to be mixed case. Any generated password that happened to have all lower or all upper case letters was discarded and regenerated.

The original password.pl default behavior generated a mixture of passwords ranging from 7 to 10 characters with two alpha sequences of 3 to 5 characters with either or both of the leading characters upper case. The alpha sequences were separated by one or two digits or a digit and a symbol with the digit and symbol in either order. In any batch of ten passwords there was usually one or two very easy ones ("Cvcdcvc" where "d" is a digit) and a few suitable for an admin on an important system. The configuration options allowed from very easy to too hard to be practical.

Top of Page - Site Map

Copyright © 2000 - 2006 by George Shaffer. This material may be distributed only subject to the terms and conditions set forth on http://GeodSoft.com/terms.htm. These terms are subject to change. Distribution is subject to the then current terms, or at the choice of the distributor, those defined in a verifiably dated printout or electronic copy of http://GeodSoft.com/terms.htm at the time of the distribution. Distribution of substantively modified versions of GeodSoft content is prohibited without the explicit permission of George Shaffer. Distribution of the work or derivatives of the work, in whole or in part, for commercial purposes is prohibited unless prior permission is obtained from George Shaffer. Distribution in accordance with these terms, for private, unrestricted and uncompensated public access, non profit, or internal company use is allowed.