Filename: 176-revising-handshake.txt
Title: Proposed version-3 link handshake for Tor
Author: Nick Mathewson
Created: 31-Jan-2011
Status: Closed
Target: 0.2.3
Supersedes: 169
1. Overview
I propose a (mostly) backward-compatible change to the Tor
connection establishment protocol to avoid the use of TLS
renegotiation, to avoid certain protocol fingerprinting attacks,
and to make it easier to write Tor clients and servers.
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 my old
proposal 169, and uses Tor cells to finish authenticating the
parties' identities once the initial TLS handshake is finished.
I discuss some alternative design choices and why I didn't make
them in section 7; please have a quick look there before
telling me that something is pointless or makes no sense.
Terminological note: I use "client" or "initiator" below to mean
the Tor instance (a client or a bridge or a relay) that initiates a
TLS connection, and "server" or "responder" to mean the Tor
instance (a bridge or a relay) that accepts it.
2. History and Motivation
The _goals_ of the Tor link handshake have remained basically uniform
since our earliest versions. They are:
* Provide data confidentiality, data integrity
* Provide forward secrecy
* Allow responder authentication or bidirectional authentication.
* Try to look like some popular too-important-to-block-at-whim
encryption protocol, to avoid fingerprinting and censorship.
* Try to be implementable -- on the client side at least! --
by as many TLS implementations as possible.
When we added the v2 handshake, we added another goal:
* Remain compatible with older versions of the handshake
protocol.
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. The security properties of this protocol are just
fine; the problem was that our behavior of sending
two-certificate chains made Tor easy to identify.
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 renegotiate 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.) So from an observer's point of view, two parties
performing the V2 handshake begin by making a regular TLS
handshake with a single certificate, then renegotiate
immediately.
To tell whether to use the V1 or V2 handshake, the 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, V2-supporting initiator behavior currently 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-supporting 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 applications' 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 the
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.
Furthermore, there are other issues related to TLS and
fingerprinting that we want to fix in any revised handshake:
1) We should make it easier to use self-signed certs, or maybe
even existing HTTPS certificates, for the server side
handshake, since most non-Tor SSL handshakes use either
self-signed certificates or CA-signed certificates.
2) We should allow other changes in our use of TLS and in our
certificates so as to resist fingerprinting based on how
our certificates look. (See proposal 179.)
3. Design
3.1. The view in the large
Taking a cue from Steven Murdoch's proposal 124 and my old
proposal 169, 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
alone.
This section outlines the protocol; we go into more detail below.
To tell the client that it can use the new cell-based
authentication system, the server sends a "V3 certificate" during
the initial TLS handshake. (More on what makes a certificate
"v3" below.) If the client recognizes the format of the
certificate and decides to pursue the V3 handshake, then instead
of renegotiating immediately on completion of the initial TLS
handshake, the client instead sends a VERSIONS cell (and the
negotiation begins).
So the flowchart on the server side is:
Wait for a ClientHello.
If the client sends a ClientHello that indicates V1:
- Send a certificate chain.
- When the TLS handshake is done, if the client sent us a
certificate chain, then check it.
If the client sends a ClientHello that indicates V2 or V3:
- Send a self-signed certificate or a CA-signed certificate
- When the TLS handshake is done, wait for renegotiation or data.
- If renegotiation occurs, the client is V2: send a
certificate chain and maybe receive one. Check the
certificate chain as in V1.
- If the client sends data without renegotiating, it is
starting the V3 handshake. Proceed with the V3
handshake as below.
And the client-side flowchart is:
- Send a ClientHello with a set of ciphers that indicates V2/V3.
- After the handshake is done:
- If the server sent us a certificate chain, check it: we
are using the V1 handshake.
- If the server sent us a single "V2 certificate", we are
using the v2 handshake: the client begins to renegotiate
and proceeds as before.
- Finally, if the server sent us a "v3 certificate", we are
doing the V3 handshake below.
And the cell-based part of the V3 handshake, in summary, is:
C<->S: TLS handshake where S sends a "v3 certificate"
In TLS:
C->S: VERSIONS cell
S->C: VERSIONS cell, CERT cell, AUTH_CHALLENGE cell, NETINFO cell
C->S: Optionally: CERT cell, AUTHENTICATE cell
C->S: NETINFO cell
A "CERTS" cell contains a set of certificates; an "AUTHENTICATE"
cell authenticates the client to the server. More on these
later.
3.2. Distinguishing V2 and V3 certificates
In the protocol outline above, we require that the client can
distinguish between v2 certificates (that is, those sent by
current servers) and v3 certificates. We further require that
existing clients will accept v3 certificates as they currently
accept v2 certificates.
Fortunately, current certificates have a few characteristics that
make them fairly well-mannered as it is. We say that a certificate
indicates a V2-only server if ALL of the following hold:
* The certificate is not self-signed.
* There is no DN field set in the certificate's issuer or
subject other than "commonName".
* The commonNames of the issuer and subject both end with
".net"
* The public modulus is at most 1024 bits long.
Otherwise, the client should assume that the server supports the
V3 handshake.
To the best of my knowledge, current clients will behave properly
on receiving non-v2 certs during the initial TLS handshake so
long as they eventually get the correct V2 cert chain during the
renegotiation.
The v3 requirements are easy to meet: any certificate designed to
resist fingerprinting will likely be self-signed, or if it's
signed by a CA, then the issuer will surely have more DN fields
set. Certificates that aren't trying to resist fingerprinting
can trivially become v3 by using a CN that doesn't end with .net,
or using a key longer than 1024 bits.
3.3. Authenticating via Tor cells: server authentication
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. If a version lower
than 3 is negotiated with the V3 handshake in place, a Tor
instance MUST close the connection.
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:
CertType [1 octet]
CLEN [2 octets]
Certificate [CLEN octets]
Any extra octets at the end of a CERT cell MUST be ignored.
CertType values are:
1: Link key certificate from RSA1024 identity
2: RSA1024 Identity certificate
3: RSA1024 AUTHENTICATE cell link certificate
The certificate format is X509.
To authenticate the server, the client MUST check the following:
* The CERTS cell contains exactly one CertType 1 "Link" certificate.
* The CERTS cell contains exactly one CertType 2 "ID" certificate.
* Both certificates have validAfter and validUntil dates that
are not expired.
* The certified key in the Link certificate matches the
link key that was used to negotiate the TLS connection.
* The certified key in the ID certificate is a 1024-bit RSA key.
* The certified key in the ID certificate was used to sign both
certificates.
* The link certificate is correctly signed with the key in the
ID certificate
* The ID certificate is correctly self-signed.
If all of these conditions hold, then the client knows that it is
connected to the server whose identity key is certified in the ID
certificate. If any condition does not hold, the client closes
the connection. If the client wanted to connect to a server with
a different identity key, the client closes the connection.
An AUTH_CHALLENGE cell is a variable-length cell with the following
fields:
Challenge [32 octets]
N_Methods [2 octets]
Methods [2 * N_Methods octets]
It is sent from the server to the client. Clients MUST ignore
unexpected bytes at the end of the cell. Servers MUST generate
every challenge using a strong RNG or PRNG.
The Challenge field is a randomly generated string that the
client must sign (a hash of) as part of authenticating. The
methods are the authentication methods that the server will
accept. Only one authentication method is defined right now; see
3.4 below.
3.4. Authenticating via Tor cells: Client authentication
A client does not need to authenticate to the server. If it
does not wish to, it responds to the server's valid CERT cell by
sending a NETINFO cell: once it has gotten a valid NETINFO cell,
the client should consider the connection open, and the
server should consider the connection as opened by an
unauthenticated client.
If a client wants to authenticate, it responds to the
AUTH_CHALLENGE cell with a CERT cell and an AUTHENTICATE cell.
The CERT cell is as a server would send, except that instead of
sending a CertType 1 cert for an arbitrary link certificate, the
client sends a CertType 3 cert for an RSA AUTHENTICATE key.
(This difference is because we allow any link key type on a TLS
link, but the protocol described here will only work for 1024-bit
RSA keys. A later protocol version should extend the protocol
here to work with non-1024-bit, non-RSA keys.)
AuthType [2 octets]
AuthLen [2 octets]
Authentication [AuthLen octets]
Servers MUST ignore extra bytes at the end of an AUTHENTICATE
cell. If AuthType is 1 (meaning "RSA-SHA256-TLSSecret"), then the
Authentication contains the following:
TYPE: The characters "AUTH0001" [8 octets]
CID: A SHA256 hash of the client's RSA1024 identity key [32 octets]
SID: A SHA256 hash of the server's RSA1024 identity key [32 octets]
SLOG: A SHA256 hash of all bytes sent from the server to the client
as part of the negotiation up to and including the
AUTH_CHALLENGE cell; that is, the VERSIONS cell,
the CERT cell, the AUTH_CHALLENGE cell, and any padding cells.
[32 octets]
CLOG: A SHA256 hash of all bytes sent from the client to the
server as part of the negotiation so far; that is, the
VERSIONS cell and the CERT cell and any padding cells. [32 octets]
SCERT: A SHA256 hash of the server's TLS link
certificate. [32 octets]
TLSSECRETS: A SHA256 HMAC, using the TLS master secret as the
secret key, of the following:
- client_random, as sent in the TLS Client Hello
- server_random, as sent in the TLS Server Hello
- the NUL terminated ASCII string:
"Tor V3 handshake TLS cross-certification"
[32 octets]
TIME: The time of day in seconds since the POSIX epoch. [8 octets]
RAND: A 16 byte value, randomly chosen by the client [16 octets]
SIG: A signature of a SHA256 hash of all the previous fields
using the client's "Authenticate" key as presented. (As
always in Tor, we use OAEP-MGF1 padding; see tor-spec.txt
section 0.3.)
[variable length]
To check the AUTHENTICATE cell, a server checks that all fields
containing from TYPE through TLSSECRETS contain their unique
correct values as described above, and then verifies the signature.
signature. The server MUST ignore any extra bytes in the signed
data after the SHA256 hash.
3.5. Responding to extra cells, and other security checks.
If the handshake is a V3 TLS handshake, both parties MUST reject
any negotiated link version less than 3. Both parties MUST check
this and close the connection if it is violated.
If the handshake is not a V3 TLS handshake, both parties MUST
still advertise all link protocols they support in their versions
cell. Both parties MUST close the link if it turns out they both
would have supported version 3 or higher, but they somehow wound
up using a v2 or v1 handshake. (More on this in section 6.4.)
Either party may send a VPADDING cell at any time during the
handshake, except as the first cell. (See proposal 184.)
A server SHOULD NOT send any sequence of cells when starting a v3
negotiation other than "VERSIONS, CERT, AUTH_CHALLENGE,
NETINFO". A client SHOULD drop a CERT, AUTH_CHALLENGE, or
NETINFO cell that appears at any other time or out of sequence.
A client should not begin a v3 negotiation with any sequence
other than "VERSIONS, NETINFO" or "VERSIONS, CERT, AUTHENTICATE,
NETINFO". A server SHOULD drop a CERT, AUTH_CHALLENGE, or
NETINFO cell that appears at any other time or out of sequence.
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, AUTH_CHALLENGE, and
AUTHENTICATE. I suggest that in link protocol 3 and higher, we
reserve a separate range of commands for variable-length cells.
See proposal 184 for more there.
5. Efficiency
This protocol adds 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 over v2.
6. Security argument
These aren't crypto proofs, since I don't write those. They are
meant to be reasonably convincing.
6.1. The server is authenticated
TLS guarantees that if the TLS handshake completes successfully,
the client knows that it is speaking to somebody who knows the
private key corresponding to the public link key that was used in
the TLS handshake.
Because this public link key is signed by the server's identity
key in the CERT cell, the client knows that somebody who holds
the server's private identity key says that the server's public
link key corresponds to the server's public identity key.
Therefore, if the crypto works, and if TLS works, and if the keys
aren't compromised, then the client is talking to somebody who
holds the server's private identity key.
6.2. The client is authenticated
Once the server has checked the client's certificates, the server
knows that somebody who knows the client's private identity key
says that he is the one holding the private key corresponding to
the client's presented link-authentication public key.
Once the server has checked the signature in the AUTHENTICATE
cell, the server knows that somebody holding the client's
link-authentication private key signed the data in question. By
the standard certification argument above, the server knows that
somebody holding the client's private identity key signed the
data in question.
So the server's remaining question is: am I really talking to
somebody holding the client's identity key, or am I getting a
replayed or MITM'd AUTHENTICATE cell that was previously sent by
the client?
Because the client includes a TLSSECRET component, and the
server is able to verify it, then the answer is easy: the server
knows for certain that it is talking to the party with whom it
did the TLS handshake, since if somebody else generated a correct
TLSSECRET, they would have to know the master secret of the TLS
connection, which would require them to have broken TLS.
Even if the protocol didn't contain the TLSSECRET component,
the server could the client's authentication, but it's a little
trickier. The server knows that it is not getting a replayed
AUTHENTICATE cell, since the cell authenticates (among other
stuff) the server's AUTH_CHALLENGE cell, which it has never used
before. The server knows that it is not getting a MITM'd
AUTHENTICATE cell, since the cell includes a hash of the server's
link certificate, which nobody else should have been able to use
in a successful TLS negotiation.
6.3. MITM attacks won't work any better than they do against TLS
TLS guarantees that a man-in-the-middle attacker can't read the
content of a successfully negotiated encrypted connection, nor
alter the content in any way other than truncating it, unless he
compromises the session keys or one of the key-exchange secret
keys used to establish that connection. Let's make sure we do at
least that well.
Suppose that a client Alice connects to an MITM attacker Mallory,
thinking that she is connecting to some server Bob. Let's assume
that the TLS handshake between Alice and Mallory finishes
successfully and the v3 protocol is chosen. [If the v1 or v2
protocol is chosen, those already resist MITM. If the TLS
handshake doesn't complete, then Alice isn't connected to anybody.]
During the v3 handshake, Mallory can't convince Alice that she is
talking to Bob, since she should not be able to produce a CERT
cell containing a certificate chain signed by Bob's identity key
and used to authenticate the link key that Mallory used during
TLS. (If Mallory used her own link key for the TLS handshake, it
won't match anything Bob signed unless Bob is compromised.
Mallory can't use any key that Bob _did_ produce a certificate
for, since she doesn't know the private key.)
Even if Alice fails to check the certificates from Bob, Mallory
still can't convince Bob that she is really Alice. Assuming that
Alice's keys aren't compromised, Mallory can't send a CERT cell
with a cert chain from Alice's identity key to a key that Mallory
controls, so if Mallory wants to impersonate Alice's identity
key, she can only do so by sending an AUTHENTICATE cell really
generated by Alice. Because Bob will check that the random bytes
in the AUTH_CHALLENGE cell will influence the SLOG hash, Mallory
needs to send Bob's challenge to Alice, and can't use any other
AUTHENTICATE cell that Alice generated before. But because the
AUTHENTICATE cell Alice will generate will include in the SCERT
field a hash of the link certificate used by Mallory, Bob will
reject it as not being valid to connect to him.
6.4. Protocol downgrade attacks won't work.
Assuming that Alice checks the certificates from Bob, she knows
that Bob really sent her the VERSION cell that she received.
Because the AUTHENTICATE cell from Alice includes signed hashes
of the VERSIONS cells from Alice and Bob, Bob knows that Alice
got the VERSIONS cell he sent and sent the VERSIONS cell that he
received.
But what about attempts to downgrade the protocol earlier in the
handshake? Here TLS comes to the rescue: because the TLS
Finished handshake message includes an authenticated digest of
everything previously said during the handshake, an attacker
can't replace the client's ciphersuite list (to trigger a
downgrade to the v1 protocol) or the server's certificate [chain]
(to trigger a downgrade to the v1 or v2 protocol).
7. Design considerations
I previously considered adding our own certificate format in
order to avoid the pain associated with X509, but decided instead
to simply use X509 since a correct Tor implementation will
already need to have X509 code to handle the other handshake
versions and to use TLS.
The trickiest part of the design here is deciding what to stick
in the AUTHENTICATE cell. Some of it is strictly necessary, and
some of it is left there for security margin in case my other
security arguments fail. Because of the CID and SID elements
you can't use an AUTHENTICATE cell for anything other than
authenticating a client ID to a server with an appropriate
server ID. The SLOG and CLOG elements are there mostly to
authenticate the VERSIONS cells and resist downgrade attacks
once there are two versions of this. The presence of the
AUTH_CHALLENGE field in the stuff authenticated in SLOG
prevents replays and ensures that the AUTHENTICATE cell was
really generated by somebody who is reading what the server is
sending over the TLS connection. The SCERT element is meant to
prevent MITM attacks. When the TLSSECRET field is
used, it should prevent the use of the AUTHENTICATE cell for
anything other than the TLS connection the client had in mind.
A signature of the TLSSECRET element on its own should also be
sufficient to prevent the attacks we care about. The redundancy
here should come in handy if I've made a mistake somewhere else in
my analysis.
If the client checks the server's certificates and matches them
to the TLS connection link key before proceding with the
handshake, then signing the contents of the AUTH_CHALLENGE cell
would be sufficient to authenticate the client. But implementers
of allegedly compatible Tor clients have in the past skipped
certificate verification steps, and I didn't want a client's
failure to verify certificates to mean that a server couldn't
trust that he was really talking to the client. To prevent this,
I added the TLS link certificate to the authenticated data: even
if the Tor client code doesn't check any certificates, the TLS
library code will still check that the certificate used in the
handshake contains a link key that matches the one used in the
handshake.
8. Open questions:
- 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.
- With which TLS libraries is it feasible to yoink client_random,
server_random, and the master secret? If the answer is "All
free C TLS libraries", great. If the answer is "OpenSSL only",
not so great.
- Should we do anything to check the timestamp in the AUTHENTICATE
cell?
- 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 stick with V1. Eventually we can
deprecate the V2 handshake as we did with the V1 handshake.
When that happens, servers can be V3-only.