[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20230423112012.GA17380@openwall.com>
Date: Sun, 23 Apr 2023 13:20:12 +0200
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Birthday paradox
On Sun, Apr 23, 2023 at 12:46:07PM +0200, magnum wrote:
> On 2023-04-23 12:28, magnum wrote:
> >Starting with no bitmap (BLOOM_K=0 disables):
> >
> >Using default input encoding: UTF-8
> >Loaded 256 password hashes with no different salts (NT-opencl [MD4 OpenCL])
> >256 hashes: Hash table in local memory (2468 B); no filter.
> >Offset tbl 380 B, Hash tbl 2088 B, Results 3076 B, Dupe bmp 36 B, TOTAL
> >on GPU: 5580 B
> >LWS=256 GWS=34816 (136 blocks) x9025
> >Press 'q' or Ctrl-C to abort, 'h' for help, almost any other key for status
> >25g 0:00:00:24 DONE (2023-04-23 12:04) 1.004g/s *30628Mp/s* 30628Mc/s
> >7190GC/s Dev#2:66°C util:95% aaUh}|..aaUh}|
> >Remaining 231 password hashes with no different salts
> >Session completed.
> >735091890625 crypts, fp from bitmap: 1/4153061529 (0.00%), 177 hash
> >table lookups
>
> Same without even using local memory:
>
> 256 hashes: Hash table in global memory (2532 B); no filter.
> Offset tbl 412 B, Hash tbl 2120 B, Results 3076 B, Dupe bmp 36 B, TOTAL
> on GPU: 5644 B
> LWS=256 GWS=34816 (136 blocks) x9025
> Press 'q' or Ctrl-C to abort, 'h' for help, almost any other key for status
> 25g 0:00:00:25 DONE (2023-04-23 12:36) 0.9723g/s *29403Mp/s* 29403Mc/s
> 6902GC/s Dev#2:67°C util:95% aaUh}|..aaUh}|
> Remaining 231 password hashes with no different salts
> Session completed.
> 735091890625 crypts, fp from bitmap: 1/3910063248 (0.00%), 188 hash
> table lookups
>
> The reported "fp from bitmap" in the no-bitmap case are 32-bit false
> positives from the hash table. They should be the same above but somehow
> isn't. I regard it as some effect of the mentioned randomness in the
> PHT (as you can see the sizes differ as well) but in the no-bitmap case
> it still puzzles me - we're comparing an actual MD4 hash word by word.
Making some guesses on what code this corresponds to and what it does,
as I am not familiar with Sayantan's and have not seen your latest:
As I understood, these PHTs use 64-bit hashes as input to index
calculation. Now you say they store 32-bit values. I notice the
discrepancy here - it's not exactly comparison of the same 32-bit part
of MD4 hashes - it probably would be if you switched to using the same
32-bit part also for the index calculation, but then that would be
suboptimal. It's more optimal to use non-overlapping parts of the hash
for index and for storage/comparison. OTOH, for tiny hash tables like
this you can reasonably switch to using a (different) 32-bit part of the
MD4 hash, as modulo division bias would be small. The modulo operation
should be faster on a 32-bit input than on 64-bit.
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.
