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 anonymous credential literature is vast and there are dozens of > credential schemes with different properties [REF_TOKEN_ZOO], in this > section > we detail the properties we care about for this use case: > > - Public Verifiability: Because of the distributed trust properties of the > Tor network, we need anonymous credentials that can be issued by one > party (the token issuer) and verified by a different party (in this case > the onion service). > > - Perfect unlinkability: Unlinkability between token issuance and token > redemption is vital in private settings like Tor. For this reason we > want > our scheme to preserve its unlinkability even if its fundamental > security > assumption is broken. We want unlinkability to be protected by > information theoretic security or random oracle, and not just > computational security. > > - Small token size: The tokens will be transfered to the service through the > INTRODUCE1 cell which is not flexible and has only a limited amount of > space (about 200 bytes) [REF_INTRO_SPACE]. We need tokens to be small. > > - Quick Verification: Onions are already experiencing resource starvation > because of the DoS attacks so it's important that the process of > verifying a token should be as quick as possible. In section > [TOKEN_PERF] > we will go deeper into this requirement. > > After careful consideration of the above requirements, we have leaned > towards > using Blind RSA as the primitive for our tokens, since it's the > fastest > scheme by far that also allows public verifiability. See also > Appendix B > [BLIND_RSA_PROOF] for a security proof sketch of Blind RSA perfect > unlinkability. > > ## 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. > > ## 3.4. Res tokens overview > > Throughout this proposal we will be using our own token scheme, named "Res", > which is based on blind RSA signatures. In this modern cryptographic world, > not only we have the audacity of using Chaum's oldest blind signature scheme > of all times, but we are also using RSA with a modulus of 1024 bits... > > The reason that Res uses only 1024-bits RSA is because we care most about > small token size and quick verification rather than the unforgeability of > the > token. This means that if the attacker breaks the issuer's RSA signing key > and issues tokens for herself, this will enable the adversary to launch DoS > attacks against onion services, but it won't allow her to link users > (because > of the "perfect unlinkability" property). > > Furthermore, Res tokens get a short implicit expiration date by having the > issuer rapidly rotate issuance keys every few hours. This means that even if > an adversary breaks an issuance key, she will be able to forge tokens for > just a few hours before that key expires. > > For more ideas on future schemes and improvements see section [FUTURE_RES]. > > ## 3.5. Token performance requirements [TOKEN_PERF] > > As discussed above, verification performance is extremely important in the > anti-DoS use case. In this section we provide some concrete numbers on what > we are looking for. > > In proposal #327 [REF_POW_PERF] we measured that the total time spent by the > onion service on processing a single INTRODUCE2 cell ranges from 5 msec to > 15 > msecs with a mean time around 5.29 msec. This time also includes the launch > of a rendezvous circuit, but does not include the additional blocking and > time it takes to process future cells from the rendezvous point. > > We also measured that the parsing and validation of INTRODUCE2 cell ("top > half") takes around 0.26 msec; that's the lightweight part before the onion > service decides to open a rendezvous circuit and do all the path selection > and networking. > > This means that any defenses introduced by this proposal should add minimal > overhead to the above "top half" procedure, so as to apply access control in > the lightest way possible. > > For this reason we implemented a basic version of the Res token scheme in > Rust and benchmarked the verification and issuance procedure > [REF_RES_BENCH]. > > We measured that the verification procedure from section [RES_VERIFY] takes > about 0.104 ms, which we believe is a reasonable verification overhead for > the purposes of this proposal. > > We also measured that the issuance procedure from [RES_ISSUANCE] takes about > 0.614 ms. > > # 4. Specification [PROTOCOL_SPEC] > > +--------------+ +------------------+ > | Token Issuer | | Onion Service | > +--------------+ +------------------+ > ^ ^ > | +----------+ | > Issuance | 1. | | 2. | Redemption > +------->| Alice |<-------+ > | | > +----------+ > > ## 4.0. Notation > > Let `a || b` be the concatenation of a with b. > > Let `a^b` denote the exponentiation of a to the bth power. > > Let `a == b` denote a check for equality between a and b. > > Let FDH_N(msg) be a Full Domain Hash (FDH) of 'msg' using SHA256 and > stretching the digest to be equal to the size of an RSA modulus N. > > ## 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 > > ## 4.3. Token issuance > > When Alice visits an onion service with an active "token-required" line in > its descriptor it checks whether there are any tokens available for this > onion service in its token store. If not, it needs to acquire some and hence > the token issuance protocol commences. > > ### 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. > > ### 4.3.3. Token Issuance [RES_ISSUANCE] > > Alice now initiates contact with the Token Issuer and spends the resources > required to get issued a token (e.g. solve a CAPTCHA or a PoW, create an > account, etc.). After that step is complete, Alice sends the blinded_message > to the issuer through a JSON-RPC API. > > After the Issuer receives the blinded_message it signs it as follows: > > blinded_signature = blinded_message ^ d (mod N) > > where: > - 'd' is the private RSA exponent. > > and returns the blinded_signature to Alice. > > XXX specify API (JSON-RPC? Needs SSL + pubkey pinning.) > > ### 4.3.4. Unblinding step > > Alice verifies the received blinded signature, and unblinds it to get the > final token as follows: > > token = blinded_signature * r^{-1} (mod N) > = blinded_message ^ d * r^{-1] (mod N) > = (dest_digest * r^e) ^d * r^{-1} (mod N) > = dest_digest ^ d * r * r^{-1} (mod N) > = dest_digest ^ d (mod N) > > where: > - r^{-1} is the multiplicative inverse of the blinding factor 'r' > > Alice will now use the 'token' to get access to the onion service. > > By verifying the received signature using the issuer keys in the consensus, > Alice ensures that a legitimate token was received and that it has not > expired (since the issuer keys are still in the consensus). > > ## 4.4. Token redemption > > ### 4.4.1. Alice sends token to onion service > > Now that Alice has a valid 'token' it can request access to the onion > service. It does so by embedding the token into the INTRODUCE1 cell to the > onion service. > > To do so, Alice adds an extension to the encrypted portion of the INTRODUCE1 > cell by using the EXTENSIONS field (see [PROCESS_INTRO2] section in > rend-spec-v3.txt). The encrypted portion of the INTRODUCE1 cell only gets > read by the onion service and is ignored by the introduction point. > > 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 > > This will increase the INTRODUCE1 payload size by 199 bytes since the data > above is 197 bytes, the extension type and length is 2 extra bytes, and the > N_EXTENSIONS field is always present. According to ticket #33650, INTRODUCE1 > cells currently have more than 200 bytes available so we should be able to > fit the above fields in the cell. > > XXX maybe we don't need to pass DEST_DIGEST and we can just derive it > > XXX maybe with a bit of tweaking we can even use a 1536-bit RSA > signature here... > > ### 4.4.2. Onion service verifies token [RES_VERIFY] > > Upon receiving an INTRODUCE1 cell with the above extension the service > verifies the token. It does so as follows: > > 1) The service checks its double spend protection cache for an element that > matches DEST_DIGEST. If one is found, verification fails. > 2) The service checks: DEST_DIGEST == FDH_N(service_pubkey || SALT), where > 'service_pubkey' is its own long-term identity pubkey. > 3) The service finds the corresponding issuer pubkey 'e' based on ISSUER_KEY > from the consensus or its configuration file > 4) The service checks: TOKEN ^ e == DEST_DIGEST > > Finally the onion service adds the DEST_DIGEST to its double spend > protection > cache to avoid the same token getting redeemed twice. Onion services keep a > double spend protection cache by maintaining a sorted array of truncated > DEST_DIGEST elements. > > If any of the above steps fail, the verification process aborts and the > introduction request gets discarded. > > If all the above verification steps have been completed successfully, the > service knows that this a valid token issued by the token issuer, and that > the token has been created for this onion service specifically. The service > considers the token valid and the rest of the onion service protocol carries > out as normal. > > # 5. Token issuers [TOKEN_ISSUERS] > > In this section we go over some example token issuers. While we can have > official token issuers that are supported by the Tor directory authorities, > it is also possible to have unofficial token issuers between communities > that > can be embedded directly into the configuration file of the onion service > and > the client. > > In general, we consider the design of token issuers to be independent from > this proposal so we will touch the topic but not go too deep into it. > > ## 5.1. CAPTCHA token issuer > > A use case resembling the setup of Cloudflare's PrivacyPass would be to have > a CAPTCHA service that issues tokens after a successful CAPTCHA solution. > > Tor Project, Inc runs https://ctokens.torproject.org which serves hCaptcha > CAPTCHAs. When the user solves a CAPTCHA the server gives back a list of > tokens. The amount of tokens rewarded for each solution can be tuned based > on > abuse level. > > Clients reach this service via a regular Tor Exit connection, > possibly via a > dedicated exit enclave-like relay that can only connect to > https://ctokens.torproject.org. > > Upon receiving tokens, Tor Browser delivers them to the Tor client via the > control port, which then stores the tokens into a token cache to be used > when > connecting to onion services. > > In terms of UX, most of the above procedure can be hidden from the user by > having Tor Browser do most of the things under the scenes and only present > the CAPTCHA to the user if/when needed (if the user doesn't have tokens > available for that destination). > > XXX specify control port API between browser and tor > > ## 5.2. PoW token issuer > > An idea that mixes the CAPTCHA issuer with proposal#327, would be to have a > token issuer that accepts PoW solutions and provides tokens as a reward. > > This solution tends to be less optimal than applying proposal#327 directly > because it doesn't allow us to fine-tune the PoW difficulty based on the > attack severity; which is something we are able to do with proposal#327. > > However, we can use the fact that token issuance happens over HTTP to > introduce more advanced PoW-based concepts. For example, we can design token > issuers that accept blockchain shares as a reward for tokens. For example, a > system like Monero's Primo could be used to provide DoS protection and also > incentivize the token issuer by being able to use those shares for pool > mining [REF_PRIMO]. > > ## 5.3. Onion service self-issuing > > The onion service itself can also issue tokens to its users and then use > itself as an issuer for verification. This way it can reward trusted users > by > giving it tokens for the future. The tokens can be rewarded from within the > website of the onion service and passed to the Tor Client through the > control > port, or they can be provided in an out-of-bands way for future use > (e.g. from a journalist to a future source using a QR code). > > Unfortunately, the anonymous credential scheme specified in this proposal is > one-show, so the onion service cannot provide a single token that will work > for multiple "logins". In the future we can design multi-show credential > systems that also have revocation to further facilitate this use case (see > [FUTURE_RES] for more info). > > # 6. User Experience > > This proposal has user facing UX consequences. > > Ideally we want this process to be invisible to the user and things > to "just > work". This can be achieved with token issuers that don't require > manual work > by the user (e.g. the PoW issuer, or the onion service itself), since > both the > token issuance and the token redemption protocols don't require any > manual work. > > 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. An explanation about the > service being under attack should be given to the user when the CAPTCHA is > provided. > > # 7. Security > > In this section we analyze potential security threats of the above system: > > - An evil client can hoard tokens for hours and unleash them all at once to > cause a denial of service attack. We might want to make the key rotation > even more frequent if we think that's a possible threat. > > - A trusted token issuer can always DoS an onion service by forging tokens. > > - Overwhelming attacks like "top half attacks" and "hybrid attacks" from > proposal#327 is valid for this proposal as well. > > - A bad RNG can completely wreck the linkability properties of this > proposal. > > XXX Actually analyze the above if we think there is merit to listing them > > # 8. Discussion [DISCUSSION] > > ## 8.1. Using Res tokens on Exit relays > > There are more scenarios within Tor that could benefit from Res tokens > however we didn't expand on those use cases to keep the proposal short. In > the future, we might want to split this document into two proposals: one > proposal that specifies the token scheme, and another that specifies how to > use it in the context of onion servicves, so that we can then write more > proposals that use the token scheme as a primitive. > > An extremely relevant use case would be to use Res tokens as a way to > protect > and improve the IP reputation of Exit relays. We can introduce an exit pool > that requires tokens in exchange for circuit streams. The idea is that exits > that require tokens will see less abuse, and will not have low scores in the > various IP address reputation systems that now govern who gets access to > websites and web services on the public Internet. We hope that this way we > will see less websites blocking Tor. > > ## 8.2. Future improvements to this proposal [FUTURE_RES] > > The Res token scheme is a pragmatic scheme that works for the space/time > constraints of this use case but it's far from ideal for the greater future > (RSA? RSA-1024?). > > After Tor proposal#319 gets implemented we will be able to pack more data in > RELAY cells and that opens the door to token schemes with bigger token > sizes. For example, we could design schemes based on BBS+ that can provide > more advanced features like multi-show and complex attributes but currently > have bigger token sizes (300+ bytes). That would greatly improve UX since > the > client won't have to solve multiple CAPTCHAs to gain access. Unfortunately, > another problem here is that right now pairing-based schemes have > significantly worse verification performance than RSA (e.g. in the order of > 4-5 ms compared to <0.5 ms). We expect pairing-based cryptography > performance > to only improve in the future and we are looking forward to these advances. > > When we switch to a multi-show scheme, we will also need revocation support > otherwise a single client can abuse the service with a single multi-show > token. To achieve this we would need to use blacklisting schemes based on > accumulators (or other primitives) that can provide more flexible revocation > and blacklisting; however these come at the cost of additional verification > time which is not something we can spare at this time. We warmly welcome > research on revocation schemes that are lightweight on the verification side > but can be heavy on the proving side. > > ## 8.3. Other uses for tokens in Tor > > There is more use cases for tokens in Tor but we think that other token > schemes with different properties would be better suited for those. > > In particular we could use tokens as authentication mechanisms for logging > into services (e.g. acquiring bridges, or logging into Wikipedia). However > for those use cases we would ideally need multi-show tokens with revocation > support. We can also introduce token schemes that help us build a secure > name > system for onion services. > > We hope that more research will be done on how to combine various token > schemes together, and how we can maintain agility while using schemes with > different primitives and properties. > > # 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. > > --- > > # 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 > _______________________________________________ > 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