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.