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.