Elliptic curves in tinc

[Guus Sliepen]

In the past 24 hours multiple persons have contacted me regarding the use of
elliptic curve cryptography in tinc 1.1 in light of the suspicion that the NSA
might have weakened algorithms and/or elliptic curves published by NIST. 

The new protocol in tinc 1.1 (SPTPS) uses ECDH and ECDSA to do session key
exchange and authentication, in such a way that it has the perfect forward
secrecy (PFS) property. For both the ephemeral keys used in ECDH and the
long-lived keys used for ECDSA, tinc uses the "secp521r1" curve, as published
by NIST. There are suspicions in the cryptographic community that the NSA has
influenced the EC standards so they contain weaknesses that the NSA supposedly
could exploit. There are two concerns I have heard of:

1) The Dual_EC_DRBG algorithm, which uses elliptic curve cryptography to create
   a pseudo random number generator (PRNG), might be flawed. NIST has since issued
   a recommendation that this algorithm should not be used anymore. Tinc does NOT
   use this algorithm.

2) The curves secp???r1 have been generated using parameters that are not
   explained, and hence these curves might have some flaws that make them weaker
   than intended. Tinc uses the secp521r1 curve.

Personally, I think that the NSA would not compromise curves that are
recommended for encryption of government data, as the risk that a foreign
country finds out about their weaknesses would then gain an advantage in
decrypting US government data. However, I might be wrong.

Some suggestions have been made for alternative curves. The first one is that,
instead of using the NIST curves defined over a prime field, one could use
those defined over a binary field (sect???k1). The drawback is that, at least
in OpenSSL, operations on those curves are an order of magnitude slower than on
a prime field curve.

The second is using Daniel J. Bernstein's Curve25519. This curve allows very
fast operations, however it only has a strength of 255 bits, and as far as I
know, only ECDH operations are well-defined on this curve, but ECDSA is not.
Note that tinc requires at least 512 bit curves in order to allow 256 bit
strength for the symmetric encryption.

There are also other groups which have found and defined elliptic curves, such
as ECC Brainpool, which has defined a 512 bit curve. I have not tried out this
curve myself, and I don't know how well their curves have been scrutinized by
the cryptographic community.

Another option would be to try to generate our own curve. However, I have no
idea what pitfalls there are when doing that.

If any of you have well informed suggestions to make about elliptic curves,
please let me know. I'm subscribed to the randombit.net and metzdowd.com
cryptography mailing lists, so anything you hear there you don't have to
repeat. I would certainly switch curves if the new one is not less suspect than
the secp curves, and if it allows at least a few ECDH or ECDSA operations per
second on low-powered devices. By the way, if you are running tinc on
low-powered devices, please run "openssl speed ecdsap521 ecdsak571 ecdhp521
ecdhk571" and send me the results.

-- 
Met vriendelijke groet / with kind regards,
     Guus Sliepen <guus at tinc-vpn.org>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://www.tinc-vpn.org/pipermail/tinc/attachments/20130914/107d09c6/attachment.sig>