[tor-dev] [draft] Proposal 220: Migrate server identity keys to Ed25519

[Nick Mathewson]

On Tue, Aug 13, 2013 at 4:25 PM, Maxim Kammerer <mk at dee.su> wrote:
> On Tue, Aug 13, 2013 at 4:13 AM, Nick Mathewson <nickm at torproject.org>
> wrote:
>>
>>    Ed25519 (specifically, Ed25519-SHA-512 as described and specified at
>>    http://ed25519.cr.yp.to/) is a desirable choice here: it's secure,
>>    fast, has small keys and small signatures, is bulletproof in several
>>    important ways, and supports fast batch verification. (It isn't quite
>>    as fast as RSA1024 when it comes to public key operations, since RSA
>>    gets to take advantage of small exponents when generating public
>>    keys.)
>
>
> At the risk of invoking something that was already discussed to death (and I
> was not aware): why not go with something established like P-521 that would
> apparently be a drop-in replacement with OpenSSL? Are the benefits really
> worth it?

P-521 isn't a signature scheme; it's a group.  You can do signatures
using that group if you pick a signature algorithm.  The one that
OpenSSL supports is ECDSA.

I'm not a big fan of this approach, for a few reasons:

Security:
   * DSA, according to its standard, requires a strong random number
generator for each signature, and fails catastrophically in the
presence of small RNG failures.  This turns out to be a crappy idea in
practice. RFC6979 explains more about why, and suggests a good
alternative. Ed25519 uses this alternative.
   * To the best of my knowledge, the OpenSSL ECDSA implementations
don't run in constant time on all platforms.  Trying to make
non-constant-time crypto code side-channel free is exciting! I'd
rather have a well-tested set of boring, constant-time
implementations.

Performance:
   * Neither P521 nor P256 is a terribly well optimized group for
software implementations.  (See
https://www.imperialviolet.org/2010/12/21/eccspeed.html for a
comparison of ECDH in P256, P521, and the curve25519 group.  The
comparison is for DH, not DSA, but the results are similar when you're
comparing ECDSA-P256, ECDSA-P521, and Ed25519.)
   * OpenSSL's ECDSA code doesn't support batch verification: that's
another big performance hit!

I'd seriously recommend the Ed25519 paper to anybody curious about
more details.  It discusses its decisions in some depth, explains more
advantages than I can do here, and and chasing its references is a fun
way to learn things about crypto.  It's not "scary weird crypto" --
it's just another Schnorr-like signature variant in an EC group over a
prime field.

(I'm a little surprised that nobody has suggested something genuinely
scary and weird, like that Multivariate-Quadratic-Quasigroups stuff.)

best wishes,
-- 
Nick