Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 9 Sep 2006 15:25:31 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: Using a pre-computed list of alphanumeric strings. (not rainbow tables)

On Tue, Aug 29, 2006 at 02:32:59PM +0200, rembrandt@...erlin.de wrote:
> Because somebody mentioned the space needed to store "Rainbowtables":
> This space can get reduced dramaticly using the "right" compression
> algorithm.

Oh, and that algorithm is the one that was used to generate those tables
originally, right? ;-)

> I will (again) mention LZMA because it compresses REALY awesome.

LZMA is good, but irrelevant.  Please stop plugging it on this mailing
list.  Rainbow tables - or any pre-computed hash lists, etc. - are
supposed to _not_ be compressible.  If they are compressible, that would
indicate a cryptographic weakness of the hash function and/or
non-optimal storage/encoding format.  In the latter case, the
storage/encoding format would possibly need to be optimized (unless it
is non-optimal deliberately - e.g., for quicker access to the data), not
a general-purpose compression algorithm used on top of it.

> And that LM can get splitted into 7 char blocks is right and this means
> you just need a rainbowtable up to 7 Chars because a PW of about 12 chars
> gets splitted into 7+5 and should get brocken absolutly fast.

That's true.

> So conclusion: It makes sense to may even enable JtR to use Rainbowbooks,
> at least for such weak algorithms.

As I had mentioned before, this might be better implemented as a
separate program because it would share little code and functionality
with the current JtR.  The primary reason to possibly stretch JtR in
this direction is that it might be good for "marketing".

> It will become kinda useless for Blowfish or maybe even MD5 but for DES/LM
> it may makes sense

Basically, it makes sense for saltless hashes and possibly for those
with small salt sizes (that's just the traditional DES-based crypt(3)
hashes with 12-bit salts).

> (combinated with a good compression).

No.

Observe:

Archive:  SSTIC04-10k.zip
 Length   Method    Size  Ratio   Date   Time   CRC-32    Name
--------  ------  ------- -----   ----   ----   ------    ----
     774  Defl:N      446  42%  07-14-04 23:20  90a9b24b  README-10k.TXT
30819324  Defl:N 30710332   0%  06-30-04 18:24  cc44f316  table0.bin
 6910420  Defl:N  2402915  65%  06-30-04 18:24  b3b6c086  table0.index
61638648  Defl:N 59604011   3%  06-30-04 18:24  746a2343  table0.start
30814120  Defl:N 30704735   0%  06-30-04 18:26  15eaf5cd  table1.bin
 6910420  Defl:N  2402928  65%  06-30-04 18:26  f7cb316c  table1.index
61628240  Defl:N 59594098   3%  06-30-04 18:26  ffc52302  table1.start
30824574  Defl:N 30715428   0%  06-30-04 18:27  f88e0d5f  table2.bin
 6910420  Defl:N  2402915  65%  06-30-04 18:27  c516e00a  table2.index
61649148  Defl:N 59613310   3%  06-30-04 18:27  3c04a219  table2.start
30811564  Defl:N 30701830   0%  06-30-04 18:28  c5165165  table3.bin
 6910420  Defl:N  2402999  65%  06-30-04 18:29  d1e8060d  table3.index
61623128  Defl:N 59589739   3%  06-30-04 18:28  d00cf97a  table3.start
--------          -------  ---                            -------
397451200         370845686   7%                            13 files

Only some files are compressible, for an average size reduction of 7%,
and that's likely due to deliberately non-optimal storage/encoding
format.  LZMA achieves only 1% better results than ZIP:

-rw-------  1 solar solar 397465600 Sep  9 15:10 SSTIC04-10k.tar
-rw-------  1 solar solar 366442679 Sep  9 15:19 SSTIC04-10k.tar.lzma
-rw-------  1 solar solar 370847438 Sep  9 15:05 SSTIC04-10k.zip

because there's simply almost no compressible data.

-- 
Alexander Peslyak <solar at openwall.com>
GPG key ID: 5B341F15  fp: B3FB 63F4 D7A3 BCCC 6F6E  FC55 A2FC 027C 5B34 1F15
http://www.openwall.com - bringing security into open computing environments

-- 
To unsubscribe, e-mail john-users-unsubscribe@...ts.openwall.com and reply
to the automated confirmation request that will be sent to you.

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ