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

[Nick Mathewson]

On Fri, Aug 16, 2013 at 10:29 AM, George Kadianakis
<desnacked at 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