Effect of password policies on keyspace reduction

The tables below show just how password policies that require either at least N character classes or at least N characters of each class affect the total keyspace for each length.

Once in a while, someone posts to john-users asking how to restrict John the Ripper to match a policy, hoping that this would substantially reduce the number of candidate passwords to try. Most of the time, such assumptions are incorrect, although in some extreme cases they are valid.

For example, for printable US-ASCII (95 different characters) and length 8 requiring at least 3 character classes (out of four: digits, lowercase letters, uppercase letters, and other characters) reduces the keyspace by only 5.5% (so it is a reasonable thing to do). However, requiring at least 2 characters of each class (which for length 8 implies exactly 2 characters of each class) reduces the keyspace for length 8 by a factor of 52.9 (which is almost as bad as making passwords one character shorter) and for length 9 by a factor of 17.6.

In practice, passwdqc combines the “at least N classes” approach with other requirements, which disallows common password patterns while not reducing the keyspace too much. More trivial approaches are just not good enough: simply requiring e.g. at least 3 classes allows for passwords of the form “Password1” (a common pattern, even when not word-based), and requiring at least 2 characters of a class often reduces the keyspace too much. Also, passwdqc supports longer passphrases, where it can require as few as 2 different character classes (such as letters and word separators).

To have John the Ripper match a trivial policy, revisions of the [List.External:Policy] external mode sample may be used (providing a filter for use with other cracking modes), which may or may not be beneficial (because generating and filtering out some candidate passwords involves overhead, and also because assumptions about passwords actually following a policy are often wrong).

• Comments on reddit /r/netsec/
• Blog post on the Norwegian National Security Authority's blog (main post in Norwegian, but it gives mathematical formulas, which are obviously international; additional comments are in English)

Here's the C program that was used to produce the tables above:

/*
 * Copyright (c) 2011 Solar Designer <solar at openwall.com>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted.
 *
 * There's ABSOLUTELY NO WARRANTY, express or implied.
 */
 
#include <stdio.h>
#include <assert.h>
 
#define MIN_LENGTH 6
 
#if defined(__GNUC__) && defined(__LP64__)
#define MAX_LENGTH 12
typedef __uint128_t count_t;
#else
#define MAX_LENGTH 9
typedef unsigned long long count_t;
#endif
 
#define MASK_BITS_PER_K 8
#define MASK_MASK_PER_K \
        ((1 << MASK_BITS_PER_K) - 1)
#define MASK_GET(mask, i) \
        (((mask) >> ((i) * MASK_BITS_PER_K)) & MASK_MASK_PER_K)
 
static char *count2str(count_t count)
{
        static char out[40];
        char *p;
 
        p = &out[sizeof(out) - 1];
        *p-- = 0;
        do {
                *p-- = '0' + count % 10;
        } while (count /= 10);
 
        return ++p;
}
 
static count_t count(unsigned int length,
    unsigned int mask, unsigned int classes)
{
        unsigned int k[MAX_LENGTH];
        unsigned int i;
        count_t total = 0;
 
        assert(length <= sizeof(k) / sizeof(k[0]));
 
        for (i = 0; i < length; i++)
                k[i] = 0;
 
        goto start;
        while (1) {
                i = length - 1;
                while (++k[i] >= 4) {
                        if (!i)
                                return total;
                        k[i--] = 0;
                }
start:
                {
                        unsigned int seen = 0, seen_classes = 0;
                        for (i = 0; i < length; i++) {
                                unsigned int shift = k[i] * MASK_BITS_PER_K;
                                seen += 1 << shift;
                                if (((seen >> shift) & MASK_MASK_PER_K) == 1)
                                        seen_classes++;
                        }
                        for (i = 0; i < 4; i++)
                                if (MASK_GET(seen, i) < MASK_GET(mask, i))
                                        break;
                        if (i < 4 || seen_classes < classes)
                                continue;
                }
                {
                        count_t n = 1;
                        for (i = 0; i < length; i++) {
                                unsigned int m;
                                switch (k[i]) {
                                case 0:
                                        m = 10;
                                        break;
                                case 1:
                                        m = 26;
                                        break;
                                case 2:
                                        m = 26;
                                        break;
                                default:
                                        m = 33;
                                }
                                assert(n * m > n);
                                n *= m;
                        }
                        assert(total + n >= total);
                        total += n;
                }
        }
}
 
int main(void)
{
        unsigned int length, classes, digits, lowers, uppers, others;
        count_t total = 0;
 
        puts("| Length | Min classes | Password count | % of total |");
        for (length = MIN_LENGTH; length <= MAX_LENGTH; length++)
        for (classes = 1; classes <= 4; classes++) {
                count_t current = count(length, 0, classes);
 
                if (classes == 1)
                        total = current;
 
                printf("| %u | %u | %s | %.2f%% |\n", length,
                    classes,
                    count2str(current), 100.0 * current / total);
                if (length > 9)
                        fflush(stdout);
        }
 
        puts("\n| Length | Min digits/lowers/uppers/others | Password count | % of total |");
        for (length = MIN_LENGTH; length <= MAX_LENGTH; length++)
        for (digits = 0; digits <= 2; digits++)
        for (lowers = 0; lowers <= 2; lowers++)
        for (uppers = 0; uppers <= 2; uppers++)
        for (others = 0; others <= 2; others++) {
                unsigned int mask =
                    digits |
                    (lowers << MASK_BITS_PER_K) |
                    (uppers << (2 * MASK_BITS_PER_K)) |
                    (others << (3 * MASK_BITS_PER_K));
                count_t current = count(length, mask, 0);
 
                if (!mask)
                        total = current;
 
                printf("| %u | %u/%u/%u/%u | %s | %.2f%% |\n", length,
                    digits, lowers, uppers, others,
                    count2str(current), 100.0 * current / total);
                if (length > 9)
                        fflush(stdout);
        }
 
        return 0;
}

The following (lazy) python script computes the list using the combinatorial formula instead. This allows us to compute it much faster and extend it to password lengths beyond 40 (if implemented in C, it should be even faster).

##
# Copyright (c) 2012 Sondre Rønjom <sondrer at gmail.com>
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted.
##
 
n1 = 10 # digits
n2 = 26 # lowercase
n3 = 26 # uppercase
n4 = 33 # special 
 
# Max length of passwords
MIN_LEN = 6 
MAX_LEN = 50 
 
# Change these parameters to change bounds on policies
max_digit = 2 
max_lower = 2
max_upper = 2
max_special = 2
 
# Cardinality of alphabets
n1 = 10 # digits
n2 = 26 # lowercase
n3 = 26 # uppercase
n4 = 33 # special 
 
def binomial(n, k):
    result = 1
    for i in range(1, k+1):
        result = result * (n-i+1) / i
    return result
 
def multinomial(t1,t2,t3,t4):
    t = t1+t2+t3+t4
    total = binomial(t,t1)*binomial(t-t1,t2)*binomial(n-t1-t2,t3)*binomial(t4,t4)
    return total
 
 
def prod(r1, r2,r3,r4):
    return pow(n1,r1)*pow(n2,r2)*pow(n3,r3)*pow(n4,r4)
 
def count2(n,r1,r2,r3,r4):
  k = r1+r2+r3+r4;
  d = n-k;
  total = 0
  for s1 in range(d+1):
      for s2 in range(d+1):
          for s3 in range(d+1):
              for s4 in range(d+1):
                  if(s1+s2+s3+s4 == d):
                      s = prod(s1,s2,s3,s4)
                      total += multinomial(r1+s1,r2+s2,r3+s3,s4+r4)*s;
  return prod(r1,r2,r3,r4)*total
 
print "\n| Length | Min digits/lowers/uppers/others | Password count | % of total |"
 
for n in range(MIN_LEN,MAX_LEN+1):
    total = count2(n,0,0,0,0)
    for r1 in range(max_digit+1):
        for r2 in range(max_lower+1):
            for r3 in range(max_upper+1):
                for r4 in range(max_special+1):
                    cnt = count2(n,r1,r2,r3,r4)
                    print " ", n , " | ", r1,"/",r2,"/",r3,"/",r4," | ",cnt, " | ", 100*(float(cnt)/float(total))

Back to John the Ripper user community resources.