[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAJ9ii1HhGL+Vsw9TPYecCKB1arvRYfKZnan--8vOf=X-TDKRGQ@mail.gmail.com>
Date: Sun, 5 Sep 2021 11:36:36 -0400
From: Matt Weir <cweir@...edu>
To: "john-dev@...ts.openwall.com" <john-dev@...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 trade-offs so I’d be interested in hearing more about your use-case.
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 proof-of-work 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.
