Re: [tor-bugs] #33712 [Core Tor/Tor]: Design a PoW/credential scheme for HS DoS defence

[Tor Bug Tracker & Wiki]

#33712: Design a PoW/credential scheme for HS DoS defence
-+-
 Reporter:  asn  |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor:
 |  unspecified
Component:  Core Tor/Tor |Version:
 Severity:  Normal   | Resolution:
 Keywords:  tor-hs, tor-dos, network-team-   |  Actual Points:
  roadmap-2020Q2, network-health, research   |
Parent ID:  #31223   | Points:  96
 Reviewer:   |Sponsor:
-+-

Comment (by asn):

 First iteration of proposal: https://lists.torproject.org/pipermail/tor-
 dev/2020-April/014215.html

--
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] #33712 [Core Tor/Tor]: Design a PoW/credential scheme for HS DoS defence

[Tor Bug Tracker & Wiki]

#33712: Design a PoW/credential scheme for HS DoS defence
-+-
 Reporter:  asn  |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor:
 |  unspecified
Component:  Core Tor/Tor |Version:
 Severity:  Normal   | Resolution:
 Keywords:  tor-hs, tor-dos, network-team-   |  Actual Points:
  roadmap-2020Q2, network-health, research   |
Parent ID:  #31223   | Points:  96
 Reviewer:   |Sponsor:
-+-
Changes (by gaba):

 * points:   => 96


--
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] #33712 [Core Tor/Tor]: Design a PoW/credential scheme for HS DoS defence

[Tor Bug Tracker & Wiki]

#33712: Design a PoW/credential scheme for HS DoS defence
-+-
 Reporter:  asn  |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor:
 |  unspecified
Component:  Core Tor/Tor |Version:
 Severity:  Normal   | Resolution:
 Keywords:  tor-hs, tor-dos, network-team-   |  Actual Points:
  roadmap-2020Q2, network-health, research   |
Parent ID:  #31223   | Points:
 Reviewer:   |Sponsor:
-+-
Changes (by gaba):

 * keywords:  tor-hs, tor-dos, network-team-roadmap-2020Q1, network-health,
 research => tor-hs, tor-dos, network-team-roadmap-2020Q2, network-
 health, research


--
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] #33712 [Core Tor/Tor]: Design a PoW/credential scheme for HS DoS defence

[Tor Bug Tracker & Wiki]

#33712: Design a PoW/credential scheme for HS DoS defence
-+-
 Reporter:  asn  |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor:
 |  unspecified
Component:  Core Tor/Tor |Version:
 Severity:  Normal   | Resolution:
 Keywords:  tor-hs, tor-dos, network-team-   |  Actual Points:
  roadmap-2020Q1, network-health, research   |
Parent ID:  #31223   | Points:
 Reviewer:   |Sponsor:
-+-

Comment (by arma):

 I think I arrive at the same conclusions as Mike, but for different
 reasons.

 To me, the reason to focus on the "client to service" defense is that I
 believe whatever design we pick is going to need to have a "client to
 service" component, i.e. I don't think we can solve this problem solely
 with a "client to intro point" component. So if we need client-to-service,
 let's try to construct a system where that is sufficient.

 I'm not much worried about time-to-upgrade. Let's think about the eventual
 result we want, and then get ourselves there. A few months for upgrades
 will pass before we know it, and if we have an important update that needs
 more relays to upgrade, we can ask them to do it.

 Or, to rephrase: I currently think that client-to-service is the right
 area to focus on, because we're going to need it for the eventual
 solution, not because we have to constrain ourselves to solutions we can
 deploy this week. If we have a solution we like that involves parts of the
 network upgrading, let's be sure to keep it on the table so we don't
 accidentally rule out our best future just because it would be more
 logistics work to get there.

--
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] #33712 [Core Tor/Tor]: Design a PoW/credential scheme for HS DoS defence

[Tor Bug Tracker & Wiki]

#33712: Design a PoW/credential scheme for HS DoS defence
-+-
 Reporter:  asn  |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor:
 |  unspecified
Component:  Core Tor/Tor |Version:
 Severity:  Normal   | Resolution:
 Keywords:  tor-hs, tor-dos, network-team-   |  Actual Points:
  roadmap-2020Q1, network-health, research   |
Parent ID:  #31223   | Points:
 Reviewer:   |Sponsor:
-+-

Comment (by mikeperry):

 TL;DR of above is that there are multiple classes of protocol changes, and
 I think we should decide our high-level preference for what order we want
 to attempt them.

 Here's a strawman ordering of the combination of (degree of network
 upgrade required, external infra required) pairs:

 1. No network upgrade required; no external infra deployment (ie: client
 and service only)
 2. Backportable network upgrade required; no external infra deployment.
 3. No network upgrade required; external infra deployment **is required**.
 4. Backportable network upgrade required, external infra deployment **is
 required**.
 5. Non-backportable IP upgrade required; no external infra deployment.
 6. Non-backportable IP upgrade required; external infra deployment **is
 required**
 7. Non-backportable **full network upgrade**; no external infra
 deployment.
 8. Non-backportable **full network upgrade**; external infra deployment
 **is required**

 Important questions to answer:
 * Does this ordering sound right in terms of what we should prefer/attempt
 to build first?
 * Does anyone want to propose a different ordering?
 * What sorts of changes are backportable for this problem?

--
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] #33712 [Core Tor/Tor]: Design a PoW/credential scheme for HS DoS defence

[Tor Bug Tracker & Wiki]

#33712: Design a PoW/credential scheme for HS DoS defence
-+-
 Reporter:  asn  |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor:
 |  unspecified
Component:  Core Tor/Tor |Version:
 Severity:  Normal   | Resolution:
 Keywords:  tor-hs, tor-dos, network-team-   |  Actual Points:
  roadmap-2020Q1, network-health, research   |
Parent ID:  #31223   | Points:
 Reviewer:   |Sponsor:
-+-

Comment (by mikeperry):

 Replying to [comment:2 asn]:
 > The strawman proposal of a basic PoW-over-INTRO scheme is:
 >
 > 1) Client sends INTRO1 with a special PoW extension
 > 2) Intro sends back INTRO_CHALLENGE to client with a nonce
 > 3) Client crafts PoW with that nonce and sends it back to client
 > 4) Intro validates PoW difficulty and either forwards intro to service
 or rejects.
 >
 > This can come with various variants like the service encoding the nonce
 and parameters [https://lists.torproject.org/pipermail/tor-
 dev/2019-June/013882.html in the descriptor] in an attempt to cut the
 challenge round trip (with extra complexity coming from replay detection
 etc.), or with clients doing PoW bidding (or "staking") as proposed in the
 recent call.

 The above protocol sketch requires that the service only choose
 intropoints that have upgraded to fully support the protocol. This is
 risky, and still will require requires at least several months to deploy.
 Possibly much longer, if we are nervous about only a few IPs being
 available for use at a time by services under attack.

 I think it is most important that we separate our protocols by how much
 network upgrade (and/or external infra) is required before they can be
 used.

 To this end, here are some variants that we should keep in mind that
 require no network upgrades, or less extensive ones.

 Service-as-validator (requires no IP upgrades):

 0. Descriptor lists a challenge input seed, updated every X minutes or
 every Y intros
 1. Client generates its own GUID challenge to combine with descriptor seed
 2. Client sends INTRO1 with PoW extension in **encrypted extension
 section**, in 253 bytes
 3. Service verifies client's GUID is unique since its last descriptor seed
 update
 4. Service itself verifies PoW (which is supposed to be fast)
 5. Service then builds rend if PoW passes (and drops otherwise)

 Now, at 253 bytes, we lose most or all memory hardness guarantees of the
 PoW, but it can still be computationally expensive and possibly also GPU-
 resistant.

 One minor variant that also requires no network upgrades is to use an
 external credential server that accepts a full memory-hard 11KB Itsuku PoW
 and gives out smaller privacy pass credentials that can be sent directly
 to service in the encrypted extension, which verifies the privacy pass
 credential. This also requires no network upgrades, but the external
 credential server must be built and deployed, and will be subject to DoS
 attack too.

 If we expand scope slightly to allow intropoint upgrades that are minimal
 enough to backport to all releases, we can remove the "1 intro1 cell per
 circuit" limit at the intropoint if rate limits are requested by the
 service (this is roughly a 3 line diff). Then, schemes like the following
 become possible:

 0. Descriptor lists a challenge input seed, updated every X minutes or
 every Y intros
 1. Client generates its own GUID challenge to combine with descriptor seed
 2. Client sends INTRO1 with "multi-cell" extension in **encrypted
 extension section**
 3. Client sends Itsuku proof (<11KB, since we don't need that much) over
 subsequent cells
 4. Service combines these chained INTROs to reassemble PoW
 5. Service verifies client's GUID is unique since its last descriptor seed
 update
 6. Service itself verifies PoW (which is supposed to be fast)
 7. Service then builds rend if PoW passes (and drops otherwise)

 Because the change to allow protocols like this is small, hopefully we can
 backport it and deploy it to the network much, much faster than a full
 release cycle. If we can't do that, we should rule out this class of
 protocol.

--
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] #33712 [Core Tor/Tor]: Design a PoW/credential scheme for HS DoS defence

[Tor Bug Tracker & Wiki]

#33712: Design a PoW/credential scheme for HS DoS defence
-+-
 Reporter:  asn  |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor:
 |  unspecified
Component:  Core Tor/Tor |Version:
 Severity:  Normal   | Resolution:
 Keywords:  tor-hs, tor-dos, network-team-   |  Actual Points:
  roadmap-2020Q1, network-health, research   |
Parent ID:  #31223   | Points:
 Reviewer:   |Sponsor:
-+-

Comment (by asn):

 The strawman proposal of a basic PoW-over-INTRO scheme is:

 1) Client sends INTRO1 with a special PoW extension
 2) Intro sends back INTRO_CHALLENGE to client with a nonce
 3) Client crafts PoW with that nonce and sends it back to client
 4) Intro validates PoW difficulty and either forwards intro to service or
 rejects.

 This can come with various variants like the service encoding the nonce
 and parameters [https://lists.torproject.org/pipermail/tor-
 dev/2019-June/013882.html in the descriptor] in an attempt to cut the
 challenge round trip (with extra complexity coming from replay detection
 etc.), or with clients doing PoW bidding (or "staking") as proposed in the
 recent call.

 

 I wanted to mention this strawman proposal as a basic building block after
 reading that mtp-argon2 type of protocols require way too much space for
 proving. I was wondering if the above strawman approach but using argon2
 as the hash function for memory-hardness would work for us, but then I
 understood that the space requirement is caused by using a merkle tree as
 part of enforcing the memory-hardness; as in that argon2 itself is not
 sufficient to enforce full memory-hardness.

 So how do we go from a simple PoW scheme like the above, to something that
 works for us? Is it just the memory-hardness that we are losing by using
 the strawman approach over a more hardcore mtp-argon2 approach?

--
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] #33712 [Core Tor/Tor]: Design a PoW/credential scheme for HS DoS defence

[Tor Bug Tracker & Wiki]

#33712: Design a PoW/credential scheme for HS DoS defence
-+-
 Reporter:  asn  |  Owner:  (none)
 Type:  defect   | Status:  new
 Priority:  Medium   |  Milestone:  Tor:
 |  unspecified
Component:  Core Tor/Tor |Version:
 Severity:  Normal   | Resolution:
 Keywords:  tor-hs, tor-dos, network-team-   |  Actual Points:
  roadmap-2020Q1, network-health, research   |
Parent ID:  #31223   | Points:
 Reviewer:   |Sponsor:
-+-
Description changed by asn:

Old description:

> Some initial research has been done on #31223 to sketch out a
> PoW/credential scheme that works for HS DoS defence.
>
> This ticket is to continue scheming and working on this design.
>
> Also see #33650 for an analysis on whether we can use v3 descriptors and
> INTRO cells as an end-to-end channel for passing parameters and tokens.
>
> Also see [https://lists.torproject.org/pipermail/tor-
> dev/2020-March/014198.html this thread] for an initial exploration of
> anon credential schemes.

New description:

 Some initial research has been done on comment:13:ticket:31223 to sketch
 out a PoW/credential scheme that works for HS DoS defence.

 This ticket is to continue scheming and working on this design.

 Also see #33650 for an analysis on whether we can use v3 descriptors and
 INTRO cells as an end-to-end channel for passing parameters and tokens.

 Also see [https://lists.torproject.org/pipermail/tor-
 dev/2020-March/014198.html this thread] for an initial exploration of anon
 credential schemes.

--

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