Is Kernel :: srand the maximum input value?

Question

I am trying to align a random number generator with a hash output. I am currently calculating the SHA-1 hash, converting it to a gigantic integer and passing it to srand to initialize the RNG. This is so that I can get a predictable set of random numbers for many infinite Cartesian coordinates (I pass the coordinates).

I am wondering if Kernel :: srand has the maximum value that is required, after which it somehow truncates it. Documents don't really make it obvious - they just say "number."

I will try to figure it out myself, but I guess someone out there has already stumbled upon it.

Answer 1

Knowing what programmers are, maybe it just calls libc srand() . In any case, it is probably limited to 2 ^ 32-1, 2 ^ 31-1, 2 ^ 16-1 or 2 ^ 15-1.

There is also the danger that the value is truncated when converting from a large object to C int / long instead of accepting only the least significant bits.

An easy test is seeds with 1 and the first conclusion. Then seeds with 2 ⁱ +1 for i in [1.644] or so, take the first conclusion of each and compare. If you get a correspondence for some i=n and all large i s, then he will probably do arithmetic modulo 2 ⁿ .

Note that the random number generator is almost certainly limited to 32 or 48 bits of entropy anyway, so a small point visits it with enormous value, and an attacker can reasonably easily predict future exits, data from past exits (and the “attacker” may just be a player on the Nethack public server).

EDIT: So, I was wrong.

As per docs for Kernel :: rand (),

Ruby currently uses a modified Twister Mersenne with a period of 2 ** 19937-1.

This means that this is not just a libc rand() call. Mersenne Twister is statistically superior (but not cryptographically secure). But anyway.

Testing using Kernel::srand(0); Kernel::sprintf("%x",Kernel::rand(2**32)) Kernel::srand(0); Kernel::sprintf("%x",Kernel::rand(2**32)) for various output sizes (2 * 16, 2 * 32, 2 * 36, 2 * 60, 2 * 64, 2 * 32 + 1, 2 * 35, 2 * 34 + 1), some things are obvious:

• It determines how many bits it needs (the number of bits in max-1 ).
• It generates output in groups of 32 bits, the most significant bits first, and discards the upper bits (ie 0x [r0] [r1] [r2] [r3] [r4], while the upper bits are masked).
• If it is not less than max , it performs some kind of retry. It is not obvious that this is from the result.
• If it is less than max , it prints the result.

I'm not sure why 2 * 32 + 1 and 2 * 64 + 1 are special (they produce the same output from Kernel::rand(2**1024) , so maybe they have the same state) - I did not find another collisions.

The good news is that it does not just copy any arbitrary maximum (i.e., passing in huge quantities is not equivalent to passing in 2 ** 31-1), which is the most obvious thing that can go wrong. Kernel :: srand () also returns the previous seed, which appears to be 128-bit, so it seems that it would be safe to transfer something big.

EDIT 2: Of course, there is no guarantee that the output will be played between different versions of Ruby (the documents just say that it is “currently using”, apparently this was originally done in 2002). Java has several portable deterministic SecureRandom.getInstance("SHA1PRNG","SUN") ( SecureRandom.getInstance("SHA1PRNG","SUN") , although slow); I don't know anything like this for Ruby.