Hello, this is my view of things, please be gentle as this is my first proposal draft :)

_ADAPTIVE POW PROPOSAL:_

Client sends the INTRODUCE1 as normal.

Introduction Point checks the Current Requests Rate and checks the DoS settings.

-DoS check is OK: send INTRODUCE2 to Hidden Service etc...

-DoS settings/rate limit reached: then

1.Introduction Point generates a random 8 bytes key (IPKey) and associates it with the client circuit. Then send INTRODUCE_POW to the Client with the IPKey.     2.Client computes POW.     Do{ Generates random 8 bytes key (ClientKey). Generates hash(sha512/256 or sha3??) of hash(IPKey + ClientKey) } while (hash does not start with "abcde")

3. Client sends INTRODUCE_POWR to the I.P. with the generated POW and the ClientKey.     4. I.P. checks the POW:

-POW is correct: send INTRODUCE2 to HS.         -POW is not correct: send INTRODUCE_POW_ERROR to client with new IPKey.

*I say 8 bytes for the Keys just for example.

PROS AND CONS, who needs to update Tor version?: --------------

Only rate limit: Introduction Point and Hidden Service. No breakage.

POW: Client, Introduction Point and Hidden Service. POW will break compatibility with other v3 Hidden Services clients, if we implement a way to bypass POW for old clients then this feature won't work as intended.

A forgotten guy here: Authenticated Rends cell: where we make sure the Client established a connection to the Rend Point before requesting the INTRODUCE1.

On 12/6/19 14:39, George Kadianakis wrote:

David Goulet dgoulet@torproject.org writes:

...

Filename: 305-establish-intro-dos-defense-extention.txt Title: ESTABLISH_INTRO Cell DoS Defense Extension Author: David Goulet, George Kadianakis Created: 06-June-2019 Status: Draft

Thanks for this proposal, it's most excellent and an essential building block for future work on intro point related defences.

...

We propose a new EXT_FIELD_TYPE value:

   [01] -- DOS_PARAMETERS.

           If this flag is set, the extension should be used by the
           introduction point to learn what values the denial of service
           subsystem should be using.

Perhaps we can name it "rate-limiting parameters"? But no strong opinion.

...

The EXT_FIELD content format is:

   N_PARAMS    [1 byte]
   N_PARAMS times:
      PARAM_TYPE  [1 byte]
      PARAM_VALUE [8 byte]

The PARAM_TYPE proposed values are:

   [01] -- DOS_INTRODUCE2_RATE_PER_SEC
           The rate per second of INTRODUCE2 cell relayed to the service.

   [02] -- DOS_INTRODUCE2_BURST_PER_SEC
           The burst per second of INTRODUCE2 cell relayed to the service.

The PARAM_VALUE size is 8 bytes in order to accomodate 64bit values
(uint64_t). It MUST match the specified limit for the following PARAM_TYPE:

   [01] -- Min: 0, Max: INT_MAX
   [02] -- Min: 0, Max: INT_MAX

How would this new addition to the cell impact the size of the cell? How much free space do we have for additional features to this cell (e.g. to do the PoW stuff of the other thread)?

...

A value of 0 means the defense is disabled which has precedence over the
network wide consensus parameter.

In this case, if the rate per second is set to 0 (param 0x01) then the
burst value should be ignored. And vice-versa, if the burst value is 0,
then the rate value should be ignored. In other words, setting one single
parameter to 0 disables the INTRODUCE2 rate limiting defense.

I think it could be cool to add a discussion section where we introduce a new cell from the intro to the service which informs the service that rate limiting limits have been hit. So that there is a way for the service to get feedback that it's under attack or capped by limits. Otherwise, there is simply no way to learn it.

This can be a later feature fwiw.

...

3. Protocol Version

   We introduce a new protocol version in order for onion service that wants to specifically select introduction points supporting this new extension. But also, it should be used to know when to send this extension or not.

   The new version for the "HSIntro" protocol is:

   "5" -- support ESTABLISH_INTRO cell DoS parameters extension for onion
          service version 3 only.
   
   

4. Configuration Options

   We also propose new torrc options in order for the operator to control those values passed through the ESTABLISH_INTRO cell.

   "HiddenServiceEnableIntroDoSDefense 0|1"
   
      If this option is set to 1, the onion service will always send to the
      introduction point denial of service defense parameters regardless of
      what the consensus enables it or not. The value will be taken from
      the consensus and if not present, the default values will be used.
      (Default: 0)
   
   "HiddenServiceEnableIntroDoSRatePerSec N sec"
   
      Controls the introduce rate per second the introduction point should
      impose on the introduction circuit.
      (Default: 25, Min: 0, Max: 4294967295)
   
   "HiddenServiceEnableIntroDoSBurstPerSec N sec"
   
      Controls the introduce burst per second the introduction point should
      impose on the introduction circuit.
      (Default: 200, Min: 0, Max: 4294967295)
   
   

   They respectively control the parameter type 0x01 and 0x02 in the ESTABLISH_INTRO cell detailed in section 2.

   The default values of the rate and burst are taken from ongoing anti-DoS implementation work [1][2]. They aren't meant to be defined with this proposal.

5. Security Considerations

   Using this new extension leaks to the introduction point the service's tor version. This could in theory help any kind of de-anonymization attack on a service since at first it partitions it in a very small group of running tor.

   Furthermore, when the first tor version supporting this extension will be released, very few introduction points will be updated to that version. Which means that we could end up in a situation where many services want to use this feature and thus will only select a very small subset of relays supporting it overloading them but also making it an easier vector for an attacker that whishes to be the service introduction point.

Interesting idea.

I'm not that worried about the service leaking its version to the intro, but I am worried about all attacked services saturating the few upgraded intro points, so I agree that such a switch makes sense.

...

For the above reasons, we propose a new consensus parameters that will
provide a "go ahead" for all service out there to start using this
extension only if the introduction point supports it.

   "enable_establish_intro_dos_extension"

      If set to 1, this makes tor start using this new proposed extension
      if available by the introduction point (looking at the new protover).

This parameter should be switched on when a majority of relays have
upgraded to a tor version that supports this extension for which we believe
will also give enough time for most services to move to this new stable
version making the anonymity set much bigger.

We propose to add a torrc option to ignore this parameter and force tor to
select introduction points supporting this extension which will
effectively, in the beginning, toss away these security considerations.

We believe that there are services that do not care about anonymity on the
service side and thus could benefit from this feature right away if they
wish to use it.

References:

[1] https://lists.torproject.org/pipermail/tor-dev/2019-May/013837.html [2] https://trac.torproject.org/15516 _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

---

tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

George Kadianakis:

...

2.Client computes POW.     Do{ Generates random 8 bytes key (ClientKey). Generates hash(sha512/256 or sha3??) of hash(IPKey + ClientKey) } while (hash does not start with "abcde")

That looks like a naive PoW scheme. It would perhaps be preferable to try to find a GPU/ASIC-resistant or memory-hard PoW scheme here, to minimize the advantage of adversaries with GPUs etc.? Are there any good such schemes?

It may be worth looking at Argon2 [1] which is designed to maximize the cost of password cracking on ASICs based on memory-hard functions. A different approach is the input-dependent use of several different hash functions (cf. e.g. [2]).

[1] https://www.cryptolux.org/images/0/0d/Argon2.pdf [2] https://www.pascalcoin.org/storage/whitepapers/RandomHash_Whitepaper.pdf

Also services should definitely be able to configure the difficulty of the PoW, and IMO this should again happen through the descriptor.

yes

juanjo juanjo@avanix.es writes:

On 13/6/19 12:21, George Kadianakis wrote:

...

Is this a new cell? What's the format? Are these really keys or are they just nonces?

Yes sorry, they are nonces.

This was only a proposal for a proposal.

...

Is this a new cell? What's the format? Are these really keys or are they just nonces?

IMO we should not do this through a new cell because that increases the round-trip by one. Instead we should just embed the PoW parameters in the onion service descriptor and clients find them there.

Yes, this is a new cell triggered only when DoS limit is reached.

We can't embed it on the onion service descriptor because the attacker could precompute the PoW and make a dictionary attack. The IPKey (will be a nonce) should unique for each new connecting client that wants to send the INTRODUCE2.

What we want this way is increasing the cost of an attacker by many times vs only a little overhead to the I.P.

I see. So you were going for an interactive PoW protocol. I wonder what else we can get if we admit we want interactive. Can we get a CAPTCHA? What else?

Still, I think the above protocol can be optimized to not require an extra round trip (extra round trips are bad for the network and for the intro point): For example, in place of an IPKey nonce that the IP explicitly sends to the client, we could use some sort of unpredictable crypto object from the circuit setup (e.g. ntor) between the client and intro point.

...

That looks like a naive PoW scheme. It would perhaps be preferable to try to find a GPU/ASIC-resistant or memory-hard PoW scheme here, to minimize the advantage of adversaries with GPUs etc.? Are there any good such schemes?

Also services should definitely be able to configure the difficulty of the PoW, and IMO this should again happen through the descriptor.

That PoW scheme was just a simple example. We should find the right choice. Something hard to find but easy to check.

Yep. We should indeed find the right choice here. I have briefly tried and failed to find papers that compare PoW schemes in a useful way for this project.

As a rule, proof-of-work does not really deliver the security properties people envision. We’ve no really canonical anti-sibel criteria in this case, but maybe some mixed approach works:

First, introduction points have a default mode in which they rate limit new connections and impose some artificial latency. Second, an onion service can issue rerandomizable certificates, blind signature, or oblivious PRFs that provide faster and non-rate limited access through a specific introduction points.

Coconut would suffice for the rerandomizable certificates of course, but sounds like overkill.. and slow.

We should consider an oblivious PRF for this use case too:

It’s easy to make an oblivious PRF from the batched DLEQ proof implemented in https://github.com/w3f/schnorrkel/blob/master/src/vrf.rs I suppose Tor might adapt this to not use Ristretto, or maybe choose an Ed25519 to Ristretto map, but regardless the whole scheme is not too much more complex than a Schnorr signature.

We require the oblivious PRF secret key be known by both the introduction point for verification and the onion service for issuing. In this, we do not share the oblivious PRF key among different introduction points because introduction points cannot share a common double redemption database anyways.

I’m worried about different oblivious PRF keys being used to tag different users though. There are complex mechanisms to prevent this using curves created with Cocks-Pinch, but..

We could simply employ blind signatures however, which avoids sharing any secrets, and thus permits binding the key uniquely to the hidden service. As a rule, blind signatures require either slow cryptography like pairings or RSA, or else issuing takes several round trips and have weak soundness. I think weak soundness sounds workable here, although I’m no longer sure about all the issues with such scheme.

Best, Jeff

p.s. We’re hiring in security https://web3.bamboohr.com/jobs/view.php?id=38 and several research areas like cryptography https://web3.bamboohr.com/jobs/view.php?id=29

On Tue, Jun 18, 2019 at 6:29 PM Chelsea Holland Komlo me@chelseakomlo.com wrote:

There are a couple approaches to consider.

POW via hashing goes for a relatively simple to implement approach. However, this incurs a high cost for all clients, and also environmental damage, per previous email.

Another approach similar to the above (but more environmentally friendly) can be Proof of Storage (or proof of space), as in https://eprint.iacr.org/2013/796.pdf

With both of the above approaches, there will be a tradeoff to what the cost is to deter a would-be attacker, versus the cost to real but bandwidth/cpu limited clients, such as on mobile platforms.

More involved approaches include anonymous blacklists/whitelists, blinded tokens, etc. Previous work has been done in this space, here is one example: https://crysp.uwaterloo.ca/courses/pet/F11/cache/www-users.cs.umn.edu/~hoppe...

Privacy Pass has already been integrated into Tor Browser. Perhaps work could be done to use it here?

While designs using a token-based approach such as what Jeff mentions below may require more design/thought up front, the benefit is that clients won't be penalized every time they connect to an onion service. Considering the goal of scaling of the Tor network and of "onions everywhere", this seems like a good tradeoff.

On 2019-06-16 18:03, Jeff Burdges wrote:

...

As a rule, proof-of-work does not really deliver the security properties people envision. We’ve no really canonical anti-sibel criteria in this case, but maybe some mixed approach works:

First, introduction points have a default mode in which they rate limit new connections and impose some artificial latency. Second, an onion service can issue rerandomizable certificates, blind signature, or oblivious PRFs that provide faster and non-rate limited access through a specific introduction points.

Coconut would suffice for the rerandomizable certificates of course, but sounds like overkill.. and slow.

We should consider an oblivious PRF for this use case too:

It’s easy to make an oblivious PRF from the batched DLEQ proof implemented in https://github.com/w3f/schnorrkel/blob/master/src/vrf.rs I suppose Tor might adapt this to not use Ristretto, or maybe choose an Ed25519 to Ristretto map, but regardless the whole scheme is not too much more complex than a Schnorr signature.

We require the oblivious PRF secret key be known by both the introduction point for verification and the onion service for issuing. In this, we do not share the oblivious PRF key among different introduction points because introduction points cannot share a common double redemption database anyways.

I’m worried about different oblivious PRF keys being used to tag different users though. There are complex mechanisms to prevent this using curves created with Cocks-Pinch, but..

We could simply employ blind signatures however, which avoids sharing any secrets, and thus permits binding the key uniquely to the hidden service. As a rule, blind signatures require either slow cryptography like pairings or RSA, or else issuing takes several round trips and have weak soundness. I think weak soundness sounds workable here, although I’m no longer sure about all the issues with such scheme.

Best, Jeff

p.s. We’re hiring in security https://web3.bamboohr.com/jobs/view.php?id=38 and several research areas like cryptography https://web3.bamboohr.com/jobs/view.php?id=29

---

tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

---

tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

On 2019-06-20 00:19, Watson Ladd wrote:

On Tue, Jun 18, 2019 at 6:29 PM Chelsea Holland Komlo me@chelseakomlo.com wrote:

...

There are a couple approaches to consider.

POW via hashing goes for a relatively simple to implement approach. However, this incurs a high cost for all clients, and also environmental damage, per previous email.

Another approach similar to the above (but more environmentally friendly) can be Proof of Storage (or proof of space), as in https://eprint.iacr.org/2013/796.pdf

With both of the above approaches, there will be a tradeoff to what the cost is to deter a would-be attacker, versus the cost to real but bandwidth/cpu limited clients, such as on mobile platforms.

More involved approaches include anonymous blacklists/whitelists, blinded tokens, etc. Previous work has been done in this space, here is one example: https://crysp.uwaterloo.ca/courses/pet/F11/cache/www-users.cs.umn.edu/~hoppe...

Privacy Pass has already been integrated into Tor Browser. Perhaps work could be done to use it here?

An approach akin to Privacy Pass could be an option to avoid serving challenges to clients with each request (see reference to anonymous tokens above), but it cannot be a drop in fix, of course. Furthermore, an acceptable POW or POS scheme still needs to be selected, the tradeoffs of which we are currently discussing.

Better understanding the requirements of the system from George and David will help define which approach is acceptable given the tradeoffs. For example, I imagine accessing onion services should not be restricted to clients from a web browser.

On 2019-06-20 00:19, Watson Ladd wrote:

...

Privacy Pass has already been integrated into Tor Browser. Perhaps work could be done to use it here?

As I said above, any oblivious PRF scheme like privacy pass violates privacy *if* you can supply different keys to different users. We cannot derive the OPRF key from the HS key, so this requires some messy solution like certificate transparency or more likely zero-knowlege proofs.

Actually there is a method to use oblivious PRFs without sharing secrets, which then makes the HS key itself usable: Just check the oblivious PRF token at the HS itself, not at the introducer. If the token checks out then the HS responds quickly, but if not then it responds after some delay. Introducers do nothing different in this design, but introduce cells can contain more data.

If otoh you use blind signatures then the blind signing key can be derived from the HS key, which avoids this complexity. We’ve new complexity in that blind signatures using an Edwards curve really suck, but we should be fine so long as only the soundness is weak, not the blindness. I have not refreshed my memory on this point yet.

There is a tricky one-more-forgery attack on Schnorr blind signatures, but not afaik any key recovery attack: https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf

As a defence, one could do blind signatures in G^3 requiring three scalar multiplications per signature from both signer and client, but limiting the forgery count to 1 per 63 signatures, which sounds acceptable. https://www.math.uni-frankfurt.de/~dmst/teaching/SS2012/Vorlesung/EBS5.pdf

We’d need to work out if using some key derived from the HS key works however because we must avoid creating a signing oracle for HS keys too.

So.. Do you want the filter at the introducer or at the HS itself?

Jeff

Hi,

On 12 Jun 2019, at 22:39, George Kadianakis desnacked@riseup.net wrote:

David Goulet dgoulet@torproject.org writes:

...

Filename: 305-establish-intro-dos-defense-extention.txt Title: ESTABLISH_INTRO Cell DoS Defense Extension Author: David Goulet, George Kadianakis Created: 06-June-2019 Status: Draft

Thanks for this proposal, it's most excellent and an essential building block for future work on intro point related defences.

+1

...

We propose a new EXT_FIELD_TYPE value:

 [01] -- DOS_PARAMETERS.

         If this flag is set, the extension should be used by the
         introduction point to learn what values the denial of service
         subsystem should be using.

Perhaps we can name it "rate-limiting parameters"? But no strong opinion.

...

The EXT_FIELD content format is:

 N_PARAMS    [1 byte]
 N_PARAMS times:
    PARAM_TYPE  [1 byte]
    PARAM_VALUE [8 byte]

The PARAM_TYPE proposed values are:

 [01] -- DOS_INTRODUCE2_RATE_PER_SEC
         The rate per second of INTRODUCE2 cell relayed to the service.

 [02] -- DOS_INTRODUCE2_BURST_PER_SEC
         The burst per second of INTRODUCE2 cell relayed to the service.

The PARAM_VALUE size is 8 bytes in order to accomodate 64bit values (uint64_t). It MUST match the specified limit for the following PARAM_TYPE:

 [01] -- Min: 0, Max: INT_MAX
 [02] -- Min: 0, Max: INT_MAX

This is ambiguous: * the value is 8 bytes long * the length of the maximum is unspecified: is it 4 bytes, 8 bytes, signed, or unsigned? * the torrc default is unsigned 4 bytes: UINT32_MAX

How would this new addition to the cell impact the size of the cell? How much free space do we have for additional features to this cell (e.g. to do the PoW stuff of the other thread)?

...

A value of 0 means the defense is disabled which has precedence over the network wide consensus parameter.

Let's say "any value has precedence over the network wide consensus parameter". Otherwise it's unclear if 0 is a special value or not.

...

In this case, if the rate per second is set to 0 (param 0x01) then the burst value should be ignored. And vice-versa, if the burst value is 0, then the rate value should be ignored. In other words, setting one single parameter to 0 disables the INTRODUCE2 rate limiting defense.

What happens if burst is less than rate?

I think it could be cool to add a discussion section where we introduce a new cell from the intro to the service which informs the service that rate limiting limits have been hit. So that there is a way for the service to get feedback that it's under attack or capped by limits. Otherwise, there is simply no way to learn it.

This can be a later feature fwiw.

...

3. Protocol Version

We introduce a new protocol version in order for onion service that wants to specifically select introduction points supporting this new extension. But also, it should be used to know when to send this extension or not.

The new version for the "HSIntro" protocol is:

 "5" -- support ESTABLISH_INTRO cell DoS parameters extension for onion
        service version 3 only.

4. Configuration Options

We also propose new torrc options in order for the operator to control those values passed through the ESTABLISH_INTRO cell.

 "HiddenServiceEnableIntroDoSDefense 0|1"

    If this option is set to 1, the onion service will always send to the
    introduction point denial of service defense parameters

if the intro point protocol supports them

...

regardless of what the consensus enables it or not. The value will be taken from

* values will be taken from

the HiddenServiceEnableIntroDoSRatePerSec and HiddenServiceEnableIntroDoSBurstPerSec torrc options, then

...

    the consensus and if not present, the default values will be used.
    (Default: 0)

 "HiddenServiceEnableIntroDoSRatePerSec N sec"

    Controls the introduce rate per second the introduction point should
    impose on the introduction circuit.
    (Default: 25, Min: 0, Max: 4294967295)

Doesn't the default come from the consensus, and then the hard-coded default?

Also see my notes about ambiguous size/signed maximums above.

...

 "HiddenServiceEnableIntroDoSBurstPerSec N sec"

    Controls the introduce burst per second the introduction point should
    impose on the introduction circuit.
    (Default: 200, Min: 0, Max: 4294967295)

Doesn't the default come from the consensus, and then the hard-coded default?

Also see my notes about ambiguous size/signed maximums above.

...

They respectively control the parameter type 0x01 and 0x02 in the ESTABLISH_INTRO cell detailed in section 2.

The default values of the rate and burst are taken from ongoing anti-DoS implementation work [1][2]. They aren't meant to be defined with this proposal.

5. Security Considerations

Using this new extension leaks to the introduction point the service's tor version. This could in theory help any kind of de-anonymization attack on a service since at first it partitions it in a very small group of running tor.

Furthermore, when the first tor version supporting this extension will be released, very few introduction points will be updated to that version. Which means that we could end up in a situation where many services want to use this feature and thus will only select a very small subset of relays supporting it overloading them but also making it an easier vector for an attacker that whishes to be the service introduction point.

Interesting idea.

I'm not that worried about the service leaking its version to the intro, but I am worried about all attacked services saturating the few upgraded intro points, so I agree that such a switch makes sense.

...

For the above reasons, we propose a new consensus parameters that will

* parameter

...

provide a "go ahead" for all service out there to start using this extension only if the introduction point supports it.

 "enable_establish_intro_dos_extension"

Can we just call it HiddenServiceEnableIntroDoSDefense?

It's weird naming some DoS consensus parameters in snake_case, and others in CamelCase. And it's also weird having different names for torrc options and consensus parameters.

...

    If set to 1, this makes tor start using this new proposed extension
    if available by the introduction point (looking at the new protover).

This parameter should be switched on when a majority of relays have upgraded to a tor version that supports this extension for which we believe will also give enough time for most services to move to this new stable version making the anonymity set much bigger.

We propose to add a torrc option

HiddenServiceEnableIntroDoSDefense?

...

to ignore this parameter and force tor to select introduction points supporting this extension which will effectively, in the beginning, toss away these security considerations.

We believe that there are services that do not care about anonymity on the service side and thus could benefit from this feature right away if they wish to use it.

I think we also need consensus parameters for HiddenServiceEnableIntroDoSRatePerSec and HiddenServiceEnableIntroDoSBurstPerSec.

...

References:

[1] https://lists.torproject.org/pipermail/tor-dev/2019-May/013837.html [2] https://trac.torproject.org/15516 _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

---

tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

On 12 Jun (15:39:55), George Kadianakis wrote:

David Goulet dgoulet@torproject.org writes:

...

Filename: 305-establish-intro-dos-defense-extention.txt Title: ESTABLISH_INTRO Cell DoS Defense Extension Author: David Goulet, George Kadianakis Created: 06-June-2019 Status: Draft

Thanks for this proposal, it's most excellent and an essential building block for future work on intro point related defences.

...

We propose a new EXT_FIELD_TYPE value:

  [01] -- DOS_PARAMETERS.

          If this flag is set, the extension should be used by the
          introduction point to learn what values the denial of service
          subsystem should be using.

Perhaps we can name it "rate-limiting parameters"? But no strong opinion.

I went more generic in order to support future "DoS" parameters which might not be rate-limiting specific.

I personally prefer that instead of later creating a "[02] -- <NEW_DOS_NAME>_PARAMETERS".

...

The EXT_FIELD content format is:

  N_PARAMS    [1 byte]
  N_PARAMS times:
     PARAM_TYPE  [1 byte]
     PARAM_VALUE [8 byte]

The PARAM_TYPE proposed values are:

  [01] -- DOS_INTRODUCE2_RATE_PER_SEC
          The rate per second of INTRODUCE2 cell relayed to the service.

  [02] -- DOS_INTRODUCE2_BURST_PER_SEC
          The burst per second of INTRODUCE2 cell relayed to the service.

The PARAM_VALUE size is 8 bytes in order to accomodate 64bit values (uint64_t). It MUST match the specified limit for the following PARAM_TYPE:

  [01] -- Min: 0, Max: INT_MAX
  [02] -- Min: 0, Max: INT_MAX

How would this new addition to the cell impact the size of the cell? How much free space do we have for additional features to this cell (e.g. to do the PoW stuff of the other thread)?

Good point. Added a section about this.

Short answer: We will be using an extra 21 bytes leaving 343 bytes unused.

...

A value of 0 means the defense is disabled which has precedence over the network wide consensus parameter.

In this case, if the rate per second is set to 0 (param 0x01) then the burst value should be ignored. And vice-versa, if the burst value is 0, then the rate value should be ignored. In other words, setting one single parameter to 0 disables the INTRODUCE2 rate limiting defense.

I think it could be cool to add a discussion section where we introduce a new cell from the intro to the service which informs the service that rate limiting limits have been hit. So that there is a way for the service to get feedback that it's under attack or capped by limits. Otherwise, there is simply no way to learn it.

This can be a later feature fwiw.

Yes indeed! Adding discussion section!

...

3. Protocol Version

   We introduce a new protocol version in order for onion service that wants to specifically select introduction points supporting this new extension. But also, it should be used to know when to send this extension or not.

   The new version for the "HSIntro" protocol is:

   "5" -- support ESTABLISH_INTRO cell DoS parameters extension for onion service version 3 only.

4. Configuration Options

   We also propose new torrc options in order for the operator to control those values passed through the ESTABLISH_INTRO cell.

   "HiddenServiceEnableIntroDoSDefense 0|1"

     If this option is set to 1, the onion service will always send to the
     introduction point denial of service defense parameters regardless of
     what the consensus enables it or not. The value will be taken from
     the consensus and if not present, the default values will be used.
     (Default: 0)
   
   

   "HiddenServiceEnableIntroDoSRatePerSec N sec"

     Controls the introduce rate per second the introduction point should
     impose on the introduction circuit.
     (Default: 25, Min: 0, Max: 4294967295)
   
   

   "HiddenServiceEnableIntroDoSBurstPerSec N sec"

     Controls the introduce burst per second the introduction point should
     impose on the introduction circuit.
     (Default: 200, Min: 0, Max: 4294967295)
   
   

   They respectively control the parameter type 0x01 and 0x02 in the ESTABLISH_INTRO cell detailed in section 2.

   The default values of the rate and burst are taken from ongoing anti-DoS implementation work [1][2]. They aren't meant to be defined with this proposal.

5. Security Considerations

   Using this new extension leaks to the introduction point the service's tor version. This could in theory help any kind of de-anonymization attack on a service since at first it partitions it in a very small group of running tor.

   Furthermore, when the first tor version supporting this extension will be released, very few introduction points will be updated to that version. Which means that we could end up in a situation where many services want to use this feature and thus will only select a very small subset of relays supporting it overloading them but also making it an easier vector for an attacker that whishes to be the service introduction point.

Interesting idea.

I'm not that worried about the service leaking its version to the intro, but I am worried about all attacked services saturating the few upgraded intro points, so I agree that such a switch makes sense.

Yup, service version leaking is not a big concern of mine either.

Thanks for feedback! I've pushed the above changes as a fixup commit!

Onto responding to teor! :)

Cheers! David