Date: Fri, 26 Jul 2013 22:00:21 -0700 From: Myrice Li <qqlddg@...il.com> To: john-dev@...ts.openwall.com Subject: Re: md5 hash comparisons Sayantan, Solar, On Sat, Jul 20, 2013 at 4:24 PM, Solar Designer <solar@...nwall.com> wrote: > Sayantan, > > > myrice tried implementing this (do take a look at the PG-test branch) > and somehow came to the conclusion that 4 small bitmaps in local memory > worked well enough (each indexed by a different portion of MD5 hash > value), without needing a global memory bitmap. Maybe a reason why > myrice got away with local memory bitmaps only (no bitmap in global > memory) is because he also implemented a hash table lookup (using global > memory), whereas, if I recall Bitweasil's explanation correctly, > Multiforcer proceeds with a linear search if the 4*128 MiB global memory > bitmaps give a hit. Yet I think we do need bitmap(s) in global memory > as well (see below for some numbers). > > I have bitmaps in both local memory and global memory. It works as follows: 1. if loaded hashes number exceeds a threshold, it will use larger mask 0xFFFFFF for hash table lookup and global bitmaps 2. otherwise, it will use 0xFFFF for hash table lookup and local memory bitmaps. > > > Also 64K loaded hahses seems to fit well within local memory using > bitmaps > > No, even 64K is too much to fit in one local memory bitmap (e.g., you'd > achieve a 78% reject rate with a single 32 KiB bitmap). The solution > is in use of multiple bitmaps, indexed by different portions of the hash > value. (Alternatively, you could use a Bloom filter - that is, just one > bitmap indexed multiple times by the different portions of hash value - > but it would be suboptimal when its size and the number of lookups are > fixed rather than tuned based on number of loaded hashes, and besides we > care about the number of lookups too - not only about the false positive > rate and the size.) > > ... > > but 16M wont fit into local memory even with bitmaps. However chances of > > rejection is higher with 16M bitmap. > > Yes, for 16M you need global memory - even the multiple bitmaps or Bloom > filter approach in local memory doesn't work at all. (Maybe we should > include a not-data-dependent conditional branch to skip the local > bitmaps and go straight to global memory when the number of loaded > hashes is this large. We'd need to tune the threshold.) > > However, if you consider e.g. 64K, then with four 8 KiB local memory > bitmaps (32 KiB total) we get an 84% or 85% reject rate (depending on > whether your 64K is 65536 or 64000). This is an improvement over 78%, > albeit not a great improvement. For the remaining 15%+ you need to > access a global memory bitmap. > I think I use 2K*4 bitmaps in local memory for hash number smaller than 6553. For each portion of bitmaps, it actually has 2K(int)*4*8 = 64K bit. That is what I think Sayantan claims that "64K loaded hash seems fit into local memory". But this is not true, For loaded hashes exceeds 6553(1/10 of 64K), it will use global memory bitmaps. Thanks, Myrice Content of type "text/html" skipped
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.