Wednesday, June 8, 2011

Truly Random and Complex Password Generator - Part 1 of 2


Skip to the 2nd part for the code snippet.

Its an important matter of security to enforce complex passwords that have a sufficient length. From personal experience, if you ask a normal user to create their own passwords, their passwords will be based on a character set consisting of 36 case-insensitive alphanumeric characters: a-z, 0-9 instead of the full 94 character set typable on all keyboard layouts. Also, most normal users would use dictionary based passwords with a predictable pattern: dictionary words at the beginning and numbers at the end.

Relying solely on the client-side or front-end to enforce the creation of passwords of at least 8 characters long and the use of special characters will not be practical in preventing the use of dictionary words as well as the usage of a certain pattern. Whatever the mechanism is on the client-side, the backend MySQL database should complement it.

Assigning complex passwords to users will, in effect, increase the number of characters from 36 to 94. By making the password randomly generated, the predictability of dictionary words and pattern matching is removed. The number of possible passwords is substantially increased. For an 8-character password string, under a reasonable time limitation, say 6 hours, and using a single modern computer, this results to a theoretical technically uncrackable password:

SELECT FORMAT(POW(32, 8), 0); 
  -- Results to 1,099,511,627,776 possible combinations. Note that the number of possible combinations is greatly reduced when the user limits the password to use dictionary words and pattern matching. This results to a crackable password in a short period of time.  

 SELECT FORMAT(POW(94, 8), 0); 
  -- Results to 6,095,689,385,410,816 possible combinations. By being randomly generated, the number of combinations is not reduced as explained above. This results to an theoretical technically uncrackable password given a short period of time.  

A password generator, to be truly random, should satisfy the following:
  • The character set for the generator should include all the typable characters on any keyboard layout: 

    a-z, A-Z, 0-9,
    and ` ~ ! @ # $ % ^ & * ( ) - = _ + [ ] { } \ / | ? ; : ' " , . < >

    This results to 26 + 26 + 10 + 32 = 94 characters.
  • Each of the allowed characters should all have an equal chance of being generated.

For practical purposes, we'll take aside arguments on password complexity versus password length, and we'll assume an 8-character password string. To generate any of the 62 alphanumeric characters, we'll use a base 36 statement as the formula:

            RAND() * 36),
      10, 36);

Using a base 36 statement gives us the most compact alphanumeric numeral system. The case sensitivity will be based on odds from a random number range in order to include the LOWER case of the alphabet.

The special characters can be generated by using the ELT function as the basis for the formula like:

      '`', '~', '!', '@', '#', '$', '%', '^',
      '&', '*', '(', ')', '-', '=', '_', '+',
      '[', ']', '{', '}', '\\', '/', '|', '?',
      ';', ':', '\'', '"', ',', '.', '<', '>');

In the continuation of this entry is an example of a true random and complex password generator function.


water outbreaks said...

If you are using mysql's Rand function, than you can't say its "Truly Random". Rand is pseudo random, not perfectly, truly random. Therefore, anything you create with it, is not truly random.

From the myslq manual

"RAND() is not meant to be a perfect random generator. It is a fast way to generate random numbers on demand that is portable between platforms for the same MySQL version. "

That will create strong passwords that are not easily cracked without brute forcing them, which unfortunately is pretty easy these days:

0v34c10ck said...

@water outbreaks

Thank you for your feedback.

The RAND() function gets predictability issues when it is seeded repeatedly with the current time, and because it is meant to be fast, the time is the same and it is re-seeded with the same seed. The predictability issue is that the random number generated is exactly the same, not a similar or close number from the previously generated one.

The solution presented here does not use seeded values such as RAND(3) in the example shown in the manual. RAND() can be repeatedly called without any predictability issues. The manual has to be updated to clarify that it refers to the seed value issue.

Regarding GPUs cracking strong passwords, the recommendation is to increase the password length. The 8-character password string stated here is meant to be just an example as stated above. Use a 12-character random password string and even GPUs will take years to crack it.