Date: Sun, 13 Sep 2015 20:28:08 -0700 From: Fred Wang <waffle.contest@...il.com> To: john-dev@...ts.openwall.com Subject: Re: Re: Judy array On Sep 13, 2015, at 7:45 PM, Sayantan Datta <std2048@...il.com> wrote: > Nice!! Unlike perfect hash tables, Judy array are supposed to be cache friendly. However, I'm curious regarding the number of lookups required!!. I'll study them in more details. > > Fred, have you compared the performance of bloom filters vs bitmaps(maybe one or multiple)? > Yes. For the most part (and in particular, when Bloom filters are very sparse), they are always a win for "our" type of lookup. In cracking, the vast majority of hashes will fail, and that is what I optimized for. A Judy array on its own is already faster than what John is doing. Fronting this with a Bloom filter vastly improves performance. Regretfully, I did not keep my bitmap timing - but it was not impressive. I use a 10-year-old Dell 2950 as my test environment, precisely because it uses slower memory, and more easily shows improvements. For my "standard" test case (MD5, 29 million hashes, a ~13 million entry dictionary, and best64 rules, yielding about 1 billion hash attempts to find about 1.7 million solutions) hashcat 3 minute 54 seconds mdxfind 1 minute 15 seconds (Judy only) mdxfind 47 seconds (Current code, Bloom filter + Judy) Its important to note that this includes the time to read 29M hashes, and store them - this takes about 22 seconds on the test box. The box uses dual E5410 @ 2.33GHz, so 8 cores. So, Judy on its own is pretty darn good, but fronting it with a Bloom filter is pure win for this application. Please take some time to try it out.
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.