Proposal 169: Eliminate TLS renegotiation for the Tor connection handshake

[Nick Mathewson <nickm@xxxxxxxxxxxxxx>]

Filename: 169-eliminating-renegotiation.txt
Title: Eliminate TLS renegotiation for the Tor connection handshake
Author: Nick Mathewson
Created: 27-Jan-2010
Status: Draft
Target: 0.2.2

1. Overview

   I propose a backward-compatible change to the Tor connection
   establishment protocol to avoid the use of TLS renegotiation.

   Rather than doing a TLS renegotiation to exchange certificates
   and authenticate the original handshake, this proposal takes an
   approach similar to Steven Murdoch's proposal 124, and uses Tor
   cells to finish authenticating the parties' identities once the
   initial TLS handshake is finished.

   Terminological note: I use "client" below to mean the Tor
   instance (a client or a relay) that initiates a TLS connection,
   and "server" to mean the Tor instance (a relay) that accepts it.

2. Motivation and history

   In the original Tor TLS connection handshake protocol ("V1", or
   "two-cert"), parties that wanted to authenticate provided a
   two-cert chain of X.509 certificates during the handshake setup
   phase.  Every party that wanted to authenticate sent these
   certificates.

   In the current Tor TLS connection handshake protocol ("V2", or
   "renegotiating"), the parties begin with a single certificate
   sent from the server (responder) to the client (initiator), and
   then renegotiated to a two-certs-from-each-authenticating party.
   We made this change to make Tor's handshake look like a browser
   speaking SSL to a webserver.  (See proposal 130, and
   tor-spec.txt.)  To tell whether to use the V1 or V2 handshake,
   servers look at the list of ciphers sent by the client.  (This is
   ugly, but there's not much else in the ClientHello that they can
   look at.) If the list contains any cipher not used by the V1
   protocol, the server sends back a single cert and expects a
   renegotiation.  If the client gets back a single cert, then it
   withholds its own certificates until the TLS renegotiation phase.

   In other words, initiator behavior now looks like this:

      - Begin TLS negotiation with V2 cipher list; wait for
        certificate(s).
      - If we get a certificate chain:
         - Then we are using the V1 handshake.  Send our own
           certificate chain as part of this initial TLS handshake
           if we want to authenticate; otherwise, send no
           certificates.  When the handshake completes, check
           certificates.  We are now mutually authenticated.

        Otherwise, if we get just a single certificate:
         - Then we are using the V2 handshake.  Do not send any
           certificates during this handshake.
         - When the handshake is done, immediately start a TLS
           renegotiation.  During the renegotiation, expect
           a certificate chain from the server; send a certificate
           chain of our own if we want to authenticate ourselves.
         - After the renegotiation, check the certificates. Then
           send (and expect) a VERSIONS cell from the other side to
           establish the link protocol version.

   And V2 responder behavior now looks like this:

      - When we get a TLS ClientHello request, look at the cipher
        list.
      - If the cipher list contains only the V1 ciphersuites:
         - Then we're doing a V1 handshake.  Send a certificate
           chain.  Expect a possible client certificate chain in
           response.
        Otherwise, if we get other ciphersuites:
         - We're using the V2 handshake.  Send back a single
           certificate and let the handshake complete.
         - Do not accept any data until the client has renegotiated.
         - When the client is renegotiating, send a certificate
           chain, and expect (possibly multiple certificates in
           reply).
         - Check the certificates when the renegotiation is done.
           Then exchange VERSIONS cells.

   Late in 2009, researchers found a flaw in most application's use
   of TLS renegotiation: Although TLS renegotiation does not
   reauthenticate any information exchanged before the renegotiation
   takes place, many applications were treating it as though it did,
   and assuming that data sent _before_ the renegotiation was
   authenticated with the credentials negotiated _during_ the
   renegotiation.  This problem was exacerbated by the fact that
   most TLS libraries don't actually give you an obvious good way to
   tell where the renegotiation occurred relative to the datastream.
   Tor wasn't directly affected by this vulnerability, but its
   aftermath hurts us in a few ways:

      1) OpenSSL has disabled renegotiation by default, and created
         a "yes we know what we're doing" option we need to set to
         turn it back on.  (Two options, actually: one for openssl
         0.9.8l and one for 0.9.8m and later.)

      2) Some vendors have removed all renegotiation support from
         their versions of OpenSSL entirely, forcing us to tell
         users to either replace their versions of OpenSSL or to
         link Tor against a hand-built one.

      3) Because of 1 and 2, I'd expect TLS renegotiation to become
         rarer and rarer in the wild, making our own use stand out
         more.

3. Design

3.1. The view in the large

   Taking a cue from Steven Murdoch's proposal 124, I propose that
   we move the work currently done by the TLS renegotiation step
   (that is, authenticating the parties to one another) and do it
   with Tor cells instead of with TLS.

   Using _yet another_ variant response from the responder (server),
   we allow the client to learn that doesn't need to rehandshake,
   and it can use a cell-based authentication system.  Once the
   TLS handshake is done, the client and server exchange VERSIONS
   cells to determine what link protocol version (including
   handshake version).  If they're using the handshake version
   specified here, the client and server arrive at link protocol
   version 3 (or higher), and use cells to exchange further
   authentication information.

3.2. New TLS handshake variant

   We already used the list of ciphers from the clienthello to
   indicate whether the client can speak the V2 ("renegotiating")
   handshake or later, so we can't encode more information there.

   We can, however, change the DN in the certificate passed by the
   server to back the client.  Currently, all V2 certificates are
   generated with CN values ending with ".net".  I propose that we
   have the ".net" commonName ending reserved to indicate the V2
   protocol, and use commonName values ending with ".com" to
   indicate the V3 ("minimal") handshake described herein.

   Now, once the initial TLS handshake is done, the client can look
   at the server's certificate(s).  If there is a certificate chain,
   the handshake is V1.  If there is a single certificate whose
   subject commonName ends in ".net", the handshake is V2 and the
   client should try to renegotiate as it would currently.
   Otherwise, the client should assume that the handshake is V3+.
   [Servers should _only_ send ".com" addesses, to allow room for
   more signaling in the future.]

3.3. Authenticating inside Tor

   Once the TLS handshake is finished, if the client renegotiates,
   then the server should go on as it does currently.

   If the client implements this proposal, however, and the server
   has shown it can understand the V3+ handshake protocol, the
   client immediately sends a VERSIONS cell to the server
   and waits to receive a VERSIONS cell in return.  We negotiate
   the Tor link protocol version _before_ we proceed with the
   negotiation, in case we need to change the authentication
   protocol in the future.

   Once either party has seen the VERSIONS cell from the other, it
   knows which version they will pick (that is, the highest version
   shared by both parties' VERSIONS cells).  All Tor instances using
   the handshake protocol described in 3.2 MUST support at least
   link protocol version 3 as described here.

   On learning the link protocol, the server then sends the client a
   CERT cell and a NETINFO cell.  If the client wants to
   authenticate to the server, it sends a CERT cell, an AUTHENTICATE
   cell, and a NETINFO cell, or it may simply send a NETINFO cell if
   it does not want to authenticate.

   The CERT cell describes the keys that a Tor instance is claiming
   to have.  It is a variable-length cell.  Its payload format is:

        N: Number of certs in cell            [1 octet]
        N times:
           CLEN                               [2 octets]
           Certificate                        [CLEN octets]

   Any extra octets at the end of a CERT cell MUST be ignored.

   Each certificate has the form:

        CertType                              [1 octet]
        CertPurpose                           [1 octet]
        PublicKeyLen                          [2 octets]
        PublicKey                             [PublicKeyLen octets]
        NotBefore                             [4 octets]
        NotAfter                              [4 octets]
        SignerID                              [HASH256_LEN octets]
        SignatureLen                          [2 octets]
        Signature                             [SignatureLen octets]

   where CertType is 1 (meaning "RSA/SHA256")
         CertPurpose is 1 (meaning "link certificate")
         PublicKey is the DER encoding of the ASN.1 representation
            of the RSA key of the subject of this certificate,
         NotBefore is a time in HOURS since January 1, 1970, 00:00
            UTC before which this certificate should not be
            considered valid.
         NotAfter is a time in HOURS since January 1, 1970, 00:00
            UTC after which this certificate should not be
            considered valid.
         SignerID is the SHA-256 digest of the public key signing
            this certificate
         and Signature is the signature of the all other fields in
            this certificate, using SHA256 as described in proposal
            158.

   While authenticating, a server need send only a self-signed
   certificate for its identity key.  (Its TLS certificate already
   contains its link key signed by its identity key.)  A client that
   wants to authenticate MUST send two certificates: one containing
   a public link key signed by its identity key, and one self-signed
   cert for its identity.

   Tor instances MUST ignore any certificate with an unrecognized
   CertType or CertPurpose.

   The AUTHENTICATE cell proves to the server that the client with
   whom it completed the initial TLS handshake is the one possessing
   the link public key in its certificate.  It is a variable-length
   cell.  Its contents are:

        SignatureType                         [2 octets]
        SignatureLen                          [2 octets]
        Signature                             [SignatureLen octets]

   where SignatureType is 1 (meaning "RSA-SHA256") and Signature is
   an RSA-SHA256 signature of the HMAC-SHA256, using the TLS master
   secret key as its key, of the following elements:

     - The SignatureType field (0x00 0x01)
     - The NUL terminated ASCII string: "Tor certificate verification"
     - client_random, as sent in the Client Hello
     - server_random, as sent in the Server Hello

   Once the above handshake is complete, the client knows (from the
   initial TLS handshake) that it has a secure connection to an
   entity that controls a given link public key, and knows (from the
   CERT cell) that the link public key is a valid public key for a
   given Tor identity.

   If the client authenticates, the server learns from the CERT cell
   that a given Tor identity has a given current public link key.
   From the AUTHENTICATE cell, it knows that an entity with that
   link key knows the master secret for the TLS connection, and
   hence must be the party with whom it's talking, if TLS works.

3.4. Security checks

   If the TLS handshake indicates a V2 or V3+ connection, the server
   MUST reject any connection from the client that does not begin
   with either a renegotiation attempt or a VERSIONS cell containing
   at least link protocol version "3".  If the TLS handshake
   indicates a V3+ connection, the client MUST reject any connection
   where the server sends anything before the client has sent a
   VERSIONS cell, and any connection where the VERSIONS cell does
   not contain at least link protocol version "3".

   If link protocol version 3 is chosen:

     Clients and servers MUST check that all digests and signatures
     on the certificates in CERT cells they are given are as
     described above.

     After the VERSIONS cell, clients and servers MUST close the
     connection if anything besides a CERT or AUTH cell is sent
     before the

     CERT or AUTHENTICATE cells anywhere after the first NETINFO
     cell must be rejected.

   ... [write more here.  What else?] ...

3.5. Summary

   We now revisit the protocol outlines from section 2 to incorporate
   our changes.  New or modified steps are marked with a *.

   The new initiator behavior now looks like this:

      - Begin TLS negotiation with V2 cipher list; wait for
        certificate(s).
      - If we get a certificate chain:
         - Then we are using the V1 handshake.  Send our own
           certificate chain as part of this initial TLS handshake
           if we want to authenticate; otherwise, send no
           certificates.  When the handshake completes, check
           certificates.  We are now mutually authenticated.
        Otherwise, if we get just a single certificate:
         - Then we are using the V2 or the V3+ handshake.  Do not
           send any certificates during this handshake.
         * When the handshake is done, look at the server's
           certificate's subject commonName.
           * If it ends with ".net", we're doing a V2 handshake:
             - Immediately start a TLS renegotiation.  During the
               renegotiation, expect a certificate chain from the
               server; send a certificate chain of our own if we
               want to authenticate ourselves.
             - After the renegotiation, check the certificates. Then
               send (and expect) a VERSIONS cell from the other side
               to establish the link protocol version.
           * If it ends with anything else, assume a V3 or later
             handshake:
             * Send a VERSIONS cell, and wait for a VERSIONS cell
               from the server.
             * If we are authenticating, send CERT and AUTHENTICATE
               cells.
             * Send a NETINFO cell.  Wait for a CERT and a NETINFO
               cell from the server.
             * If the CERT cell is a good cert signing the public
               key in the x.509 certificate we got during the TLS
               handshake, we connected to the server with that
               identity key.  Otherwise close the connection.
             * Once the NETINFO cell arrives, continue as before.

   And V3+ responder behavior now looks like this:

      - When we get a TLS ClientHello request, look at the cipher
        list.

      - If the cipher list contains only the V1 ciphersuites:
         - Then we're doing a V1 handshake.  Send a certificate
           chain.  Expect a possible client certificate chain in
           response.
        Otherwise, if we get other ciphersuites:
         - We're using the V2 handshake.  Send back a single
           certificate whose subject commonName ends with ".com",
           and let the handshake complete.
         * If the client does anything besides renegotiate or send a
           VERSIONS cell, drop the connection.
         - If the client renegotiates immediately, it's a V2
           connection:
           - When the client is renegotiating, send a certificate
             chain, and expect (possibly multiple certificates in
             reply).
           - Check the certificates when the renegotiation is done.
             Then exchange VERSIONS cells.
         * Otherwise we got a VERSIONS cell and it's a V3 handshake.
           * Send a VERSIONS cell, a CERT cell, an AUTHENTICATE
             cell, and a NETINFO cell.
           * Wait for the client to send cells in reply.  If the
             client sends a CERT and an AUTHENTICATE and a NETINFO,
             use them to authenticate the client.  If the client
             sends a NETINFO, it is unauthenticated.  If it sends
             anything else before its NETINFO, it's rejected.

4. Numbers to assign

   We need a version number for this link protocol.  I've been
   calling it "3".

   We need to reserve command numbers for CERT and AUTH cells.  I
   suggest that in link protocol 3 and higher, we reserve command
   numbers 128..240 for variable-length cells.  (241-256 we can hold
   for future extensions.

5. Efficiency

   This protocol add a round-trip step when the client sends a
   VERSIONS cell to the server, and waits for the {VERSIONS, CERT,
   NETINFO} response in turn.  (The server then waits for the
   client's {NETINFO} or {CERT, AUTHENTICATE, NETINFO} reply,
   but it would have already been waiting for the client's NETINFO,
   so that's not an additional wait.)

   This is actually fewer round-trip steps than required before for
   TLS renegotiation, so that's a win.

6. Open questions:

  - Should we use X.509 certificates instead of the certificate-ish
    things we describe here?  They are more standard, but more ugly.

  - May we cache which certificates we've already verified?  It
    might leak in timing whether we've connected with a given server
    before, and how recently.

  - Is there a better secret than the master secret to use in the
    AUTHENTICATE cell?  Say, a portable one?  Can we get at it for
    other libraries besides OpenSSL?

  - Does using the client_random and server_random data in the
    AUTHENTICATE message actually help us?  How hard is it to pull
    them out of the OpenSSL data structure?

  - Can we give some way for clients to signal "I want to use the
    V3 protocol if possible, but I can't renegotiate, so don't give
    me the V2"?  Clients currently have a fair idea of server
    versions, so they could potentially do the V3+ handshake with
    servers that support it, and fall back to V1 otherwise.

  - What should servers that don't have TLS renegotiation do?  For
    now, I think they should just get it.  Eventually we can
    deprecate the V2 handshake as we did with the V1 handshake.