augmenting RSA identities/signatures with ECC and beyond
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. 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. 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? All the best, Jacob
On Sat, Aug 3, 2013 at 9:29 PM, Jacob Appelbaum <jacob@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
Nick Mathewson:
On Sat, Aug 3, 2013 at 9:29 PM, Jacob Appelbaum <jacob@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
On Sat, Aug 3, 2013 at 10:59 PM, Jacob Appelbaum <jacob@appelbaum.net> wrote:
Nick Mathewson:
On Sat, Aug 3, 2013 at 9:29 PM, Jacob Appelbaum <jacob@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
participants (2)
-
Jacob Appelbaum -
Nick Mathewson