[tor-dev] [RFC] Proposal: "Res tokens: Anonymous Credentials for Onion Service DoS Resilience"

[Nicholas Hopper]

Hi George!

A couple of thoughts about this proposal:

On Thu, Feb 11, 2021 at 5:36 PM George Kadianakis
<desnacked at riseup.net> 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, then set the 4 least-significant bytes of a candidate q to
(t*p^{-1} mod 2^{32}) before choosing the rest of q at random)

-Nick

-- 
------------------------------------------------------------------------
Nicholas Hopper (he/him/his)
Professor, Computer Science & Engineering
University of Minnesota
------------------------------------------------------------------------