TRENT: Possible issue with stuck/biased random generation

[sebastiannielsen]

Found a possible issue with stuck or biased random generation. It apparently generates lots of 5's in a row, which seems uncertainable and weird.

https://defuse.ca/trustedthirdparty.htm?drawingnum=9273 https://defuse.ca/trustedthirdparty.htm?drawingnum=9274 https://defuse.ca/trustedthirdparty.htm?drawingnum=9275 https://defuse.ca/trustedthirdparty.htm?drawingnum=9276 https://defuse.ca/trustedthirdparty.htm?drawingnum=9279

I got then told by a guy that mcrypt_create_iv() is depreciated and random_bytes() should be used. Just a little bit strange, and hopefully it could be looked into and hopefully fixed.

Ran a bit more tests and seems to be fine, but as I said, could be worth looking into.

[defuse]

Yeah, that's strange. The probability of getting any of the same number in a row in a sequence of five similar drawings is 1 * 1/6 * 1/15 * 1/6 * 1/15 = 0.012345679%. Overestimating the probability of that happening anywhere in 1000 drawings (treating each drawing as the potential start of such a sequence independently even though they're not independent) would be 12%. So yeah it's really unlikely.

(Aside: If you're curious about where that 12345679 comes from, here's the explanation).

mcrypt_create_iv() should still be reliable and secure even though it's deprecated. The host this is running on has long uptimes so I'd expect /dev/urandom to be well-seeded all the time. I took a closer look at the code and I don't see any mistakes that would make this more likely. The way it works is it reduces a random 256-bit number modulo the number of possible values. So in this case we got...

r₁ = 5 (mod 8) r₂ = 5 (mod 6) r₃ = 5 (mod 15) r₄ = 5 (mod 6) r₅ = 5 (mod 15)

...which rules out the RNG having returned zero or the same 256-bit number multiple times in a row (the usual ways RNGs fail). The 256-bit numbers are the output of a cryptographic hash in the Linux kernel, so since they are different, part of the input to that hash must have different, and so even if the input were low-entropy (like a simple counter) the output should still be indistinguishable from random by most statistics.

I think it was actually by chance!