On Tue, Aug 13, 2013 at 4:25 PM, Maxim Kammerer mk@dee.su wrote:
On Tue, Aug 13, 2013 at 4:13 AM, Nick Mathewson nickm@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,