[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20120115230035.GA16305@openwall.com>
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
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
