Hacker News new | past | comments | ask | show | jobs | submit login
Signify: Securing OpenBSD from Us to You (openbsd.org)
140 points by glass- on June 12, 2015 | hide | past | web | favorite | 81 comments



Signify is the first OpenBSD code that I've ever read from start to finish - (minus the external libraries like the Ed25519 package). Watching the initial checkins, followed by the amazing improvement in the command line options within a a few weeks of checking by external contributors - the final product is much, much better than the first checkin. What I really appreciate, is that they managed to strike a balance between keeping the tool 100% lean, and adding tiny bits of syntactic sugar (such as the Untrusted Comment field, and, the ability to simultaneously verify the SHA256 hash and signature of a list of files.)

Teaching people how to use the tool, from the point of generating keys, to generating signature manifests for a packages, to signing, and verifying takes < 3 minutes for someone who already knows what a hash is.

And, the complete absence of CA architecture, or web-of-trust - and an focus on sharing their (really short) public keys in a visible and widely distributed manner just makes the system so much simpler to understand.

For example - this literally is all you have to do on OS X to have a complete end-end signing/manifest/verification system:

Generate your keypair:

   signify -G -p pub -s sec
Your public key is tiny, and can be shared anywhere/everywhere:

  RWRGNg6NU+JAt9ju3ItQfOMmDhXmEkHp28mej8ickx4lOJjE2Tg2DxEO
Created your manifest (On OpenBSD you just go "sha256 file* ")

   shasum -a 256 file* | awk '{print "SHA256 ("$2") = "$1}'> manif
Sign your manifest, and embed the signature in the resulting sig file:

   signify -S -e -s sec -m manif -x manif.sig
And now, anybody who has your public key, can verify that manifest:

   signify -C  -p pub -x manif.sig
That's it, that's the entire system from beginning to end.


"... the complete absence of CA architecture, or web-of-trust..."


That decision eliminates a lot (50%, 75%, 90%?) of the complexity that comes with GPG and most CA architectures. It also means the keys can be typed in by hand.


Correct.


Another tool that generates compatible signatures: https://jedisct1.github.io/minisign/

The main addition is a "trusted comment" line, that can be used to verify metadata, instead of just the content, for example to verify a timestamp and prevent unwanted downgrades. This is not an issue with packages, but it can be an issue with files that don't contain any version/timestamp.

And since keys are very short, they can also directly be given on the command-line, making the verification very simple from a user perspective. For example the list of public resolvers compatible with DNSCrypt can be verified with a oneliner: https://github.com/jedisct1/dnscrypt-proxy#dnscrypt-enabled-...

OpenWRT is now also leveraging Ed25519 signatures to sign their packages, using a slightly modified version of signify. The result is way smaller than GPG, and a better fit for embedded systems. Unfortunately, they sign `sha512(message)` instead of the message itself, making the signature incompatible with signify.

But even though they only do one thing, these tools are overall way easier to use than GPG, way smaller, and having short keys is really great.


That's definitely an improvement and pretty easy to use as well.


A recent reddit post where a (US) user ordered OpenBSD by mail: http://www.reddit.com/r/openbsd/comments/369vmw/looks_like_i...


Given the NSA's reputation for doing things on the sly, isn't this a little clumsy to attribute to them? As one of the commentators says, it was more likely to be a border agent on the lookout for new music.

At one place I worked, we had USB security dongles for license management. We started sending them out in envelopes, and found that few reached their destination intact - the envelope would arrive, with a hole in the corner. Someone was raiding the envelopes for USB sticks, for whatever reason.


Could it be that they were damaged by the postal equipment? Envelopes with keys often undergo this fate too, unless you pad the key with something of similar thickness.


I think-hope he's kidding about the NSA part.


@tedu writes:

> There was a PGP usability study conducted a few years ago where a group of technical people were placed in a room with a computer and asked to set up PGP. Two hours later, they were never seen or heard from again.

This argument doesn't hold ground. If "technical people" can not setup a new GnuPG key in 20 minutes, they are obviously not "technical" in this context. I'm 100% sure OpenBSD is absolutely NOT fit for people who find GnuPG confusing enough to avoid usage.

> Or as Prof. Green put it, "Can someone who built GnuPG 2.1.1 on Debian/Ubuntu give me a hint on which libgpg-error you used?" If he doesn't which libgpg-error to use, I doubt I'm going to pick the right one.

I can, here:

    $ pkg info|grep libgpg-error
    libgpg-error-1.19_1            Common error values for all GnuPG components
Given that this is @tedu, I'm sure I missed the point/joke.

The only real argument here is that it's at least 10 times easier to write code than to read another mans code. So I give him that... Which one is more secure, GPG or signify remains to be seen.


He's written a tool that solves one problem using one set of algorithms and a very simple format in a few thousand lines of c.

It almost certainly contains fewer bugs than gnupg.


Do one thing, and do it well


Praise be Unix.


GnuPG is complicated, the gpg(1) man page is quite extensive compared to signify.

I imagine very few people have set up PGP without the help of a search engine.

    $ man gpg | pr | grep Page | awk '{print $6}' | tail -1
    58
    $ man signify | pr | grep Page | awk '{print $6}' | tail -1
    2


I got back on GnuPG recently because an associate wouldn't communicate without it. We came up with a trustworthy way to exchange keys. After that, I just cut and pasted crap from this:

http://irtfweb.ifa.hawaii.edu/~lockhart/gpg/

Been working fine so far. I'm sure there's all kinds of complicated ways to use it but it just takes a few commands to do most of the work. I only use two these days: one for sending and one for receiving. I scripted the more complicated one (send) where I type an alias and a text file with it doing the rest. The decrypt command, -d (file), is easy to remember. Pretty simple compared to trying to learn OpenBSD.

Not to say they're wrong for making something easier or the interface couldn't be way better. Just that me using this thing with almost no thought argues against all this difficulty people are bringing up.


Are you really confident that cutting and pasting crap from a random web page (particularly one without TLS, so the guy sitting across from you at Starbucks can MITM it) provides you with sufficient understanding to notice when you are accidentally doing something insecure?


I cross-referenced it against the documentation. Let's assume someone won't, though. The commands' appearance make their intent pretty obvious. Further, using them produces output that confirms what the cheat sheet says. For instance, adding a public key said something along the lines of "public key added." Decrypting the incoming message showed its plaintext. Encrypting outgoing plaintext turned it into ciphertext other party decrypted. Along with a warning that the key didn't have others' signatures on it, which ironically re-assured me more because it shouldn't.

So, a visual inspection of the commands and their results in a sandboxed machine was about all one needed to know that they worked. My experience with similar tools helps there. More concerned people can thoroughly cross-reference them with the documentation, source code, program's author, and so on. Whatever level of assurance they like. The basic level, though, was incredibly simple.

I'd take using GPG over learning Emacs or OpenBSD any day. In level of difficulty, that is.


The problem with copying and pasting from a website is not whether you think you know what the command does. It is that copying from a HTML page might contain stuff you can see.

https://thejh.net/misc/website-terminal-copy-paste


Damn! That was a surprise! Alright, point taken. I'll... have to validate things on terminals a lot more thoroughly in the future. And type my own code by hand based on the documentation. Maybe just make my own cheat-sheets for the cut and paste. Text files.


s/can/can't


Agree with regard to Emacs, but OpenBSD has some of the best technical documentation I've ever come across. For example, their networking FAQ[0] or (especially) the PF guide[1].

[0] http://www.openbsd.org/faq/faq6.html

[1] http://www.openbsd.org/faq/pf/


Their documentation is great. I won't disagree in the slightest. I also praised them in other places for working as hard on docs as software itself. Docs are lacking in most places. The only point of these comments is that people are way overhyping the difficulty of basic GPG use given I installed it easily using Google and used it by cut n pasting a cheat sheet. Others have too. That's all I'm trying to do here while using things like the overall OpenBSD experience (or Emacs) as points of comparison to support that.

I'd have to use my brain with either OpenBSD stuff or Emacs. Of course, I cheated there too: Absolute OpenBSD. I know I could've used their great docs for everything but the reviews of the book were too good. I had to attempt using it to shortcut the learning process. Lol.


[flagged]


There's a good reason for that, actually. Besides, it doesn't matter how long ago I went to key-signing parties and such. The number of people I know using PGP I can count on one hand, maybe two. I have reliable channels to them to get keys. Web of trust is useless to me and despite my poor memory I can remember debating people about its many weaknesses even back when we did it a lot.

Modern tech has moved on to more interesting and reliable reputation systems. Web of trust's time has passed, for now.


I meant the whole thing - subkeys, their very purpose (even CAs use subkeys to sign certificats!) or usage, etc.

Seems a bit strange for security researcher - that's all.


Lost much of my memory in an accident where I took severe head injury. What my brain kept it kept. What it didn't it didn't. Most stuff I hadn't used in forever went poof. Web of trust model was one of those. Some things I'd just have to straight up relearn and I'm not bothering unless I have a need given only so much memory to spare.

Hope that makes sense.


> you haven't a slightest clue

No personal swipes, please.


How is this personal?

I'm not trying to insult anyone, it's a mere statement of a fact - the OP hasn't a slightest clue about web of trust, subkeys, key-signing, etc. and he clearly demonstrated it in several comments. In those he spreads misinformation and FUD - and those are signs of a troll. So if I say "you haven't a slightest clue" to such an individual, I'm being polite.

Good day.


I'm surprised that there seems to be a consensus here that using the GPG command line tool is complicated when the HN community regularly discusses, for example, time complexity of algorithms.


Using gnupg unfortunately requires a fairly complete understanding of the specific Web of Trust model used.

On top of that the interface is atrocious, go find someone with an image in their pubkey and try to display it from the command line.

Good luck.


You actually just need a reliable way to get information from them once plus a good cheat sheet (see above comment) on GPG. So, you both use cut and paste to (a) generate keys, (b) add keys, (c) send messages and (d) receive messages. Exchanging the key file is the only step that requires slight thought and there's a dozen ways to do that.

I still don't use or fully understand the web of trust model as I haven't studied it in ages. I do use GPG every night with the right person on the other end, though. Still don't know anything else about it. Don't want to, either.


But then a friend tries to be more secure and sends something using --throw-keyids or --hidden-recipient. He tells me I should use --try-all-secrets, but adding that to enigmail doesn't work. I still don't know why.

I'm trying to do this with some friends, and we keep on running into problems like that. Everything turns out to be easy to solve, but only if you know exactly how it works.


You'd have to be an idiot to read those command names and try them. Whereas "gen-key," "import," "export," "-e," and "-d" have obvious, low-risk usage. More so if you cross-reference against the docs.

Nice strawman, though.


I have the misfortune of having encrypted some files in the past with PGP. At the time, the default algorithm appeared to be IDEA which was removed since for patent reasons. Find the old sources and getting it to built is not trivial.

These days I'm leaning towards bundling encrypted files along with the C code that encrypted it and that works better if the latter is small and self-contained.


That's a very interesting concept of a cross-platform self-unpacking archive. Unfortunately it requires the C compiler binary which is missing on the Windows platform out of the box. Perhaps some kind of tiny C compiler or interpreter windows binary might be bundled along for 99% compatibility.


I know that the RAR format, for one, effectively embeds the compensating decompression program for whatever it did into the archive, in the form of some bytecode for a VM with an ABI that has been stable since RAR was created. So RAR has actually been a bunch of different algorithms over time, but unrar(1) doesn't need to care; it just runs the embedded program in its VM. (Most exciting fact: this means that older versions of the program can decompress archives created by newer versions, using algorithms that didn't exist at the time the older version shipped!)

It would definitely be possible to do the equivalent for encryption. The main problem† being that while compression algorithms get outmoded, encryption algorithms break. This is true of all encryption, but it's especially scary when you can just scan a disk and signature-identify crackable files by the embedded algorithm.

So, if you were going to do something like this, you'd probably want a higher-level abstraction than "self-describing encrypted file"; maybe something more like a "self-describing encrypted mutable volume." Mutable so that it would (hopefully) get an update() operation called on it at least every so often (even if just from a fsck-during-mount), letting it start a background process to change out an old-and-broken backing-store encryption algorithm for a new-and-trusted one (think of how bcrypt handles strength changes.)

---

† There's also the performance problem: if you have a stable ABI, and it was frozen 20 years ago, how would you ever do something like elliptic-curve operations efficiently? Heck, doesn't using a frozen ABI mean you couldn't make use of a modern processor's native instructions for RSA ciphering et al?

The answer to this, I think, is VM-runtime instruction-level pattern-recognition ala urbit's "jets". The new version of the encryption program would prepend a program for the stable ABI, that tells the old version how to (inefficiently) implement elliptic-curve decryption in terms of things it understands. However, running this program against a new version of the decryption VM would recognize the signature/pattern of "what elliptic-curve decryption instructions encoded in [this VM]'s ABI" looks like, and execute a native procedure with the same preconditions and postconditions as that instruction-sequence instead. Sort of like typehints for a JIT, but where the instruction-sequences themselves are the hints, since they have canonical forms.


The paper is full of jokes like this. It’s clear, though, that GPG is much larger than we would like our TCB to be, and that it does have serious usability problems, some of which are inherent to its trust model and therefore cannot be papered over by GPG frontends. (They don't, however, stop you from using it to authenticate upgrades, as Debian and Ubuntu do.)


You made a good point: OpenBSD is way more complicated than GPG. I set up GPG with one command I got off the Internet. I also got a cheat sheet giving common commands I need for common scenarios. These people weren't just barely technical: they were unable to use Google as well. I'm dismissing the study as having little value. Need a new one with people who can follow steps they find on Google. If they fail, the author's point would stand.

One more thing they forgot to mention: GPG is apparently so secure that Snowden leaks show that NSA hates running into it and even uses it internally. Biggest endorsement one can get. I'd replace the interface for sure, though, where users would never see it.


This is a good point: Revocation is probably a cure worse than the disease.


See this follow-up as well "Ted Unangst: signify shortcomings": https://news.ycombinator.com/item?id=9721737


It's bizarre that they consider https as an alternative to cryptographic signing, rather than an unrelated addition.


My reading was they did the exact opposite: considered https to be a failure of end-to-end security they wanted. It was various users that apparently wanted HTTPS. I could see how they got to that: I access the site with HTTP; an intercept might happen; HTTPS protects HTTP; let's protect it with HTTPS! Fortunately, the experts knew better and avoided that nonsense.


If end-to-end sec (e.g., crypto signatures) are used, like say with Debian packages which uses GPG, packages and metadata can be released over http without a problem.


Exactly. One of many reasons the developers went with an end-to-end solution instead of HTTPS. It makes the transport mechanism moot except for the initial key exchange.


Linux port of signify:

http://sourceforge.net/projects/slackdepot/files/signify/

Files signified on OpenBSD will verify on Linux and vice versa.


One exciting thing about software distribution with ed25519 signatures is that when Ripple finally releases their threshold signature library for their cryptocurrency we get the ability to create public keys that express software signing policies for free!


Quick comment regarding key sizes. NSA has a patent on ECC, expects licenses for commercial use, and has some kind of conditions you must adhere to if applying for a license. I'll let your imagination wonder on that last part as mine does. The choice is easy for me between asymmetric crypto that's patent-free and a kind the NSA controls. This might not apply to your personal use but it can to any company using such a tool.

Given the leaked BULLRUN slide, I'd rather not be in a position of NSA showing up with plans for my product along with a legal claim on it. RSA or DH it is, then! Or clever symmetric schemes that avoid that stuff entirely. I do that, too. I haven't missed not using ECC as I rarely need to transmit asymmetric keys.

EDIT: The few legitimate responses to this showed NSA patents are expired, Certicom's 130+ still require license from new owner Blackberry, and Bernstein's curves might be exempt. I appreciate those updates. Status quo: forms of ECC are covered by patents and you need to consult an attorney if doing it commercially.


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.


@ 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.


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.


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?


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.


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.


@ 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.


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.


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...




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: