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

 Using the code in `nickm/privcount_nm_v2_shake_032`, this is the image
 that `sample_unit_gaussian()` would produce from that domain, if it used
 `crypto_rand_double()` to generate `x` and `y` (see #23147).

 First, let's look at `y` and `r`:

 || y              || r Output Calculation          || r Output Value ||
 || 0              || sqrt(-2.0*ln(1.0 - 0.0)       || -0.0           ||
 || 1 * 2^-53^     || sqrt(-2.0*ln(1.0 - 2^-53^))   || 1.49*10^-8^    ||
 || 2 * 2^-53^     || sqrt(-2.0*ln(1.0 - 2*2^-53^)) || 2.11*10^-8^    ||
 || ...            || ...                           || ...            ||
 || 1.0 - 2*2^-53^ || sqrt(-2.0*ln(2*2^-53^))       || 8.49           ||
 || 1.0 - 2^-53^   || sqrt(-2.0*ln(2^-53^))         || 8.57           ||

 Then `x` and `sin(theta)`, near-zero points:

 || x            || sin(theta) Output Calculation || sin(theta) Output
 Value ||
 || 0            || sin(2*pi*0.0)                 || 0.0
 ||
 || 1 * 2^-53^   || sin(2*pi*2^-53^)              || 6.98*10^-16^
 ||
 || ...          || ...                           || ...
 ||
 || 0.5 - 2^-53^ || sin(2*pi*(0.5 - 2^-53^))      || 1.01*10^-15^
 ||
 || 0.5          || sin(2*pi*0.5)                 || 1.22*10^-16^
 ||
 || 0.5 + 2^-53^ || sin(2*pi*(0.5 + 2^-53^))      || -7.66*10^-16^
 ||
 || ...          || ...                           || ...
 ||
 || 1.0 - 2^-53^ || sin(2*pi*(1.0 - 2^-53^))      || -1.13*10^-15^
 ||

 Then `x` and `sin(theta)`, near-one points:

 || x             || sin(theta) Output Calculation || sin(theta) Output
 Value ||
 || 0.25 - 2^-53^ || sin(2*pi*(0.25 - 2^-53^))     || 1.0
 ||
 || 0.25          || sin(2*pi*0.25)                || 1.0
 ||
 || 0.25 + 2^-53^ || sin(2*pi*(0.25 + 2^-53^))     || 1.0
 ||
 || ...           || ...                           || ...
 ||
 || 0.75 - 2^-53^ || sin(2*pi*(0.75 - 2^-53^))     || -1.0
 ||
 || 0.75          || sin(2*pi*0.75)                || -1.0
 ||
 || 0.75 + 2^-53^ || sin(2*pi*(0.75 + 2^-53^))     || -1.0
 ||

 This means that the largest values are:

 || x    || y            || r * sin(theta) Output Value ||
 || 0.25 || 1.0 - 2^-53^ || 8.57                        ||
 || 0.75 || 1.0 - 2^-53^ || -8.57                       ||

 And given the slope of the sine curve at those points, we should be able
 to get nearby values easily.

 And the smallest values are:

 || x            || y      || r * sin(theta) Output Value ||
 || 0.0          || any    || 0.0                         ||
 || 0.5          || 2^-53^ || 1.82*10^-24^                ||
 || 0.5 + 2^-53^ || 2^-53^ || -1.14*10^-23^               ||

 Typical standard deviations in experimental PrivCount go from 10^3^ to
 10^10^. I think we need the smallest possible noise to be `1.0`, so this
 granularity looks OK. (But it might limit our standard deviations to about
 10^23^ or so, which could be a problem. I need to check this with Aaron.)

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