Thursday, 6 September 2007

Good Password Generation?

Following on from my previous articles about password generation and the potential flaws in using password generation tools, I thought it might be useful to produce a tool that generates robust passwords based upon a generation code (such as an asset number).

I had the following objectives for the tool:
- Generate passwords that were random every time
- Generate a repeatable password based on a numeric seed using an algorithm that was not easy to break
I also wished for the generation to be configurable:
- Allow passwords between 1 and 15 characters
- Allow a character set to be specified
- For random passwords, allow a quantity of passwords to be specified
- For repeatable passwords, allow an asset number to be entered

I started off by looking at producing passwords that were random every time. These would not be based on asset codes, but instead should generate passwords that appear truly random when compared to each other.

I decided to implement two types of random password generator, both based on Microsoft .Net random number generators.
The first was to be based on the simple subtractive random number generator which is implemented by the .Net class Random.
The second would be based on the cyptographic random number generator, RNGCryptServiceProvider (in System.Security.Cryptography).

To produce the passwords, the random number generator would be used to supply a byte array containing a sequence of character positions from the character set used to seed the passwords.

For simplicity, say I was using the character set 'ABCDE' and I wanted a 8 character password.
I request a sequence of 8 bytes from the random number generator, each with a value between 0 and 4, and receive the byte array '0, 3, 2, 4, 4, 2, 0, 1'.
I then use these positions to retrieve characters from the character set, as so:
0 = A, 3 = D, 2 = C, 4 = E, 4 = E, 2 = C, 0 = A, 1 = B
Which gives a password 'ADCEECAB'.

Passwords based on random number generators can be good because there should be no discernable pattern present in the generated sequence.

However, passwords generated in this way do result in some security problems:
- The passwords are not repeatable because they are not based on an asset number. This means they have to be stored somewhere for later retrieval, which may potentially represent a huge security risk.
- The passwords may not be truly random. Random number generators work from a predefined formula for which gives the appearance of randomness, however, they are not truly random (see below for more on this).

Before I move on, I would like to discusss the randomness of the passwords that can be generated using a random number generator.
A simple random number generator, such as the Random class in Microsoft.Net, is a pseudo-random number generator, that is, the numbers that are generated are not random at all, they are derived mathematically using a formula, and the numbers appear to be random.
The Random class (in .Net) uses a "seed" to generate a sequence of numbers. In .Net, by default this is based on the number of ticks so far in the day. However, a seed can also be supplied directly to the class Constructor.
This highlights an important limitation of simple random number generators - if the same seed is used again, the sequence of numbers generated will be the same.

Create a simple program that instantiates a Random class with a seed of 1, and then gets the first 10 integers (Random.Next()).
Execute the program a few times. Each time the numbers generated will be the same, in the same order.
It is very important to accept that if the seed used to create the Random class can be ascertained, the entire sequence of numbers used to generate a password can be recreated, and this may prove the undoing of any password generator based on pseudo-random number generation.

For a repeatable password to be generated, an asset code will be required. To simplify matters, the asset code will be limited to numerics only.

I decided to implement two repeatable password generators:
- Simple. This will be based on the principals outlined above with regards to using a fixed seed for random number generation. The seed will be the asset code.
- Complex. This will be based on a method that uses a predefined formula to generate the asset code. I will not reveal the formula because I would like to see whether anyone can figure it out for themselves.

To generate the actual passwords, the repeatable password generation will work in the same way as the random number generator, that is a sequence of valid numbers will be generated that will indicate the positions of the character to be used in the password from a character set.

Repeatable password generators offer advantages over randomly generated passwords, because they do not need to be written down anywhere; They can be generated at any later time simply by supplying the asset code.

However, they do have limitations:
- The password that is generated is, ultimately, based on a formula of some sort and so can be broken given a large enough set to work with
- The tool must be properly protected from unauthorised access. Access to the tool is, essentially, access to the entire system.

I decided to implement each of the different generation methods (both random and repeatable) in classes that support a common interface, IRNG. This way my generation program does not care which actual implementation is being used to generate the passwords.

I wrote a manager class called PwManager, which will be responsible for generating the passwords using the desired generator.

I then placed the manager class, the interface and the generator classes in an assembly, and referenced this from my Windows Forms project.

In my Windows Forms project, I added a form to allow the user to configure the generation method, password length and character set and also, depending upon the chosen generation method, the number of passwords to be generated or the asset code.
I then added a second form which would be used to display the results of the generation.

When a button is pushed on the first form, the PwManager is instantiated and configured with the appropriate parameters, and the generation of the password(s) takes place. The resulting configuration information and password list is displayed on the second form.

If you would like to download and use the password generator program, it can be downloaded here.

There are two assemblies in the download, a library and an executable. The executable is simply a UI which presents the functionality from the library.
Feel free to reference the library from your own code and make use of the generation methods.

A final note: Please do not use the program to generate passwords for your organisation - it is freely available on the web (from my blog) and others could easily obtain it. Instead, the source code is (as always) available upon request - ask me for it and modify it to make it unique to your organisation.

I have demonstrated several techniques for generating passwords during this article.
I would be interested to hear if anyone can break the repeatable password generators, you are welcome to try!


JustSomeGirl said...

Is there any chance of source code for those of us who have our own pet project password generators but they do not fare so well under the FIPS standards test with applications like Burp Suite Sequencer. I'd be interested in how you achieve so much entropy.

Memia said...

Thanks for your comment on my article.
You are more than welcome to the source code for the demo project, simply drop me an e-mail (my contact details are on the bottom of my blog page) and I will get the code over to you.

JustSomeGirl said...

I sent the email several days ago.

No reply.

Anonymous said...

Good brief and this fill someone in on helped me alot in my college assignement. Thank you as your information.