[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Mon, 29 Jun 2015 15:53:38 -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 1:30 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
> Sorry I'm not really following you...
Me neither :)
There is some research in perfect Hash tables to reduce memory and speed up access with TMTO:
- 2005, "Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints"
- 2001, "Real Time Cryptanalysis of A5/1 on a PC"
Other topic:
I begin only recently to research TMTO but one optimization appear obvious, and to some extent was used but not completely.
N: size of key space
m: number of chains
t: chain length
The common analysis supposed mt^2=N for each table and t different tables. This is because larger m, t generate more probably duplicates and chain merges. t tables generate t^2 hash executions and t disk access in the online phase. Using more tables is only an optimization to cover a larger part of the keyspace, so generating only one table with distinguished points reduce hash execution to t and only one disk access at the expense of more offline time. How much? We can brute force the entire key space so at most t more expensive, possibly less with a smarter search. Note that we can easily eliminate duplicates because we use DP. This is a very large online speedup and I am not sure why this was not used.
This algorithm is not parallelizable as is but if many hashes are available, they can be searched in parallel.
Other big advantage is the very good client-server architecture. You don't need to download large table file. In the client you calculate the DP (performance heavy part) and ask the server if exists. The server only search in disk or RAM and return the start point, or false if the DP not exists.
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.
