Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [day] [month] [year] [list]
Date: Mon, 29 Jun 2015 17:36:42 -0400
From: Alain Espinosa <alainesp@...ta.cu>
To: john-dev@...ts.openwall.com
Subject: Re: Re: precomputed attacks for john: rainbow tables and?  other ways



-------- Original message --------
From: Aleksey Cherepanov <lyosha@...nwall.com> 
Date:06/29/2015 4:54 PM (GMT-05:00) 
To: john-dev@...ts.openwall.com 
Cc: 
Subject: Re: [john-dev] Re: precomputed attacks for john: rainbow tables and? other ways 

...I do not really get your algorithm

There is no new algorithm. I propose standard Hellman tables with distinguished points (DP). The difference is that I propose to use only one table instead of n or l or t (there are different notation) different tables. In rainbow terminology is using only one color.

...let's end chains based on
hash value, for instance end chain if hash has 2 leading zero bytes;

This is exactly how DP works.

...this way we compute (number of colors)*(chain length)
hashes but check only (number of colors) hashes against the table

In rainbow tables:
 - (number of colors)==(chain length)
- We compute ((number of colors)^2)/2 hashes. Instead what I suggest calculate only (number of colors).
- We check  (number of colors) hashes against the table in disk or ram. Instead what I suggest check only one time.

Why was not used before then? I am not sure. DP can't merge easily with rainbow tables, that are the more used TMTO. Only one Hellman table generate to much duplicate - merges that hit performance. Only Hellman tables with DP can easily eliminate the duplicates. Also using only one table considerably increase the offline precomputation time.

When I say isn't parallelizable I mean the online phase. The offline is very parallel, even GPU friendly.

Regards, 
Alain
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.