[<prev] [next>] [thread-next>] [day] [month] [year] [list]
```Date: Tue, 18 Apr 2023 17:57:51 +0200
From: magnum <magnumripper@...hmail.com>
To: john-dev@...ts.openwall.com

Hi folks,

Can anyone point me to a (approximation) formula for the birthday
paradox, where for example we have a bitmap with 4096 bits and populate
it with 1024 random bits. What is the expected number of bits set in the
bitmap?

I think the answer is ~907, as that's what I'm seeing in my experiments
- and also what this simple script shows:

\$ perl -e '\$n=0; \$s=0; while (\$n < 1000) { my %nums = undef; foreach
(0..1023) { \$nums{int(rand(4096))} = 1; } \$n++; \$s += scalar
keys(%nums); print "Average ", int(\$s/\$n), "\r"; } print "\n";'
Average 907

I settles at 907 in just 10 rounds. But what is a good formula for
calculating this, given n=1024 and d=4096? Either my google-fu has
deteriorated or the search engines have become too bloated to be of use
anymore.

I recall Solar mentioned somewhere (at some time in the last, say, 12
years, lol) that "given n random DES-crypt hashes, we can expect x
unique salts" and I believe that's the exact same math.

Cheers,
magnum

```

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.