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

 Replying to [comment:13 catalyst]:
 > In ba199f789922484b8a2b2efd909ad3dab124dd62, why define
 `EXPECTED_RAND_MANTISSA_BITS` as a hardcoded number instead of using
 `DBL_MANT_DIG`?  (assuming you've already tested for `FLT_RADIX==2`)

 Because we might decide that the contract is N bits of mansissa, rather
 than DBL_MANT_DIG.
 (For example, on my machine, we get 56. Before the patch, we got 31 on
 i386 and 32 on x86_64.)

 > Not directly related to any of the changes, but `crypto_rand_double()`
 could use a comment clarifying its contract.  That would also help us make
 clear what we're trying to achieve.  Are the double values assumed to be
 uniformly distributed in the range 0.0 <= d < 1.0?  How much entropy is it
 supposed to have?  Is it supposed to produce all representable double
 values? (assuming only the values that are more frequent than `2**-b`
 where `b` is the claimed entropy; for IEC 60559 doubles, this means we can
 ignore subnormals unless we're using more than a thousand bits of entropy)

 Yes, I agree we need to define the contract better.
 We need uniform distribution.
 While it would be nice to deliver all values in the range, values below
 10^-13^ (or 2^-43^) are more likely to be produced by RAM bit errors than
 entropy, so at some point we can ignore small values.

 > Regarding the `ldexp()` approach, we could save operations by doing them
 in 32-bit chunks (because I think we can assume at least 32 bits of
 mantissa for a double).

 As long as ldexp() supports 32 bits of input.

 And we might need to modify the ldexp() approach, because the current one
 only gives 64 bits of entropy. The algorithm could be:
 1. Generate a random 64-bit double using ldexp()
 2. If it's zero, generate a random 64-bit double and scale down using
 ldexp() to the next 64 bits

 Terminate when we reach our desired entropy (the contract), which should
 be based on:
 * the RAM bit error rate,
 * the maximum subnormal double bits (DBL_EXP_DIG +
 ceil(log2(DBL_MANT_DIG)).

 Unless we expect really good RAM bit error rates in future RAM, I suggest
 we go for 64 or 128 bits of entropy, and leave it there. (Also, the
 likelihood of any smaller numbers is miniscule, and some calculations will
 turn them into zeroes or infinities anyway.)

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