Re: [tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.4.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.6.2-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:  1.0
  031-backport, 029-backport |
Parent ID:  #25263   | Points:  0.5
 Reviewer:   |Sponsor:
 |  SponsorQ
-+-
Changes (by teor):

 * parent:  #23061 => #25263


--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.3.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.6.2-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:  1.0
  031-backport, 030-backport, 029-backport,  |
  028-backport   |
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
 |  SponsorQ
-+-
Changes (by teor):

 * milestone:  Tor: 0.3.2.x-final => Tor: 0.3.3.x-final


Comment:

 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@.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.6.2-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:  1.0
  031-backport, 030-backport, 029-backport,  |
  028-backport   |
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
 |  SponsorQ
-+-

Comment (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.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.6.2-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:  1.0
  031-backport, 030-backport, 029-backport,  |
  028-backport   |
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-

Comment (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.)

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.6.2-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:  1.0
  031-backport, 030-backport, 029-backport,  |
  028-backport   |
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-
Changes (by teor):

 * status:  needs_review => needs_revision


Comment:

 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.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  needs_review
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.6.2-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:  1.0
  031-backport, 030-backport, 029-backport,  |
  028-backport   |
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-
Changes (by teor):

 * status:  needs_revision => needs_review
 * actualpoints:   => 1.0


Comment:

 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

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.6.2-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport,  |
  028-backport   |
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-
Changes (by teor):

 * keywords:
 tor-relay, security-low, privcount, 031-backport, 030-backport,
 029-backport, 028-backport-maybe, 026-backport-maybe
 =>
 tor-relay, security-low, privcount, 031-backport, 030-backport,
 029-backport, 028-backport


Comment:

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

 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).

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  needs_revision
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.6.2-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-
Changes (by teor):

 * status:  needs_review => needs_revision


Comment:

 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.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

Re: [tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  teor
 Type:  defect   | Status:
 |  needs_review
 Priority:  Medium   |  Milestone:  Tor:
 |  0.3.2.x-final
Component:  Core Tor/Tor |Version:  Tor:
 |  0.2.6.2-alpha
 Severity:  Normal   | Resolution:
 Keywords:  tor-relay, security-low, privcount,  |  Actual Points:
  031-backport, 030-backport, 029-backport, 028  |
  -backport-maybe, 026-backport-maybe|
Parent ID:  #23061   | Points:  0.5
 Reviewer:   |Sponsor:
-+-
Changes (by teor):

 * status:  assigned => needs_review


Comment:

 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.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs

[tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-+-
 Reporter:  teor |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor: 0.3.2.x-final
Component:  Core |Version:  Tor: 0.2.6.2-alpha
  Tor/Tor|   Keywords:  tor-relay, security-low, privcount,
 Severity:  Normal   |  031-backport, 030-backport, 029-backport, 028
 |  -backport-maybe, 026-backport-maybe
Actual Points:   |  Parent ID:  #23061
   Points:  0.5  |   Reviewer:
  Sponsor:   |
-+-
 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.

--
Ticket URL: 
Tor Bug Tracker & Wiki 
The Tor Project: anonymity online
___
tor-bugs mailing list
tor-bugs@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs