Timeline for Exactly how bad is using 'mod' to clamp reduce numbers to a given range?
Current License: CC BY-SA 3.0
18 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Aug 2, 2022 at 10:48 | comment | added | Yann Droneaud | Modulo would affect the output distribution if range is not a multiple of the generator's range. Hopefully, it exists many ways to avoid the issue, see Efficiently Generating a Number in a Range for some examples | |
Jan 31, 2016 at 5:59 | answer | added | Yehuda Lindell | timeline score: 5 | |
Jan 31, 2016 at 4:15 | comment | added | user541686 | @RickyDemer: Yeah that factor of 2 is precisely what I was referring to. Your point about the stream cipher could be a good answer if you'd like to write one. | |
Jan 31, 2016 at 4:12 | comment | added | user991 | ... "than" what one-half you talked about? (I only see a mention of "a factor of 2".) For example, if you used that as the keystream for a stream cipher, then an eavesdropper could easily distinguish between [encryptions of long mostly-0 plaintexts] and [encryptions of long mostly-1 plaintexts]. | |
Jan 31, 2016 at 4:03 | comment | added | user541686 | @RickyDemer: Yeah so that's already way less than the one-half I talked about (I think that's the max too? I didn't really think about it). My question stands exactly as-is: why is that a real problem for a system that is otherwise designed to be secure? Who cares if the attacker saves 1/6 of his time? | |
Jan 31, 2016 at 1:30 | history | tweeted | twitter.com/StackCrypto/status/693607131484917762 | ||
Jan 31, 2016 at 0:33 | comment | added | user991 | If m=2 and n=3, then using the simple method on true randomness would have a 2/3 probability of outputting 0 and a 1/3 probability of outputting 1. (That differs by 1/6 from the uniform distribution on {0,1}.) | |
Jan 31, 2016 at 0:30 | comment | added | user541686 | @RickyDemer: Can you elaborate? Give me an example? Pretend I'm dumb. That tells me nothing about your thought process. | |
Jan 31, 2016 at 0:29 | comment | added | user991 |
"the problem here" is that you've assumed m <= n but nothing else about m and n.
|
|
Jan 31, 2016 at 0:28 | comment | added | user541686 | To add to what @RickyDemer said, aren't current cryptographic systems far more difficult to crack than by a factor of 2? What's the problem here? | |
Jan 31, 2016 at 0:26 | comment | added | user991 | @squeamishossifrage : The distinguishing advantage increases by less than m/(2$\hspace{-0.02 in}\cdot$n), so it'll also be secure when that is negligible. | |
Jan 31, 2016 at 0:18 | comment | added | r3mainer | I think this question already has an answer. Unless $m$ is a factor of $n$, your RNG is no longer cryptographically secure. | |
Jan 30, 2016 at 21:47 | comment | added | Hilder Vitor Lima Pereira | @E.Rose take for instance $n = 10$ and $m=7$. So, the value 1 has double of the chance to appear, because 1 % 7 = 8 % 7 = 1 ... | |
Jan 30, 2016 at 21:43 | comment | added | Ella Rose | I would like to understand how the modulo operation influences the uniformity of k. Can someone link or summarize the information for me? | |
Jan 30, 2016 at 21:41 | comment | added | emory | I don't think it is a serious problem. The distribution of k will not be uniform (unless n%m=0), but it will be close to uniform. As an attacker I will start from zero and work up, rather than m-1 and work down. | |
Jan 30, 2016 at 21:34 | comment | added | user541686 | @those who migrated this question: I wasn't just talking about crypto though... imagine an attacker trying to DDoS a service by making it execute worst-case behavior on a hashtable. Or whatever. | |
Jan 30, 2016 at 21:32 | history | migrated | from security.stackexchange.com (revisions) | ||
Jan 30, 2016 at 21:19 | history | asked | user541686 | CC BY-SA 3.0 |