john-dev - candidate shuffling, and external mode limitations

Follow @Openwall on Twitter for new release announcements and other news

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <20200911205333.GA20904@openwall.com>
Date: Fri, 11 Sep 2020 22:53:33 +0200
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: candidate shuffling, and external mode limitations

Hi,

The "rain mode" discussion went back on GitHub, now on a pull request
that we're unlikely to ever accept.

Anyhow, this reminded me of an algorithm I came up with 20+ years ago,
for shuffling DNS query IDs in a glibc patch for Owl
(glibc-2.1.3-owl-res_randomid.diff, first committed "Wed Jul 5 04:27:23
2000 UTC (20 years, 2 months ago) by solar" according to our CVSweb).

I just translated it to JtR external mode as very rough PoC, see below.
Unfortunately, to have it work over a meaningfully large keyspace we'd
need much larger than the (effectively) 31-bit integers, and that would
mean having to implement big integers right in an external mode, so
quite cumbersome.  If we add big integer support to external mode VM, it
could actually become quite clean and fast (even the VM overhead would
be relatively less, as it'd occur once per a larger and naturally slower
operation), but I doubt we have enough use cases for big integers in
external modes to justify that, or do we?

[List.External:Shuffle]
int a, b, n, base, div;

void init()
{
	a = b = 1;
	n = 0;
	div = 7777; // Keyspace size + 1
	base = div + 3;
	base += 1234; // Any even number to choose shuffling sequence
}

void generate()
{
	if (n >= div - 1) {
		word = 0;
		return;
	}

	if (n && b <= a) {
		while (1) {
			b = ++a;
			while (1) {
				b *= base;
				b %= div;
				if (b <= a)
					break;
			}
			if (a == b)
				break;
		}
	}

	b *= base;
	b %= div;
	n++;

	int i, v;
	i = 0; v = b;
	while (1) {
		word[i++] = '0' + v % 10;
		if (!(v /= 10))
			break;
	}
	word[i] = 0;
}

This outputs (reversed) decimal numbers, but mapping onto any other
charset is easy to implement (pointless to do without solving the big
integers problem first).

A (performance) drawback is that the conversion from a (big) integer to
a string in the target charset would have to be fully re-done for each
candidate generated - that's a side-effect of good shuffling.  (For some
other modes, we're able to alter only some characters while leaving the
rest intact.)  Maybe not-so-good shuffling like what I understand "rain
mode" attempts to achieve is sufficient, and would result in higher
performance.  This only matters when attacking fast hashes.

Testing:

$ ./john --stdout -external=shuffle | sort -u | wc -l
Press 'q' or Ctrl-C to abort, almost any other key for status
7776p 0:00:00:00 77760p/s 4141
7776

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.