Opened 16 months ago

Last modified 2 months ago

#23414 assigned defect

rep_hist_format_hs_stats() should add noise, then round

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

Description

In order to guarantee differential privacy, we need to:

  • sample at the scale of the noise (not unit scale)
  • add the noise to the signal
  • round the noisy signal

This is the "snapping" mitigation from "On Significance of the Least Significant Bits For Differential Privacy" by Ilya Mironov
https://pdfs.semanticscholar.org/2f2b/7a0d5000a31f7f0713a3d20919f9703c9876.pdf

rep_hist_format_hs_stats() rounds once to the bin size, then adds noise which has been rounded to the nearest integer. This isn't ideal, because it makes the least significant bits of the noise meaningless.

Instead, we should:

  • round the noise to integer precision
  • add the signal to the noise
  • round the noisy signal to the bin size

I think this was introduced in 14e83e6.

Child Tickets

TicketStatusOwnerSummaryComponent
#19130closednickmSeg fault in round_int64_to_next_multiple_of()Core Tor/Tor

Change History (20)

comment:1 Changed 15 months ago by teor

Owner: set to teor
Status: newassigned

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

comment:2 Changed 15 months ago by teor

Status: assignedneeds_review

See my branch bug23414 for a fix to this, and the additions to add_laplace_noise() that are required to make it safe. They're part of #23416, and there is no changes file for them yet.

comment:3 Changed 15 months ago by teor

Status: needs_reviewneeds_revision

This needs another fix: if we treat signal INT_MIN and INT_MAX as if they are infinite (saturating arithmetic), then the security guarantees are much easier to reason about. And the explanations are shorter, too :-)

Also, the code would be simpler, and the explanations shorter, if we added the noise when we reset the counter. I opened #23501 for this.

comment:4 Changed 15 months ago by teor

Keywords: 028-backport added; 028-backport-maybe 026-backport-maybe removed

I made a new branch at bug23414-v4, and split off some unrelated changes into #23523.

It needs a working round_int64_to_next_multiple_of(), which also needs to be backported to 0.2.8 and later. There is a possible fix in #19130 (which we closed by deleting the buggy function).

Edit: the related ticket is #23523

Last edited 15 months ago by teor (previous) (diff)

comment:5 Changed 15 months ago by teor

Actual Points: 1.0
Status: needs_revisionneeds_review

See my branches bug23414-029 and bug23414-028, which are security-low because the current code leaks the low bits of the noise. (And it biases the result upwards by an average of the bin size divided by 2, because it rounds first, then adds noise.)

bug23414-028 has the following changes:

  • the context is different due to #19130 going into 0.2.9 (but we replace the code from 0.2.8 and 0.2.9 with the same code)
  • there's no BUG macro in 0.2.8
  • the existing unit tests for round_int64_to_next_multiple_of() were based on the old implementation, which had the same upwards bias as the 0.2.9 implementation, due to the rounding function itself, rather than the order of operations

comment:6 Changed 15 months ago by teor

Status: needs_reviewneeds_revision

Oops, the original tests were right: the only thing worse than a consistent bias is one that is inconsistent (it changes when the noised signal is negative).

Good news is that round_int64_to_next_multiple_of() becomes a two-liner:

const uint64_t bias = (uint64_t)INT64_MAX + 1;
return round_uint64_to_next_multiple_of(number + bias, divisor) - bias;

Bad news is that it's my weekend, so it will be Monday before I get to this.

Edit: I bet there's also some adjustment based on bias % divisor. Which also means there's some chance of overflow. So it's not quite this easy.

Last edited 15 months ago by teor (previous) (diff)

comment:7 Changed 15 months ago by teor

I don't think I'll have time to fix round_int64_to_next_multiple_of until the end of the week. So if anyone else wants to do it, please feel free to grab this ticket. (Or split it off into its own ticket.)

comment:8 Changed 14 months ago by nickm

Sponsor: SponsorQ

comment:9 Changed 13 months ago by teor

We also need to implement a scaling/sensitivity mechanism to guarantee differential privacy. See https://trac.torproject.org/projects/tor/ticket/23523#comment:12 for details.

comment:10 Changed 13 months ago by teor

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

We're still working out the best way to do this in the PrivCount in Tor spec. Let's revisit this issue when that's been reviewed on tor-dev@.

comment:11 Changed 13 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 12 months ago by teor

Keywords: 028-backport removed

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

comment:13 Changed 11 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:14 Changed 10 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:15 Changed 10 months ago by teor

Parent ID: #23061#25263

comment:16 Changed 9 months ago by nickm

Keywords: 034-triage-20180328 added

comment:17 Changed 9 months ago by nickm

Keywords: 034-removed-20180328 added

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

comment:18 Changed 8 months ago by nickm

Milestone: Tor: 0.3.4.x-finalTor: unspecified

These needs_revision, tickets, tagged with 034-removed-*, are no longer in-scope for 0.3.4. We can reconsider any of them, if somebody does the necessary revision.

comment:19 Changed 6 months 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.

comment:20 Changed 2 months ago by teor

Owner: teor deleted
Status: needs_revisionassigned

We should fix these issues by migrating these statistics to PrivCount in Tor.
See #25263 and its parents for details.

Note: See TracTickets for help on using tickets.