Bugs in random

[Sc00bz]

• randomInt32() gets 8 bytes of random for a 32 bit int.

  spg/util.go

  Line 44 in 5a36bf7

  b := make([]byte, 8)

• int31n() gets a random uint32 [0, 2**32). When n is not a power of 2, max is at most 2**31-2. This has a >25% to <50% vs a >50% to <100% chance of success each loop. To fix this mask the random v := randomInt32() & math.MaxInt32.

• spg/util.go

  Lines 82 to 95 in 5a36bf7

  	func int31n(n uint32) uint32 {
  	if n <= 0 {
  	panic("invalid argument to int31n")
  	}
  	if n&(n-1) == 0 { // n is power of two, can mask
  	return randomInt32() & (n - 1)
  	}
  	max := uint32((1 << 31) - 1 - (1<<31)%uint32(n))
  	v := randomInt32()
  	for v > max {
  	v = randomInt32()
  	}
  	return v % n
  	}

  if int31n() is called with n > 2**31 it is not uniform. This bug was caused by switching n from int32 to uint32. Switch n back, do if int32(n) <= 0 { panic..., or rename to uint32n() and fix max (see https://github.com/Sc00bz/ModRandom/blob/a2cd9247a0dcb0183ec6305574b5696f51186540/csprng-cpp/csprng.cpp#L259-L284).

[Sc00bz]

(Note these are just performance bugs and a bug that isn't triggered in your code... well I'm pretty sure int31n() isn't called with an n that's more than 2**31)

[robyoder]

Nice finds, @Sc00bz! I'm looking at this code for the first time as well. It looks like we intended to switch to uint32 but didn't quite get there as you noticed. So I was going to go with option 3: rename and fix max.

But then I found out why this was originally an int32 and not a uint32. In order to fix max, I need something like max := (1<<32 - 1) - (1<<32)%n, but 1<<32 overflows my uint32 and means I'd need to cast to uint64.

I looked at your implementation to see how you solved that, and I don't think you did. You're doing MaxUint32 - (MaxUint32 % n), which is wrong and means you have a modulo bias (unless I'm missing something obvious).

[robyoder]

Best thing I could come up with is max := uint32(math.MaxUint32 - (1<<32)%uint64(n)). Could do some fancy modular arithmetic to keep values inside uint32, but at that point we're using more memory and doing more computations, so not really worth it.

[robyoder]

I'm an idiot. Yours is perfectly fine when n is not a power of 2, which was caught before we get here.