[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 23 Apr 2023 23:36:29 +0200
From: magnum <magnumripper@...hmail.com>
To: john-dev@...ts.openwall.com
Subject: Re: Birthday paradox
On 2023-04-23 13:20, Solar Designer wrote:
> 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:
It's basically the code in current bleeding, just with "cmp()"(which
check the bitmap) disabled so we always call "cmp_final()". BTW the
current test code is in "bitmaptest" branch in magnumripper repo on
Github. It's in a state of flux but currently exactly what I used for
the tests I posted.
> As I understood, these PHTs use 64-bit hashes as input to index
> calculation. Now you say they store 32-bit values.
Not really, I said 32-bit collision. cmp_final() compares the hash with
the 64 bits we have. My debug kernel normally counts FP from the bitmap
but in this case it has nothing to do, so I had it simply count the
occasions where only the first 32 bits matches (so one in 4G FP is
always ecpected) as a canary that I didn't make some coding mistake.
Now the variation seen in the tests is curious too I'm not giving it too
much thought right now.
magnum
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.
