Draft of proposal "Migrate HS identity keys to Ed25519"
Greetz, I'm posting the draft of a proposal that specifies how to upgrade the identity keys of HSes (currently RSA-1024) to use Ed25519. This proposal is supposed to go along with a proposal that specifies how to hide HS descriptors from HSDirs. I'm going to post that second proposal in a few minutes. This proposal is incredibly drafty in the sense that I might have forgotten to specify things that need to be specified. On the other hand, "release early; release often" they say, so here it goes. Inlining: Filename: xxx-hs-ecc-id-keys.txt Title: Migrate HS identity keys to Ed25519 Author: George Kadianakis Created: 10 August 2013 Target: 0.2.5.x Status: Draft [More draft than Guiness.] 0. Overview: This proposal suggests the adoption of ECDSA keys as the long-term identity keys of Hidden Services. It also proposes the adoption of ECDSA keys for the per-introduction-point service key that was introduced in the v2 hidden service protocol. This proposal specifies the key generation procedure, paths where the keys should be stored, and flagday/migration procedures. XXX 1. Motivation: Hidden Services currently use an RSA-1024 keypair as their long-term identity keys. RSA-1024 is considered weak and should be replaced. Dan Bernstein's ed25519 ECDSA scheme provides 2^128 bits of security and better signature performance than RSA. Furthermore, the keysize is much smaller than the keys of RSA. 2. Related proposals This document is part of a proposal triptych. Upcoming sister proposals are: - "Stop HS address enumeration by HSDirs", where we propose an alternative HS descriptor format that will not allow HSDirs to learn the addresses of the Hidden Services it serves. - "Deployment strategy for recent HS proposals", where we specify how these proposals should be deployed without making people angry. 3. Changes to the current HS protocol 3.0. Overview of changes to the current HS protocol There are two places where RSA-1024 is used in the current HS: Longterm RSA-1024 "identity keys" are used by the HSes to authenticate themselves to clients. Multiple short-term RSA-1024 "service keys" are used by the HSes for each introduction point so that they don't reveal their identity key. This proposal specifies: a) The generation of the new ed25519 long-term identity keys and service keys (#KEYGEN) b) The new HS descriptor format (v3) that contains identity keys and service keys (#NEWDESC) c) A way for clients to upload and fetch v3 descriptors from HSDirs (#HSDIRV3) 3.1. Generation of ed25519 keypairs (#KEYGEN) 3.1.0. Generation of long-term ed25519 identity key Compliant Hidden Services need to generate a fresh ed25519 keypair and store the private key in: $HiddenServiceDirectory/hs_ed25519_privkey For deployment and migration reasons, the new ed25519 keys must be kept alongside with the old RSA-1024 keys. 3.1.1. Generation of short-term ed25519 service keys Hidden Services generate an ed25519 service key for each introduction point -- instead of the RSA-1024 key they currently generate. 3.2. New v3 Hidden Service descriptors 3.2.0. New v3 Hidden Service Descriptor Format (#NEWDESC) v2 Hidden Service descriptors contain both the long-term identity public key of the Hidden Service, and service keys for each introduction point. It also contains a signature of the descriptor. We need to change all these fields to carry our brand new ed25519 keys. For v3 Hidden Service descriptors, we keep the v2 format and perform the following changes: [*] The "permanent-key" field is replaced by "permanent-key-ed25519": "permanent-key-ed25519" NL an ed25519 public key [Exactly once] The public key of the hidden service which is required to verify the "descriptor-id" and the "signature-ed25519". In base64 format with terminating =s removed. [*] The "service-key" field is replaced by "service-key-ed25519': "service-key-ed25519" NL an ed25519 public key [Exactly once] The public key that can be 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" NL signature-string [At end, exactly once] A signature of all fields above with the private ed25519 key of the hidden service. In base64 format with terminating =s removed. 3.2.1. Uploading v3 HS descriptors to HSDirs (#HSDIRV3) A new type of Hidden Service Directory Server must be established which understands 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". (This part of the proposal conflicts with the "Stop HS address enumeration by HSDirs" proposal.) 3.3. Fetching v3 HS descriptors from HSDirs (#HSDIRV3) 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>". (This part of the proposal conflicts with the "Stop HS address enumeration by HSDirs" proposal) 3.4. Service keys and INTRODUCE cells In INTRODUCE cells, when v2 descriptors are used, PK_ID is defined as the hash of the service key. This means that we don't need to change the format of INTRODUCE cells since we can just use the hash of the ed25519 service key. # XXX will this cause problems?
George Kadianakis <desnacked@riseup.net> writes:
Greetz,
I'm posting the draft of a proposal that specifies how to upgrade the identity keys of HSes (currently RSA-1024) to use Ed25519.
This proposal is supposed to go along with a proposal that specifies how to hide HS descriptors from HSDirs. I'm going to post that second proposal in a few minutes.
This proposal is incredibly drafty in the sense that I might have forgotten to specify things that need to be specified. On the other hand, "release early; release often" they say, so here it goes.
Inlining:
Filename: xxx-hs-ecc-id-keys.txt Title: Migrate HS identity keys to Ed25519
<snip>
3.1.1. Generation of short-term ed25519 service keys
Hidden Services generate an ed25519 service key for each introduction point -- instead of the RSA-1024 key they currently generate.
Since we are upgrading the service keys, we might also need to upgrade the RELAY_COMMAND_ESTABLISH_INTRO cell so that it can carry the new service keys. Maybe we can add a <key type> field to a new RELAY_COMMAND_ESTABLISH_INTRO_2 cell? Or we can use the current cell type, but try to distinguish between old-style and new-style service keys.
On Fri, Aug 16, 2013 at 10:29 AM, George Kadianakis <desnacked@riseup.net> wrote:
Greetz,
I'm posting the draft of a proposal that specifies how to upgrade the identity keys of HSes (currently RSA-1024) to use Ed25519.
This proposal is supposed to go along with a proposal that specifies how to hide HS descriptors from HSDirs. I'm going to post that second proposal in a few minutes.
This proposal is incredibly drafty in the sense that I might have forgotten to specify things that need to be specified. On the other hand, "release early; release often" they say, so here it goes.
Thanks! Let me know once you think it should get a number. I've made some initial comments inline below.
Filename: xxx-hs-ecc-id-keys.txt Title: Migrate HS identity keys to Ed25519 Author: George Kadianakis Created: 10 August 2013 Target: 0.2.5.x Status: Draft
[More draft than Guiness.]
0. Overview:
This proposal suggests the adoption of ECDSA keys as the long-term identity keys of Hidden Services. It also proposes the adoption of ECDSA keys for the per-introduction-point service key that was introduced in the v2 hidden service protocol.
This proposal specifies the key generation procedure, paths where the keys should be stored, and flagday/migration procedures. XXX
Not yet it doesn't. ;)
1. Motivation:
Hidden Services currently use an RSA-1024 keypair as their long-term identity keys. RSA-1024 is considered weak and should be replaced.
Dan Bernstein's ed25519 ECDSA scheme provides 2^128 bits of security and better signature performance than RSA. Furthermore, the keysize is much smaller than the keys of RSA.
Also, 80-bit onion identifiers are just too short. See also proposals 220 and 216.
2. Related proposals
This document is part of a proposal triptych. Upcoming sister proposals are:
- "Stop HS address enumeration by HSDirs", where we propose an alternative HS descriptor format that will not allow HSDirs to learn the addresses of the Hidden Services it serves.
I think that perhaps these should become one proposal. In other words, we shouldn't support both formats; we should just support *this* format as modified by the "stop address enumeration proposal. (Rationale: why not?)
- "Deployment strategy for recent HS proposals", where we specify how these proposals should be deployed without making people angry.
Think instead in terms of balancing the security/annoyance tradeoff. We're always going to make _somebody_ angry any time we breaking backward compatibility, but that's no excuse for perpetuating RSA-1024. :)
3. Changes to the current HS protocol
3.0. Overview of changes to the current HS protocol
There are two places where RSA-1024 is used in the current HS:
Longterm RSA-1024 "identity keys" are used by the HSes to authenticate themselves to clients.
Multiple short-term RSA-1024 "service keys" are used by the HSes for each introduction point so that they don't reveal their identity key.
These service keys are also used for _encrypting_ the information sent in INTRODUCE cells.
This proposal specifies: a) The generation of the new ed25519 long-term identity keys and service keys (#KEYGEN)
b) The new HS descriptor format (v3) that contains identity keys and service keys (#NEWDESC)
c) A way for clients to upload and fetch v3 descriptors from HSDirs (#HSDIRV3)
3.1. Generation of ed25519 keypairs (#KEYGEN)
3.1.0. Generation of long-term ed25519 identity key
Compliant Hidden Services need to generate a fresh ed25519 keypair and store the private key in: $HiddenServiceDirectory/hs_ed25519_privkey
Generally, it's not part of the specification to say where you store the keys. Our specs are usually about the protocol, not the implementation.
For deployment and migration reasons, the new ed25519 keys must be kept alongside with the old RSA-1024 keys.
1) I'm not sure I believe this paragraph, but since nothing about migration has been specified, I'll hold off on judgment.
3.1.1. Generation of short-term ed25519 service keys
Hidden Services generate an ed25519 service key for each introduction point -- instead of the RSA-1024 key they currently generate.
Will this work? The service key is used to sign the ESTABLISH_INTRO cell. Let me suggest another approach: Instead of a single RSA-1024 service key for each intro point, we generate two keys: a curve25519 encryption key for handling the INTRODUCE cell(s), and an ESTABLISH_INTRO key whose type will be Ed25519 on introduction points that support that, and RSA-1024 on older intro points. That way we can continue using all existing nodes as introduction points.
3.2. New v3 Hidden Service descriptors
3.2.0. New v3 Hidden Service Descriptor Format (#NEWDESC)
v2 Hidden Service descriptors contain both the long-term identity public key of the Hidden Service, and service keys for each introduction point. It also contains a signature of the descriptor. We need to change all these fields to carry our brand new ed25519 keys.
For v3 Hidden Service descriptors, we keep the v2 format and perform the following changes.
Let's try to use the same format, so far as possible, as is currently suggested in prop220. That would mean using a space rather than a newline between keywords and keys/signatures, for example.
[*] The "permanent-key" field is replaced by "permanent-key-ed25519":
"permanent-key-ed25519" NL an ed25519 public key
[Exactly once]
The public key of the hidden service which is required to verify the "descriptor-id" and the "signature-ed25519".
In base64 format with terminating =s removed.
Perhaps we should prove ownership of service keys by having them cross-sign the permanent key or something? (Also, remember that signing and encryption aren't the same any more, so we might need two keys here.)
[*] The "service-key" field is replaced by "service-key-ed25519':
"service-key-ed25519" NL an ed25519 public key
[Exactly once]
The public key that can be 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" NL signature-string
[At end, exactly once]
A signature of all fields above with the private ed25519 key of the hidden service.
In base64 format with terminating =s removed.
3.2.1. Uploading v3 HS descriptors to HSDirs (#HSDIRV3)
A new type of Hidden Service Directory Server must be established which understands 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".
(This part of the proposal conflicts with the "Stop HS address enumeration by HSDirs" proposal.)
So let's kill it?
3.3. Fetching v3 HS descriptors from HSDirs (#HSDIRV3)
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>".
What is "<z>" at this point?
(This part of the proposal conflicts with the "Stop HS address enumeration by HSDirs" proposal)
So let's kill it too?
3.4. Service keys and INTRODUCE cells
In INTRODUCE cells, when v2 descriptors are used, PK_ID is defined as the hash of the service key. This means that we don't need to change the format of INTRODUCE cells since we can just use the hash of the ed25519 service key.
I believe that we will. INTRODUCE cells start with a PK_ID that must correspond to the public key used to sign the ESTABLISH_INTRO cell. So with existing introduction points, that key must be an RSA key. With new ones, we need a new INTRODUCE1 format -- ideally, one not involving SHA1 (because seriously). Second, the handshake in the INTRODUCE2 cells specifies the rendezvous point by its IPv4 address and port, its RSA ID, and its RSA onion key. It negotiates a key using a g^x value for a 1024-bit diffie hellman handshake. And it encrypts the whole thing to an RSA service key, using a somewhat broken hybrid encryption mechanism. Every last thing there is broken, deprecated, or in some way problematic. To specify the introduction point (in the descriptor) rendezvous point (in INTRODUCE2), we should include all of the stuff currently allowed in EXTEND2 cells to specify a node, including the additions of proposal 220. The handshake itself should be done with curve25519, not with 1024-bit GP_p. The hybrid encryption should use curve25519 and should not be malleable. (In other words, use the curve25519 handshake result to derive a MAC key and an encryption key, and encrypt-then-mac the plaintext.) best wishes, -- Nick
Nick Mathewson <nickm@alum.mit.edu> writes:
On Fri, Aug 16, 2013 at 10:29 AM, George Kadianakis <desnacked@riseup.net> wrote:
Greetz,
<SNIP>
(This part of the proposal conflicts with the "Stop HS address enumeration by HSDirs" proposal)
So let's kill it too?
3.4. Service keys and INTRODUCE cells
In INTRODUCE cells, when v2 descriptors are used, PK_ID is defined as the hash of the service key. This means that we don't need to change the format of INTRODUCE cells since we can just use the hash of the ed25519 service key.
I believe that we will.
INTRODUCE cells start with a PK_ID that must correspond to the public key used to sign the ESTABLISH_INTRO cell. So with existing introduction points, that key must be an RSA key. With new ones, we need a new INTRODUCE1 format -- ideally, one not involving SHA1 (because seriously).
Second, the handshake in the INTRODUCE2 cells specifies the rendezvous point by its IPv4 address and port, its RSA ID, and its RSA onion key. It negotiates a key using a g^x value for a 1024-bit diffie hellman handshake. And it encrypts the whole thing to an RSA service key, using a somewhat broken hybrid encryption mechanism. Every last thing there is broken, deprecated, or in some way problematic.
To specify the introduction point (in the descriptor) rendezvous point (in INTRODUCE2), we should include all of the stuff currently allowed in EXTEND2 cells to specify a node, including the additions of proposal 220.
The handshake itself should be done with curve25519, not with 1024-bit GP_p.
The hybrid encryption should use curve25519 and should not be malleable. (In other words, use the curve25519 handshake result to derive a MAC key and an encryption key, and encrypt-then-mac the plaintext.)
Hm, I think we should zoom out a bit and try to figure out what we want to change. We all know that Hidden Services need lots of attention. The crypto needs to improve (upgrade keys to other cryptosystems, fix hybrid encryption, etc.) and the protocol needs to improve (make hidden services scale, oblivious transfer for HS descriptors, prevent DoS attacks, valet services, etc.). IMO, to properly fix Hidden Services someone needs to think of the big picture and write a "Next generation Hidden Services" paper/essay that proposes new protocols and addresses most of the known problems. Then, after we know how these new changes influence each other, we can start writing proposals and figuring out implementation and deployment strategies. Unfortunately, even though I know that some people are thinking about this, I'm not sure if we will see such a paper soon (within the next months). Personally, I started writing these two proposals because: a) They would address two problems I care about. The fact that HS addresses are leaked to HSDirs, and the fact that 80 bits are not enough to make HS addresses secure against an impersonating adversary. b) Fixes should be implementable and deployable "soon" (next 18 months or so). c) Fixes are orthogonal to a large part of the HS protocol. d) Fixes might also be applicable after a "next gen hs" system is proposed. That is, HSes won't need to change addresses again. After reading your comments on this proposal, I realised that my decision to also change the IP service keys complicated the proposal considerably. Now we also need to incorporate a cryptosystem capable of encryption (curve25519), we need to fix the INTRODUCE2 cell format, and we also need to fix our hybrid encryption to use curve25519 (and not be malleable). OTOH, if we remove the service key part from the scope of this proposal, it gets simpler to implement and easier to reason about. In the future, we can still change the service keys in a completely orthogonal manner to this proposal. I'm not sure what we should do. I think we should figure out how much stuff we want to change at this time: * Should we change nothing, stay still and wait for the "next gen hs" paper that might never arrive? * Should we change a few things we care about (keysize, #9001 etc.) and leave the rest for the "next gen hs" paper? * Or maybe we should start incrementally fixing everything we can and think again when we read the "next gen hs" paper? * Or maybe something else? (I guess we should also speak with our researchers friends and see whether any of them are actually planning to write such a paper or whether we are on our own.)
On 08/31/2013 09:28 AM, George Kadianakis wrote:
We all know that Hidden Services need lots of attention. The crypto needs to improve (upgrade keys to other cryptosystems, fix hybrid encryption, etc.) and the protocol needs to improve (make hidden services scale, oblivious transfer for HS descriptors, prevent DoS attacks, valet services, etc.).
IMO, to properly fix Hidden Services someone needs to think of the big picture and write a "Next generation Hidden Services" paper/essay that proposes new protocols and addresses most of the known problems. Then, after we know how these new changes influence each other, we can start writing proposals and figuring out implementation and deployment strategies. Unfortunately, even though I know that some people are thinking about this, I'm not sure if we will see such a paper soon (within the next months).
FYI, we just started a project on improving hidden service protocol. I am working on ticket #8510 so we can first set up tools to profile hidden service traffic. That said, we are probably not going to publish a paper within the next months ;p -- qp
On Sat, Aug 31, 2013 at 9:28 AM, George Kadianakis <desnacked@riseup.net> wrote: [...]
I'm not sure what we should do. I think we should figure out how much stuff we want to change at this time: * Should we change nothing, stay still and wait for the "next gen hs" paper that might never arrive?
* Should we change a few things we care about (keysize, #9001 etc.) and leave the rest for the "next gen hs" paper?
* Or maybe we should start incrementally fixing everything we can and think again when we read the "next gen hs" paper?
* Or maybe something else?
My thought is that we should write the best hidden services designs and specifications that we currently can figure out how to write, figure out what we _don't_ know how to write in it, and then decide whether that merits delay or not. We should also try to guess how compatible/incompatible what we don't know how to do will be with what we *do* know how to do, and have that influence or decisions too. There could be a fine "next gen hs" design paper in the works, or there might not, but IMO indefinite delay is a bad idea. yrs, -- Nick
participants (3)
-
George Kadianakis -
Nick Mathewson -
Qingping Hou