john-users - matching a password policy (was: generate passwords with wDDDwDDD template)

Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20100314202733.GA21262@openwall.com>
Date: Sun, 14 Mar 2010 23:27:33 +0300
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: matching a password policy (was: generate passwords with wDDDwDDD template)

On Thu, Mar 11, 2010 at 12:58:39AM +0300, Gogol Bordello wrote:
> Ok, I need a passwords list where password is only 8 chars in length, 
> chars are [a-Z] and [0-9], each password must contain at least one digit 
> or at least one letter. For example:
> 
> qwertyu1 - matches my needs
> qwertyui - doesn't match
> 1234567a - matches
> 12345678 - doesn't match

I assume you meant "at least one digit and at least one letter" (not
"or").  Do you realize that applying such a policy to the complete set
of 8-character passwords using those 62 different characters (lowercase
and uppercase letters, and digits) reduces your total search space only
by 24%?  It might not be worth the bother.  You might waste more CPU
time trying to avoid those "impossible" passwords than actually testing
them against your hashes.  On the other hand, if your hashes are slow to
compute and/or salted (and you have many salts) or if you're going to
focus on searching a subset of your total password space where the
"impossible" passwords happen to be more common, then applying the
policy would make more sense.

(In case I misunderstood and you did not mean to include uppercase
letters, then excluding the "impossible" passwords is of even less
benefit - they account for 7% of the total number of 8-character
passwords consisting of lowercase letters and digits.)

Below is a revision of the external mode filter() from:

http://www.openwall.com/lists/john-users/2009/10/28/11

that enforces your policy the way I understood it (your description was
still not precise enough).

[List.External:Policy]
int mask[0x100];

void init()
{
	int c;

	mask[0] = 0x100;
	c = 1;
	while (c < 0x100)
		mask[c++] = 0x200;

	c = 'a';
	while (c <= 'z')
		mask[c++] = 1;
	c = 'A';
	while (c <= 'Z')
		mask[c++] = 1; /* treat them same as lowercase letters */
	c = '0';
	while (c <= '9')
		mask[c++] = 2;
}

void filter()
{
	int i, seen;

/*
 * This loop ends when we see NUL (sets 0x100) or a disallowed character
 * (sets 0x200).
 */
	i = -1; seen = 0;
	while ((seen |= mask[word[++i]]) < 0x100)
		continue;

/*
 * We should have seen at least one character of each type (which "add up"
 * to 3) and then a NUL (adds 0x100), but not any other characters (would
 * add 0x200).  The length must be 8.
 */
	if (seen != 0x103 || i != 8)
		word = 0; // Does not conform to policy
}

You use it like it is shown here:

http://www.openwall.com/lists/john-users/2009/02/10/3

Please note that I included a length check in the filter(), but you're
better off configuring JtR to try passwords of length 8 only by other
means - e.g., by setting MinLen and MaxLen to 8 for "incremental" mode.

Also, since digits-only passwords correspond to a negligible portion of
your total password space (0.000046% of all 8-character passwords using
the set of 62 different characters), you could simplify the check to
"contains at least one digit":

[List.External:AtLeast1]
void filter()
{
	int i, c;

	i = 0;
	while (c = word[i++])
		if (c >= '0' && c <= '9')
			return; // Found at least one suitable character, good

	word = 0; // No suitable characters found, skip this "word"
}

or optimizing it for speed of the filter() function:

[List.External:AtLeast1]
int mask[0x100];

void init()
{
	int c;

	mask[0] = 0;
	c = 1;
	while (c < 0x100)
		mask[c++] = 1;

	c = '0';
	while (c <= '9')
		mask[c++] = 0;
}

void filter()
{
	int i;

	i = -1;
	while (mask[word[++i]])
		continue;
	if (word[i])
		return; // Found at least one suitable character, good

	word = 0; // No suitable characters found, skip this "word"
}

Alexander
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.