Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 26 Jul 2013 22:00:21 -0700
From: Myrice Li <>
Subject: Re: md5 hash comparisons

Sayantan, Solar,

On Sat, Jul 20, 2013 at 4:24 PM, Solar Designer <> 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

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


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.