Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150715142414.GA4514@openwall.com>
Date: Wed, 15 Jul 2015 17:24:14 +0300
From: Aleksey Cherepanov <lyosha@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: precomputed attacks for john: rainbow tables and
 other ways

Cryptohaze have Open Source rainbow tables generator and cracker for
gpu. It may be interesting to investigate:

http://cryptohaze.com/gpurainbowcracker.php

On Tue, Jul 07, 2015 at 07:07:21PM +0300, Aleksey Cherepanov wrote:
> I made an implementation in C with openssl. I did not try cracking so
> the code may be broken.
> 
> I implemented cyclic buffer for tracking limited to 'tracking_buffer'
> size, 'total_count / 8' is max.

I added Distinguished Points and 2 passes postponing very long chains.

Distinguished Points are quite interesting: they allow crackable
hashes to be cracked very quick: 98% of chains are 2 times shorter
than the longest one. So full test of good hashes goes at 45 h/s while
not crackable hashes are checked at 1 h/s.

The algo needs unlimited number of colors (or it should exit by
length), otherwise it can get into infinite loop.

I tried 2 passes to reduce max length at expense of additional
computations: it is not possible (reliably) reduce max length, it is
possible to reduce average length. 2 passes are not compatible with
cyclic buffer so I disabled it.

2 passes are quite interesting: there are not so much remaining
candidates, it is possible to reduce max length of chain by 2 with
small hashing overhead storing only 0.0005 of candidates (we skip 2
times more, but later chains cover some of skipped beginnings). These
problematic candidates can be stored as is. Also it is possible to
make a separate table with other mapping algo (then it is desirable to
reduce length more so 2 checks give profit), but this approach does
not seem reliable.

It is possible to use cyclic buffer with 2 passes if there are not so
much skipped values: one can track them separately in a binary tree or
something like that.

A hybrid can be made: make a table with disabled points and with
regular ends by length. During cracking, you remember all
intermediates but look them up only if you do not meet a Distinguished
Point. Also regular table can be smaller so look up can be quicker.

> Again, I am afraid the code is broken so the stats and conclusions may
> be wrong.

The code worked, but I did not print stats at the end so the number of
chains is underestimated.

Current code has code for cracking. The code is in attach.

Thanks!

-- 
Regards,
Aleksey Cherepanov

View attachment "ossl.c" of type "text/x-csrc" (16080 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.