[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <87tuj0z7wl.fsf@d>
Date: Sat, 04 Sep 2021 18:18:18 +0300
From: Aleksey Cherepanov <lyosha@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: precomputed attacks for john: rainbow tables and other ways
Aleksey Cherepanov <lyosha@...nwall.com> writes:
> On Tue, Jul 07, 2015 at 07:07:21PM +0300, Aleksey Cherepanov wrote:
>> I made an implementation in C with openssl. I did not try cracking so
>> the code may be broken.
>>
>> I implemented cyclic buffer for tracking limited to 'tracking_buffer'
>> size, 'total_count / 8' is max.
>
> I added Distinguished Points and 2 passes postponing very long chains.
> /* (candidate_number & mask) == 0 ends chains */
> #define dp_mask 0xff
Years after this thread hanged, ch3root introduced idea about rainbow
tables: let's end chains at hash with a few zero bits at the beginning,
so we could distinguish end without looking into table. So it turns out
that this trick is known already as distinguished points.
I just realized the true value of this point: if chains always end in
such distinguishable hashes, then a device with low memory and low
bandwidth may be used to compute chains. ZTEX 1.15y board is a perfect
example of such device.
BTW distinguished points might help with the following problem:
https://en.wikipedia.org/wiki/Rainbow_table
"Simple hash chains have several flaws. Most serious if at any point two
chains collide (produce the same value), they will merge and
consequently the table will not cover as many passwords despite having
paid the same computational cost to generate. Because previous chains
are not stored in their entirety, this is impossible to detect
efficiently."
Back to precomputed attacks, it is possible to ensure that all
candidates are in the table starting a chain from each and merging all
chains avoiding dupes. DPs reduce number of lookups, but technically it
was possible with simple chains. But approach does not seem practical
because it requires a lot of hashing: keyspace * chain length, plus a
some more to merge chains.
Thanks!
--
Regards,
Aleksey Cherepanov
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.
