[zeromq-dev] Considerations about Elliptic Curve algorithms

Laurent Alebarde l.alebarde at free.fr
Wed Sep 18 09:29:01 CEST 2013

Quotes from tinc Digest Vol 107 Issue 9 (I have bolded the interesting 
parts. Daniel J. Bernstein's Curve25519 is also discussed) :

ECDSA curve used in new protocol has suspicious seed value
De :
Markus Teufelberger <markusteufelberger at gmail.com>
Date :
14/09/2013 04:53

Pour :
tinc at tinc-vpn.org

Hi there,

As I'm sure you are aware, *there are suspicions (as usual) against the 
NSA potentially weakening crypto around the globe*. This time it is 
about a cipher that is/will be used in the new tinc protocol: ECDSA

According to 
https://github.com/gsliepen/tinc/blob/1.1/src/openssl/ecdsagen.c you use 
the secp521r1 curve, which is derived (according to 
http://www.secg.org/collateral/sec2_final.pdf - page 18) from the seed 
value "D09E8800 291CB853 96CC6717 393284AA A0DA64BA". There is suspicion 
around, that this seed value might weaken a ECDSA curve (as it is not 
explained where it actually comes from and how/why it was selected) to 
an attack not yet known to the public, chosen potentially by brute force 
to make this attack easier.

Unfortunately, there is no alternative curve defined for these key sizes 
in Fp, as far as I'm aware (for 256 bits, one could use secp256k1 for 
example, which does not use an unexplained seed value), so this is 
mainly a heads-up and maybe a request to change to any widely accepted 
curve that might emerge in the future for that key size.

I don't know enough about ECDSA to give any more input than: The next 
largest Koblitz-curve would be sect571k which still has 256 bit 
strength, maybe it would be possible to use this one. I'll let people 
more intimate with crypto in general, openssl in particular and tinc 
sort this out though, since it uses a different finite field (F2^m).

Stay safe and thank you for tinc,


Elliptic curves in tinc
De :
Guus Sliepen <guus at tinc-vpn.org>
Date :
14/09/2013 10:25

Pour :
tinc at tinc-vpn.org, tinc-devel at tinc-vpn.org

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>

tinc mailing list
tinc at tinc-vpn.org

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.zeromq.org/pipermail/zeromq-dev/attachments/20130918/713e13eb/attachment.htm>

More information about the zeromq-dev mailing list