[tor-dev] Transitioning to new crypto (again, but with substance)

[Watson Ladd]

Dear all,
After thinking hard about the issues involved with new cryptography in
Tor I came to the following idea for a somewhat reasonable upgrade
path for OP's and OR's that preserves everyone's privacy and security
at all points (to the extent that this is possible: new connections
are by new clients). The only issue is what actually goes out on the
wire needs to be though through.

First note that the connection between the identity used to ensure
EXTEND cells go over canonical connections and the keys actually
presented by two OR's that have formed a connection can be pretty much
arbitrary: it isn't necessary for the client to know what it is. So we
could have each OR have an identity key that stays 1024 bit RSA for
old ORs while newer ORs trust some snazzy new elliptic curve key,
while using the same 1024 bits to form the identity. Note that if we
use elliptic curves to secure the endpoints,(and don't mind
incompatibility with old clients) the RSA key doesn't even need to be
an RSA key.

Also note that the Tor directory spec permits new types of lines. In
particular we could have a curve-ident-key line  and a curve-onionkey
line each containing base-64 encoded keys, and a curve-sig line that's
a signature of the rest of the entry, except for the RSA signature.
The RSA signature would be as normal. To an old client this looks
exactly like an old style directory entry. To a new client this looks
like the elliptic curve key is the root of trust. This is OK: fiddling
with an RSA signature doesn't let you fool a new client into thinking
things about identities, because the identity is derived from the RSA
key which is signed with the curve-ident-key. The onion-key is trusted
by both the curve-ident-key and the RSA identity key. It is still
possible to selectively invalidate one signature, but that signature
is the RSA signature: the curve-ident-signature is also covered by the
RSA signature. This would have the effect of ensuring that only new
clients can connect to the OR: we could require that new clients still
check the RSA signature to prevent this.

Lastly comes the problem of EXTEND cells. All the OR before the new
extension has to do is copy what is given to it without caring about
the version. To signal versions we can just use length: 64 bytes vs.
128 bytes. Sadly this signals what version a client is, but an OR can
guess anyway by how it was connected to if it lists both descriptors.

One thing I have not taken on is the use of the new keys in the TLS
negotiations.We could extend the CERTS and AUTH cells to include them
as possible types, and this is possibly the best solution. I also
haven't addressed the problem of UDP transport: TLS has issues where
instead of sending another packet to be processed by the next router
it resends a dropped packet, holding up the queue.
I've probably missed a lot of issues here, but hopefully this moves
the conversation forward.
Sincerely,
Watson Ladd