Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 15 Jul 2015 17:24:14 +0300
From: Aleksey Cherepanov <>
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:

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.


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.