[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CANJ2NMNN6U49kuzhDTcwzsOu0wMb71kpb+UbZj56XOE1MOSYcA@mail.gmail.com>
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.
