[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <87mtorz0bl.fsf@d>
Date: Sun, 05 Sep 2021 15:14:22 +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:
> 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
View attachment "ossl3.c" of type "text/x-csrc" (1697 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.
