On the Complexity of Passwords

Passwords protect your accounts
Passwords protect your accounts

Nowadays, many applications and services run remotely somewhere on the Internet. In order to use the tools, you usually need to authenticate yourself with a user name and password. The complexer the password the safe your account. There are several ways to make a password complex. For example, you can choose characters from many different character classes: small letters, capital letters, numbers, special characters. Or you can use an extraordinarily long password, for example a sentence like ‘my pigeon loves to jump with the sunglasses of my neighbour on Sundays’. The password will be even more secure if the sentence contains a spelling mistake, and if it reveals something embarrassing it will be easier to remember the sentence :)

I claim that the password sentence above is much more secure than the password a0%Al;k/m (and various password analysis tools support my claim). Consequently, it is even more vexing when the service providers have annoying requirements for a password: it must, for example, consist of lower case letters, upper case letters, digits and be at least 8 and at most 20 characters long. I absolutely cannot understand why some providers put a ceiling on the length of a password!? My secure password sentence above would be rejected, but the rather insecure password gets accepted.

The password strength measured in terms of entropy

I wrote this article when I needed to implement password authentication for one of my projects. However, instead of demanding different character classes and a minimum length I decided to demand a minimum complexity. Here, I measured the complexity in terms of theoretical entropy of the password: the entropy per character of a password, which contains characters from many character classes, is much higher than the entropy of a password, which only consists of numbers.

I calculate the entropy H\Eta (Greek letter Eta) as H=Llog2N\Eta = L\log_2 N, with LL being the length of the password and NN being the size of the alphabet. Thus, a long password has a higher entropy than a short one; a password, which contains characters of different classes, has a higher entropy than a password, which contains only numbers. According to this method, the following passwords have a similar complexity:

  • a0%Al;k/m (59.2647 bit entropy)
  • 123456789012345678 (59.7947 bit entropy)

This allows service operators to define a minimum entropy for chosen passwords and users can chose passwords more liberally. I have attached my implementations below this article.

General password tips

Finally, I have some general tips on choosing and storing passwords.

Use different passwords!

In my opinion that is the most important rule. Passwords get compromised pretty often: A hacker breaks into a provider’s site or a dissatisfied administrator shares the database in some underground forums. If you are using the same password for all services, an attacker will immediately get access to all your accounts. For example, if Twitter gets hacked, the hackers can also access your Facebook profile with your login data.

Of course, it is difficult to remember a different password for each service, especially if you want to have them very complex. Therefore, two tricks:

  • Choose a password rule. For example a_0%Al;k/m, where you always replace the underscore with the first and last letter of the service you want to use the password for. For Twitter the password would be atr0%Al;k/m. This password will then fail on Facebook, where the password would be afk0%Al;k/m.
  • Use a password manager! They are really good. If you do not trust the password safe, you can also remember a prefix or suffix to the passwords. Thus, the password manager only stores a part of the password (which can be complex and long), but you would have to enter a few more characters to use it. This means, even if the password database gets into the wrong hands, an attacker cannot do anything with it: None of the passwords work without your additional knowledge! :)

Use several factors

Many services offer a two-factor authentication. Usually you have to enter a code in addition to a password,

  • which you will receive via SMS,
  • which is calculated by an app, or
  • which is generated by a hardware token.

This type of authentication is much more secure than a pure password.

Implementation of the entropy check

Maybe my implementation helps someone?

Client side at an Angular frontend:

import { AbstractControl, ValidationErrors, ValidatorFn } from '@angular/forms';

/**
 * A validator that checks if a string contains enough entropy.
 * It accept a validation error object to return if it encounters an error,
 * and the minimum number of bits required
 */
export function entropyValidator(error: ValidationErrors, minBits: number = 80): ValidatorFn {
  return (control: AbstractControl): { [key: string]: any } => {
    if (!control.value) {
      // if control is empty return no error
      return null;
    }

    let alphabetSize = 0;
    if (/\d/.test(control.value)) alphabetSize += 10;
    if (/[a-z]/.test(control.value)) alphabetSize += 26;
    if (/[A-Z]/.test(control.value)) alphabetSize += 26;
    if (/[^0-9a-zA-Z]/.test(control.value)) alphabetSize += 34;

    // if true, return no error (no error), else return error passed in the second parameter
    return control.value.length * Math.log2(alphabetSize) > minBits ? null : error;
  };
}

Server side at an PostgreSQL database:

create or replace function XXX.assert_valid_password
(
  new_password text
) returns void as
$$
declare
  alphabet_size  integer := 0;
  min_bits integer := 80;
begin

    -- contains lower case letter
    if (select new_password ~ '[a-z]') then
        alphabet_size = alphabet_size + 26;
    end if;

    -- contains upper case letter
    if (select new_password ~ '[A-Z]') then
        alphabet_size = alphabet_size + 26;
    end if;

    -- contains digit
    if (select new_password ~ '[0-9]') then
        alphabet_size = alphabet_size + 10;
    end if;

    -- contains special char
    if (select new_password ~ '[^A-Za-z0-9]') then
        alphabet_size = alphabet_size + 34;
    end if;

    -- estimate entropy
    if length(new_password) * log (2, alphabet_size) < min_bits then
        raise exception 'Password is too weak' using errcode = 'WEAKP';
    end if;
    
end;
$$
  language plpgsql volatile;