Opened 12 months ago

Last modified 7 weeks ago

#23415 assigned defect

sample_laplace_distribution() should take multiple random inputs

Reported by: teor Owned by: teor
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version: Tor: 0.2.8.1-alpha
Severity: Normal Keywords: tor-relay, security-low, privcount, 029-backport, 026-backport-maybe, 034-triage-20180328, 034-removed-20180328, 031-unreached-backport
Cc: Actual Points:
Parent ID: #25263 Points: 0.5
Reviewer: Sponsor: SponsorQ-can

Description (last modified by teor)

Currently, sample_laplace_distribution() takes a random double as input, and then extracts the following random values:

  • a random sign
  • a random value in (0.0, 1.0]

This reduces the precision of the result. For details, see:
https://trac.torproject.org/projects/tor/ticket/23061#comment:32

Instead, the function could take a random boolean sign and p, and the transform becomes:

result = mu - b * (sign ? 1.0 : -1.0)
                * tor_mathlog(1.0 - p);

This would increase the precision by one bit, plus whatever precision is lost in 2.0 * fabs(p - 0.5).

This may have been introduced in dad5eb7.

Child Tickets

Change History (21)

comment:1 Changed 12 months ago by teor

Description: modified (diff)
Status: newneeds_review

comment:2 Changed 12 months ago by nickm

Should this be in needs_review? I see a suggestion for writing a patch, but I don't see the actual patch itself.

comment:3 Changed 12 months ago by catalyst

Wouldn't it be better to have a function that outputs a random double in (-1.0, +1.0)? If you're only using 53 bits of entropy from a RNG call that generates 64, there are spare bits to use for generating the sign.

comment:4 in reply to:  3 Changed 12 months ago by teor

Status: needs_reviewneeds_revision

Replying to catalyst:

Wouldn't it be better to have a function that outputs a random double in (-1.0, +1.0)? If you're only using 53 bits of entropy from a RNG call that generates 64, there are spare bits to use for generating the sign.

sample_laplace_distribution() takes the log of a strictly positive floating point number, and then applies a random sign.

We could use sgn() and abs() to decompose [-1.0, 1.0] into {+, -} and [0.0, 1.0], but we'd still have to reject 0.0 before doing the log, and then apply the sign. So it seems more complex than the alternative.

comment:5 Changed 12 months ago by catalyst

I meant that the new function would exclude -1.0 and +1.0, so 1 - fabs(x) would still be nonzero.

comment:6 Changed 12 months ago by teor

That works, too: it costs us another random double function, but saves us an argument, and some complexity in the callers. Want to write the patch, or should I?

comment:7 Changed 12 months ago by yawning

Produces random values in the range (-1.0, 1.0), with similar semantics to my other routine. Timing characteristics depend on how copysign() is implemented, though I expect most libms to use bit twiddling of some sort.

double
uint64_to_dbl_neg1_1(uint64_t x) {
#if DBL_MANT_DIG > 63
#error System double mantissa is unexpectedly large.
#endif
  return copysign(uint64_to_dbl_0_1(x), 0.0 - (x >> 63));
}

Edit: The routine can produce both 0.0 and -0.0, which is probably not what you want. If that's a problem the caller should re-sample entropy on either 0 or 1 << 63 depending on which zero you want it to return.

Last edited 12 months ago by yawning (previous) (diff)

comment:8 Changed 11 months ago by teor

Owner: set to teor
Status: needs_revisionassigned

I'll do these in 0.3.2, some of them are security-low.

comment:9 Changed 11 months ago by teor

Milestone: Tor: 0.3.2.x-finalTor: 0.3.3.x-final

This can wait until 0.3.3

comment:10 Changed 10 months ago by nickm

Sponsor: SponsorQ-can

comment:11 Changed 9 months ago by teor

We should revise or close these tickets based on Appendix C in the latest privcount-shamir spec:

https://github.com/teor2345/privcount_shamir/blob/noise-limits/doc/xxx-privcount-with-shamir.txt

The good news is that we probably don't need to care about extreme values or binning, because properly implemented noise has known limits, and doesn't need binning.

comment:12 Changed 8 months ago by teor

0.2.8 is EOL, so we won't be backporting to it.

comment:13 Changed 8 months ago by teor

Keywords: 028-backport-maybe removed

0.2.8 is EOL, so we won't be backporting to it.

comment:14 Changed 7 months ago by teor

Milestone: Tor: 0.3.3.x-finalTor: 0.3.4.x-final

Moving most of my assigned tickets to 0.3.4

comment:15 Changed 7 months ago by nickm

Keywords: 030-backport removed

Remove 030-backport from all open tickets that have it: 0.3.0 is now deprecated.

comment:16 Changed 7 months ago by nickm

Remove 026-backport from all open tickets that have it: 0.2.6 has been deprecated for some while.

comment:17 Changed 6 months ago by teor

Parent ID: #23061#25263

comment:18 Changed 5 months ago by nickm

Keywords: 034-triage-20180328 added

comment:19 Changed 5 months ago by nickm

Keywords: 034-removed-20180328 added

Per our triage process, these tickets are pending removal from 0.3.4.

comment:20 Changed 4 months ago by nickm

Milestone: Tor: 0.3.4.x-finalTor: unspecified

These tickets, tagged with 034-removed-*, are no longer in-scope for 0.3.4. We can reconsider any of them, if time permits.

comment:21 Changed 7 weeks ago by teor

Keywords: 031-unreached-backport added; 031-backport removed

0.3.1 is end of life, there are no more backports.
Tagging with 031-unreached-backport instead.

Note: See TracTickets for help on using tickets.