How to use permutation for a password generation

Simple Password is Like an Open Door

As hacker tools and computing power are getting more efficient every day passwords have to be very strong in order to avoid system breach and data theft. It is our duty as developers to employ all the possible mechanisms in order to prevent that kind of a situation.

We can not rely on users that they will always set a strong password but instead we have to enforce a strong password policy. I am also one of those users. When I am in hurry or just testing some new application sometimes I will use weak passwords similar to “orange123” or “green password”. Smile if you have done it too :-)

So never ever, never, ever, use a simple password. Never!

In shared systems like a cloud hosting and email servers this is especially important.  Where acts of one user can have impact on other. For example email password was breached with brute-force attack and the attacker started to send SPAM email which resulted in blocking of that server by other servers on the Internet.

The Password Policy

On the profile page users have the option to change their own passwords let's validate that the password must be in specific format which will ensure the strength from the beginning.

Password Format:

• Must contain at least 1 lowercase letter
• Must contain at least 1 uppercase letter
• Must contain at least 1 number
• Must contain at least 1 special character
• Must contain at least 8 characters in total
• Must avoid sequence of the same characters ( e.g. “aa” )

Following defined rules can sometimes be hard, frustrating and just bad user experience. When user needs to spend quite a time to create a password.

So let’s write simple password generation tool that can generate passwords like $tR0n9Ps.

Naive Approach to the Password Generation Code

Normally when you are presented with this kind of a problem and you need some simple solution you just start prototyping code in your mind. At first everything seems very simple, just few lines of code and no more than one hour of work. In the following text we will find out if its true.

Quick solution could be the following algorithm:

• For the base we will generate 8 random lowercase letters
• If a generated letter is the same as a new letter pick new random letter
• Insert 1 uppercase letter on random spot
• Keep track of used random spots in order to prevent overwriting
• Insert 1 random digit
• Insert 1 random special character
• And hopefully we will end up with the password like aeTw1d?j

Even though this algorithm will satisfy given rules it has many limitations. The lowercase letters are always the base, there is no possibility that the password can contain two or more characters that are not lowercase letters, etc.

To avoid these limitations we need to dive deeper into the code, refactorize it and add even more exceptions and cases. Now our task has become fairly complicated and all of the estimates from the beginning can be flushed down the drain.

Enter the World of Permutation

Let’s repeat our goal to generate simple password generator and validate user typed passwords. So big class level enterprise solutions with a lot of lines of code are off the table.

With permutation approach of programming our code becomes piece of cake because computer will deal with all of the rules with just few simple instructions from our side. At the same time we will write password validation code and therefore have complete solution in just few lines of a code.

Example of a Simple Permutation Code

Here is the code that for given number will try to generate the same and it will repeat process until it succeeds. This algorithm will use digits  from 0 to 9 and try to generate wanted number from scratch.

function randomCharFromSet(set) {
  return set.charAt(Math.random() * set.length);
}

function matchViaPermutation(result, counter) {
  counter || (counter = 1);
  var set = '0123456789', generated = '';

  for (var n = 0; n < result.length; n++) {
    generated += randomCharFromSet(set);
  }

  if (result !== generated) {
    return matchViaPermutation(result, ++counter);
  } else {
    console.log('Matched result "' + result + '" in', counter, 'permutations');
    return generated;
  }
}

// > matchViaPermutation('15');
// > Matched result "15" in 144 permutations

Password Generator via Permutation

var characterSet = 
    'abcdefghijklmnopqrstuvwxyz' +
    'ABCDEFGHIJKLMNOPQRSTUVWXYZ' +
    '0123456789' +
    '.!#$%&-';

var PASSWORD_FORMAT = new RegExp([
   /^/                    //start
  ,/(?=.{8,})/            //must contain at least 8 characters
  ,/(?=.*\d)/             //must contain one digit
  ,/(?=.*[a-z])/          //must contain one lowercase letter  
  ,/(?=.*[A-Z])/          //must contain one uppercase letter
  ,/(?=.*\W)/             //must contain one special character
  ,/(?:(.)(?!\1+))*/      //must not have repeating characters in a sequence (aa)
  ,/$/                    //end
].map(function(r) {return r.source; }).join(''));


function generatePassword(length){
  if(length < 8){ throw Error('Password length too short for given rule!'); }
  
  for(var n = 0, result = '', l = length || 10; n < l; n++){
    result += characterSet.charAt(Math.random() * characterSet.length);
  }

  return PASSWORD_FORMAT.test(result) ? result : generatePassword(length);
}

// Let's execute the code:
// generatePassword();
// Fmihd#vW9f

The most important part of this code is the PASSWORD_FORMAT.

That part contains all of the rules for the password and additionally it also serves as password validator. Therefore if we want to change password format we only need to change one line and the code will figure out how to generate a password in given format.

From the above code we can see that the steps are as follow:

1. Here is the format of the password
2. Here are the characters that we want to use
3. Try to generate password that matches given format
4. If it does not match our demands repeat step 3.