Re: [tor-dev] [RFC] Proposal: "Res tokens: Anonymous Credentials for Onion Service DoS Resilience"
George Kadianakis: > Hello all, > > after lots of investigation on anonymous credentials, we are glad to > present you with a draft of the onion services anti-DoS proposal using > tokens. Thanks! I finally managed to read through and think about the proposal (but note: I've not read proposal 327 yet, so I hope my remarks are not too silly were that proposal comes into play). I have some comments inline but did not tackle any XXX parts yet (and I'll provide a torspec branch later for fixing the typos I found). > While the basic idea of the proposal should remain reasonably solid, > there are various XXX sprinkled around the proposal and some of them > definitely need to be addressed before the proposal becomes truly > usable. > > We are particularly looking forward to feedback about: > - Token issuance services > - The anonymous credential scheme chosen > - The XXXs and design decisions of the proposal > > Hope you have a pleasant read! > > --- > > ``` [snip] > ## 3.3. Other security considerations > > Apart from the above properties we also want: > > - Double spending protection: We don't want Malory to be able to double > spend > her tokens in various onion services thereby amplifying her attack. For > this reason our tokens are not global, and can only be redeemed at a > specific destination onion service. > > - Metadata: We want to encode metadata/attributes in the tokens. In > particular, we want to encode the destination onion service and an > expiration date. For more information see section [DEST_DIGEST]. For > blind RSA tokens this is usually done using "partially blind signatures" > but to keep it simple we instead encode the destination directly in the > message to be blind-signed and the expiration date using a set of > rotating signing keys. > > - One-show: There are anonymous credential schemes with multi-show support > where one token can be used multiple times in an unlinkable > fashion. However, that might allow an adversary to use a single token to > launch a DoS attack, since revocation solutions are complex and > inefficient in anonymous credentials. For this reason, in this work we > use one-show tokens that can only be redeemed once. That takes care of > the revocation problem but it means that a client will have to get more > tokens periodically. While reading I had the feeling we have the one-show property because we want to (easily) prevent double-spending. Thus, can't we just fold that part into the "Double spending protection" one? As it stands I found it confusing/redundant. [snip] > ## 4.2. Onion service signals ongoing DoS attack Let me look at that from a slightly different angle. What about something like ## 4.2. Onion service signals DoS attack protection ? That is, would we be okay if onion services used the mechanism in this proposal for *preventing* DoS attacks(, too,) in the first place? Worst case would be every onion service has the anti-DoS security feature on 24/7 but there are other scenarios conceivable that point in a similar direction (e.g. anti-DoS protection only on on weekends or just at particular times). Looking at the proposal for answering my question I am not sure. It seems you indicate in section 6 that this would be strongly undesired at least in cases where manual work needs to be done: """ In the cases where manual work is needed by the user (e.g. solving a CAPTCHA) it's ideal if the work is presented to the user right before visiting the destination and *only* if it's *absolutely* required. [emphasis mine, GeKo] """ But there are other token issuers with different constraints conceivable (as you mention in the proposal itself). The reason why I bring this up is two-fold: 1. We had been thinking about that issue back then when we were evaluating Prviacy Pass for an inclusion into Tor Browser and as a solution to/against Cloudflare's CAPTCHAs. One of the biggest arguments against doing that was that we were afraid of enabling a mechanism that would boil down in the longer run to requiring a kind of "driver's license" (you need to solve a CAPTCHA first) to just reading news on the Internet anywhere. Even though that may come anyway at some point in the future we thought the Tor Project should not be at the forefront on that trend essentially pushing it with our "seal of acceptance". While I think that both contexts (the Privacy Pass - website and the Res token - onion service one) are sufficiently different that our concerns from back then do not apply 1:1, I do wonder how the story in the onion services one looks like... 2. Why would onion service providers even do such a thing as using the tokens outside of an ongoing DoS attack? Well, nobody wants to get hit by an attack in the first place if they can easily *prevent* it. Tokens would offer that (likely even for more attacks than just the intended DoS). In particular, the
Re: [tor-dev] [RFC] Proposal: "Res tokens: Anonymous Credentials for Onion Service DoS Resilience"
Nice work, George! In case folks are interested, I wrote up a very similar proposal independently: https://chris-wood.github.io/draft-wood-cfrg-blind-signatures/draft-wood-cfrg-rsa-blind-signatures.html Perhaps we should converge? :-) Best, Chris On Thu, Feb 11, 2021, at 3:36 PM, George Kadianakis wrote: > Hello all, > > after lots of investigation on anonymous credentials, we are glad to > present you with a draft of the onion services anti-DoS proposal using > tokens. > > While the basic idea of the proposal should remain reasonably solid, > there are various XXX sprinkled around the proposal and some of them > definitely need to be addressed before the proposal becomes truly > usable. > > We are particularly looking forward to feedback about: > - Token issuance services > - The anonymous credential scheme chosen > - The XXXs and design decisions of the proposal > > Hope you have a pleasant read! > > --- > > ``` > Filename: 331-res-tokens-for-anti-dos.md > Title: Res tokens: Anonymous Credentials for Onion Service DoS Resilience > Author: George Kadianakis, Mike Perry > Created: 11-02-2021 > Status: Draft > ``` > > +--+ +--+ > | Token Issuer | | Onion Service| > +--+ +--+ > ^^ > |+--+| > Issuance | 1.| | 2. | Redemption > +--->| Alice |<---+ > | | > +--+ > > > # 0. Introduction > > This proposal specifies a simple anonymous credential scheme based on Blind > RSA signatures designed to fight DoS abuse against onion services. We call > the scheme "Res tokens". > > Res tokens are issued by third-party issuance services, and are verified by > onion services during the introduction protocol (through the INTRODUCE1 > cell). > > While Res tokens are used for denial of service protection in this proposal, > we demonstrate how they can have application in other Tor areas as well, > like > improving the IP reputation of Tor exit nodes. > > # 1. Motivation > > Denial of service attacks against onion services have been explored > in the past > and various defenses have been proposed: > - Tor proposal #305 specifies network-level rate-limiting mechanisms. > - Onionbalance allows operators to scale their onions horizontally. > - Tor proposal #327 increases the attacker's computational > requirements (not implemented yet). > > While the above proposals in tandem should provide reasonable protection > against many DoS attackers, they fundamentally work by reducing the > assymetry > between the onion service and the attacker. This won't work if the attacker > is extremely powerful because the assymetry is already huge and cutting it > down does not help. > > we believe that a proposal based on cryptographic guarantees -- like Res > tokens -- can offer protection against even extremely strong attackers. > > # 2. Overview > > In this proposal we introduce an anonymous credential scheme -- Res tokens > -- > that is well fitted for protecting onion services against DoS attacks. We > also introduce a system where clients can acquire such anonymous credentials > from various types of Token Issuers and then redeem them at the onion > service > to gain access even when under DoS conditions. > > In section [TOKEN_DESIGN], we list our requirements from an anonymous > credential scheme and provide a high-level overview of how the Res token > scheme works. > > In section [PROTOCOL_SPEC], we specify the token issuance and > redemption protocols, > as well as the mathematical operations that need to be conducted for > these to work. > > In section [TOKEN_ISSUERS], we provide a few examples and guidelines for > various token issuer services that could exist. > > In section [DISCUSSION], we provide more use cases for Res tokens as well as > future improvements we can conduct to the scheme. > > # 3. Design [TOKEN_DESIGN] > > In this section we will go over the high-level design of the system, and on > the next section we will delve into the lower-level details of the protocol. > > ## 3.1. Anonymous credentials > > Anonymous credentials or tokens are cryptographic identifiers that allow > their bearer to maintain an identity while also preserving anonymity. > > Clients can acquire a token in a variety of ways (e.g. registering on a > third-party service, solving a CAPTCHA, completing a PoW puzzle) and then > redeem it at the onion service proving this way that work was done, but > without linking the act of token acquisition with the act of token > redemption. > > ## 3.2. Anonymous credential properties > > The
Re: [tor-dev] [RFC] Proposal: "Res tokens: Anonymous Credentials for Onion Service DoS Resilience"
On 2/11/21 7:42 PM, Nicholas Hopper wrote:
>
> Hi George!
Sp, fellow Chaum fan! I liked bnymble! It was the least scary of all
of the revocation schemes I've read. At least I could understand the
linkability properties.
Were you at the party when Chaum's patents expired? I forget. I suppose
there probably was more than one of those, too.
> A couple of thoughts about this proposal:
>
> On Thu, Feb 11, 2021 at 5:36 PM George Kadianakis
> wrote:> ## 4.1. Token issuer setup>
>> The Issuer creates a set of ephemeral RSA-1024 "issuance keys" that will be
>> used during the issuance protocol. Issuers will be rotating these ephemeral
>> keys every 6 hours.
>>
>> The Issuer exposes the set of active issuance public keys through a REST
>> HTTP
>> API that can be accessed by visiting /issuers.keys.
>>
>> Tor directory authorities periodically fetch the issuer's public keys and
>> vote for those keys in the consensus so that they are readily available by
>> clients. The keys in the current consensus are considered active, whereas
>> the
>> ones that have fallen off have expired.
>>
>> XXX how many issuance public keys are active each time? how does
>> overlapping
>> keys work? clients and onions need to know precise expiration date for
>> each key. this needs to be specified and tested for robustness.
>>
>> XXX every how often does the fetch work? how does the voting work? which
>> issuers are considered official? specify consensus method.
>>
>> XXX An alternative approach: Issuer has a long-term ed25519 certification
>> key
>> that creates expiring certificates for the ephemeral issuance keys.
>> Alice
>> shows the certificate to the service to prove that the token comes from
>> an issuer. The consensus includes the long-term certification key of
>> the
>> issuers to establish ground truth.
>> This way we avoid the synchronization between dirauths and issuers, and
>> the multiple overlapping active issuance keys. However, certificates
>> might not fit in the INTRODUCE1 cell (prop220 certs take 104 bytes on
>> their own). Also certificate metadata might create a vector for
>> linkability attacks between the issuer and the verifier.
>>
>> ## 4.2. Onion service signals ongoing DoS attack
>>
>> When an onion service is under DoS attack it adds the following line in the
>> "encrypted" (inner) part of the v3 descriptor as a way to signal to its
>> clients that tokens are required for gaining access:
>>
>> "token-required" SP token-type SP issuer-list NL
>>
>> [At most once]
>>
>> token-type: Is the type of token supported ("res" for this proposal)
>> issuer: A comma separated list of issuers which are supported by this
>> onion service
>>
>
> How are issuers identified? I ask because of a potential problem noted
> below...
We debated this and ultimately decided on a REST service that listed
issuer keys, that the dirauths fetch (See Section 4.1 above). We can pin
the TLS key(s) used to auth the request.
>> ### 4.3.1. Client preparation [DEST_DIGEST]
>>
>> Alice first chooses an issuer supported by the onion service depending on
>> her
>> preferences by looking at the consensus and her Tor configuration file for
>> the current list of active issuers.
>>
>> After picking a supported issuer, she performs the following preparation
>> before contacting the issuer:
>>
>> 1) Alice extracts the issuer's public key (N,e) from the consensus
>>
>> 2) Alice computes a destination digest as follows:
>>
>>dest_digest = FDH_N(destination || salt)
>>
>> where:
>> - 'destination' is the 32-byte ed25519 public identity key of
>> the destination onion
>> - 'salt' is a random 32-byte value,
>>
>> 3) Alice samples a blinding factor 'r' uniformly at random from [1, N)
>>
>> 4) Alice computes:
>>blinded_message = dest_digest * r^e (mod N)
>>
>> After this phase is completed, Alice has a blinded message that is tailored
>> specifically for the destination onion service. Alice will send the blinded
>> message to the Token Issuer, but because of the blinding the Issuer does
>> not
>> get to learn the dest_digest value.
>>
>> XXX Is the salt needed? Reevaluate.
>
> Yes, the salt is needed (or, *some* input besides the destination must
> go into the FDH) otherwise, all (unblinded) tokens signed by a given
> issuance key will be identical. This would be great for unlinkability
> but not so good for double-spend prevention. :)
Aha! George and I knew we needed to salt our Chaum burgers, but neither
of us could remember why. Such ancient lore. Much teriyaki.
See, this is why we need real cryptographers looking at this stuff!
>> We propose a new EXT_FIELD_TYPE value:
>>
>> [02] -- ANON_TOKEN
>>
>> The EXT_FIELD content format is:
>>
>>TOKEN_VERSION[1 byte]
>>ISSUER_KEY [4 bytes]
>>
Re: [tor-dev] [RFC] Proposal: "Res tokens: Anonymous Credentials for Onion Service DoS Resilience"
Hi George!
A couple of thoughts about this proposal:
On Thu, Feb 11, 2021 at 5:36 PM George Kadianakis
wrote:> ## 4.1. Token issuer setup>
> The Issuer creates a set of ephemeral RSA-1024 "issuance keys" that will be
> used during the issuance protocol. Issuers will be rotating these ephemeral
> keys every 6 hours.
>
> The Issuer exposes the set of active issuance public keys through a REST
> HTTP
> API that can be accessed by visiting /issuers.keys.
>
> Tor directory authorities periodically fetch the issuer's public keys and
> vote for those keys in the consensus so that they are readily available by
> clients. The keys in the current consensus are considered active, whereas
> the
> ones that have fallen off have expired.
>
> XXX how many issuance public keys are active each time? how does overlapping
> keys work? clients and onions need to know precise expiration date for
> each key. this needs to be specified and tested for robustness.
>
> XXX every how often does the fetch work? how does the voting work? which
> issuers are considered official? specify consensus method.
>
> XXX An alternative approach: Issuer has a long-term ed25519 certification
> key
> that creates expiring certificates for the ephemeral issuance keys.
> Alice
> shows the certificate to the service to prove that the token comes from
> an issuer. The consensus includes the long-term certification key of the
> issuers to establish ground truth.
> This way we avoid the synchronization between dirauths and issuers, and
> the multiple overlapping active issuance keys. However, certificates
> might not fit in the INTRODUCE1 cell (prop220 certs take 104 bytes on
> their own). Also certificate metadata might create a vector for
> linkability attacks between the issuer and the verifier.
>
> ## 4.2. Onion service signals ongoing DoS attack
>
> When an onion service is under DoS attack it adds the following line in the
> "encrypted" (inner) part of the v3 descriptor as a way to signal to its
> clients that tokens are required for gaining access:
>
> "token-required" SP token-type SP issuer-list NL
>
> [At most once]
>
> token-type: Is the type of token supported ("res" for this proposal)
> issuer: A comma separated list of issuers which are supported by this
> onion service
>
How are issuers identified? I ask because of a potential problem noted below...
> ### 4.3.1. Client preparation [DEST_DIGEST]
>
> Alice first chooses an issuer supported by the onion service depending on
> her
> preferences by looking at the consensus and her Tor configuration file for
> the current list of active issuers.
>
> After picking a supported issuer, she performs the following preparation
> before contacting the issuer:
>
> 1) Alice extracts the issuer's public key (N,e) from the consensus
>
> 2) Alice computes a destination digest as follows:
>
>dest_digest = FDH_N(destination || salt)
>
> where:
> - 'destination' is the 32-byte ed25519 public identity key of
> the destination onion
> - 'salt' is a random 32-byte value,
>
> 3) Alice samples a blinding factor 'r' uniformly at random from [1, N)
>
> 4) Alice computes:
>blinded_message = dest_digest * r^e (mod N)
>
> After this phase is completed, Alice has a blinded message that is tailored
> specifically for the destination onion service. Alice will send the blinded
> message to the Token Issuer, but because of the blinding the Issuer does not
> get to learn the dest_digest value.
>
> XXX Is the salt needed? Reevaluate.
Yes, the salt is needed (or, *some* input besides the destination must
go into the FDH) otherwise, all (unblinded) tokens signed by a given
issuance key will be identical. This would be great for unlinkability
but not so good for double-spend prevention. :)
> We propose a new EXT_FIELD_TYPE value:
>
> [02] -- ANON_TOKEN
>
> The EXT_FIELD content format is:
>
>TOKEN_VERSION[1 byte]
>ISSUER_KEY [4 bytes]
>DEST_DIGEST [32 bytes]
>TOKEN[128 bytes]
>SALT [32 bytes]
>
> where:
>- TOKEN_VERSION is the version of the token ([0x01] for Res tokens)
>- ISSUER_KEY is the public key of the chosen issuer (truncated to 4 bytes)
>- DEST_DIGEST is the 'dest_digest' from above
>- TOKEN is the 'token' from above
>- SALT is the 32-byte 'salt' added during blinding
Is it a problem that it is trivial to produce an RSA key with a given
4-byte truncation? (so an adversarial issuer could choose a key to
match another issuer's keys) Because you can generate an RSA key with
a targeted most- or least-significant bytes value in roughly the same
amount of work that it takes to generate an RSA key at all. (For
example, if we are talking about the 4 least-significant bytes: find a
prime p, th
Re: [tor-dev] [RFC] Proposal: "Res tokens: Anonymous Credentials for Onion Service DoS Resilience"
On 2/11/21 5:36 PM, George Kadianakis wrote:
> We are particularly looking forward to feedback about:
> - Token issuance services
> - The anonymous credential scheme chosen
> - The XXXs and design decisions of the proposal
>
> Hope you have a pleasant read!
> # 9. Acknowledgements
>
> Thanks to Jeff Burdges for all the information about Blind RSA and anonymous
> credentials.
>
> Thanks to Michele Orrù for the help with the unlinkability proof and for the
> discussions about anonymous credentials.
>
> Thanks to Chelsea Komlo for pointing towards anonymous credentials in
> the context of DoS defenses for onion services.
Yooo, duuude! We need to give a public shoutout to OG Chaum! Almost 40
years later, and still the best properties we could find for our use
case. Oldest *AND* best! Fine 1983 vintage crypto, well aged, and
post-quantum unlinkable!
If you know anything about the history of this token, you will know with
certainty that Murs wrote this song about Chaum, referring to when
someone once asked Chaum how to link his tokens to track users:
https://open.spotify.com/track/0RdiYSv0mUfqYXN5WwYXjl
(Ok, so the Murs part may be apocryphal, but the rest is true!)
The One True Anonymity OG was even in talks with credit card companies:
https://decrypt.co/resources/digicash-what-is-cryptocurrency-explainer
https://www.satoshiwatch.com/hall-of-fame/dr-david-chaum/in-depth/digicash-blew-everything-david-chaums/
> ---
>
> # Appendix A: RSA Blinding Security Proof [BLIND_RSA_PROOF]
>
> This proof sketch was provided by Michele Orrù:
>
> ```
> RSA Blind Sigs:
> https://en.wikipedia.org/wiki/Blind_signature#Blind_RSA_signatures
>
> As you say, blind RSA should be perfectly blind.
>
> I tried to look at Boneh-Shoup, Katz-Lindell, and Bellare-Goldwasser for a
> proof, but didn't find any :(
>
> The basic idea is proving that:
> for any message "m0" that is blinded with "r0^e" to obtain "b" (that is
> sent to the server), it is possible to freely choose another message "m1"
> that blinded with another opening "r1^e" to obtain the same "b".
>
> As long as r1, r0 are chosen uniformly at random, you have no way of
> telling if what message was picked and therefore it is *perfectly* blind.
>
> To do so:
> Assume the messages ("m0" and "m1") are invertible mod N=pq (this happens
> at most with overwhelming probability phi(N)/N if m is uniformly distributed
> as a result of a hash, or you can enforce it at signing time).
>
> Blinding happens by computing:
> b = m0 * (r0^e).
>
> However, I can also write:
> b = m0 * r0^e = (m1/m1) * m0 * r0^e = m1 * (m0/m1*r0^e).
>
> This means that r1 = (m0/m1)^d * r0 is another valid blinding factor for b,
> and it's distributed exactly as r0 in the group of invertibles (it's unif at
> random, because r0 is so).
> ```
>
> ---
>
> [REF_TOKEN_ZOO]: https://tokenzoo.github.io/
> [REF_INTRO_SPACE]:
> https://gitlab.torproject.org/legacy/trac/-/issues/33650#note_2350910
> [REF_CHAUM]: https://eprint.iacr.org/2001/002.pdf
> [REF_PRIMO]: https://repo.getmonero.org/selene/primo
> https://www.monerooutreach.org/stories/RPC-Pay.html
> [REF_POW_PERF]:
> https://gitlab.torproject.org/tpo/core/torspec/-/blob/master/proposals/327-pow-over-intro.txt#L1050
> [REF_RES_BENCH]: https://github.com/asn-d6/res_tokens_benchmark
--
Mike Perry
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
