Hacker News Reader

Ed25519 and Curve25519 are not encumbered by any patents, see http://cr.yp.to/ecdh/patents.html and http://ed25519.cr.yp.to/software.html.

You should prefer state-of-the-art elliptic curve systems to RSA and finite field DH.

I appreciate the update on the situation for those curves.

It's not just those curves. Virtually all elliptic-curve cryptography is patent-free, as you would expect for a family of cryptosystems studied since 1986 based on centuries-old math. There are a few current patents, but they cover techniques almost nobody uses.

If it's patent free, why are people paying for it as I linked to? NSA paid for it and are specific that it applies to FIPS 140-2 solutions. Companies were paying Certicom for it. As far as a few years ago, an article gripes about how much Blackberry charges for it. Just weird that it doesn't apply to anything yet companies and governments were all paying for it.

If something has changed, I'd like the definitive answer to come from legal experts (esp aforementioned companies' lawyers) who say the 100+ patents no longer apply to anything we use and they all stopped paying for ECC. Haven't seen it. I'll continue to warn people until (a) I see that contrary reports acknowledge the existence of 100+ patents that companies are actually paying for rather than falsely claim no patents exist and (b) show why all of them never applied or no longer apply to existing ECC schemes. Got a link to that?

People are paying for it because they get value out of what they are paying for. TCP/IP isn't patented, but companies will pay several million dollars for a TCP/IP stack for their embedded firmware.

Don't conflate people's willingness to pay for a particular implementation (accompanying documentation, support, tools), with a legal requirement that they need to do so for the underlying technology.

I didn't. I thought that, after much publicity and a lawsuit, they paid for patent licenses out of coercion rather than willingness. The usual reason. Maybe the patents don't apply to anything, NSA was just being generous by buying patent licenses for nothing, and everyone else was buying software licenses. As I asked above, I just want a solid reference showing this and that the 100+ patents don't apply to anything we use.

So far, everyone wants me to take their word for it despite my references showing government and companies buying patent licenses. Weird. I'm thinking I should send a letter to Blackberry asking if ECC is covered by their patents or if everyone just wanted to pay for an implementation for various reasons. Might simplify this debate.

tptacek has already responded to your nonsense below at greater length than I have the patience for: https://news.ycombinator.com/item?id=9709692

FIPS 140-2 is not a cryptosystem standard; it covers the design of hardware security modules using a wide range of algorithms, the majority of which don't use ECC at all. The fact that you mention it at all (rather than, say, FIPS 186-2 Appendix 6) suggests that you have no idea what it is.

Certicom (now part of BlackBerry) offers not just patent licenses but also software licenses.

Several of the previously potentially relevant patents (mentioned in the link upthread) have expired within the last five years.

I recommend you stop giving people advice on subjects where not only do you know nothing, but the things you think you know are false.

@ kragen

The FIPS 140-2 claim comes from the NSA's licensing of those patents and requirements:

https://www.nsa.gov/business/programs/quick_facts.shtml

Far as patents, there's a quite a variety of them with some filed within the current 20 year window. I repeat for a third time, do you have a resource with a list of patents relevant to ECC and showing that none of them apply to any current implementations (esp BSD licensed)? It might surprise you but your word doesn't mean jack in a patent case: it's the patents, lawyers, and judges that settle it. So, I'm only going to back down on ECC patent risk if we get a definitive statement across these patent portfolios that there's zero risk on one or more implementations. What you all have given me so far is (a) there's no patents on ECC whatsoever, a lie or idiocy; (b) some non-lawyer said certain ones don't apply so magically they all don't in a real court; (c) you personally believe nothing applies so they won't in a court; (d) there's software licenses going on so patents don't apply in a real court despite NSA et al licensing patents. It all sounds really weak. People have lost suits and their profits for less.

I'm still awaiting your reference with evidence that each of the ECC patents don't apply to OSS or commercial implementations. Additionally, since it was added, I'd like your side to cite evidence that everyone is licensing software implementations instead of patents that don't apply to anything. That contradicts what I linked to so burden of proof is on you to show there's no patent-related licensing but software instead.

The references you've linked back up what I've said, not what you've said; not my problem if you don't understand them.

The references I linked cover 8 patents out of 130. For the fourth time, please link to evidence that they and the other 122 don't apply to anything we might build in ECC. And also that NSA and companies wasted millions on patent licenses for nothing.

Otherwise, it's obvious that you are spreading advice without the slightest idea of what's true here. Otherwise, you'll probably have a link to all those patents and analysis of how they don't apply that you can post within next few minutes. A link to analysis you and your side have already done rather than crap you're making up on the spot. You're faking it though, so you won't have anything to post.

Like everyone else in the ECC debate. Nothing but your word, which at one point thought patents didn't exist (neither the NSA nor anybody else has a patent on ECC). Given you're knee deep in this stuff and supposedly a security professional you must have been lying. There's no way you couldn't have known as a crypto/security geek that there were patents on ECC given all the debates. But you assured everyone here that nobody else has a patent on ECC. Such lies could've cost commercial groups that trusted you quite a lot.

I understand if you're more focused on dismissing the competition than proving 100+ patents don't apply to your claims. It's way less work that way. You'd have to dig them up, read them, evaluate them from a legal perspective, and write up reasons they don't apply. Complex, boring stuff compared to coding. I'll understand if you never take the effort to back your claims about 100+ patents and expect the rest of us to do the same.

It is still true that neither the NSA nor anybody else has a patent on ECC, any more than anybody has a patent on computers at this point. I'm sure you can find 100+ patents with titles like "Parallel Digital Computer" with very little effort, though. That doesn't mean that anybody who wants to use a computer for something needs to worry they're infringing patents.

I am not a "security professional", nor have I ever been, nor have I ever claimed to be.

There is no "competition" involved here.

There is no "ECC debate".

You already linked to a Wikipedia article that explains the patent status of different ECC systems. It's not my problem if you don't understand it.

@ ghshephard

Your comment implies they're only paying for an implementation. To be sure, do you have a link to a resource analyzing the patents on ECC and showing they don't apply to anything they (or we) use for ECC? That it's a moot issue in its entirety or mostly except for known cases? Otherwise, I'm going to guess that you're guessing like everyone else.

I'm not sure why you are responding to me here, but don't put words in my mouth. Your question was, "If it's patent free, why are people paying for it as I linked to?" - there are other reasons to purchase a technology than just the patent.

Let me spin it another way, and put the ball back in your court. Not that this proves anything, but has anyone (recently) purchased a license for ECC patented technology, that wasn't a license for a certicom specific implementation?

Seriously, someone who is an expert in this field (if not the expert), has already made a pretty clear statement here on patent problems wth Ed25519: http://ed25519.cr.yp.to/software.html.

As of 2015.06.11 "The authors have not been notified of any claims of patent problems wth Ed25519."

People only get hit with patent suits for commercial use that I'm aware of. They wouldn't be as it's all free and they don't monetize it. A commercial product using it is where the risk is. I'm assessing that risk.

Anyway, thanks for the link as he covers a lot of key patents and some prior art to use.

That would be a neat trick, since the foundational patents for ECC were filed in early 90s. The NSA patents are even earlier.

It was: Certicoms ECC patents got them acquired for roughly 7 times what Matasano got. A neater trick would be if you're right, the patents don't exist, and Blackberry was scammed. It go down as one of the greatest cons of that year with Blackberry's shareholders having more to gripe about. I'm just going with Occam's Razor: the ECC patents exist and you're just trolling my latest comment without any evidence to back up your claims. That's been your M.O. so far.

You write this as if the comment I responded to wasn't right there for everyone to read. You said:

NSA has a patent on ECC, expects licenses for commercial use, and has some kind of conditions you must adhere to

My presumption was that you were referring to patents assigned to NSA. NSA had patents relevant to number theoretic crypto. They're long-expired.

Apparently, what you actually meant was:

NSA has licensed a patent now owned by Blackberry.

What this has to do with open source ECC software, you have not made clear. Nobody is talking about using MQV.

It had never occurred to me that I'd sold a company that came within a factor of 7 of the value of Certicom's ECC patents. I did better than I thought I did! Woohoo!

RSA is significantly less safe than ECC alternatives. The situation is not as clear with DH, but it is if you just use Curve25519; Curve25519 is much safer than multiplicative group DH.

That's a semi-clarification. You brought up foundational patents and NSA patents in a dismissal form. You didn't acknowledge any patent risk on ECC, the gist of my comment, at all. Anyone reading your comment would think there was no patent risk much like the other commenters. Might have not been your intention.

Far as open source, the BSD licenses are used in part to encourage proprietary adoption of superior technology for everyone's benefit. Well, OpenBSD team might have their own reasons as they often do for a lot of things. Any company using BSD code in a commercial product (many do) is fine unless it's covered by patents. It's why Apache license mentions patents specifically. If this ECC was covered by ECC patents, then this could add risk to such a company over other technologies unless they licensed the patents from Blackberry. A specific example would be Genua, a German defense contractor that builds security appliances on OpenBSD.

And congratulations for beating your own expectations on the sale. One of a rare few. ;)

You keep using the words "ECC patents" as if they meant something. If you used the term "computer patents", your comments would be semantically identical.

Key agreement based on the elliptic curve discrete log problem isn't patented.

Straightforward, efficient point multiplication for elliptic curves --- the foundation of the ECDLP --- is not patented.

The the DLP-based DSA algorithm, which was invented at NSA, is not patented. Every browser uses it.

The elliptic curve variant of DSA, ECDSA, is not patented.

Fast floating point math mod 2^255-19: not patented. First published by a rabidly anti-patent researcher.

Elliptic curve point compression --- sending just the x, not the y --- was patented. Most researchers believe the patent was invalid; lots of very popular software ignored it. The patent has since expired.

Edwards curves? Bernstein claims to have invented Edwards curve cryptography, after being in the room when Harold Edwards published them.

Using elliptic curves in random number generators as a key escrow system? Certicom does appear to have a valid patent on that. So maybe that will cramp your style a bit.

I could keep going, breaking down binary extension fields, 3-party DH, ratchets, specific multiplication ladders, but that would defeat my point, which is that the most important, most mainstream, most typical uses of ECC --- the only things anyone should be doing with them --- are all unencumbered. That you can generate a first-principles binary extension field curve without tripping over a patent hardly matters. But it's also true.

Please stop spreading FUD.

^ What he said, the only relevant patents expired long ago.

> NSA has a patent on ECC ...

Wow, I was not aware that it was even possible for government agencies to hold patents.

Is there any reasonable justification for that?

Maybe to prevent some private company from patenting it?

It depends on what one does with a patent. I would think making it free for anyone use, if that were indeed the case, would be appropriate though.

Who knows NSA's purpose. Certicom's was money from licensing: so much that their company (mainly patents) sold for over a hundred million dollars to Blackberry. I have details in comment above.

Neither the NSA nor anybody else has a patent on ECC. (And no, there is no reasonable justification for government agencies to hold patents, except to make them free to the public.) There are some patents on particular ECC techniques, as explained in http://cr.yp.to/ecdh/patents.html, but they do not cover the currently most popular ECC systems, and in any case they are mostly expired.

That's what I would have thought, but then I DuckDuckGo'ed it (awkward!)...

http://foreignpolicy.com/2014/07/30/the-nsas-patents-in-one-...

Also, from https://www.nsa.gov/research/tnw/tnw193/articles/pdfs/TNW193... (PDF):

> You may be surprised to hear that NSA seeks patents. However, many of the technologies developed by NSA not only satisfy mission requirements, but also have great potential for commercial use. Following extensive review, NSA may seek patent protection for such technologies as a way to protect and build on the US government’s (USG) investment in research and development.

I don't see anything in there that contradicts what I said.

See my above reply concerning 130 patents on ECC.

That's not what you said. You said NSA had patents, demanded licenses for their commercial use, and then more or less implied that the condition they imposed on the use of those curves was to backdoor or subvert software that use them.

Obviously, no.

I've updated it for clarification. The NSA did have patents, though. After those expired, they licensed Certicom's and their web site even mentions that this only applies to products conforming to their expectations. As in, they control those to quite a degree. The alternative was paying Certicom a licensing fee.

It's still on their web site.

See https://www.nsa.gov/business/programs/quick_facts.shtml for the ECC patent license agreement.

It appears to be free, but your use needs to pass some fairly specific restrictions. Not sure if the PLA is available at any cost if your use does not pass.

@ quesara

Yeah that's the one. It has to be FIPS 140-2 compliant or approved by NSA. Outside Type 1 devices or FIPS Level 3-4, both of those seem to suck in practice for security. One way or another, it doesn't get unless they approve it.

Edit to add: That covers the small selection of patents NSA licensed for use in their implementations (esp FIPS 140-2 products). There's around a hundred more of unknown effect. I'd love to see a detailed breakdown of those and risk posed in various ECC use cases.

You do not need a patent license to use ECDH or ECDSA on a NIST P-curve, nor do you need one to negotiate keys with Curve25519 or to sign with Ed25519.

This covers more or less everything a normal developer would ever do with elliptic curves.

Is there some wacky curve nobody uses that is patent-encumbered, or for which the point multiplication formula is based on patented math code? Maybe. Is there some wacky protocol --- not ECDH, not ECDSA, not EdDSA --- that's similarly encumbered. Yes! For instance: you need a license from Certicom to safely deploy ECMQV. NSA likes ECMQV, and licensed it.

You are not going to use MQV.

The same thing is true of conventional multiplicative group DH and RSA: there are variants and wacky protocols that are patented. Nobody uses them, nobody cares. They're the same kind of patent minefield as putting a shopping cart on a web page is: somebody somewhere has some godawful paper on it maybe, but you can't avoid it and still have a career.

The specifics of this situation aren't very complicated, but they're just complicated enough for people to spread mistrust of curve software. You've gotten a pageful of that on this thread. That's sad, because curve software is much more secure than RSA/DH. Every new system that requires public key crypto should be using curves.

Sure, I'm with you there. I was surprised to learn that NSA held patents at all.

It looks like NSA bought their ECC patents (the ones they license on the forelinked ECC PLA page) from Certicom. I'm still confused as to why NSA would buy a portfolio of patents and then license them restrictively (albeit at no cost).

Just seems a weird thing for a govt agency to do. Not suspicious or nefarious. Just weird.

A few of these people didn't seem to do much research. There's not only one patent on ECC: there's around 130 esp by Certicom with a whole wikipedia article [1] dedicated to the topic. The early NSA patents are indeed expired while the linked Certicom patents seem to be in effect. Article also mentions Bernstein's might be exempt but anyone following patent troll suits won't be assured by that. Certicom loosing the lawsuit against Sony's high-priced lawyers with some prior art is somewhat assuring. Yet, it's a fact that ECC in certain forms (or in general?) is patented and even Schneier was disturbed by how well the patents were written.

So, next time ECC patents come up, those replying like they don't exist hopefully will not mislead HN readers again. (sdevlin's fair comment being an exception) I mean, if there are no patents, we wouldn't have people griping about licensing costs [2] or companies dropping $100+mil on the company for its ECC patents, would we?

[1] https://en.wikipedia.org/wiki/ECC_patents

[2] http://seekingalpha.com/article/2554945-blackberry-make-cert...