[tor-dev] augmenting RSA identities/signatures with ECC and beyond

[Nick Mathewson]

On Sat, Aug 3, 2013 at 10:59 PM, Jacob Appelbaum <jacob at appelbaum.net> wrote:
> Nick Mathewson:
>> On Sat, Aug 3, 2013 at 9:29 PM, Jacob Appelbaum <jacob at appelbaum.net> wrote:
>>> Hi,
>>>
>>> Linus and I had an interesting discussion at IETF 87 this past week in
>>> Berlin. We're both concerned about long term Directory Authority
>>> identity keys as well consensus signing with RSA keys.
>>>
>>> We've agreed that we're interested in writing a proposal whereby we add
>>> additional identity keys for authorities. Thus, we'll have whatever
>>> security may be provided by RSA and the security that should be provided
>>> by ECC signatures. The work on ntor should directly assist us in having
>>> almost all the required crypto we'll need for such augmentation.
>>
>> Well, the ntor stuff should be orthogonal, right?  A good curve25519
>> implementation has some of what you'd need for implementing
>> signatures, but not all.
>
> Do you feel good about using djb's ed25519 code from SUPERCOP or should
> we just plan to use it in NaCL?

Well, the NaCl release with a proper ed25519 implementation isn't out
yet.  So if we're to have an ed25519 implementation without waiting,
we'll need to look for one.

I'm not inclined to ship assembly, so we'd want to pick one or more of
the C (or C-with-GCC-extensions, or C-with-simd-intrinsics)
implementations.  I've got some thoughts on that, but IMO picking out
the implementation now is orthogonal to writing all the proposals.

In addition to the supercop code, have a look at
   https://github.com/floodyberry/ed25519-donna
as a promising-looking C implementation.

>> (Have a look at what's in ed25519 vs curve25519.)
>>
>
> Do you think we'll want to create src/ext/ed25519 and put inside as I
> suspect?

Probably.

 [...]
>>> What do you think we should consider as we draft this proposal?
>>
>> 1) We'll want to also migrate to ed25519 for regular nodes' identity keys.
>
> I would like to consider this as part of a different proposal.

Yes, sorry, that's the idea.  I'm working on a "migrate node IDs"
proposal, and you can do this one, and if they're done around the same
time, we can than take a pass to

>> 1a) Wouldn't it be cool if regular nodes could also have an offline signing key?
>
> Yes.
>
>> 1b) Some of the same analysis here would seem to apply for authority
>> ECC migration and router ECC migration.
>
> I agree.
>
>> 1c) I've actually started writing up a proposal for this.  Let's do
>> our drafts independently, and then see which ideas each can borrow
>> from the other once it's done.
>
> Do you think yours is larger in scope than what I proposed in my
> previous email?

Yes indeed.

> My thought is that we can add ~eight new identity keys quite easily and
> eight new upgrades, which could happen in any order as no client will
> use it until they're all doing it - we might even put on implementing
> using those keys on the client side for a bit.

I agree with that as far as it goes, but remember that "there are only
three numbers in software: zero, one, and infinity."  In other words,
the hard part isn't going to be getting the authorities onboard
one-by-one or getting the routers to upgrade: it's going to be the
design and implementation.

>> 2) Make sure to come up with some kind of scheme for eventually
>> dropping RSA keys.
>>
>
> I'd like to keep RSA around actually - I like the idea of composing
> their security properties. When RSA signatures are busted at some point
> in the future, we'll be better off for having ECC in the mix - removing
> RSA doesn't give us the same security returns. Especially if we find
> that the ECC code has a subtle bug. I suspect that there is nearly no
> overhead of consequence for DA or clients if we design it right.

This might be the case -- we might never actually want to drop the RSA
support -- but we should nonetheless have a migration plan away from
it that we *can* follow if we choose to. We should actually plan a few
steps ahead with this kind of stuff.

>> 3) The current way that directory documents are signed is suboptimal.
>> Ideally, we'd want something that required almost zero parsing before
>> you could check its signatures.  I wonder if we can move in that
>> direction without breaking the existing format somehow.
>
> I agree. I have some ideas but I also think that this is out of scope
> for the proposal size that  we discussed at the IETF.
>
>> 4) Identity keys and signing keys should cross-certify one another.
>> (That is, RSA-identity, RSA-signing, ECC-identity, and ECC-signing
>> should all cross-certify.)
>
> Don't we effectively achieve a similar level of security for identity
> keys by simply having them built into the Tor binary at compile time,
> given that the cross signature is implicitly over the data they sign
> every hour?

No; we get cross-certification of authority identity keys by signing
keys by including those identity keys in the signed consensus.  (And
we certify signing keys with individual identity keys by using
authority certificates.)

>>
>> 5) One thing that concerns me here is that when you have two parallel
>> signature schemes, it's comparatively easy to come up with documents
>> that old clients will accept but which new clients will reject.  We
>> should analyze how bad this would be, and what we could do to mitigate
>> it.
>>
>
> I agree. However - I'm not sure that I am ready to suggest how clients
> will behave. I want to suggest at this time a proposal where we might
> create the network consensus documents. We could then use a diverse set
> of ways to verify the data that is the Tor network. What we do after the
> verification process seems a bit more than I was hoping to tackle in
> this proposal. :)

Here I need to disagree.  Designing a signature system without
figuring out the client behavior is just plain broken.  If we don't
know what the client behavior is (or even if there *is* a sensible
client behavior), we can't know that we have the right authority
behavior.

That said, it's fine for the first draft to leave client behavior
sketchy.  Just -- we can't call the proposal done, or merge any
implementation, unless we know what the clients are actually going to
do.


peace,
-- 
Nick