[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 12 Sep 2020 00:30:30 +0200
From: owein <yvain29@...il.com>
To: john-dev@...ts.openwall.com
Subject: Re: candidate shuffling, and external mode limitations
On Fri, 2020-09-11 at 22:53 +0200, Solar Designer wrote:
> 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
Hi, finally what I had found out when working on zhou is that a
modifier used inside an iterative procedure and cut off with a modulo
must be set diferently according to the used modulo.
In my case I was
trying to work on the character set, which is not enough, but lately (a
few days ago) I realized that I needed to work on the index of the
state, and I find out again that rule to be true, and to be more
precise, we have to check if the value is a multiple of 10, of 2, or is
odd.
It is easy to think of only odd and even numbers and to stay stuck
in a sequence of testing where nothing seems to work. I think that my
latest commit that is only working on the index can make you realize
the power of this technique, I am going to push a version that uses the
same technique to work on the picking of the characters also, which is
the initial technique that I would call rain, but not enough
'deserialisation' takes place. Using the trick on the index also makes
the method valid, because the sequence is truly exploded then.
Regards,
Yvain.
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
