228-cross-certification-onionkeys.txt

Filename: 228-cross-certification-onionkeys.txt
Title: Cross-certifying identity keys with onion keys
Author: Nick Mathewson
Created: 25 February 2014
Status: Closed


0. Abstract

   In current Tor router descriptor designs, routers prove ownership
   of an identity key (by signing the router descriptors), but not
   of their onion keys.  This document describes a method for them
   to do so.

1. Introduction.

   Signing router descriptors with identity keys prevents attackers
   from impersonating a server and advertising their own onion keys
   and IP addresses.  That's good.

   But there's nothing in Tor right now that effectively stops you
   (an attacker) from listing somebody else's public onion key in
   your descriptor.  If you do, you can't actually recover any keys
   negotiated using that key, and you can't MITM circuits made with
   that key (since you don't have the private key).

   (You _could_ do something weird in the TAP protocol where you
   receive an onionskin that you can't process, relay it to the
   party who can process it, and receive a valid reply that you
   could send back to the user.  But this makes you a less effective
   man-in-the-middle than you would be if you had just generated
   your own onion key.  The ntor protocol shuts down this
   possibility by including the router identity in the material to
   be hashed, so that you can't complete an ntor handshake unless
   the client agrees with you about what identity goes with your
   ntor onion key.)

   Nonetheless, it's probably undesirable that this is possible at
   all.  Just because it isn't obvious today how to exploit this
   doesn't mean it will never be possible.

2. Cross-certifying identities with onion keys

2.1. What to certify

   Once proposal 220 is implemented, we'll sign our Ed25519 identity
   key as described in proposal 220.  Since the Ed25519 identity key
   certifies the RSA key, there's no strict need to certify both
   separately.

   On the other hand, this proposal may be implemented before proposal
   220.  If it is, we'll need a way for it to certify the RSA1024 key
   too.

2.2. TAP onion keys

   We add to each router descriptor a new element,
   "onion-key-crosscert", containing a RSA signature of:

       A SHA1 hash of the identity key  [20 bytes]
       The Ed25519 identity key, if any [32 bytes]

   If there is no ed25519 identity key, or if in some future version
   there is no RSA identity key, the corresponding field must be
   zero-filled.

   Parties verifying this signature MUST allow additional data beyond
   the 52 bytes listed above.

2.3. ntor onion keys

   Here, we need to convert the ntor key to an ed25519 key for
   signing.  See the appendix A for how to do that.  We'll also need
   to transmit a sign bit.

   We can add an element "ntor-onion-key-crosscert", containing an
   Ed25519 certificate in the format from proposal 220 section 2.1,
   with a sign indicator to indicate which ed25519 public key to use
   to check the key:

      "ntor-onion-key-crosscert" SP SIGNBIT SP CERT NL

      SIGNBIT = "0" / "1"

   Note that this cert format has 32 bytes of of redundant data, since it
   includes the identity key an extra time.  That seems okay to me.

   The signed key here is the master identity key.

   The TYPE field in this certificate should be set to
      [0A] - ntor onion key cross-certifying ntor identity key

3. Authority behavior

   Authorities should reject any router descriptor with an invalid
   onion-key-crosscert element or ntor-onion-key-crosscert element.

   Both elements should be required on any cert containing an
   ed25519 identity key.

   See section 3.1 of proposal 220 for rules requiring routers to
   eventually have ed25519 keys.

4. Performance impact

   Routers do not generate new descriptors frequently enough for the
   extra signing operations required here to have an appreciable affect
   on their performance.

   Checking an extra ed25519 signature when parsing a descriptor is
   very cheap, since we can use batch signature checking.

   The point decompression algorithm will require us to calculate
   1/(u+1), which costs as much as an exponentiation in
   GF(2^255-19).

   Checking an RSA1024 signature is also cheap, since we use small
   public exponents.

   Adding an extra RSA signature and an extra ed25519 signature to
   each descriptor will make each descriptor, after compression,
   about 128+100 bytes longer.  (Compressed base64-encoded random
   bytes are about as long as the original random bytes.) Most
   clients don't download raw descriptors, though, so it shouldn't
   matter too much.


A. Converting a curve25519 public key to an ed25519 public key

   Given a curve25519 x-coordinate (u), we can get the y coordinate
   of the ed25519 key using

         y = (u-1)/(u+1)

   and then we can apply the usual ed25519 point decompression
   algorithm to find the x coordinate of the ed25519 point to check
   signatures with.

   Note that we need the sign of the X coordinate to do this
   operation; otherwise, we'll have two possible X coordinates that
   might have correspond to the key.  Therefore, we need the 'sign'
   of the X coordinate, as used by the ed25519 key expansion
   algorithm.

   To get the sign, the easiest way is to take the same private key,
   feed it to the ed25519 public key generation algorithm, and see
   what the sign is.


B. Security notes

   It would be very bad for security if we provided a diffie-hellman
   oracle for our curve25519 ntor keys.  Fortunately, we don't, since
   nobody else can influence the certificate contents.

C. Implementation notes

   As implemented in Tor, I've decided to make this proposal cross-dependent
   on proposal 220. A router descriptor must have ALL or NONE
   of the following:
            * An Ed25529 identity key
            * A TAP cross-certification
            * An ntor cross-certification

   Further, if it has the above, it must also have:
            * An ntor onion key.