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 > > > > 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. > > 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). -- Mike Perry
Attachment:
signature.asc
Description: Digital signature
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev