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

[Jacob Appelbaum]

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?

> 
> (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?

>> I tend to think that every directory authority should generate an
>> additional and new long term ECC identity key. This will require that
>> tor-gencert is extended to understand both ECC and RSA. We'll want to
>> add these fingerprints to src/or/config.c for each respective DA.
>>
>> We'll want each directory authority to sign with both RSA and ECC. We'll
>> also want to extend the consensus format to handle publication of such
>> signatures. Older clients should be able to parse the consensus without
>> worry and they will check RSA signatures as always. Newer clients should
>> check both and report a mismatch into the logs at a high level. When
>> combined with ntor, I believe that we will have significantly improved
>> the cryptography in Tor.
> 
> Agreed.
> 
> (Let's just cut to the chase and specify ed25519 as the signature algorithm.)
> 

Sounds fine with me.

>> It would be nice to be able to add other signature schemes -
>> specifically for pq crypto related undertakings. In an ideal world, I'd
>> like to be able to sign the consensus from my directory authority with
>> RSA, ECC and some kind of djb approved, tanja tested post-quantum
>> computer signature construct.
>>
>> 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.

> 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?

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.

> 
> 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.

> 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?

> 
> 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. :)

All the best,
Jake