[tor-dev] Proposal 228: Cross-certifying identity keys with onion keys

[Nick Mathewson]

Here's a proposal that's been kicking around on my laptop for a while.
I cleaned it up to use the revised certificate format from the revised
proposal 220.

My math and crypto claims might be incorrect here; I'm sure hoping
somebody will tell me if they are.



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


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 .

   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 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
   them to need to

   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 decomporession
   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.