The random number generation for `srand()` is weak

[scottchiefbaker]

Description

As part of my exploration into the guts of how Perl handles random numbers I've come across some interesting things. When rand() is called without calling srand() first, a "random" seed is chosen to kick off the drand48 PRNG.

On Linux (or any system with /dev/urandom) the seed is chosen by taking four bytes from urandom and generating a U32 from it. For 90% of use cases this is probably find for a general seed. This is good, well thought out, and the correct way to seed a PRNG.

On non-Linux systems, or when /dev/urandom fails to read, Perl fails back to very simple hash of: unixtime, Perl PID, Pointer address, and a hash of a pointer address. On it's face this should be a semi-decent random seed. It would be pretty difficult to guess or repeat a given seed.

However after doing some testing I'm finding that repeated calls to seed() return very similar values. Usually the values only vary between 2 to 4 bits.

Steps to Reproduce

Call the seed() function repeatedly

3106881140, 3106881131, 3106881119, 3106881110
662064185, 662064176, 662064164, 662064155
2315860893, 2315860881, 2315860869, 2315860857

I used the following code:

PerlIO_printf(Perl_debug_log, "SEED: %u/%u/%u/%u\n", seed(), seed(), seed(), seed());

at the end of the Perl_drand48_init_r() and then called rand() from the CLI and saw the very similar values.

Expected behavior

Whatever seed() function we employ, that has the sole purpose of seeding a PRNG, should return better, more spaced out, more randomish values. This is very easily solved by simply employing a better hash of the u value at the end of Perl_seed(pTHX). To be clear, this only affects systems where we do not read from /dev/urandom. Windows I'm looking at you.

This should be a pretty simple fix, and I'd like to take a run at it. Before I go too much farther I need to figure out the status of #22962 so I can move forward appropriately.

[scottchiefbaker]

It worth noting that the Perl_seed() function includes a big chunk of text at the top saying it would be better with a "real" hash:

    /*
     * This is really just a quick hack which grabs various garbage
     * values.  It really should be a real hash algorithm which
     * spreads the effect of every input bit onto every output bit,
     * if someone who knows about such things would bother to write it.
     * Might be a good idea to add that function to CORE as well.
     * No numbers below come from careful analysis or anything here,
     * except they are primes and SEED_C1 > 1E6 to get a full-width
     * value from (tv_sec * SEED_C1 + tv_usec).  The multipliers should
     * probably be bigger too.
     */

This text has been here for 28 years now. It was originally part of d7d933a from 1997.

[demerphq]

On Sat, 1 Feb 2025, 11:03 Scott Baker, ***@***.***> wrote: *Description* As part of my exploration into the guts of how Perl handles random numbers I've come across some interesting things. When rand() is called without calling srand() first, a "random" seed is chosen to kick off the *drand48* PRNG. On Linux (or any system with /dev/urandom) the seed is chosen by taking four bytes from urandom <https://github.com/Perl/perl5/blob/blead/util.c#L4718> and generating a U32 from it. For 90% of use cases this is probably find for a general seed. This is good, well thought out, and the correct way to seed a PRNG. On *non*-Linux systems, or when /dev/urandom fails to read, Perl fails back to very simple hash <https://github.com/Perl/perl5/blob/blead/util.c#L4747> of: unixtime, Perl PID, Pointer address, and a hash of a pointer address. On it's face this should be a semi-decent random seed. It would be pretty difficult to guess or repeat a given seed. However after doing some testing I'm finding that repeated calls to seed() return *very* similar values. Usually the values only vary between 2 to 4 bits.

You aren't supposed to seed an RNG like Drand48 more than once in a process, in general even with a better seed function it *reduces* the randomness of the RNG, especially with a small state RNG (aka bad/weak) like Drand48. Consider Drand48 is a ring function, it produces a predetermined sequence of 2^48-1 values before repeating , srand() merely determines where on the ring the sequence starts. If you initialize twice then you merely skip over a chunk of the sequence, reducing the length of the sequence before it repeats output it had already produced. We document you shouldn't call srand() more than once per process for a reason, and it isn't because on some platforms it is "weak", but because it just doesn't make anything better, it makes things worse. *Steps to Reproduce*

Call the seed() function repeatedly 3106881140, 3106881131, 3106881119, 3106881110 662064185, 662064176, 662064164, 662064155 2315860893, 2315860881, 2315860869, 2315860857 I used the following code: PerlIO_printf(Perl_debug_log, "SEED: %u/%u/%u/%u\n", seed(), seed(), seed(), seed()); at the end of the Perl_drand48_init_r() and then called rand() from the CLI and saw the very similar values. *Expected behavior* Whatever seed() function we employ, that has the sole purpose of seeding a PRNG, should return better, more spaced out, more randomish values. This is very easily solved by simply employing a better hash of the u value at the end of Perl_seed(pTHX).

While this is true, it is based on a misconception and is arguably not necessary. Nevertheless improvements in this area can't hurt, and might make cross process srand() a little stronger. There are a number of options available, you could use the hash function perl is built with (I'd avoid SBOX), or use one of the Marsaglia mixer functions used in the hash randomization. Or have a look at the change log, we used to bundle a perfectly good integer pointer hash in the code. I think it was removed at some point but I might have restored it again later. (I'll find a reference later) I do thing however think you are polishing a corpolite here, however well intentioned. Drand48 is a rubbish RNG. If we really cared about the quality of randomness we provide we would replace it with something based on AES or something from the WELL family (MT state is too large and is sensitive to initialization). 48 bits of random state is ridiculously small in a 64 bit world and linear congruent RNGs have all kinds of issues. Anyone noticing or caring about artifacts with our srand() or rand() shouldn't be using Drand48 at all. Cheers, Yves

[scottchiefbaker]

My long term goal would be to replace the PRNG that Perl uses. There was some pushback on p5p about that which lead me to write Random::Simple as an easy way to "upgrade" the built in rand() and srand() with a high quality PRNG. While we wait for bikeshedding about whether or not we can or should upgrade away from drand48, we should at least look at improving what we have.

A very simple solution would be to implement a good hashing algorithm in core and use that to hash state variables to generate the seed. The over-simplified solution I came up with is:

uint32_t p[3];
p[0] = when.tv_sec * 1000000 * when.tv_usec; // Microseconds
p[1] = (U32)PerlProc_getpid();               // Perl process PID
p[2] = PTR2UV(&when);                        // Pointer address

uint32_t seed32 = komihash(&p, sizeof(p), 0);
uint64_t seed64 = komihash(&p, sizeof(p), 0);

This is very flexible and easy to upgrade/replace later if we find better state variables down the road. My initial testing on this method produces good results. To repeat, this only affects platforms that do not have /dev/urandom. The /dev/urandom code path is good (for 32bit).

[demerphq]

On Sat, 1 Feb 2025 at 18:30, Scott Baker ***@***.***> wrote: My long term goal would be to replace the PRNG that Perl uses. There was some pushback on p5p about that which lead me to write Random::Simple <https://metacpan.org/pod/Random::Simple> as an easy way to "upgrade" the built in rand() and srand() stuff with a high quality PRNG. While we wait for bikeshedding about whether or not we can or should upgrade away from drand48 we should at *least* look at improving what we have. A very simple solution would be to implement a good hashing algorithm in core and use that to hash state variables to generate the seed. The over-simplified solution I came up with is: uint32_t p[3]; p[0] = when.tv_sec * 1000000 * when.tv_usec; // Microseconds p[1] = (U32)PerlProc_getpid(); // Perl process PID p[2] = PTR2UV(&when); // Pointer address uint32_t seed32 = komihash(&p, sizeof(p), 0); uint64_t seed64 = komihash(&p, sizeof(p), 0); This is very flexible and easy to upgrade/replace later if we find better state variables down the road. My initial testing on this method produces good results. To repeat, this only affects platforms that do *not* have /dev/urandom. The /dev/urandom code path is good (for 32bit). Im sorry, but IMO this really is overkill. I don't think we should add

komihash just for this purpose. A simple patch like the following should suffice. We could probably remove SEED_C5 and the line that uses it as well and replace it with the ptr_hash() call added below. $ git diff diff --git a/util.c b/util.c index fa946b4153..ffb2ddaf29 100644 --- a/util.c +++ b/util.c @@ -4750,6 +4750,7 @@ Perl_seed(pTHX) UV ptruv = PTR2UV(&when); u += SEED_C5 * ptr_hash(ptruv); #endif + u = ptr_hash(u); return u; } I'm fine with adding komihash as a build option to replace Zaphod32 (see hv_func.h), but IMO adding it just for seed() is massive overkill. What we use seed() for doesn't justify this. Yves -- perl -Mre=debug -e "/just|another|perl|hacker/"

[scottchiefbaker]

Thanks for double checking me on this. I will update my PR to include hashing as you mention above so we can address this.

[scottchiefbaker]

Thinking more about this... you are 100% right that Komihash or xxHash or any "real" hash is way overkill for this. This is a pretty minor issue and is easily addressed with the ptr_hash() we already have.

However, if we had a good general purpose, byte based hash, like Komihash or xxHash already in core it would certainly be a better solution than ptr_hash(). I'm happy to move forward with ptr_hash() for this, but I can definitely see use cases in the future where having a good general purpose hashing algorithm in core would be helpful.

A byte based hash is great because you can hash strings, integers, arrays, etc.

[demerphq]

On Mon, 3 Feb 2025, 04:14 Scott Baker, ***@***.***> wrote: Thinking more about this... you are 100% right that Komihash or xxHash or any "real" hash is *way* overkill for this. This is a pretty minor issue and is easily addressed with the ptr_hash() we already have.

Cool, glad to hear we are on the same page here.

However, *if* we had a good general purpose, byte based hash, like Komihash or xxHash already in core it would certainly be a better solution than ptr_hash().

Fwiw, xxHash isn't a byte based hash, and I'd be surprised if Komihash was either (see below it is not). Typically modern hash functions operate on blocks, either 32 bit, 64 bit or larger, for speed. FNV and some of the older OAAT (meaning "One byte At A Time") functions like the Jenkins function we used to bundle are the exceptions to the rule. General purpose block based hash functions include fairly standard code to handle partial blocks but that doesn't make them "byte based", they still operate on blocks internally. I am really curious about your focus with these two hash functions in particular. Siphash is a perfectly good family of hash function IMO, seeded, secure (as in peer reviewed by cryptographers), and fast enough and widely used and tested. We bundle it for a reason. The only reason it isn't the only hash function is that it requires 64 bit registers. So why do you keep talking as though it doesn't exist? Also I just checked, the komihash header file uses uint64_t which means it will have the same build issues as Siphash does. Also it appears it is either using 64 or 128 bit blocks. It is also quite a bit more complex than Siphash. One of the nice things about Siphash is it is simple and clean and easy to validate.

I'm happy to move forward with ptr_hash() for this, but I can *definitely* see use cases in the future where having a good general purpose hashing algorithm in core would be helpful.

Like I said, we *do* have a *good* general l purpose hashing function in core. Siphash. The way you say it makes it sound like you don't consider it to be good or general purpose or both, which makes no sense to me. It can't be because it's 64bit or you'd say "32 bit hash function", so what gives? A byte based hash is great because you can hash strings, integers, arrays,

etc

Imo calling a hash function "byte based" is just going to confuse matters, especially when most hash functions operate on blocks. Calling a hash function an "integer hash function" just means it was designed to hash exactly one block of data, and it is the callers responsibility to deal with partial blocks. This is an optimization only. Very Very few hash functions process data one bye at a time, it is just not efficient to do so. I would LOVE it if we could find a decent peer reviewed 32 bit hash function so I could remove my Zaphod32 hash from core. But imo neither komihash nor xxHash meet the bill. I'd be very happy to be wrong though. Cheers, Yves

[scottchiefbaker]

I don't mean to imply anything about SipHash. I don't know anything about it actually. As we move forward with (maybe) replacing the PRNG we will need some sort of hash that generates 64bit integers to generate seeds for the new PRNG. Can you help me learn how to use SipHash to do that?

When I say byte-based hash I just mean that you can feed Komihash or xxHash any data structure not just integers. You can feed it a one byte boolean, or a 256 byte string. That is very valuable when it comes to generating a seed from several different states variables. It sounds like SipHash will already do that I just need to be educated how to use it like that.

[scottchiefbaker]

Can you elaborate on "the komihash header file uses uint64_t which means it will have the same build issues as Siphash does"?