[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [tor-bugs] #23061 [Core Tor/Tor]: crypto_rand_double() should produce all possible outputs on platforms with 32-bit int
#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
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs