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

[George Kadianakis]

Nick Mathewson <nickm at alum.mit.edu> writes:

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