Hey Niels and other Nettle folks--
Have you given any thought about adding elliptic curve cryptography to nettle as another public-key algorithm?
There are many references for elliptic curve online (i confess i'm not up on the implementation details), including:
http://www.secg.org/?action=docs_secg
and OpenSSL, libecc, sks-ecc, and libcrypto++ have free implementations that might be worth perusing for reference or for comparison / test suites:
http://libecc.sourceforge.net/
It would be great to have a GPL-compatible, C implementation of ECC, and nettle seems like a good fit.
Any thoughts, plans, or concerns about this?
--dkg
On Mon, Dec 20, 2010 at 5:37 PM, Daniel Kahn Gillmor dkg@fifthhorseman.net wrote:
Hey Niels and other Nettle folks--
Have you given any thought about adding elliptic curve cryptography to nettle as another public-key algorithm?
There are many references for elliptic curve online (i confess i'm not up on the implementation details), including:
http://www.secg.org/?action=docs_secg
and OpenSSL, libecc, sks-ecc, and libcrypto++ have free implementations that might be worth perusing for reference or for comparison / test suites: ... http://www.cryptopp.com/ ... Any thoughts, plans, or concerns about this?
All (or nearly all) Crypto++ files are in public domain, without licensing restrictions. But its a c++ library.
Jeff
Daniel Kahn Gillmor dkg@fifthhorseman.net writes:
Any thoughts, plans, or concerns about this?
I'd consider adding elliptic curve cryptography, if I get some reasonably authoritative information on some variant of ecc which is (1) useful, and (2) not patented, or patented with gpl compatible licensing.
I'm not very familiar with ecc, but my understanding is that the entire area is more or less a patent swamp, and that technically, ecc cryptography mostly makes sense in some embedded devices where small keys and signatures are important, or where modexp based cryptography is too slow.
As for performance of ecc, I suspect there are two main issues: The first is what to believe in regards to what security level you get for small ecc key sizes. The second is that I expect it will take quite some effort to do sliding window ecc exponentiation which is as well tuned as gmp's modexp (but maybe that code can be borrowed from other libraries).
I realize I'm sounding quite a bit negative. I'll be more positive if I get some clear answers to the above issues (which spec to implement, patents situation, ecc usecases, expected performance); as I said I'm not very familiar with ecc details.
Regards, /Niels
On 12/21/2010 04:24 AM, Niels Möller wrote:
which spec to implement,
Well, for my purposes, i'd start with the curves slated for use in the upcoming OpenPGP ECC extension:
https://tools.ietf.org/html/draft-jivsov-openpgp-ecc-06#section-4
I think this has allows for conformance to the NSA's Suite B recommendations, for whatever that's worth.
patents situation,
Unfortunately, the patent system seems to be such that even if i were a patent lawyer (i am not, fortunately), i could make no iron-clad guarantees. The best i can offer is a sort of suggestive inference:
In addition to the list of other free implementations of ECC i started this thread with, it looks like NSS ("netscape security services", the crypto toolkit supporting firefox and its peers) has been shipping on major distros with ECC support not only in source, but enabled for over a year now:
http://bugs.debian.org/490826 https://bugs.launchpad.net/ubuntu/+source/nss/+bug/232392
libgcrypt is also about to add ECC support, according to a recent conversation on the libgcrypt mailing list. This should result in gpg 2.1 having ECC when it releases.
Anyway, this is no guarantee that there aren't patent trolls lurking, but there are certainly some tastier/deeper-pocket/higher-profile targets who don't seem to have been attacked on account of shipping functional ECC implementations.
ecc usecases,
As you mentioned, embedded devices and devices (like smartphones) with metered or severely limited connectivity will all benefit from the reduced keysize. Also, attacks against traditional asymmetric crypto are expected to continue apace, and expected power of machinery will keep improving; so tools that use RSA and DSA will need to keep expanding keysize to keep up. ECC offers a chance to stay within the current overhead size for a while longer still.
expected performance
sorry, i don't have good figures for this, but i'd be happy to help you set up performance comparisons with other free implementations if you're interested in that.
--dkg
On Tue, Dec 21, 2010 at 7:12 PM, Daniel Kahn Gillmor dkg@fifthhorseman.net wrote:
On 12/21/2010 04:24 AM, Niels Möller wrote:
which spec to implement,
Well, for my purposes, i'd start with the curves slated for use in the upcoming OpenPGP ECC extension:
https://tools.ietf.org/html/draft-jivsov-openpgp-ecc-06#section-4
I think this has allows for conformance to the NSA's Suite B recommendations, for whatever that's worth.
I think Daniel is on the right track by choosing standardized domain parameter support. When using standard parameters, you only have to choose your private key and publish the public key. In this case, RFC 5114 - Additional Diffie-Hellman Groups for Use with IETF Standards (et al), would also be of interest.
If you want to offer a full blown EC implementation, you will need to implement domain parameter generation. The tricky part of custom curves is the pointing counting to ensure the curve meets the requisite security level. I don't believe OpenSSL offers domain parameter generation, and I know Crypto++ does not offer domain parameter generation.
When I need a custom curve due to relaxed security requirements, I use Marcel Martin's Elliptic Curve Builder. Martin implemented the point counting algorithms to ensure the group order meets requirements. The way I use ECB with Crypto++ can be found at http://www.cryptopp.com/wiki/Elliptic_Curve_Builder.
If you look at IEEE/IETF/ISO-IEC/NESSIE/NIST/NSA/{Favorite Standards Body} support as a base implementation in Nettle, then think of domain parameter generation as incremental.
patents situation,
Unfortunately, the patent system seems to be such that even if i were a patent lawyer (i am not, fortunately), i could make no iron-clad guarantees.
Offload the responsibility on the users of the library, seek counsel from the FSF, or consult with an outside attorney.
I am not aware of Certicom ever bringing suit against users, developers or libraries. Most likely, you will not have to worry about Certicom since persuing a lawsuit would be a waste of time and money for the company. The only technology company that appears to voraciously assert its rights against folks like users and developers is Apple.
For those interested, Certicom, which holds many EC patents and is owned by RIM, lost a few "slam dunk" cases recently. The events caused paralysis in RIM's legal department to the point where the sales team has not inked a license in over a year. When I inquired about licensing over the summer, I was told to go to RSA Data Securities even though RSA is probably violating Certicom. The fellow who advised me worked for Certicom.
Jeff
Daniel Kahn Gillmor dkg@fifthhorseman.net writes:
patents situation,
Unfortunately, the patent system seems to be such that even if i were a patent lawyer (i am not, fortunately), i could make no iron-clad guarantees. The best i can offer is a sort of suggestive inference:
I'm aware that there are no guarantees. I think a reasonable requirement for implementing a new algorithm (ecc or otherwise) is that at least all known patent holders license related patents on royalty-free (and otherwise GPL compatible) terms.
Jeffrey Walton noloader@gmail.com writes:
I think Daniel is on the right track by choosing standardized domain parameter support. When using standard parameters, you only have to choose your private key and publish the public key. In this case, RFC 5114 - Additional Diffie-Hellman Groups for Use with IETF Standards (et al), would also be of interest.
Noted.
For those interested, Certicom, which holds many EC patents and is owned by RIM, lost a few "slam dunk" cases recently. The events caused paralysis in RIM's legal department to the point where the sales team has not inked a license in over a year. When I inquired about licensing over the summer, I was told to go to RSA Data Securities even though RSA is probably violating Certicom. The fellow who advised me worked for Certicom.
Intriguing story... as I've said, I haven't been following the area.
My conclusions for now are:
1. It makes sense to add support for certain elliptic curves or types of curves to nettle. I'm still not quite sure what the applications are, diffie-hellman key exchange have been mentioned, do the most important standards also use them for encryption and signatures (e.g., ElGamal style)? The implementation ought to include an ecc exponentiation primitive that can be used for various applications.
(BTW, Nettle currently doesn't include any support for ElGamal using the usual modular group, is that something that would be useful? I try to give higher priority to algorithms that are in used in real protocols and applications, and lower priority to more academic constructions).
2. I will not have much time to spend on ecc in the near future. I'm happy to comment on, and integrate, well-written patches. As usual, test cases are a very important part of the implementation...
3. On the legal side, I'd like to have some clear evidence that the particular curves implemented are unlikely to lead to trouble with known patents, possibly with fsf legal staff or sflc in the loop. I'm not sure I know the area well enough to provide all needed input to legal staff, though, so I may need help with this part as well.
Regards, /Niels
On 01/07/2011 04:11 PM, Niels Möller wrote:
It makes sense to add support for certain elliptic curves or types of curves to nettle. I'm still not quite sure what the applications are, diffie-hellman key exchange have been mentioned, do the most important standards also use them for encryption and signatures (e.g., ElGamal style)? The implementation ought to include an ecc exponentiation primitive that can be used for various applications.
(BTW, Nettle currently doesn't include any support for ElGamal using the usual modular group, is that something that would be useful? I try to give higher priority to algorithms that are in used in real protocols and applications, and lower priority to more academic constructions).
OpenSSH 5.7 (due out later this month) will add the use of Elliptic Curve DH and DSA. Interoperability with OpenSSH by ssh clients using nettle would be an excellent real-world scenario.
ElGamal is still widely used for asymmetric OpenPGP encryption. Try scanning the public keyservers for people with ElGamal subkeys (i wish i had some easy way to present statistics from them -- sorry i don't!)
so yes, both EC and ElGamal have very clear real-world (non-academic) usefulness.
- On the legal side, I'd like to have some clear evidence that the particular curves implemented are unlikely to lead to trouble with known patents, possibly with fsf legal staff or sflc in the loop. I'm not sure I know the area well enough to provide all needed input to legal staff, though, so I may need help with this part as well.
i'll point the SFLC lawyers at this thread. hopefully they can get in touch.
--dkg
nisse@lysator.liu.se (Niels Möller) writes:
- On the legal side, I'd like to have some clear evidence that the particular curves implemented are unlikely to lead to trouble with known patents, possibly with fsf legal staff or sflc in the loop. I'm not sure I know the area well enough to provide all needed input to legal staff, though, so I may need help with this part as well.
I believe the SFLC is aware of the ECC situation, so you may want to talk to them about it. It is a messy area.
/Simon
nettle-bugs@lists.lysator.liu.se
-
Daniel Kahn Gillmor -
Jeffrey Walton -
nisse＠lysator.liu.se -
Simon Josefsson