#8765

[Dr Paul Dale]

#8765 <https://github.com/openssl/openssl/pull/8765> has been sitting in an OTC hold state for a while and @DDvO has asked how it can be progressed.

The PR is attempting to change the bnrand_range() function.
Our existing code iterates (up to 100 times) and generates candidates which each have a 75% chance of being within the desired range.  It guarantees an unbiased result but is slow and variable in its timing.  It is also difficult to understand.
The code that currently stands <https://github.com/openssl/openssl/pull/8765/files> in the PR uses the method FIPS 186-4 B.1.1 / BSI TR-02102-1 Table B4 Method 2 to generate random numbers within a range quickly, although there is a very slight bias introduced.  This generates an extra 64 bits of randomness, modulo reduces the result and returns it.  The bias being that 2^(n+64) isn’t exactly divisible by the range (at least in general).  Again
The third approach <https://github.com/siemens/openssl/commit/71ce233d5d640de79b14130c78debe059c9f563d> with takes advantage of an idea from Lemire’s exquisite Fast Random Integer Generation in an Interval <https://arxiv.org/abs/1805.10941> to produce a similar biassed result using a multiplication instead of a modulus.  I.e. this one can be constant time and is faster again.
It is possible to implement Lemire’s algorithm completely which gives fast and unbiassed results, although it might have to iterate on occasion.
Do RNGs need to be constant time?  I’m not sure.  Our BN_mod() function isn’t and exposes potential side channel attacks (we have this now).
The variable number of iterations cannot be used for a timing attack because iteration means that the generated number is out of range and thrown away.  An attacker only learns that and nothing about the final out.

Do we want our RNG to be faster?  This seems like a decent idea.

Can we live with (slightly) biassed output?


As noted by @DDvO, some of the tests are failing.  At one point I implemented Lemire’s algorithm and the broken tests were what stopped me.  I don’t remember the precise details, I’ve a niggle that it might have been NIST’s KATs implicitly relying on the “standard” modulo reduce approach being used for random range generation.


Thoughts or suggestions?

Pauli
-- 
Dr Paul Dale | Distinguished Architect | Cryptographic Foundations 
Phone +61 7 3031 7217
Oracle Australia




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mta.openssl.org/pipermail/openssl-project/attachments/20201208/654a0b2a/attachment.html>