How a bad password generator can ruin security

This is a true story about really broken password generator that was used at my college. The good idea and a bad implementation.

On 30th of December 2005 all students at PJIIT received email which sounded like this:

From today (30.12.2005) new password policy is going to be used:

Password must contain eight or more characters
Password must not contain username or any part of it
Password should contain characters from three of four specified categories:
1. Small letters [a-z]
2. Capital letters [A-Z]
3. Digits [0-9]
4. Special characters: [!#$%^&*()_+{}:";'<>,.?]

This policy seems to be reasonable. Every of at least eight letters in password could be one of 82 possible characters ([a-zA-Z0-9!#$%^&*()_+{}:";'<>,.?] = 25+25+10+22 = 82).
Number of possible passwords is huge 82⁸ = 2044*10¹².

But creating such complicated password that fits to that policy was too hard for some students. Some of them just added some characters to the end of their previous password (password bart78 became bart78##). Others used password generator supplied by our college network adminstrators.


At first glance generator seems to create reasonable passwords. Let's concentrate at passwords generated at default "complexity 3".

character family	[a-zA-Z]	[0-9]	[!"#$%&'()*+,-./]
number of characters in generated pass	4-6	1-2	1-2

Number of characters for each character family is selected randomly from specified range. There are only four possible character patterns 4-1-1, 5-2-1, 5-1-2 and 6-1-1. I haven't written this password generator myself but I can bet that every pattern have the same probability to be selected. Let's count number of possible passwords in each pattern.

letters	digits	special	probability to be selected	number of uniqe possible passwords
4	2	2	25%	504 * 102 * 152 = 0.140 * 1012
5	2	1	25%	505 * 102 * 151 = 0.468 * 1012
5	1	2	25%	505 * 101 * 152 = 0.703 * 1012
6	1	1	25%	506 * 101 * 151 = 2.243 * 1012
			sum:	3.656 * 1012

That's not good. From 2044 * 10¹² possible passwords, generator can generate only 3.6*10¹² passwords. It's less than two pro miles of possible passwords!

The generator is even worse. That's because of Microsoft's programming framework and their approach to random numbers.
From Microsoft's documentation of Randomize function:
"[...] This example uses the Randomize statement to initialize the random-number generator. Because the number argument has been omitted, Randomize uses the return value from the Timer function as the new seed value."

And the magic "Timer function" documentation:
"Timer Function returns the number of seconds that have elapsed since 12:00 AM (midnight)"

Seconds from midningt, it means 24*60*60 = 86400 possible initial seed values for random number generator. That means only 86400 unique possible generated passwords.

Take a look at previous table. Most of unique passwords are in the fourth category. But probability of selecting this category is only 25%.
If we omit this category, we will still have 75% of probability of guessing the generated password. In our situation there are only 32000 unique passwords in first three categories.

In conclusion, from 2044*10¹² possible passwords, bogus password generator created situation that 75% of passwords will be in group of only 32*10³ unique passwords.
In this case brute force attack will have great chances of success.

UPDATE #1: The Visual Basic random number generator is even worse. Mark Hutchinson writes that in fact there are only 64000 possible random seeds values! (Not 86000 I mentioned before).