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