[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <877dftzayb.fsf@d>
Date: Mon, 06 Sep 2021 23:49:16 +0300
From: Aleksey Cherepanov <aleksey.4erepanov@...il.com>
To: john-dev <john-dev@...ts.openwall.com>
Subject: Re: precomputed attacks for john: rainbow tables and other ways
Royce Williams <royce@...hsolvency.com> writes:
> A while back, I did some crude caching of all descrypt salts for targeted
> terms here:
>
> https://github.com/roycewilliams/kens-salty-rainbow
>
> And yes, I'm deliberately making ironic use of the word "rainbow" here. :D
Heh, that's an interesting position on TMTO spectrum.
I just tried my previous idea about splitting wordlist into parts based
on prefix of hash. But I stored only indexes of candidates and
compressed everything.
So to attack a hash, I would pick respective file and try candidates
from it only. Also I would know that other files would not help. So for
a particular hash I could say that the attack is exhausted reliably.
Unlike regular RT, one might attack all hashes with given prefix in
single run.
In my test, keyspace is 16M (256 * 256 * 256). I split it into 1024
files based on 10 bits from hash. Each file contains binary array of
4-byte integers for indexes of candidates (not plaintexts). Each file is
~64kb, sizes vary slightly. Then I compressed all files together as
`tar c out | time xz -0 > out.tar.xz`. Resulting size is 34176740 bytes,
that's 2.04 bytes per candidate.
I iterated indexes of candidates sequentially in one thread, so output
files are sorted by construction.
I tried to store 3 bytes instead of 4, but it gave 45020660 bytes of
output from xz (I guess xz has heuristics to find binary tables of
numbers).
Times:
- 7.3s to hash every candidate and write index to appropriate file,
- 13.1s to compress the files.
I like that I hashed everything only once. But compression takes a lot
of time. I am not sure if it scales this way, but I would define such
possible baseline (with and without compression):
- ~1024x speed-up, ~3x work to prepare, storing ~2 bytes per candidate,
- ~1024x speed-up, ~1x work to prepare, storing 4 bytes per candidate.
All with 100% success.
I think speed-up is very flexible in such method, but for small
keyspaces compression would degrade. OTOH for larger keyspaces, 4 bytes
per candidate without compression is not possible. But I guess very fast
and very specific compression could be used.
Thanks!
--
Regards,
Aleksey Cherepanov
View attachment "ossl7.c" of type "text/x-csrc" (1493 bytes)
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.
