Re: [tor-dev] Draft of proposal "Migrate HS identity keys to Ed25519"

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,