Filename: 248-removing-rsa-identities.txt Title: Remove all RSA identity keys Authors: Nick Mathewson Created: 15 August 2015 Status: Draft
1. Summary
With 0.2.7.2-alpha, all relays will have Ed25519 identity keys. Old identity keys are 1024-bit RSA, which should not really be considered adequate. In proposal 220, we describe a migration path to start using Ed25519 keys. This proposal describes an additional migration path, for finally removing our old Ed25519 keys.
See also proposal 245, which describes a migration path away from the old TAP RSA1024-based circuit extension protocol.
1.1. Steps of migration
Phase 1. Prepare for routers that do not advertise their RSA identities, by teaching clients and relays and other dependent software how to handle them. Reject such routers at the authority level.
Phase 2. Once all supported routers and clients are updated to phase 1, we can accept routers at the authority level which lack RSA keys.
Phase 3. Once all authorities accept routers without RSA keys, we can finally remove RSA keys from relays.
2. Accepting descriptors without RSA identities
We make the following changes to the descriptor format:
If an ed25519 key and signature are present, then these elements may be omitted: "fignerprint", "signing-key", "router-signature". They must either be all present or all absent. If they are all absent, then the router has no RSA identity key.
Authorities MUST NOT accept routers descriptors of this form in phase 1.
3. Accepting handshakes without RSA identities
When performing a new version of our link handshake, only the Ed25519 key and certificates and authentication need to be performed. If the link handshake is performed this way, it is accepted as authenticating the route with an ed25519 key but no RSA key.
A circuit extension EXTEND2 cell may contain an Ed25519 identity but not an RSA identity. In this case, the relay should connect the circuit to any connection with the correct ed25519 identity, regardless of RSA identity. If an EXTEND2 cell contains an RSA identity fingerprint, however, its the relay receiving it should not connect to any relay that has a different RSA identity or that has no identity, even if the Ed25519 identity does match.
4. UI updates
In phase 1 we can update our UIs to refer to all relays that have Ed25519 keys by their Ed25519 keys. We can update our configuration and control port interfaces so that they accept Ed keys as well as RSA keys.
During phase 1, we should warn about identifying any dual-identity relays by their Ed identity alone.
For backward compatibility, we should consider a default that refers to referring to Ed25519 relays by the first 160 bits of their key. This would allow many controller-based tools to work transparently with the new key types.
5. Changes to external tools
This is the big one. We need a relatively comprehensive list of tools we can break with the above changes. Anything that refers to relays by SHA1(RSA1024_id) will need to be able to remember and use an Ed25519 key instead.
5. Testing
Before going forward with phase 2 and phase 3, we need to verify that we did phase 1 correctly. To do so, we should create a small temporary testing network, and verify that it works correctly as we make the phase 2 and phase 3 changes.
On Wed, Jul 15, 2015 at 01:37:06PM -0400, Nick Mathewson wrote:
Filename: 248-removing-rsa-identities.txt Title: Remove all RSA identity keys Authors: Nick Mathewson Created: 15 August 2015 Status: Draft
Summary
With 0.2.7.2-alpha, all relays will have Ed25519 identity keys. Old identity keys are 1024-bit RSA, which should not really be considered adequate. In proposal 220, we describe a migration path to start using Ed25519 keys. This proposal describes an additional migration path, for finally removing our old Ed25519 keys.
Did you mean "RSA" in that last phrase?
For backward compatibility, we should consider a default that refers to referring to Ed25519 relays by the first 160 bits of their key. This would allow many controller-based tools to work transparently with the new key types.
Hmmm. What trouble could one make by choosing an Ed25519 key that starts with another router's 160-bit fingerprint (or the first 160 bits of another router's Ed25519 key)? I wonder what the complexity is of finding a valid private/public key Ed25519 pair where the public part starts with a given 160 bits. I would not be surprised if the answer were 2^80. I guess that's about the complexity of factoring the RSA-1024 key in the first place, but I wouldn't want to encourage controllers to stick with displaying only 160 bits of the key once the RSA keys are deprecated.
- Ian
Ian Goldberg:
On Wed, Jul 15, 2015 at 01:37:06PM -0400, Nick Mathewson wrote:
Filename: 248-removing-rsa-identities.txt Title: Remove all RSA identity keys Authors: Nick Mathewson Created: 15 August 2015 Status: Draft
Summary
With 0.2.7.2-alpha, all relays will have Ed25519 identity keys. Old identity keys are 1024-bit RSA, which should not really be considered adequate. In proposal 220, we describe a migration path to start using Ed25519 keys. This proposal describes an additional migration path, for finally removing our old Ed25519 keys.
Did you mean "RSA" in that last phrase?
For backward compatibility, we should consider a default that refers to referring to Ed25519 relays by the first 160 bits of their key. This would allow many controller-based tools to work transparently with the new key types.
Hmmm. What trouble could one make by choosing an Ed25519 key that starts with another router's 160-bit fingerprint (or the first 160 bits of another router's Ed25519 key)? I wonder what the complexity is of finding a valid private/public key Ed25519 pair where the public part starts with a given 160 bits. I would not be surprised if the answer were 2^80.
Interesting. You might be right about this being 2^80 if there is some odd shortcut using the high-order bits for the DLP instead of a pure collision. I think you'd lose what you need to do the algebra for easy stuff like Shanks or Pollards, but who knows.
However, if this 160-bit number is always a SHA1 (or SHA256-prefix) hash in both the ed25519 case and the RSA case, then this should become equivalent to a collision attack on SHA1 if you want two keys to collide, or a pre-image attack if you want to collide with a pre-existing relay's identity.
To me, this does say that if we're worried about odd DLP/ECC identity gymnastics, hashing the relay identity first is better?
I guess that's about the complexity of factoring the RSA-1024 key in the first place, but I wouldn't want to encourage controllers to stick with displaying only 160 bits of the key once the RSA keys are deprecated.
Such a collision is also detectable by tor-core, since tor-core knows the full 256bit identifier internally, regardless of what the controller does. In fact, Tor can easily check every single consensus for colliding 160bit identity values for ed25519 relays.
Therefore, in the interest of preserving backwards compatibility, I think it would be better if Tor just shouted loudly at controllers who try to use a short 160bit identity that is known to collide in the current consensus, rather than simply break all of them irrevocably before this even happens.
As the Tor releases roll on (or perhaps even immediately), the code could change to use increasingly harder forms of error upon 160bit collision (like asserts). But there seems to be no real reason to break all the old code before we actually spot a collision in a consensus (which again, we can determine in the field on the fly at any time).
On Wed, Jul 15, 2015 at 7:54 PM, Ian Goldberg iang@cs.uwaterloo.ca wrote:
On Wed, Jul 15, 2015 at 01:37:06PM -0400, Nick Mathewson wrote:
Filename: 248-removing-rsa-identities.txt Title: Remove all RSA identity keys Authors: Nick Mathewson Created: 15 August 2015 Status: Draft
Summary
With 0.2.7.2-alpha, all relays will have Ed25519 identity keys. Old identity keys are 1024-bit RSA, which should not really be considered adequate. In proposal 220, we describe a migration path to start using Ed25519 keys. This proposal describes an additional migration path, for finally removing our old Ed25519 keys.
Did you mean "RSA" in that last phrase?
Yes; will fix.
For backward compatibility, we should consider a default that refers to referring to Ed25519 relays by the first 160 bits of their key. This would allow many controller-based tools to work transparently with the new key types.
Hmmm. What trouble could one make by choosing an Ed25519 key that starts with another router's 160-bit fingerprint (or the first 160 bits of another router's Ed25519 key)? I wonder what the complexity is of finding a valid private/public key Ed25519 pair where the public part starts with a given 160 bits. I would not be surprised if the answer were 2^80. I guess that's about the complexity of factoring the RSA-1024 key in the first place, but I wouldn't want to encourage controllers to stick with displaying only 160 bits of the key once the RSA keys are deprecated.
Would you imagine we could boost the difficult of this to a nice safe 2^160 by using e.g. the first 160 bits of a SHA256 hash of the Ed25519 key?
On 16 Jul 2015, at 03:37 , Nick Mathewson nickm@torproject.org wrote:
For backward compatibility, we should consider a default that refers to referring to Ed25519 relays by the first 160 bits of their key.
Typo: "refers to referring to"
- Changes to external tools
This is the big one. We need a relatively comprehensive list of tools we can break with the above changes. Anything that refers to relays by SHA1(RSA1024_id) will need to be able to remember and use an Ed25519 key instead.
What does "remember and" mean here? Do you mean "remember to use Ed25519 and"?
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com pgp ABFED1AC https://gist.github.com/teor2345/d033b8ce0a99adbc89c5
teor at blah dot im OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7
- Changes to external tools
This is the big one. We need a relatively comprehensive list of tools we can break with the above changes. Anything that refers to relays by SHA1(RSA1024_id) will need to be able to remember and use an Ed25519 key instead.
What does "remember and" mean here? Do you mean "remember to use Ed25519 and"?
I think it means "remember Ed25519 key and use it instead".
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com pgp ABFED1AC https://gist.github.com/teor2345/d033b8ce0a99adbc89c5
teor at blah dot im OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
On 22 Jul 2015, at 22:58 , rl1987 rl1987@sdf.lonestar.org wrote:
- Changes to external tools
This is the big one. We need a relatively comprehensive list of tools we can break with the above changes. Anything that refers to relays by SHA1(RSA1024_id) will need to be able to remember and use an Ed25519 key instead.
What does "remember and" mean here? Do you mean "remember to use Ed25519 and"?
I think it means "remember Ed25519 key and use it instead".
Thanks, my English parser was confused by the line break.
Once I read your explanation, I can't see how I could have missed it.
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com pgp ABFED1AC https://gist.github.com/teor2345/d033b8ce0a99adbc89c5
teor at blah dot im OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7
-
Ian Goldberg -
Mike Perry -
Nick Mathewson -
Nick Mathewson -
rl1987 -
teor