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>
I also like the idea of keeping tinc fast for low-powered devices. Of
course I think security should come first.
I run tinc on routers running 3rd party firmware TomatoUSB. Below are
the speed test results running the latest OpenSSL version with the asm
optimizations that exist for mips.
This was run on an Asus RT-N16.
OpenSSL 1.0.1e 11 Feb 2013
built on: Sat Sep 14 11:48:11 MDT 2013
options:bn(64,32) rc4(ptr,char) des(idx,cisc,16,long) aes(partial)
idea(int) blowfish(ptr)
compiler: mipsel-linux-gcc -fPIC -DOPENSSL_PIC -DOPENSSL_THREADS
-D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -DL_ENDIAN -DTERMIO -O3
-mtune=mips32 -mips32 -fomit-frame-pointer -Wall -DSHA1_ASM -DSHA256_ASM
-DAES_ASM
sign verify sign/s
verify/s
521 bit ecdsa (nistp521) 0.0191s 0.0995s 52.4 10.1
571 bit ecdsa (nistk571) 0.1139s 0.4976s 8.8 2.0
op op/s
521 bit ecdh (nistp521) 0.0832s 12.0
571 bit ecdh (nistk571) 0.2463s 4.1
On Sat, Sep 14, 2013 at 10:25:31AM +0200, Guus Sliepen wrote:> 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.I have created a utility called "sptps_speed" which tests the speed of various ECC operations, the number of SPTPS connections you can create per second, and the throughput of data on SPTPS connections. It is now part of the 1.1 branch in git. At the moment it only works on Linux though (due to the use of some less portable time functions). I also created a branch called 1.1-brainpool, which uses the 512 bit Brainpool curve instead of the 521 bit NIST curve. I ran the benchmark using both curves, and operations using the Brainpool curve are a factor 5 slower. I found out that the main reason they are slower is that OpenSSL, when compiled with the right options, contains optimized routines for the NIST curves, for those CPUs which support efficient 128 bit arithmetic operations. These routines were not enabled in Debian wheezy (nor in earlier releases, I presume), and running sptps_speed with the unoptimized routines will show that the NIST curve operations are slightly slower than the Brianpool curve (which is likely just because the NIST curve is slightly bigger). The results from 4 different machines, using OpenSSL 1.0e with the ec_nistp_64_gcc_128 option enabled: Intel Atom 330, 1.6 GHz secp521r1 brainpoolp512r1 ------------------------------------------------------------------- Generating keys for 10 seconds: 358.05 op/s 79.35 op/s ECDSA sign for 10 seconds: 283.61 op/s 75.50 op/s ECDSA verify for 10 seconds: 117.49 op/s 64.75 op/s ECDH for 10 seconds: 90.83 op/s 37.32 op/s SPTPS authenticate for 10 seconds: 43.05 op/s 17.99 op/s SPTPS transmit for 10 seconds: 79.72 Mbit/s 80.49 Mbit/s AMD Phenom II X4 965, 3.4 GHz ----------------------------- Generating keys for 10 seconds: 3372.31 op/s 620.81 op/s ECDSA sign for 10 seconds: 2528.65 op/s 572.68 op/s ECDSA verify for 10 seconds: 1156.60 op/s 496.38 op/s ECDH for 10 seconds: 917.37 op/s 287.61 op/s SPTPS authenticate for 10 seconds: 419.87 op/s 137.65 op/s SPTPS transmit for 10 seconds: 336.96 Mbit/s 336.74 Mbit/s Intel Core i3-3220T, 2.8 GHz ---------------------------- Generating keys for 10 seconds: 3475.43 op/s 603.47 op/s ECDSA sign for 10 seconds: 2496.11 op/s 545.96 op/s ECDSA verify for 10 seconds: 1178.88 op/s 481.76 op/s ECDH for 10 seconds: 959.02 op/s 277.01 op/s SPTPS authenticate for 10 seconds: 427.49 op/s 132.20 op/s SPTPS transmit for 10 seconds: 543.64 Mbit/s 540.05 Mbit/s Intel Core i7-3960X, 3.3 GHz ---------------------------- Generating keys for 10 seconds: 4151.82 op/s 738.11 op/s ECDSA sign for 10 seconds: 3034.75 op/s 677.21 op/s ECDSA verify for 10 seconds: 1418.88 op/s 584.20 op/s ECDH for 10 seconds: 1157.84 op/s 328.61 op/s SPTPS authenticate for 10 seconds: 517.64 op/s 160.81 op/s SPTPS transmit for 10 seconds: 787.99 Mbit/s 783.57 Mbit/s So, I extrapolate from the results of "openssl speed" that people sent in, that using the Brainpool curve: GuruPlug: ARM9E, 1.2 GHz: 5 authentications/s Asus RT-N16: MIPS 74K, 480 MHz: 3 authentications/s AMD Athlon, 667 MHz: 9 authentications/s -- 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/20130915/22a9cd50/attachment.sig>
> 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.On a Nanos G20: folkert at time5:~$ openssl speed ecdsap521 ecdsak571 ecdhp521 ecdhk571 Doing 521 bit sign ecdsa's for 10s: 120 521 bit ECDSA signs in 5.00s Doing 521 bit verify ecdsa's for 10s: 23 521 bit ECDSA verify in 5.02s Doing 571 bit sign ecdsa's for 10s: 28 571 bit ECDSA signs in 5.07s Doing 571 bit verify ecdsa's for 10s: 7 571 bit ECDSA verify in 5.62s Doing 521 bit ecdh's for 10s: 28 521-bit ECDH ops in 5.13s Doing 571 bit ecdh's for 10s: 13 571-bit ECDH ops in 5.11s OpenSSL 1.0.1e 11 Feb 2013 built on: Mon Mar 18 21:53:12 UTC 2013 options:bn(64,32) rc4(ptr,char) des(idx,cisc,16,long) aes(partial) blowfish(ptr) compiler: gcc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4 -Wformat -Werror=format-security -D_FORTIFY_SOURCE=2 -Wl,-z,relro -Wa,--noexecstack -Wall sign verify sign/s verify/s 521 bit ecdsa (nistp521) 0.0417s 0.2183s 24.0 4.6 571 bit ecdsa (nistk571) 0.1811s 0.8029s 5.5 1.2 op op/s 521 bit ecdh (nistp521) 0.1832s 5.5 571 bit ecdh (nistk571) 0.3931s 2.5 folkert at time5:~$ cat /proc/cpuinfo Processor : ARM926EJ-S rev 5 (v5l) BogoMIPS : 197.01 Features : swp half thumb fastmult edsp java CPU implementer : 0x41 CPU architecture: 5TEJ CPU variant : 0x0 CPU part : 0x926 CPU revision : 5 Hardware : NanosG20 Revision : 0000 Serial : 0000000000000000 Raspberry PI model B: folkert at incontrol ~ $ openssl speed ecdsap521 ecdsak571 ecdhp521 ecdhk571 Doing 521 bit sign ecdsa's for 10s: 686 521 bit ECDSA signs in 9.78s Doing 521 bit verify ecdsa's for 10s: 129 521 bit ECDSA verify in 9.99s Doing 571 bit sign ecdsa's for 10s: 87 571 bit ECDSA signs in 8.05s Doing 571 bit verify ecdsa's for 10s: 25 571 bit ECDSA verify in 7.95s Doing 521 bit ecdh's for 10s: 148 521-bit ECDH ops in 9.77s Doing 571 bit ecdh's for 10s: 63 571-bit ECDH ops in 9.93s OpenSSL 1.0.1e 11 Feb 2013 built on: Sun Mar 24 12:44:00 UTC 2013 options:bn(64,32) rc4(ptr,char) des(idx,cisc,16,long) aes(partial) blowfish(ptr) compiler: gcc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4 -Wformat -Werror=format-security -D_FORTIFY_SOURCE=2 -Wl,-z,relro -Wa,--noexecstack -Wall -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DAES_ASM -DGHASH_ASM sign verify sign/s verify/s 521 bit ecdsa (nistp521) 0.0143s 0.0774s 70.1 12.9 571 bit ecdsa (nistk571) 0.0925s 0.3180s 10.8 3.1 op op/s 521 bit ecdh (nistp521) 0.0660s 15.1 571 bit ecdh (nistk571) 0.1576s 6.3 folkert at incontrol ~ $ cat /proc/cpuinfo processor : 0 model name : ARMv6-compatible processor rev 7 (v6l) BogoMIPS : 2.00 Features : swp half thumb fastmult vfp edsp java tls CPU implementer : 0x41 CPU architecture: 7 CPU variant : 0x0 CPU part : 0xb76 CPU revision : 7 Hardware : BCM2708 Revision : 000e Serial : 00000000475466e5 Folkert van Heusden -- www.TrustedTimestamping.com is a service that enables you to show that at a certain point in time, you had access to a hash-value reflecting the contents of a file (this file can be a word document, a jpeg image, everything). ---------------------------------------------------------------------- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
There has been a recent discussion on debian-devel on this subject:
RSA vs ECDSA (Was: Bits from keyring-maint: Pushing keyring updates. Let us
bury your old 1024D key!)
In particular:
* http://thread.gmane.org/gmane.linux.debian.devel.announce/1893/focus=191567
We can read that 4096-bit RSA should be preferred over ECDSA.
http://safecurves.cr.yp.to/ does not list P-521 but there's no reason to
think it does not have any flaw of other NIST curves. E-521 may be a better
choice but it seems too new.
Then I wonder: would it be possible to choose the algo to use in the new tinc
protocol ?
(BTW, when testing ExperimentalProtocol=yes, I was surprised to see that tincd
refuses to start if there's no private RSA key)
* http://thread.gmane.org/gmane.linux.debian.devel.announce/1893/focus=191567
How is ECDSA used in Tinc ? It seems a proper implementation is to not rely on
a RNG, as described by RFC 6979.
About performance:
sign verify sign/s verify/s
521 bit ecdsa (nistp521) 0.0005s 0.0012s 1891.0 829.8
rsa 4096 bits 0.010225s 0.000164s 97.8 6100.3
I guess Tinc uses both operations equally, so RSA would be slower.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL:
<http://www.tinc-vpn.org/pipermail/tinc/attachments/20140325/158a223e/attachment.sig>