
Date: Sun, 5 Sep 2021 11:36:36 0400
From: Matt Weir <cweir@...edu>
To: "johndev@...ts.openwall.com" <johndev@...ts.openwall.com>
Subject: Re: precomputed attacks for john: rainbow tables and other ways
What factors are you trying to optimize? Precomputation techniques are all
about tradeoffs so I’d be interested in hearing more about your usecase.
Most of the places I see rainbow tables used is when you need to crack an
individual unsalted hash in minutes, and you don’t have the hardware to
back up a GPU cracking session to accomplish that reliably.
Cheers,
Matt
On Sunday, September 5, 2021, Aleksey Cherepanov <lyosha@...nwall.com>
wrote:
> Aleksey Cherepanov <lyosha@...nwall.com> writes:
> > Aleksey Cherepanov <lyosha@...nwall.com> writes:
> >> On Tue, Jul 07, 2015 at 07:07:21PM +0300, Aleksey Cherepanov wrote:
> >> /* (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.
>
> For precomputed attacks, I bumped into theoretical limitation with plain
> chains: a table should contain >36.7% of keyspace in some form.
>
> At abstract level, we have a directed graph where each candidate points
> to another candidate. If we stop chains at candidates with
> numbers/indexes with a few zeros at the beginning, then the whole graph
> would be a bunch of trees growing with roots in such distinguished
> points plus a few cycles that don't contain such point. Let's omit the
> cycles for simplicity. Our table could be a lookup of distinguished
> points with lists of leafs. So during cracking we would go from given
> hash to root, look up all possible starts, go from them and maybe crack
> the hash.
>
> But there is a problem with size of such table: ~36.7% (1/e) of nodes in
> randomly generated graph are leafs, and we are going to store the leafs.
> This amount does not depend onto number of zeros to distinguish end of
> chain. The ends would be leafs in other chains but that would be in
> addition to these 36.7%.
>
> The code to demonstrate that is attached. The code does not find
> distinguished points. Output:
> total_count: 16777216
> leafs: 6172648
>
> In python, 1 / math.e gives 0.36787944117144233.
> 6172648.0 / 16777216 gives 0.3679184913635254.
>
> Well, we could store indexes of leafs instead of candidates. Also we
> could sort the lists and compress them. But I doubt we could get less
> than ~1/4 of uncompressed space.
>
> BTW random graphs are used in cuckaroo29 proofofwork algorithm: the
> goal is to find a cycle of given size in such graph. So there are
> efficient miners that can track some chains on graphs without much
> memory.
>
> Idea: split keyspace into partitions and go from one partition to other
> instead of chaining over one keyspace. So we start in the first part and
> end in the last always. All chains have same length always. But cracking
> would require length^2/2 hashing because we need to assume every part as
> current for given hash. It would not help to reduce number of leafs. So
> we could introduce configurable perfect hash function to make mapping
> from one part to another part perfect. But I guess configuration of the
> perfect hash function would require a lot of space. Yet a function with
> smaller configuration could improve mapping. Also such structure of
> chain would reduce amount of memory required to track all candidates.
>
> Colors were mentioned in previous messages. So I guess there may be
> known ways to cover keyspace well without storing many starting points.
>
> Thanks!
>
> 
> Regards,
> Aleksey Cherepanov
>
Content of type "text/html" skipped
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.