[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[tor-commits] [torspec/master] Prop331: Merge Res tokens proposal



commit e0a1c4bd5ac92e02533e011fb51ef78ed157170b
Author: George Kadianakis <desnacked@xxxxxxxxxx>
Date:   Thu Apr 1 18:27:30 2021 +0300

    Prop331: Merge Res tokens proposal
---
 proposals/331-res-tokens-for-anti-dos.md | 618 +++++++++++++++++++++++++++++++
 1 file changed, 618 insertions(+)

diff --git a/proposals/331-res-tokens-for-anti-dos.md b/proposals/331-res-tokens-for-anti-dos.md
new file mode 100644
index 0000000..23e2aa9
--- /dev/null
+++ b/proposals/331-res-tokens-for-anti-dos.md
@@ -0,0 +1,618 @@
+```
+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-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits