Opened 8 months ago

Last modified 2 weeks ago

#23414 needs_revision defect

rep_hist_format_hs_stats() should add noise, then round

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


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

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

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

Change History (18)

comment:1 Changed 8 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 7 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 7 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 7 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 7 months ago by teor (previous) (diff)

comment:5 Changed 7 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 7 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 7 months ago by teor (previous) (diff)

comment:7 Changed 7 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 6 months ago by nickm

Sponsor: SponsorQ

comment:9 Changed 6 months ago by teor

We also need to implement a scaling/sensitivity mechanism to guarantee differential privacy. See for details.

comment:10 Changed 5 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 5 months ago by teor

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

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 4 months ago by teor

Keywords: 028-backport removed

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

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

Parent ID: #23061#25263

comment:16 Changed 4 weeks ago by nickm

Keywords: 034-triage-20180328 added

comment:17 Changed 4 weeks ago by nickm

Keywords: 034-removed-20180328 added

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

comment:18 Changed 2 weeks 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.

Note: See TracTickets for help on using tickets.