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 18.104.22.168 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.