14 ms·
The definitive guide to “modulo bias” and how to avoid it (2020)
- rrobukef 4y agoRejection sampling moves the information leak from bias to time. As always don't use your own cryptography in production.
- cronokirby 4y agoIf you have a random stream of bits, and you use rejection sampling to extract a value from that stream, then you don't reveal any information about the value. At most, you reveal information about the stream prior to the value you chose, but each bit of a secure RNG should be unrelated to all prior bits, so this is not an issue.
- omegalulw 4y agoBut you do? You expose some information on the range of the value via the time it took to sample assuming for example that the attacker knows the rejection sampling method in use.
- cronokirby 4y agoThat is true. That said, there are few situations where the modulus being used is not a public parameter of a protocol, and it is very difficult to perform operations with a secret modulus in constant-time, as your comment points out. You'll always be able to get an approximate guess of the size of the modulus too, since larger moduli will need more registers to represent data.
- some_furry 4y agoWe don't consider "leaks the length of a SHA256 hash" to be a valid timing attack in most protocols for similar reasons (i.e. it's public knowledge). When developers encounter timing attacks in their code, they often invent really dumb ways to side-step the length "leaking". This might be understandable if it was a MAC then Encrypt protocol with PKCS padding (hello lucky13), but instead this comes up in the context of "validate this HMAC-SHA256 tag for our JWT-like protocol".
- LudwigNagasena 4y agoA cleaner example without bit masking: https://github.com/openbsd/src/blob/master/lib/libc/crypt/arc4random_uniform.c https://github.com/openbsd/src/blob/master/lib/libc/crypt/ar...
- fanf2 4y agoI was hoping for a mention of Daniel Lemire’s nearly-divisionless algorithm for unbiased sampling. I recently replaced BIND’s copy of OpenBSD arc4random_uniform() with Lemire’s algorithm https://gitlab.isc.org/isc-projects/bind9/-/blob/main/lib/isc/random.c#L150 https://gitlab.isc.org/isc-projects/bind9/-/blob/main/lib/is... and I blogged on the subject a couple of times https://dotat.at/@/2020-10-29-nearly-divisionless-random-numbers.html https://dotat.at/@/2020-10-29-nearly-divisionless-random-num... https://dotat.at/@/2022-04-20-really-divisionless.html https://dotat.at/@/2022-04-20-really-divisionless.html
- anomalroil 4y agoLemire's technique is really nice, in general a good thing to learn about, since it's a bit mind bending how it's playing with intervals. Sadly last time I benchmarked it in code on x86-64 for cryptographic purposes, it wasn't faster than rejection sampling, or just using a large value and a modulo reduction: in all cases what is actually taking a lot of time is the call to get good quality randomness out of a CSPRNG, the rest being negligible in comparison.
- makobado 4y agoThis is going to be fun at work
- anomalroil 4y agoNotice that nowadays, unlike 2 years ago, people usually recommend to use the last technique I presented there in the last paragraph before the Conclusion. Which is to generate a random value that is big enough, so that n-log(p) > 128 so that the bias will be too small to be exploitable in practice. It's simpler and unlike rejection sampling ensures your code cannot fall into an infinite loop in case your PRNG is broken. (I'd argue you might want your code to fail in that case anyway, but YMMV.)
- stephencanon 4y agoThe other virtue of this technique is that some of the more popular fast rejection sampling methods (e.g. Lemire's "nearly divisionless") leak a small amount of information via timing side channel, because the divisionless fast path is _not_ unbiased.
- tarakat 4y ago> You shouldn’t rely on these claims, because even 1 bit of bias on a 256 bit nonce value can be enough to attack certain cryptographic schemes! This seems like a very high bar for a random generator to clear. It also raises a question: would using a larger nonce size actually increase risk, if the additional bits were biased?
- barsonme 4y agoWith some schemes, like ECDSA, you can't use a larger nonce since the nonce is a field element. In general, you shouldn't need to worry about it unless you're using a broken CSPRNG or a bad cryptography library. And some libraries will try and work around bad RNGs: https://cs.opensource.google/go/go/+/refs/tags/go1.19.1:src/crypto/ecdsa/ecdsa.go;l=240 https://cs.opensource.google/go/go/+/refs/tags/go1.19.1:src/...
- jstanley 4y agoIt seems like the general case answer is "no, using a larger nonce does not increase risk". Otherwise an attacker could just imagine that instead of a 256-bit nonce, the nonce was actually 257 bits long but the first bit is always 0.
- eisbaw 4y ago(r_dist * n) / <max value of r_dist> is better than r_dist % n that linear scaling should mitigate such bias from modulo bias.
- yorwba 4y agoThat just moves the bias to other numbers. In the example of reducing a byte-sized random value modulo 107, the bias is that 0 can be generated by three different possible inputs (0, 107 and 214), while 42 can only be generated by two (42 and 149; 256 is just out of range), so 0 ends up being 50% more common than 42 in the long run. With your proposed scheme, 0 can be generated by three possible inputs again (0, 1 and 2), while 1 can only be generated by two (3 and 4), so 0 ends up being 50% more common than 1 in the long run.
- exabrial 4y agoInteresting. In Java, there’s random.nextInt(max). Curious if that takes this into account.
- brazzy 4y agoI have zero doubt that it does. This is extremely high visibility code that has been around for decades. And I also have zero doubts that there are a bunch of reimplementations that don't, from assclowns who don't trust libraries on general principle.
- deleted 4y ago[deleted]
- anomalroil 4y agoIt does but it does not! java.util.Random is not a CSPRNG at all and is terrible, so even tho the nextInt() method is using rejection sampling, it's still producing biased values and also completely fails to be "unpredictable" because java.util.Random is weak and predictable.
- deleted 4y ago[deleted]
- brazzy 4y agoThat's why we have public class SecureRandom extends Random
- the_af 4y agoInteresting! How come this wasn't fixed? Nobody noticed, or is it that java.util.Random is not meant for serious cryptographic use? I know there are other parts of the Java standard lib that are so terrible [1] that people for years have recommended not using them, like anything with dates and timezones... --- [1] or used to, haven't kept up with the latest Java versions. Maybe they fixed it.
- 4y ago
- deleted 4y ago[deleted]
- barbegal 4y agoThe claim "even 1 bit of bias on a 256 bit nonce value can be enough to attack certain cryptographic schemes" is true but there have been no practical attacks against 256 bit secured schemes. And the example of the mod 107 issue only reduces the amount of bits from 6.74bits to 6.71bits (a reduction of 0.4%) so hardly worth worrying about in the real world.
- xxpor 4y agoEverything here is focused on cryptography, but there's other common issues that can fall into this trap too. For example, naive implementations of a hash function for a basic array + linked list hash table. If you generate a hash, and then modulo that to pick a hash bucket, you could end up with a biased distribution across the buckets, and customers complaining your performance varies wildly based on the input value. Just more things to think about :)
- kelnos 4y agoIsn't that why most tutorials on writing hash tables that use this bucketing method recommend using table sizes that are powers of two? I guess most tutorials don't exactly explain why, though, so someone who doesn't understand could decide to not use a power of two without understanding why that's bad.
- xxpor 4y agoThere's another reason why (mathematically related) to use a power of 2 as well: it makes the modulo a simple and fast mask, instead of a slow division.
- astrobe_ 4y agoI remember very old versions of man random [1] warning against that sort of thing and recommending to pick the high (or low) bits of the random value. Probably the piece of advice was not correct.
- morelisp 4y agoPicking different bits doesn't solve modulo bias. This is more likely a memory of the warning concerning the low quality of the randomness in the low bits (e.g. in LCGs where it always alternates in the lowest bit), or the fact the high bits of rand(3) were often zero due to a small RAND_MAX.
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- 10000truths 4y agoIf you need to generate multiple such random numbers, an alternative way to resolve modulo bias with minimal entropy waste is to batch the random number generation. For example, you can generate 6 random integers in [0, 100) by generating a random integer in [0, 100^6) and performing modulo reductions on the result to get your 6 integers. 100^6 is slightly less than 256^5, so if your RNG works in units of bytes, then you can use 5 bytes to generate 6 integers in [0, 100) instead of 6 bytes.
- nraynaud 4y agoI knew the concept (every post on "I want a randome number in a range" mentions it), but I didn't know the name, thanks.