[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 yawning):

 Replying to [comment:15 nickm]:

 > Here are some goals I think we probably care about, but I could be
 wrong:

 If that's what you want:
 {{{
 double uint64_to_dbl_0_1(uint64_t x) {
   /* Can't merely check for __STDC_IEC_559__ because not every compiler we
 care about defines it. */
 #if FLT_RADIX != 2
 #error FLT_RADIX != 2, your system is the most special of them all.
 #endif
   x >>= (sizeof(double) * CHAR_BIT) - DBL_MANT_DIG;
   return (DBL_EPSILON/2) * x;
 }}}

 >    * 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.)

 Check.

 >    * 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.)

 Check.

 >    * Run with reasonable efficiency.

 Check.

 >    * Run in constant time.

 Check.

 >    * Use the whole mantissa, or almost the whole mantissa.

 Check.

 >    * Provide at least some number of bits of entropy in the output.

 Check.

 >    * Work at least to a minimal degree on all c99 platforms.

 If people want to run tor on something that is exotic to the point where
 this sort of approach breaks, they can send patches.

 Yes this still leaves out "possible" values, but it trivially accomplishes
 uniform, fast, and constant time.

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