Re:The definitive guide to “modulo bias” and how to avoid it...
by cronokirby on Thursday September 15, 2022 @06:42AM
(#32849810)
If 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.
[ Parent
| on HN ]
Re:The definitive guide to “modulo bias” and how to avoid it...
by omegalulw on Thursday September 15, 2022 @06:49AM
(#32849861)
But 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.
Re:The definitive guide to “modulo bias” and how to avoid it...
by cronokirby on Thursday September 15, 2022 @06:57AM
(#32849913)
That 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.
Re:The definitive guide to “modulo bias” and how to avoid it...
by some_furry on Thursday September 15, 2022 @07:29AM
(#32850161)
We 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".