[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_review
 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, 026-backport-maybe, review-   |
  group-22                                       |
Parent ID:                                       |         Points:  0.1
 Reviewer:                                       |        Sponsor:
                                                 |  SponsorQ
-------------------------------------------------+-------------------------

Comment (by teor):

 If we use `uint64_to_dbl_0_1()`, then each random double is of the form
 N*2^-53^, N = 0..(2^53^ - 1).

 This is the image that sample_laplace_distribution() produces from that
 domain:

 || rand_double || Output Calculation                       || Output Value
 ||
 || 0            || INT64_MIN                                || - 2^63^
 ||
 || 1 * 2^-53^   || - ln(2*2^-53^) * delta_f / epsilon       || 36.04 *
 delta_f / epsilon ||
 || 2 * 2^-53^   || - ln(4*2^-53^) * delta_f / epsilon       || 35.35 *
 delta_f / epsilon ||
 || ...          || ...                                      || ...
 ||
 || 0.5 - 2^-53^ || - ln(1.0 - 2*2^-53^) * delta_f / epsilon || 2.22 *
 delta_f / epsilon  ||
 || 0.5          || - ln(1.0) * delta_f / epsilon            || 0.0 *
 delta_f / epsilon   ||

 0.5 to 1.0 - 2^-53^ has the same pattern, but mirrored and negative.

 The greatest `delta_f / epsilon` we currently have is `2048 / 0.3 =
 6826.66`, so the maximum noise is 246033, with a discontinuity that
 destroys the signal when 0.0 maps to INT64_MIN (let's track that bug in
 #23323).

 The gap between 0.5 and 0.5 - 2^-53^ concerns me, because I think we need
 the smallest possible noise to be `1.0`, rather than `2.22 * delta_f /
 epsilon = 2.22 * 8 / 0.3 = 59.2`. But maybe this granularity is OK.

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