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

[Nick Mathewson]

On Wed, Jul 15, 2015 at 7:54 PM, Ian Goldberg <iang at 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
>>
>> 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?

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?