7

Commonly used cryptosystems like RSA or ECC, on the other hand, will be broken if and when quantum computers become available. - https://tbuktu.github.io/ntru/

How can we introduce NTRU in GPG and TLS to send NTRU-Encrypted emails and communicate over NTRU encrypted https protocols to be ready for the post-quantum age?

For example, could we just create a public and private keypairs with NTRU like now with SHA in GPG?

Edit: In fact, I really would like to use one of the possible quantum-safe encryption algorythms like Ring-LWE, NTRU or McEliece to encrypt my internet communication instead of continuing using an encryption, that is not PFS and will be decrypted in 20 years anyway.

So can I use any quantum safe algorythm for sending e-mails already?

rubo77
  • 2,350
  • 10
  • 26
  • 48
  • As of 2018 nist folks are still in discussions, they had a conference spring 2018 for the 2017 round 1 submissions, but this has some of those ready for playing around with: https://github.com/open-quantum-safe/liboqs – jmunsch Nov 17 '18 at 17:21

3 Answers3

5

Easy there cowboy, you've got about 15 years until this is really a problem. You are also making a massive assumption that NTRU is going to be the cryptosystem of choice for a post-quantum age.

NTRU is part of a collection of schemes called "Lattice-based crypto". Still within lattice-based schemes, many people prefer Ring Learning With Errors over NTRU for several reasons. In general, the expert cryptographers of the world agree that lattice-based schemes - as a whole - is a branch of mathematics that we don't understand well enough to trust them with any serious information at the moment.

There are also collections of crypto schemes called "code based" with McEliece being the leading candidate, and isogeny-based techniques, both of which are considered better than NTRU for reasons of security, key size, and speed.

Bottom line: none of the post-quantum algorithms are mature enough yet to be included in anything other than research code (although it wouldn't shock me if GPG included an experimental version at some point). Try again around 2020.

EDIT:

In response to your updated question:

So can I use any quantum safe algorythm for sending e-mails already?

No, no you cannot. None of these algorithms are considered safe yet; they still need several years of research by basic mathematicians before we decide whether or not to trust them. Then we need to standardize protocols and stuff around them.

I understand that you read something on the internet and now you're on a crusade about it. Trust me, this is moving as fast as it can - in the world of mathematics research, sometimes a theorem takes 200 years to prove - by comparison 5 years for completely redesigning crypto is warp-speed. You'll get your GPG / TLS / Thunderbird plugins by the year 2020. Until then you need to chill out.

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • maybe you can write a thunderbird-addon that encrypts with McEliece? I really think we shouldn't use an encryption that will be decrypted in 20 years anyway. (I edited my question) – rubo77 May 02 '16 at 19:58
  • @rubo77 You want _me_ to write a thunderbird addon?? What if I don't want to? Also, I updated my question. – Mike Ounsworth May 02 '16 at 20:27
  • 1
    I meant "one can wrinte an addon", but cool, thanks for your response, I am serching quite a while now and didn't find any ready to use algorythms either. But maybe we should start using one of them together with old-style GPG, although it is not mathematicaly proven to be safe still. If we would use such a **double encryption**, it would be still safe as before and probably quantum-safe too – rubo77 May 02 '16 at 20:31
  • 1
    @rubo77 Yeah, that idea of chaining a pre-quantum and a post-quantum algorithm has been called "The P + Q approach" by the famous cryptographer Dan Burnstein. NIST is considering standardizing something like that once we've had a chance to look at all the candidate algorithms. – Mike Ounsworth May 02 '16 at 20:39
  • Sounds great. Who is "we"? Who will decide the standard, we will use? And who sais, it takes exactly 3 years to decide which? – rubo77 May 02 '16 at 20:41
  • @rubo77 [NIST](https://en.wikipedia.org/wiki/National_Institute_of_Standards_and_Technology) is the US government department in charge of setting standards. They are leading the charge for PQCrypto. Currently they are getting ready to host a 5 year competition where all the cryptography researchers of the world can submit their algorithms, and everyone else can have a chance to scrutinize them. At the end of it, hopefully NIST will have enough evidence to pick "the best" post-quantum algorithms. So the "we" is all the cryptography researchers of the world. – Mike Ounsworth May 02 '16 at 20:45
  • So this means, that all our encrypted traffic that is recorded by surveillance programs will be decrypted in some 20 years, when QC are big enough. This may not be true! We have to use a P + Q solution Now! ;) – rubo77 May 02 '16 at 21:21
  • @rubo77 lol - yup. – Mike Ounsworth May 02 '16 at 21:32
  • You could use both NTRU with another algorithm that isn't quantum-safe like RSA, and it would be considerably more secure, even though NTRU hasn't proven to be completely secure. – Aaron Esau Sep 01 '17 at 01:56
  • https://www.zdnet.com/article/ibm-warns-of-instant-breaking-of-encryption-by-quantum-computers-move-your-data-today/ suggests this can be a problem already around 2023 instead of 2031 as suggested by the answer. – Jonas Berlin May 23 '18 at 09:38
  • When this becomes a problem depends on your attacker. If you assume that your messages are being stored now for later analyses, then you might very well be concerned. – Frederick Nord Oct 22 '18 at 14:33
2

TLDR; An experimental version of GnuPG for post-quantum cryptography does exist, CodeCrypt. As for SSL/TLS, implementation is possible but getting servers to use it would be a nightmare. For true, absolute security, use One Time Pads.

Long Version: Well, it's 2020 now, and the only solution that looks decent is CodeCrypt (mirror of repo hosted on a site that takes ages to load). It's hardly a complete answer to your question, but it's something. It's designed to work like GnuPG, as the README begins:

This is a GnuPG-like unix program for encryption and signing that uses only quantum-computer-resistant algorithms:

McEliece cryptosystem (compact QC-MDPC variant) for encryption Hash-based Merkle tree algorithm (FMTSeq variant) for digital signatures

You requested the McEliece algorithm, and I think this is probably the best you'll get as of right now. In terms of security, I haven't reviewed the code myself, but it's recommended by Whonix (leading open-source anonymity software used and recommended by Snowden himself) in their page on post-quantum cryptography. Those are pretty good credentials, and certainly enough to warrant interest and research in the project.

In terms of convenient encrypted email with it, unfortunately, the only extension for Thunderbird I could find is "an experiment", AnnealMail, so I wouldn't recommend using it in any serious scenario.

CodeCrypt itself is apparently an experiment, but its recommendation by Whonix and Whonix's guides on its use are promising. It's certainly worth trying out, and given that I wasn't able to find any other GPG-like systems that implement PQCrypto, I'd say it's a viable alternative to GPG for now. Probably, the best solution would be to double-encrypt, once with GPG (which we can presume to be not backdoored), and then once with CodeCrypt (which we can leverage the possible security of without trusting the system to protect from backdooring). This gives us a solution secure against classical attacks at least, and allows us to leverage the possible security of CodeCrypt, without completely trusting it yet, given that it is very new.

As for SSL (by which I sincerely hope you mean TLS), good luck with that. Given the existence of CodeCrypt, the protocols shouldn't be too difficult now, but getting them to work with servers other than your own? Good luck. It'll be like IPv6, a great solution to a very real problem, one that still isn't globally implemented, and has been being phased into for years. Replacing TLS would be hellish, because not only would you have to have a custom browser (or at least a custom build), but you'd also need servers that support it, and a translation gateway from this protocol to TLS would be utterly security-wise useless, defeating the whole purpose. I think we have a while to wait yet before widespread use of a PQCrypto protocol that can stand in for TLS.

If you want PQCrypto that is absolutely guaranteed, and doesn't even need (and really shouldn't use) a computer, check out One Time Pads. The KGB used them, and they're the only information-theoretically secure encryption algorithm we have (to my knowledge). That means that even an adversary with literally infinite computational power couldn't break it. You want encrypted email that's really perfectly secure? Use them. Be warned, say goodbye to the instant in instant messaging if you do!

schroeder
  • 123,438
  • 55
  • 284
  • 319
arctic_hen7
  • 121
  • 2
  • Sure, I corrected my question to TLS. Why would it be such a problem? TLS also comes in new versions, so TLS v1.5 could include a PQ crypto – rubo77 Jul 21 '20 at 23:27
  • For an extremely limited portion of browsers and servers, implementation of PQ crypto has technically already happened twice, in September 2016 as well as last year, with the CECPQ experiments. At the very least, it demonstrated that TLS need not be replaced, simply a plugin added for the additional key exchange. – timuzhti Jul 22 '20 at 12:54
  • While OTP can be useful in very specific scenarios, the difficulty of key management and randomness is a massive hurdle. And if your threat model has you worried about backdoored GPG, you'd better start rolling some dice and XORing with a pen and paper or else you're not really achieving anything. A simple alternative for some circumstances is just using very complex passphrases and distributing those according to your threat model as the current understanding is block ciphers aren't significantly weakened by quantum computing - only asymmetric algorithms. – Jim Dec 05 '20 at 00:50
1

Lots of organizations are working on PQCrypto for TLS: Google, Cloudflare, AWS. It is likely you have used PQ TLS, as part of the experiments Google ran.

When the NIST PQCrypto competition is settled, an IETF RFC and IANA cipher suite ids will be published I expect Chrome, Firefox and Safari to quickly adopt a PQ key exchange (or KEM), and OpenSSL to quickly support it. BoringSSL, Microsoft SChannel, AWS s2n, OpenJDK, etc. will support it too, some faster than others. The smaller TLS libraries will lag behind, but you should avoid them anyway (except maybe BearSSL).

A NIST FIPS standard on PQ HSMs will be published and HSM manufacturers will start selling PQ HSMs, and the WebPKI ecosystem will start planning for PQ leaf certs, PQ online signatures for handshakes, and eventually even PQ sub-CA and root certs.

It will all take time.

A key exchange is more urgent than certificates because a quantum computer that is available a day after you stopped using a certificate will not do an attacker any good: can't MiTM connections in the past. But the same quantum computer will break the key exchange and decrypt previously recorded traffic. So everyone wants to start using a PQ key exchange as soon as possible, so that by the time the adversary has a big enough quantum computer, the secrets in the old breakable traffic are worthless.

If you're worried about criminals, bitcoin is a canary: it will be attacked first. If you're worried about government intelligence services, they'll use parallel construction to hide the source of intelligence and you won't know they broke your cryptography.

Z.T.
  • 7,768
  • 1
  • 20
  • 35