release early; release often again
This is a draft of a proposal that merges the two proposals I posted last month, namely the "Migrate HS identity keys to Ed25519" and "Stop HS address enumeration by HSDirs" proposals.
This goes together with the "Migration to ed25519 HS identity keys and privacy-preserving directory documents" I posted two weeks ago.
It tried to address most of the comments from Nick and Matthew. There are still lots of stuff to fix (especially the key derivation part).
Inlining:
Filename: xxx-hs-id-keys-and-onion-leaking.txt Title: On upgrading HS identity keys and on a new HS directory scheme that does not leak Author: George Kadianakis Created: 10 August 2013 Target: 0.2.5.x Status: Draft
[More draft than Guiness.]
ToC:
0. Overview 1. Motivation 2. Related proposals 3. Overview of changes 4. Specification of changes 5. Discussion 6. Acknowledgments
Appendix: A0. Security proof of directory scheme
---
0. Overview:
This proposal has two aims:
a) Improve the strength of HS identity keys.
Specifically, this proposal suggests the adoption of Ed25519 ECDSA keys as a replacement for the RSA-1024 keys that are currently in use by hidden services.
b) Stop HS address enumeration by HSDirs
When a client asks for the descriptor of a hidden service the hidden service address is leaked to the HSDir that was inquired. This proposal suggests a new directory scheme that prevents HSDirs from learning the hidden service address or the contents of the hidden service descriptors they serve.
1. Motivation
The long-term identity keys of Hidden Services are RSA-1024 keys; we consider these weak and in need for replacement. Furthermore, 80-bit hidden service addresses are short enough to be prone to brute-force impersonation attacks.
Ed25519 (specifically, Ed25519-SHA-512 as described and specified at http://ed25519.cr.yp.to/) is a good alternative: it's secure, fast, has small keys and small signatures, is bulletproof in several important ways, and supports fast batch verification. (It isn't quite as fast as RSA1024 when it comes to public key operations, since RSA gets to take advantage of small exponents when generating public keys.)
2. Related proposals
This proposal goes hand in hand with proposal XXX "On the migration to Ed25519 HS identity keys and privacy-preserving directory documents". Proposal XXX specifies how the schemes described in this proposal should be deployed in the real Tor network to minimize frustration and bad vibes.
XXX Another related proposal is proposal XXX "On the upgrade of Hidden Service service keys" which defines the upgrade from the current RSA-1024 HS service keys to a more powerful cryptosystem.
3. Overview of changes
This section provides a high-level overview of the changes suggested in this document.
3.0. Overview of identity-key changes
Longterm RSA-1024 "identity keys" are used by hidden services to authenticate themselves to clients.
This proposal specifies: * The generation of new Ed25519 long-term identity keypairs (#KEYGEN) * A new HS descriptor format (v3) that contains Ed25519 HS identity keys (#NEWDESC) * A way for clients to upload and fetch v3 descriptors from HSDirs (#DESCFETCH and #DESCUPLOAD)
3.1. Overview of anti-enumeration scheme
Currently, Hidden Services upload their unencrypted descriptor to hidden service directories (HSDirs). HSDirs store the unencrypted descriptor in an internal map of: <hs address> -> <hs descriptor> When a client wants the descriptor of an HS, it asks an HSDir for the descriptor that corresponds to <hs address>. If the HSDir has such an index in its map, it returns the <hs descriptor> to the client.
This proposal asks Hidden Services to periodically derive a new ephemeral keypair from their long-term identity key; the new keypair being a function of the identity key and a time-dependent nonce. The derivation should be one-way; if you know the identity key you should be able to derive the ephemeral key but not the other way around. Finally, a client should be able to derive the ephemeral HS public key from the long-term HS public key without knowing the long-term HS private key (#KEYPAIRDERIVATION)
Hidden Services then encrypt their descriptor with a symmetric key (derived from the long-term identity public key) and sign the ciphertext and the ephemeral public key with their ephemeral private key (#NEWDESC). Then they place the ephemeral public key, the encrypted descriptor and the signature in a v3 hidden servide descriptor and send that to the HSDir (#DESCUPLOAD).
When the HSDir receives a v3 hidden service descriptor, it validates the signature using the embedded ephemeral public key and if it verifies it stores the descriptor in an internal map of: <ephemeral public key> -> <v3 descriptor> (#DESCHANDLING).
Now, out of band, the HS gives to its clients a <z>.onion address. <z> in this case is the long-term public key of the HS (this is different from the current situation where <z> is the hash of the long-term public key).
A client that knows the <z>.onion address and wants to acquire the HS descriptor, derives the <ephemeral public key> of the HS using <z> and the same key derivation procedure that the HS uses. She also derives the symmetric key that decrypts the encrypted HS descriptor (#KEYPAIRDERIVATION).
The client then contacts the appropriate HSDir and queries it for the descriptor with index <ephemeral public key>. If the HSDir has such an index in its internal map it passes the <v3 descriptor> to the client (#DESCFETCH).
The client then verifies the signature of the v3 descriptor, and if it's legit she decrypts the encrypted descriptor using the ephemeral symmetric key. The client now has the Hidden Servide descriptor she was looking for (#DESCHANDLING).
4. Specificaton of changes
4.0 Generation of long-term identity-key Ed25519 keypairs (#KEYGEN)
When a hidden service starts up with no Ed25519 identity keys, it generates a new identity keypair.
4.1. Ephemeral keypair derivation (anti-enumreation) (#KEYPAIRDERIVATION)
XXX Leaving this unpsecified for now till the security proof comes along.
4.1.0. By Hidden Services:
For now, let's assume that after this paragraph each HS has a per-TIME_PERIOD ephemeral keypair. It also has a symmetric key derived from the identity public key to encrypt its descriptor.
4.1.1. By clients:
When a Tor client is asked to connect to a hidden service address <z>.onion, it assumes that <z> is the long-term public key of the hidden service. Internally, and without notifying the user, the Tor client generates the ephemeral public key and ephemeral symmetric key of the HS for that time period (using the long-term public key of the hidden service and the procedure specified in the previous section).
4.2. New v3 Hidden Service Descriptor Format (#NEWDESC)
To serve the purposes of this proposal we need to perform multiple modifications to hidden service descriptors. Specifically, to migrate to new identity keys we need to change the format of the v2 Hidden Service descriptor to use Ed25519 keys. Furthermore, to provide enumeration protection we need to encrypt the whole descriptor with the ephemeral symmetric key.
To do so we define a new construct just for this section, called "intermediate descriptor". It has the same format as a v2 hidden service descriptor but uses Ed25519 instead of RSA-1024. The following changes are performed to the v2 HS descriptor:
[*] The "permanent-key" field is replaced by "permanent-key-ed25519":
"permanent-key-ed25519" SP an Ed25519 public key
[Exactly once]
The public key of the hidden service which is required to verify the "descriptor-id" and "signature-ed25519".
In base64 format with terminating =s removed.
[*] The "service-key" field is replaced by "service-key-ed25519':
"service-key-ed25519" SP an Ed25519 public key
[Exactly once]
The public key used to encrypt messages to the hidden service.
In base64 format with terminating =s removed.
[*] The "signature" field is replaced by "signature-ed25519':
"signature-ed25519" SP signature-string
[At end, exactly once]
A signature of all fields above using the private Ed25519 key of the hidden service.
In base64 format with terminating =s removed.
Now we define the format of the new v3 Hidden Service descriptor that is uploaded to the HSDirs:
"ephemeral-public-key" SP public-key
[At start, exactly once]
The ephemeral HS public key for this time period.
In base64 format with terminating =s removed.
"encrypted-descriptor" SP encrypted-descriptor
[Exactly once]
An encrypted intermediate descriptor (as specified above).
It's encrypted with AES in CTR mode with a random initialization vector of 128 bits that is written in the beginning of the encrypted string. The ephemeral symmetric key derived in section XXX is used as the secret key of AES.
The encrypted string is encoded in base64 and surrounded with "-----BEGIN MESSAGE-----" and "-----END MESSAGE-----".
"publication-time" SP YYYY-MM-DD HH:MM:SS NL
[Exactly once]
A timestamp when this descriptor has been created. It should be rounded down to the nearest day. The timestamp SHOULD be used by the clients and HSDirs to discard old descriptors.
XXX Should we specify how long the HSDir is supposed to keep the descriptor? rend-spec.txt doesn't do so.
XXX Is "rounded down to the nearest day" too extreme of a rounding? Other Tor documents round it down to the nearest hour. Does it matter if our expiration time is longer than a day?
XXX Should we kill the "publication-time" in the HS descriptors? Or just leave it there?
"signature" SP signature
[At end, exactly once]
A signature of all fields above using the ephemeral private key of the hidden service.
In base64 format with terminating =s removed.
4.3. Uploading v3 HS descriptors to HSDirs (#DESCUPLOAD)
A new type of Hidden Service Directory Server must be established which knows how to handle v3 Hidden Service descriptors.
The Hidden Service follows the same publishing procedure as for v2 descriptors but instead of sending an HTTP 'POST' to "/tor/rendezvous2/publish", the HS sends the 'POST' request to "/tor/rendezvous3/publish" with the descriptor included in the body of the 'POST'.
4.4. Fetching v3 HS descriptors from HSDirs (#DESCFETCH)
When a client needs to fetch a v3 Hidden Service Descriptor from an HSDir, it follows the exact same procedure as for v2 descriptors but instead of sending an HTTP 'GET' to "/tor/rendezvous2/<z>", it sends an HTTP 'GET' to "/tor/rendezvous3/<z>" where <z> is the base32 encoding of the *ephemeral* public key of the Hidden Service.
XXX base32 is used because it's URL-safe and because we don't really care about the extra length.
XXX example?
4.5. v3 hidden servide descriptor handling (#DESCHANDLING)
4.5.1. By HSDirs:
When an HSDir receives a v3 hidden service descriptor, it verifies its signature using the ephemeral public key that was included in the descriptor. If the signature verifies and the descriptor timestamp is reasonable, the descriptor is accepted and cached. Otherwise, the descriptor is discarded.
4.5.2. By clients:
When a client receives a v3 hidden service descriptor, it checks the timestamp and verifies the signature using the previously derived keys and discards it if the signature was not proper.
If the signature is proper, the client uses the derived ephemeral symmetric key to decrypt the 'encrypted-descriptor' part of the metadescriptor.
5. Discussion
[Points here might deserve their own sections]
Do we need the HSDir hash ring, even though the HS address and the descriptor are now hidden from HSDirs?
An Ed25519 public key is 32 bytes. 32 bytes in base32 encoding is 56 characters (or 52 with the '=' padding removed). Do we want a different URL encoding or are we happy with addresses like: mfrggzdfmztwq2lknnwg23tpobyxe43uov3ho6dzpjaueq2eivda.onion ?
6. Acknowledgments
The cryptography behind this proposal was originally proposed by Robert Ransom in a private email thread and subsequently posted in tor-dev [0]. Discussion was continued in trac ticket #8106 [1].
During the past 6 months many bright people have looked at the cryptography behind this scheme. The list of people includes Nadia Heninger, Leonid Reyzin, Nick Hopper, Aggelos Kiayias, Tanja Lange, Dan J. Bernstein and probably others that I can't recall at this point. Thanks!
Parts of this proposal has been based on discussions with Nick Mathewson and his proposal 220.
XXX "One more: Christian Grothoff told me in Garching that GNUnet does something quite similar for its keys. So we should probably check out their approach too, and include them in the "related work" section of any hypothetical publication here. :)"
Appendix:
A0. Security proof of directory scheme
XXX A security proof of the above scheme is under development. We are not going to implement or deploy anything before we have a solid proof of this.