5 ms·

Plagiarism as a patent amplifier: Understanding the delayed rollout of PQC

kragen 5y ago
Like the Crypto AG affair, this is likely to be one of the major drivers of historical events in the next few decades. I haven't finished reading this post yet, and I don't know much about cryptography, so it is somewhat risky for me to be summarizing it; but my summary is that Google's planned rollout of post-quantum-resistant TLS was aborted in November 02016 without explanation after only a few months rather than being continued for a few years as planned, apparently because it infringed a patent by Ding, even though it was based on a paper by Peikert that didn't credit Ding and thus didn't give any warning that a patent might be lying in wait. The plagiarism mentioned in the title is summarized just before the section "The concept of plagiarism": > But 2012 Ding did reduce the LPR ciphertext size "nearly twofold", specifically replacing "one of the two ring elements" with "a binary string of the same dimension n", in the words of 2014 Peikert. The problem is that this isn't how 2014 Peikert was describing 2012 Ding; this was 2014 Peikert claiming this space reduction as something new, the result of an "innovation" in 2014 Peikert. Though the post doesn't say this, the patent in question (https://patents.google.com/patent/US9246675B2 https://patents.google.com/patent/US9246675B2) was filed in 02013 and issued in January 02016. Bernstein explains that one result of this delay in deployment is that a great deal of TLS traffic that has already been captured and archived will probably be decrypted when quantum computers become available. He doesn't mention this, but I think this includes ciphersuites that claim "perfect forward secrecy".
- formerly_proven 5y ago
  > He doesn't mention this, but I think this includes ciphersuites that claim "perfect forward secrecy". Very much so, yes.
  - kragen 5y ago
    Thanks for the confirmation.
formerly_proven 5y ago
I'm not sure what the point of tenured crypto researchers patenting their crypto is. The only thing it guarantees is that your crypto is barred from standards because crypto is so extremely widespread that collecting royalties is simply impossible. AES-OCB is a prime example of this. It was faster than GCM and not quite as brittle, so many people would've liked to use it - but it was patented. No one used it. It now has a non-commercial FOSS patent grant, which still means no one uses it.
- rdpintqogeogsaa 5y ago
  Rogaway has abandoned his patents on OCB[0]. But by now, AES-GCM has hardware support and is ubiquitous. Nowadays, misuse resistance and resistance against partitioning oracle attacks are things you'd (also) expect from a modern AEAD design. AEGIS outperforms AES-OCB. The AEAD horse has already left the barn; there is no longer any point in closing the door. [0] https://mailarchive.ietf.org/arch/msg/cfrg/qLTveWOdTJcLn4HP3ev-vrj05Vg/ https://mailarchive.ietf.org/arch/msg/cfrg/qLTveWOdTJcLn4HP3...
gjm11 5y ago
Brief-ish TLDR (note: I am summarizing what Daniel Bernstein says in the linked article, and make no comment on its correctness; this is relevant because Bernstein makes some accusations about another academic) -- Back in 2016, Google began an experiment with "post-quantum cryptography", deploying some cryptographic algorithms in Chrome and in Google's servers that should be resistant to attack by quantum computers. (Most present-day crypto would be very badly broken if non-toy quantum computing becomes practical.) But they shut it down after a few months, even though it seemed to be working well. They'd originally said that if it went well they'd find a better algorithm and switch to it in a couple of years. So what happened? Plausible answer: shortly after beginning this experiment they were contacted by a cryptography researcher (Jintai Ding) who holds a patent that allegedly covers the algorithm they were using. The easiest course of action when this happens is just to shut the thing down. So how come they didn't know about this patent? Plausible answer: because another cryptography researcher (Chris Peikert) deliberately and systematically misled the academic community in order to avoid them noticing Ding's work -- because Ding did an important thing in 2012, and Peikert did essentially the same thing in 2014, and Peikert wanted to take credit for inventing it. Peikert succeeded, everyone thinks he invented the relevant things first, and no one thought to check whether Ding might have patents on it. (I reiterate that I am summarizing Bernstein's claims, and I do not know whether they are right or not.) TLDR of the TLDR: according to Bernstein, a dishonest academic cryptographer went out of his way to deceive his colleagues into ignoring earlier work by another cryptographer, so as to get the credit for it himself, this led to an important patent being overlooked by Google, and this has been a completely unnecessary stumbling block in the way of getting post-quantum cryptography deployed, so that Peikert's (alleged) selfishness and dishonesty have made everyone's data much less safe against future quantum-computer-based attacks.
- Ar-Curunir 5y ago
  I will note that DJB has a long-running beef with Chris Peikert, and seems generally opposed to lattice-based PQC. From my impression (as another academic cryptographer), Chris seems to be a genuine person, and not one to "deceive his colleagues"; he is also generally well-liked in the community. DJB, on the other hand, is known for being highly opinionated, and is a bit of an iconoclast in the cryptography community.
boardwaalk 5y ago
Besides the alleged plagiarism of Peikert, it seems massively immoral of Ding to lay a patent landmine in something important as secure communications for the next century. At the same time, I wonder how much he asked for from Google and how open the algorithm would have been (/ if it could have been "bought out").
- gjm11 5y ago
  Suppose you think up something brilliant that could be a big improvement to secure communications for the next century. Isn't it reasonable to expect to benefit from it? The whole point of the patent system is to enable people to benefit from thinking up brilliant somethings from which everyone will benefit. I'm not a big fan of the patent system and maybe we'd all be better off with something else, or with nothing at all, but given that the system's there it's not unreasonable for people who think up valuable things to use it. (Within reason! If Ding says "everyone who uses this has to give me ten billion dollars" then obviously what happens is that Ding gets no money and no one else gets to use Ding's idea, and that's plainly the worst of all worlds. But presumably Ding isn't stupid and that sort of outcome is unlikely.) Obviously it's a different matter if e.g. there are other equally good ways to do Ding's thing and Ding tried to conceal his patent in the hope that others would pick his way of doing it and make expensive-to-change decisions from which he could then profit. (I'm not sure whether "the alleged plagiarism of Peikert" means "Ding's alleged plagiarism of Peikert" or "the alleged plagiarism committed by Peikert"; what Bernstein is alleging is definitely the latter.)
upofadown 5y ago
>...large-scale attackers are already recording as much Internet traffic as they can. Do they throw the data away if it's encrypted with RSA-2048? Of course not. They keep it forever[1], hoping and expecting that someday they'll develop the ability to decrypt it, for example by building a quantum computer. The Forbes reference actually says that an oversight body allows the NSA to keep encrypted data forever, not that they actually do. There is so much encrypted data on the internet now that the NSA would have to use a significant amount of all the storage produced each year to keep a running archive of everything. A victory of sorts... [1] https://www.forbes.com/sites/andygreenberg/2013/06/20/leaked-nsa-doc-says-it-can-collect-and-keep-your-encrypted-data-as-long-as-it-takes-to-crack-it/ https://www.forbes.com/sites/andygreenberg/2013/06/20/leaked...

Like the Crypto AG affair, this is likely to be one of the major drivers of historical events in the next few decades. I haven't finished reading this post yet, and I don't know much about cryptography, so it is somewhat risky for me to be summarizing it; but my summary is that Google's planned rollout of post-quantum-resistant TLS was aborted in November 02016 without explanation after only a few months rather than being continued for a few years as planned, apparently because it infringed a patent by Ding, even though it was based on a paper by Peikert that didn't credit Ding and thus didn't give any warning that a patent might be lying in wait. The plagiarism mentioned in the title is summarized just before the section "The concept of plagiarism": > But 2012 Ding did reduce the LPR ciphertext size "nearly twofold", specifically replacing "one of the two ring elements" with "a binary string of the same dimension n", in the words of 2014 Peikert. The problem is that this isn't how 2014 Peikert was describing 2012 Ding; this was 2014 Peikert claiming this space reduction as something new, the result of an "innovation" in 2014 Peikert. Though the post doesn't say this, the patent in question (https://patents.google.com/patent/US9246675B2 https://patents.google.com/patent/US9246675B2) was filed in 02013 and issued in January 02016. Bernstein explains that one result of this delay in deployment is that a great deal of TLS traffic that has already been captured and archived will probably be decrypted when quantum computers become available. He doesn't mention this, but I think this includes ciphersuites that claim "perfect forward secrecy".

formerly_proven 5y ago
> He doesn't mention this, but I think this includes ciphersuites that claim "perfect forward secrecy". Very much so, yes.
- kragen 5y ago
  Thanks for the confirmation.

formerly_proven 5y ago

I'm not sure what the point of tenured crypto researchers patenting their crypto is. The only thing it guarantees is that your crypto is barred from standards because crypto is so extremely widespread that collecting royalties is simply impossible. AES-OCB is a prime example of this. It was faster than GCM and not quite as brittle, so many people would've liked to use it - but it was patented. No one used it. It now has a non-commercial FOSS patent grant, which still means no one uses it.

rdpintqogeogsaa 5y ago
Rogaway has abandoned his patents on OCB[0]. But by now, AES-GCM has hardware support and is ubiquitous. Nowadays, misuse resistance and resistance against partitioning oracle attacks are things you'd (also) expect from a modern AEAD design. AEGIS outperforms AES-OCB. The AEAD horse has already left the barn; there is no longer any point in closing the door. [0] https://mailarchive.ietf.org/arch/msg/cfrg/qLTveWOdTJcLn4HP3ev-vrj05Vg/ https://mailarchive.ietf.org/arch/msg/cfrg/qLTveWOdTJcLn4HP3...

gjm11 5y ago

Brief-ish TLDR (note: I am summarizing what Daniel Bernstein says in the linked article, and make no comment on its correctness; this is relevant because Bernstein makes some accusations about another academic) -- Back in 2016, Google began an experiment with "post-quantum cryptography", deploying some cryptographic algorithms in Chrome and in Google's servers that should be resistant to attack by quantum computers. (Most present-day crypto would be very badly broken if non-toy quantum computing becomes practical.) But they shut it down after a few months, even though it seemed to be working well. They'd originally said that if it went well they'd find a better algorithm and switch to it in a couple of years. So what happened? Plausible answer: shortly after beginning this experiment they were contacted by a cryptography researcher (Jintai Ding) who holds a patent that allegedly covers the algorithm they were using. The easiest course of action when this happens is just to shut the thing down. So how come they didn't know about this patent? Plausible answer: because another cryptography researcher (Chris Peikert) deliberately and systematically misled the academic community in order to avoid them noticing Ding's work -- because Ding did an important thing in 2012, and Peikert did essentially the same thing in 2014, and Peikert wanted to take credit for inventing it. Peikert succeeded, everyone thinks he invented the relevant things first, and no one thought to check whether Ding might have patents on it. (I reiterate that I am summarizing Bernstein's claims, and I do not know whether they are right or not.) TLDR of the TLDR: according to Bernstein, a dishonest academic cryptographer went out of his way to deceive his colleagues into ignoring earlier work by another cryptographer, so as to get the credit for it himself, this led to an important patent being overlooked by Google, and this has been a completely unnecessary stumbling block in the way of getting post-quantum cryptography deployed, so that Peikert's (alleged) selfishness and dishonesty have made everyone's data much less safe against future quantum-computer-based attacks.

Ar-Curunir 5y ago
I will note that DJB has a long-running beef with Chris Peikert, and seems generally opposed to lattice-based PQC. From my impression (as another academic cryptographer), Chris seems to be a genuine person, and not one to "deceive his colleagues"; he is also generally well-liked in the community. DJB, on the other hand, is known for being highly opinionated, and is a bit of an iconoclast in the cryptography community.

boardwaalk 5y ago

Besides the alleged plagiarism of Peikert, it seems massively immoral of Ding to lay a patent landmine in something important as secure communications for the next century. At the same time, I wonder how much he asked for from Google and how open the algorithm would have been (/ if it could have been "bought out").

gjm11 5y ago
Suppose you think up something brilliant that could be a big improvement to secure communications for the next century. Isn't it reasonable to expect to benefit from it? The whole point of the patent system is to enable people to benefit from thinking up brilliant somethings from which everyone will benefit. I'm not a big fan of the patent system and maybe we'd all be better off with something else, or with nothing at all, but given that the system's there it's not unreasonable for people who think up valuable things to use it. (Within reason! If Ding says "everyone who uses this has to give me ten billion dollars" then obviously what happens is that Ding gets no money and no one else gets to use Ding's idea, and that's plainly the worst of all worlds. But presumably Ding isn't stupid and that sort of outcome is unlikely.) Obviously it's a different matter if e.g. there are other equally good ways to do Ding's thing and Ding tried to conceal his patent in the hope that others would pick his way of doing it and make expensive-to-change decisions from which he could then profit. (I'm not sure whether "the alleged plagiarism of Peikert" means "Ding's alleged plagiarism of Peikert" or "the alleged plagiarism committed by Peikert"; what Bernstein is alleging is definitely the latter.)

upofadown 5y ago

>...large-scale attackers are already recording as much Internet traffic as they can. Do they throw the data away if it's encrypted with RSA-2048? Of course not. They keep it forever[1], hoping and expecting that someday they'll develop the ability to decrypt it, for example by building a quantum computer. The Forbes reference actually says that an oversight body allows the NSA to keep encrypted data forever, not that they actually do. There is so much encrypted data on the internet now that the NSA would have to use a significant amount of all the storage produced each year to keep a running archive of everything. A victory of sorts... [1] https://www.forbes.com/sites/andygreenberg/2013/06/20/leaked-nsa-doc-says-it-can-collect-and-keep-your-encrypted-data-as-long-as-it-takes-to-crack-it/ https://www.forbes.com/sites/andygreenberg/2013/06/20/leaked...