[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:  teor
     Type:  defect                               |         Status:
                                                 |  assigned
 Priority:  Medium                               |      Milestone:  Tor:
                                                 |  0.3.6.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
  029-backport, review-group-22,                 |
  034-triage-20180328, 034-removed-20180328,     |
  031-unreached-backport, 035-roadmap-subtask,   |
  035-triaged-in-20180711                        |
Parent ID:  #26637                               |         Points:  0.1
 Reviewer:                                       |        Sponsor:
                                                 |  SponsorV-can
-------------------------------------------------+-------------------------

Comment (by riastradh):

 I should add about `sample_uniform_01` vs `sample_uniform_01_open` that,
 generally, the only reason you should use `sample_uniform_01_open` is as a
 drop-in replacement for the current `crypto_rand_double` to avoid breaking
 downstream code that assumes it can't get the floating-point number 1.

 If you want to take the log of the sample without getting -infinity, for
 instance to generate an exponential sample, you want a floating-point
 number in (0, 1], not a floating-point number in [0, 1).  (Even better,
 for an exponential sample, you can use -log(p/2) if a fair coin toss turns
 up heads, and -log1p(-p/2) if it turns up tails -- then the sampler
 supports high precision negative and positive outputs; flip another coin
 to pick the sign, for a Laplace sampler.)  If for some reason you are
 tempted to compute log1p(-p) or 1/(1 - p) downstream where p is uniform in
 [0, 1), better to change what happens downstream to compute log(p) or 1/p
 where p is in (0, 1] -- log1p and 1/(1 - p) are ill-conditioned near 1, so
 it's always better to avoid relying on computations involving such
 intermediate quantities.

 The Mironov paper analyzes the use of (a) a correct uniform distribution
 like I provided (actually, sometimes he vacillates between (0,1) and (0,1]
 but I don't think it matters for the proof except maybe requiring a small
 adjustment to Eq. (7)), together with (b) a correctly rounded natural
 logarithm, and proves a differential privacy result, Theorem 1, under
 those assumptions.

 The system's libm is unlikely to have a correctly rounded log, with
 maximum 0.5ulp error, corresponding to 2^-53^ relative error, but it is
 likely to have something very close to that -- almost certainly much
 better than 1ulp or 2^-52^ relative error.  As a rough approximation, I
 think you can just take eta in Sec. 5.2 of the paper to be 2^-52^ instead
 of 2^-53^, and instead of the (1/lambda + 2^-49^B/lambda)-differential
 privacy asserted in Theorem 1, you get (1/lambda +
 2^-48^B/lambda)-differential privacy.

 P.S.  If in your Laplace sampler you use the exponential sampler I
 described above -- toss a fair coin to decide whether to use -log(p/2) or
 -log1p(-p/2), instead of the standard unconditional -log(p) -- I bet
 you'll get a slightly better differential privacy bound.  But it would
 take a bit of work to identify the better bound and prove it, and really,
 most of this is just to get confidence that the bound doesn't explode and
 is reasonably small in concrete parameters, not to prove the bestest most
 tightest bound possible.

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