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

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

(Have a look at what's in ed25519 vs curve25519.)

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

> 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.
1a) Wouldn't it be cool if regular nodes could also have an offline signing key?
1b) Some of the same analysis here would seem to apply for authority
ECC migration and router ECC migration.
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.

2) Make sure to come up with some kind of scheme for eventually
dropping RSA keys.

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.

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

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.


yrs,
-- 
Nick