john-users - try all small character sets (too few different characters)

[<prev] [next>] [day] [month] [year] [list]
Date: Fri, 6 Aug 2010 09:20:41 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: try all small character sets (too few different characters)

Hi,

The attached external mode, called Subsets, will generate candidate
passwords from many small subsets of characters from a much larger full
character set.  This will test for passwords containing too few
different characters.

When applied to the contest NTLM hashes with its default settings
(lengths 1 to 8, up to 3 different characters), it cracks 25 passwords
in under 6 minutes (on one modern CPU core).  That's not too exciting:
many times more are crackable in the same amount of time with other
attacks, and many of the 25 would be quickly cracked with other attacks
too.  However, a few of them would be more difficult to crack by other
means.  When re-configured for lengths 9 to 10 (still up to 3 different
characters), it cracks 16 passwords in 48 minutes.  The first one of
these 16 is cracked in 1 second, and all of them look like they could be
more difficult to crack by other means.  Going to 4 different characters
would result in more cracks, but the attack duration would increase a
lot (yet this may be worth a try).

First test run, lengths 1 to 8:

ac               (ewakham)
te               (ceyerman)
guesses: 2  time: 0:00:00:02  c/s: 165696M  trying: **m m* m - **m* *m 
747!!            (dstrawhorn)
guesses: 3  time: 0:00:00:19  c/s: 125115M  trying: !QQQQy!Q - !QQQyyQy
guesses: 3  time: 0:00:01:35  c/s: 121405M  trying: fE)Ef)Ef - fE)f)E))
1111110*         (cwintermantel)
guesses: 4  time: 0:00:01:45  c/s: 121337M  trying: i**OiiO - i*O***i
guesses: 4  time: 0:00:02:28  c/s: 121134M  trying: /upp/up/ - /upppuup
00000B30         (pcerceo)
00000Z99         (iblasetti)
00000T>0         (tciubal)
r00tr00t         (hstanchfield)
2222221|         (kginard)
6G161            (lmorrical)
guesses: 10  time: 0:00:02:38  c/s: 121106M  trying: 1uu1>uu1 - 1uu>111>
333333}4         (dcoppedge)
guesses: 11  time: 0:00:03:03  c/s: 121043M  trying: k44dkkd - k4d444k
55555R]5         (jbrozie)
guesses: 12  time: 0:00:03:10  c/s: 121040M  trying: l555tl5l - l55l5llt
guesses: 12  time: 0:00:04:15  c/s: 120935M  trying: cA|cccc| - cA|c||AA
Art              (tseabright)
Bay              (hebia)
Def              (tpayment)
Ida              (rjez)
Jazz             (csrour)
New              (fburkey)
guesses: 18  time: 0:00:05:03  c/s: 120887M  trying: sOsSsOss - sOssOSSO
bla              (nmangiamele)
asv              (rgorlich)
fco              (mduplaga)
oneone           (kamey)
glgr             (sdudas)
whi              (tversluis)
sixsix           (sdanekas)
guesses: 25  time: 0:00:05:46  c/s: 120781M  trying: ~~~~~~}| - ~~~~~~~~

Second test run, lengths 9 to 10:

???????:::       (notinger_admin)
guesses: 1  time: 0:00:00:01  c/s: 188811M  trying: l```l```l` - l``l`````l
guesses: 1  time: 0:00:07:24  c/s: 113066M  trying: iiiii$}i$ - iiiiii}}i
77&777722        (cbuetow)
guesses: 2  time: 0:00:09:13  c/s: 114034M  trying: 9&96&&&669 - 9&96&&69&&
guesses: 2  time: 0:00:14:12  c/s: 114131M  trying: 22**2*2*2D - 22**2*D2**
99999959*        (csposato)
sssssss>*        (sgravelle)
guesses: 4  time: 0:00:14:42  c/s: 113119M  trying: *b*bA*bA* - *b*bAAbbA
guesses: 4  time: 0:00:16:47  c/s: 113697M  trying: ,8,,>8,>,8 - ,8,,>88>8>
000000}10        (fsellen)
0~0000020        (elandini)
000000Q08        (mdudney)
111111N16        (uspecken)
aaaaaa11>        (eseip)
44444424<        (buzzo)
guesses: 10  time: 0:00:22:58  c/s: 114932M  trying: AA22722277 - AA227272AA
55~555575        (fpickford)
99999995;        (sheyne)
99999977@        (nknezevic)
?7777777[        (dmerlin)
{7777777]        (thashaway)
guesses: 15  time: 0:00:32:24  c/s: 115828M  trying: =[=H===[=[ - =[=H==H[[=
guesses: 15  time: 0:00:40:00  c/s: 116232M  trying: YYXYJXJJJX - YYXYJXXJXY
whthtwhtht       (mloots)
guesses: 16  time: 0:00:47:46  c/s: 116549M  trying: ~~~~~~~}|| - ~~~~~~~~~~

Alexander

# Generate candidate passwords from many small subsets of characters from a
# much larger full character set.  This will test for passwords containing too
# few different characters.  As currently implemented, this code will produce
# some duplicates, although their number is relatively small when the maximum
# number of different characters (the maxdiff setting) is significantly lower
# than the maximum length (the maxlength setting).  Nevertheless, you may want
# to pass the resulting candidate passwords through "unique" if you intend to
# test them against hashes that are salted and/or of a slow to compute type.
[List.External:Subsets]
int minlength;		// Minimum password length to try
int maxlength;		// Maximum password length to try
int startdiff;		// Initial number of characters in a subset to try
int maxdiff;		// Maximum number of characters in a subset to try
int last;		// Last character position, zero-based
int lastid;		// Character index in the last position
int id[0x7f];		// Current character indices for other positions
int subset[0x100], c0;	// Current subset
int subcount;		// Number of characters in the current subset
int subid[0x100];	// Indices into charset[] of characters in subset[]
int charset[0x100];	// Full character set
int charcount;		// Number of characters in the full charset

void init()
{
	int i, c;

	minlength = 1;	// Minimum password length to try, must be at least 1
	maxlength = 8;	// Must be at least same as minlength

	startdiff = 1;	// Initial number of different characters to try
	maxdiff = 3;	// Maximum number of different characters to try

/* This defines the character set */
	i = 0;
	c = 0x20;
	while (c <= 0x7e)
		charset[i++] = c++;

	if (maxdiff > (charcount = i))
		maxdiff = i;
	if (maxdiff > maxlength)
		maxdiff = maxlength;

/*
 * Initialize the variables such that generate() gets to its "next subset"
 * code, which will initialize everything for real.
 */
	subcount = (i = startdiff) - 1;
	while (i--)
		subid[i] = charcount;
	subset[0] = c0 = 0;
	last = maxlength - 1;
	lastid = -1;
}

void generate()
{
	int i;

/* Handle the typical case specially */
	if (word[last] = subset[++lastid]) return;

	lastid = 0;
	word[i = last] = c0;
	while (i--) {			// Have a preceding position?
		if (word[i] = subset[++id[i]]) return;
		id[i] = 0;
		word[i] = c0;
	}

	if (++last < maxlength) {	// Next length?
		id[last] = lastid = 0;
		word[last] = c0;
		word[last + 1] = 0;
		return;
	}

/* Next subset */
	if (subcount) {
		int j;
		i = subcount - 1;
		j = charcount;
		while (++subid[i] >= j) {
			if (i--) {
				j--;
				continue;
			}
			subid[i = 0] = 0;
			subset[++subcount] = 0;
			break;
		}
	} else {
		subid[i = 0] = 0;
		subset[++subcount] = 0;
	}
	subset[i] = charset[subid[i]];
	while (++i < subcount)
		subset[i] = charset[subid[i] = subid[i - 1] + 1];

	if (subcount > maxdiff) {
		word = 0;		// Done
		return;
	}

/*
 * We won't be able to fully use the subset if the length is smaller than the
 * character count.  We assume that we've tried all smaller subsets before, so
 * we don't bother with such short lengths.
 */
	if (minlength < subcount)
		last = subcount - 1;
	else
		last = minlength - 1;
	c0 = subset[0];
	i = 0;
	while (i <= last) {
		id[i] = 0;
		word[i++] = c0;
	}
	lastid = 0;
	word[i] = 0;
}