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?