Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Mon, 16 Jan 2012 03:00:35 +0400
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: bitmaps

Hi,

Here's what I implemented today (it's in 1.7.9.3 in CVS):

* Implemented bitmaps for fast initial comparison of computed hashes against
those loaded for cracking.  This is applied before hash table lookups, and it
allows for the use of smaller hash tables (thereby saving memory) while
achieving the same or greater speed that larger hash tables previously did.
The speed increase is due to improved locality of reference (where only the
smaller bitmap is accessed all the time, whereas the larger hash table behind
it is only accessed for a percentage of comparisons and additionally it is
smaller than it would otherwise need to be).

Here are some speed numbers and memory usage for LM hashes on a
linux-x86-64 build using one core in E5420 running incremental mode
(alpha.chr, length fixed at 7, nothing gets cracked - these test hashes
are for all-digit strings, so alpha.chr doesn't get them).

hashes	c/s	VSZ	RSS
--test	38M	6 MB	1 MB
1	32M	12 MB	5 MB
10	29M	12 MB	5 MB
100	25M	12 MB	5 MB
1K	24M	12 MB	5 MB
10K	22M	14 MB	8 MB
100K	19M	52 MB	47 MB
1M	13M	121 MB	115 MB
10M	5.7M	1046 MB	1039 MB

--save-memory=1 (disables loading of login names, should not affect speed)
1M	13M	106 MB	100 MB
10M	5.3M?	893 MB	887 MB

--save-memory=2 (smaller bitmaps and hash tables)
1M	2.0M	75 MB	68 MB
10M	2.2M	656 MB	650 MB

--save-memory=3 (extreme: no bitmaps, no hash tables, no alignment)
1M	3200	66 MB	59 MB
10M	320	555 MB	549 MB

1M hashes pwdump file size is 86 MB
10M hashes pwdump file size is 884 MB

These are raw hashing speeds; the effective c/s rate reported while
cracking is obviously much higher.

Before adding bitmaps, I could only get 1M hashes to run at 6M c/s; with
bitmaps, I got that same test to 13M c/s.  That's a 2x speedup, and
memory usage reduced too.

Alexander

Powered by blists - more mailing lists

Your e-mail address:

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