[tor-dev] Proposal 248: Remove all RSA identity keys

[Mike Perry]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20150715/90750b88/attachment-0001.sig>