3 ms·

Right, this is a generator that's used in contexts where a timing side-channel is not a concern, but it's still a great distinction to point out. More broadly,

Right, this is a generator that's used in contexts where a timing side-channel is not a concern, but it's still a great distinction to point out. More broadly, the Swift language--like almost every other language--doesn't have any notion of constant-time operation, so it's not clear what you would do with an RNG free of timing side channels if you had one; use it in a computation that can't make any guarantees about side channels?* You're correct that the number of expected calls collapses to 2 (matching the worst case for Lemire) even in that case, but (for our purposes) it's a "better" 2 (at least with most random sources) since (a) it still never divides (b) it is branch-free, so it never mispredicts and (c) it's always 2 instead of 1 with probability 1/2, 2 with probability 1/4, 3 with probability 1/8 and so on. * I am generally very (probably too) negative on “best effort” constant time operations in high-level languages, but having seen innumerable schemes undone by compiler optimizations, I’m jaded. If you need to eliminate side channels, use hardware designed to do so. [All that said, I added a note to the PR to make this clear.]

nneonneo 5y ago
Cryptographic operations come to mind. I could see someone reaching for this function to get a uniform value below some prime, for example, which might be reasonable if it were backed by a good CSPRNG for the underlying bits - and a good CSPRNG might well be slow enough to make this timing channel easily observable. Some of the good modern crypto libraries make fairly strong guarantees about constant-time or at least data-independent operations. Granted, these may not be 100% side-effect-free thanks to processor bugs, but at least those are fairly time-intensive to attack. In any case, the concern isn’t the variable number of calls, but the fact that the number of calls could leak information about the results. EDIT: Well, two of the places your PR has been linked to are RustCrypto (https://github.com/RustCrypto/utils/issues/453 https://github.com/RustCrypto/utils/issues/453) and OpenSSL (https://github.com/openssl/openssl/issues/16500 https://github.com/openssl/openssl/issues/16500), two places where I definitely would not want to see a significant timing vulnerability. I wish that the folks posting these to crypto libraries would be more aware that this timing issue exists! To concretely demonstrate the problem: suppose that the 64-bit upper bound is `2^64 * 3/4 = 13835058055282163712`. In this case, if the early exit is triggered, the result modulo 3 must be 0 or 2 (with 50% probability for each): numbers congruent to 1 mod 3 cannot come out of the early exit. By contrast, Lemire's method always outputs a uniform distribution of outputs at each iteration. Lemire's method has a smaller timing leak in that the division doesn't always happen - and since divisions are expensive, this could be significant, but it won't outweigh the cost of an unbuffered read of urandom, for example.
- stephencanon 5y ago
  Having worked on implementations of side-channel resistant crypto libraries, processor bugs mostly don’t scare me, but uArch and compiler optimizations very much do.

nneonneo 5y ago

Cryptographic operations come to mind. I could see someone reaching for this function to get a uniform value below some prime, for example, which might be reasonable if it were backed by a good CSPRNG for the underlying bits - and a good CSPRNG might well be slow enough to make this timing channel easily observable. Some of the good modern crypto libraries make fairly strong guarantees about constant-time or at least data-independent operations. Granted, these may not be 100% side-effect-free thanks to processor bugs, but at least those are fairly time-intensive to attack. In any case, the concern isn’t the variable number of calls, but the fact that the number of calls could leak information about the results. EDIT: Well, two of the places your PR has been linked to are RustCrypto (https://github.com/RustCrypto/utils/issues/453 https://github.com/RustCrypto/utils/issues/453) and OpenSSL (https://github.com/openssl/openssl/issues/16500 https://github.com/openssl/openssl/issues/16500), two places where I definitely would not want to see a significant timing vulnerability. I wish that the folks posting these to crypto libraries would be more aware that this timing issue exists! To concretely demonstrate the problem: suppose that the 64-bit upper bound is `2^64 * 3/4 = 13835058055282163712`. In this case, if the early exit is triggered, the result modulo 3 must be 0 or 2 (with 50% probability for each): numbers congruent to 1 mod 3 cannot come out of the early exit. By contrast, Lemire's method always outputs a uniform distribution of outputs at each iteration. Lemire's method has a smaller timing leak in that the division doesn't always happen - and since divisions are expensive, this could be significant, but it won't outweigh the cost of an unbuffered read of urandom, for example.

stephencanon 5y ago
Having worked on implementations of side-channel resistant crypto libraries, processor bugs mostly don’t scare me, but uArch and compiler optimizations very much do.