[tor-bugs] #23061 [Core Tor/Tor]: crypto_rand_double() should produce all possible outputs on platforms with 32-bit int

[Tor Bug Tracker & Wiki]

#23061: crypto_rand_double() should produce all possible outputs on platforms with
32-bit int
-------------------------------------------------+-------------------------
 Reporter:  teor                                 |          Owner:  nickm
     Type:  defect                               |         Status:
                                                 |  needs_revision
 Priority:  Medium                               |      Milestone:  Tor:
                                                 |  0.3.2.x-final
Component:  Core Tor/Tor                         |        Version:  Tor:
                                                 |  0.2.2.14-alpha
 Severity:  Normal                               |     Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:  0.5
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 027-backport-maybe, 026       |
  -backport-maybe                                |
Parent ID:                                       |         Points:  0.1
 Reviewer:                                       |        Sponsor:
                                                 |  SponsorQ
-------------------------------------------------+-------------------------

Comment (by nickm):

 We have a lot of options here, depending on what we want!  Let's try to
 collect the possible goals, and see which we care about.

 Here are some goals I think we probably care about, but I could be wrong:
    * We should return a number uniformly at random in the range [0, 1.0).
 (That is, for all "suitable" x<y in [0,1.0), we should return a value in
 [x,y] with probability very close to y-x. Defining "suitable" and "very
 close" will be important, and might not include every possible double.)
    * Return outputs with at least some minimum granularity. (i.e, for some
 granularity delta, if x is a possible output, and x ± delta is in [0.0,
 1.0), then there exists a possible output between x and x ± delta other
 than x.)
    * Run with reasonable efficiency.
    * Run in constant time.
    * Use the whole mantissa, or almost the whole mantissa.
    * Provide at least some number of bits of entropy in the output.
    * Work at least to a minimal degree on all c99 platforms.

 Here are some goals I think we do not care about, but I could be wrong:
    * Work perfectly on systems where FLT_RADIX is not 2.
    * Provide identical output on all architectures regardless of floating-
 point implementation.
    * Return every possible output with some probability. (For example,
 values less than 1e-300 are _possible_ doubles. But they have cumulative
 probability of 1e-300, which is less likely than just guessing the RNG
 seed on the first try.)
    * Possibly return subnormal values.
    * Perfect behavior on corner cases with total probability less than
 some epsilon (maybe 2^-96)?
    * Run as fast as possible.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/23061#comment:15>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online