crypto/rand: rand.Int consumes and wastes a large percentage of bytes #18165
Comments
|
A better way to word this might be that 75% of the bytes read from the source are wasted unnecessarily. To generate 1,000 random bytes, 4,000 bytes are read from the random source. |
|
See also https://go-review.googlesource.com/c/10161/. I am planning to push on it a bit. It probably won't go in the core as it stands, but might become available as an alternative, or just stay in exp. Better properties across the board, at least potentially, yet has fundamentally the same interface. Will need some assembly language to increase the entropy of the source, but it's been "abandoned" for now to avoid confusing people. |
bradfitz
added
the
NeedsDecision
|
I have a patch that fixes the off by 1 that I can submit for review if there is interest in merging this. |
bradfitz
added
NeedsFix
|
crypto/rand not math/rand so no compatibility problem. But also "if the cryptographic random source is expensive" seems not to be true, right? We use /dev/urandom. |
|
I've submitted my patch here: https://go-review.googlesource.com/c/43891/ |
|
CL https://golang.org/cl/43891 mentions this issue. |
The test relies on this fix: - golang/go#18165
calling
rand.Int(rand.Reader, 256)should only consume 1 byte from the reader to provide a random number from 0-255. Instead it consumes at least 2 bytes and on average 4 bytes. This means that 300% extra bytes are read from the random source. If the cryptographic random source is expensive, this is a lot of wasted reads.The issue is an off-by-one error when selecting how many bytes are necessary to read from the source. For max=256, only 1 byte should be read as any bit still set in the extra byte after filtering will cause the function to re-run anyways (it will be greater than or equal to the max).
examples for the common cases of reading a random int8, int16 and int32:
https://play.golang.org/p/gWXjn51ehn
The off-by-one error is here (should be equivalent of
(max-1).BitLen()): https://github.com/golang/go/blob/go1.7.4/src/crypto/rand/util.go#L110The text was updated successfully, but these errors were encountered: