Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <49b30016d22a6552a0a4ef71c1b10119@smtp.hushmail.com>
Date: Sun, 23 Apr 2023 12:28:27 +0200
From: magnum <magnumripper@...hmail.com>
To: john-dev@...ts.openwall.com
Subject: Re: Birthday paradox

On 2023-04-22 23:55, Solar Designer wrote:
> On Wed, Apr 19, 2023 at 11:47:56PM +0200, magnum wrote:
>> I now added code that checks if the offset + hash tables fit into local
>> memory and if so, skips the bitmap completely.  This happens up to about
>> 5300 loaded hashes.  But just like most things I tried, this performs
>> just the same as using the bitmap - neither better or worse.
> 
> A complete lack of speed difference is puzzling.  Can you share some
> speeds you're getting by loaded hash count - e.g., 1, 100, 5300, 100k,
> 1M, 10M, 100M?

I meant at low numbers of hashes - at larger numbers the bitmap is 
definitely needed. Here's 256 hashes, to start with. It performs the 
same as with a single hash loaded, without a bitmap or with a Bloom 
filter with any k.  The figure is literally the same, like there's a 
timer somewhere with too low resolution?

Oh, I see now I need longer tests because of the speed involved. At 
30Gp/s a nano-second timer indeed *is* low resolution. Still, the 
difference is very small. I now bumped a 2.5 second test to 25 seconds 
for the below.  Difference still is small and shows "steps" in reported 
speed.

Starting without a bitmap:

$ for num in 256 ; do head -$num scraped-bare.in > test.$num.in && for k 
in 0 1 2 3 4 5 6 ; do rm -f ../run/john.pot && BLOOM_K=$k 
BITMAP_SIZE=$(($num*64)) ../run/john -form:nt-opencl -mask:?a -len=6 
test.$num.in -lws=512 -gws=34816 -v:1 || break 2 ; done ; rm 
test.$num.in ; done

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

For the rest I've snipped some lines with no new info:

256 hashes: Bloom filter m=16384 (2 KiB local) k=1, 14-bit (effectively 
6), expecting 1/64 FP.
Offset tbl 404 B, Hash tbl 2136 B, Results 3076 B, Dupe bmp 36 B, TOTAL 
on GPU: 7700 B
25g 0:00:00:24 DONE (2023-04-23 12:05) 1.008g/s *30628Mp/s* 30628Mc/s 
7190GC/s Dev#2:77°C util:95% aaUh}|..aaUh}|
735091890625 crypts, fp from bitmap: 1/64 (1.56%), 11485838124 hash 
table lookups

256 hashes: Bloom filter m=16384 (2 KiB local) k=2, 14-bit (effectively 
10), expecting 1/1056 FP.
Offset tbl 412 B, Hash tbl 2120 B, Results 3076 B, Dupe bmp 36 B, TOTAL 
on GPU: 7692 B
25g 0:00:00:23 DONE (2023-04-23 12:05) 1.082g/s *31960Mp/s* 31960Mc/s 
7502GC/s Dev#2:83°C util:94% aaUh}|..aaUh}|
735091890625 crypts, fp from bitmap: 1/1057 (0.09%), 695643250 hash 
table lookups

256 hashes: Bloom filter m=16384 (2 KiB local) k=3, 14-bit (effectively 
12), expecting 1/10410 FP.
Offset tbl 412 B, Hash tbl 2120 B, Results 3076 B, Dupe bmp 36 B, TOTAL 
on GPU: 7692 B
25g 0:00:00:23 DONE (2023-04-23 12:05) 1.042g/s *31960Mp/s* 31960Mc/s 
7502GC/s Dev#2:85°C util:94% aaUh}|..aaUh}|
735091890625 crypts, fp from bitmap: 1/10634 (0.01%), 69123983 hash 
table lookups

256 hashes: Bloom filter m=16384 (2 KiB local) k=4, 14-bit (effectively 
16), expecting 1/74178 FP.
Offset tbl 380 B, Hash tbl 2088 B, Results 3076 B, Dupe bmp 36 B, TOTAL 
on GPU: 7628 B
25g 0:00:00:24 DONE (2023-04-23 12:06) 1.019g/s *30628Mp/s* 30628Mc/s 
7190GC/s Dev#2:85°C util:95% aaUh}|..aaUh}|
735091890625 crypts, fp from bitmap: 1/74391 (0.00%), 9881521 hash table 
lookups

256 hashes: Bloom filter m=16384 (2 KiB local) k=5, 14-bit (effectively 
15), expecting 1/416871 FP.
Offset tbl 412 B, Hash tbl 2120 B, Results 3076 B, Dupe bmp 36 B, TOTAL 
on GPU: 7692 B
25g 0:00:00:25 DONE (2023-04-23 12:06) 0.9932g/s *29403Mp/s* 29403Mc/s 
6902GC/s Dev#2:85°C util:95% aaUh}|..aaUh}|
735091890625 crypts, fp from bitmap: 1/395378 (0.00%), 1859212 hash 
table lookups

256 hashes: Bloom filter m=16384 (2 KiB local) k=6, 14-bit (effectively 
18), expecting 1/1944949 FP.
Offset tbl 412 B, Hash tbl 2120 B, Results 3076 B, Dupe bmp 36 B, TOTAL 
on GPU: 7692 B
25g 0:00:00:25 DONE (2023-04-23 12:07) 0.9900g/s *29403Mp/s* 29403Mc/s 
6902GC/s Dev#2:85°C util:95% aaUh}|..aaUh}|
735091890625 crypts, fp from bitmap: 1/1810179 (0.00%), 406088 hash 
table lookups

I've often aimed at 30 second tests when doing scripted tests with many 
different parameters.  Perhaps I should use 1000-second tests (about 16 
minutes) for more precision but then cooling becomes more important so 
it doesn't skew sarly/late tests, or I need a couple minutes of cooling 
between each run adding even more to total test time.  Slow science for 
fast speeds :-/

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.