Post-Quantum Cryptography

Hi lainons, this is the Post-Quantum Cryptography thread! Although the threat of quantum computers is currently not a concern, but any individual who cares about privacy, cryptography or security needs to learn more about PQC right now, before the quantum apocalypse. Feel free discuss anything relevant, e.g. practical software solutions that utilize PQC, theoretical development. As a starter, here's a list of recommendations. If you know more, share it! Software >https://github.com/i2p/i2p.i2p-bote i2p-bote, decentralized email, NTRU encryption. >http://goldbug.sourceforge.net/ Goldbug, instant messaging, NTRU and McEliece. >https://github.com/tbuktu/libntru C Implementation of NTRUEncrypt. Lectures >https://www.youtube.com/watch?v=bbkCBlWfwaQ Daniel Bernstein - The Post-Quantum Internet >https://www.youtube.com/watch?v=MG6g04R_Ims Phong Nguyen - Lattice-Based Cryptography >https://www.youtube.com/watch?v=EqRsel-rXac Tanja Lange - Code-Based Cryptography >https://www.youtube.com/watch?v=FrM6zAuI7-4 Jintai Ding - State of Art of MPKC >https://www.youtube.com/watch?v=nfLAVybabMs Dustin Moody - Post-Quantum Cryptography: NIST's Plan for the Future

>Codecrypt, a GnuPG-lie unix program for encryption and signing that uses only quantum-computer-resistant algorithms: https://github.com/exaexa/codecrypt

The definitive website for theoretical PQC, made by Daniel Bernstein himself. https://pqcrypto.org/

Why won't normal cryptology work on the quantum computing networks ?

>>33 A lot of modern cryptography is based on the difficulty of the discrete log problem, but Shor's algorithm can crack that in polynomial-time on a large enough quantum computer.

>>33 Symmetric ciphers are still defending you against quantum computers, but all security bits will be square-rooted, 128-bit is 64-bit. If you encrypt your data with a passphrase and AES-256 (SHA-384 for HMAC) you have already defeated the quantum computers anyway. Public key cryptography will be another story... I wonder should I write a FAQ for people who have never heard of PQC.

>>46 Why SHA-384 for HMAC? HMAC-SHA-256 will still give you 128-bits of security, no?

>>61 yes, but in the worst case the security bit of hash functions can be cube-rooted, this attack is unlikely according to a DJB paper, but for some reasons from one of NIST documents, NIST P-256, RSA-2048 and SHA-256 are all derezzed for encrypting secret government documents, apparently the NIST/NSA is worrying about quantum computers and they want to extend the length to gain some extra time. I cannot find that document, but I'll post it later after I find it, but ironically I remembered the NIST server that hosted that PDF was using a SHA-1 certificate.

>>62 oh the word filter... It's amusing given the correct context, but this time is not the case.

>>46 > Public key cryptography will be another story... I wonder should I write a FAQ for people who have never heard of PQC. please do, beginner level too if possible

>>46 idea: write it for next edition of lainzine

>>73 The math of PQC is far-beyond my ability. I think I could write it from a user's point of view. >>74 good idea. btw does the recent disruption affect lainzine?

>>73 >>79 I came into these papers a while ago. the reading is dense but it's mostly just lin alg

>>90 >the reading is dense but it's mostly just lin alg That sounds like physics alright.

I'n studying Quantum Mechanics atm actually. And all of those pop-sci explanations of quantum computing letting you have 'not just 1s and 0s but also a third bit that is both at the same time!' make my blood boil. If you ever read an explanation of quantum computing that describes it using Schrodinger's Cat, stop reading and close the tab. Quantum computing is about using overlapping probability waveforms that can interfere and cancel each other out at certain places. The idea is that by setting up the right waveforms, you can use their interference to find that the probabilities of the wrong answer cancels out to zero, and the probability of the right answer is the only one left. All this gumpf about 'parallel processing' is complete soykafe, or at least not related to quantum computing in the core sense.

>>79 doesn't really affect lainzine, it was hosted on gitla.in issue 4 was done but is getting reformatted due to some issues >>96 can you also tell us how it's going to be used in the future? (in the correct, non-schroedingers cat way)

>>97 The main thing about quantum computing as I understand it, is that it will never be useful for new problems - it requires a very specific and fiddly setup to get the appropriate waveforms for a problem. At the moment we can only use quantum computing for a select few simple problems, and while it seems likely in the future we'll be able to use it for more and more problems, I don't think its a generic one-size-fits-all solution to every single computing problem.

>>103 That was the take-away line from this blog which you might enjoy: http://www.scottaaronson.com/blog/

>>97 lainzine is moderated by Junk though, probably moving over to .jp if he's that arrogant :/

>>107 I worried about that too, asked him but he said he's probably going to change it too just lainchan's lainzine, without a specific domain

>>94 abstracted from the physics. it's more computational, you won't need a phys background to get it >>97 a vector of qbits each has a probability of being in one of two given states on observation, that looks like a probability distribution. great. now you can operate on bit vectors to change the distributions. build a circuit with gates that operate on probability distributions of qbit vectors. check the value of the output. check the value a few times. you can induce the distribution of outputs from a relatively small number of values. good for finding collisions, not a nondeterministic turing machine, can't represent extra bits with two bits, no time travel, no infinite resources, no virtual infinite parallelism. you can solve certain probability problems in fewer cycles. algorithms will precede hardware as people do stuff with math. so far as I understand anyway.

So, as we all know, NSA (and China, and Germany, and Russia) collect all my waifu's international SSH traffic right now. As I understand, in 20 years (at most, <10 is likely) NSA (and the rest) will get the QC and will be able to break the (ECC)DH exchange of the SSH session my waifu had today, fuarrrking up the SSH's pre-QC forward secrecy assumptions. Then they will take the symmetric stream cipher key out of the broken exchange and decrypt the soykaf out of the packets, collecting all the private bits. What can my waifu use right now for SSH (specifically) if the data her SSH sessions carry would still be sensitive 20-30 years from now? Assume life-or-death sensitive. 1Mb public keys are not a problem. Even secret sharing with a trusted offline courier that would carry a number of encrypted microSDs with secrets in body cavities and destroy any that were copied by border security can be arranged. One time pad is impossible, however, as there's just too much data to transfer, but 128Gb pre-shared secret can be done. So, let us start simple by assuming she has a small pre-shared secret on both client and server. Can she write something into the ssh_config on one or both hosts to wrap the stream data with an additional symmetric stream encryption layer (the key for which is not going to be stored encrypted with DH in Utah data center)? I assume the answer is yes. But how can she do that exactly?

Are full disk encryptions like LUKS safe against Quantum decryption?

>>917 >As I understand, in 20 years (at most, <10 is likely) NSA (and the rest) will get the QC honestly it might be more like 30 years. Getting lots of qubits to work together is a pretty big challenge and if I were the NSA, I'd be spending that time and money on side-channel attacks instead. >What can my waifu use right now for SSH (specifically) if the data her SSH sessions carry would still be sensitive 20-30 years from now? Assume life-or-death sensitive. All current QC-resistant crypto is experimental and relatively untested, I wouldn't rely on it in a life-or-death scenario. Use steganography to exchange AES256 keys(with a big file and <100 bytes of data, virtually undetectable with good algorithms) and use those to establish a secure channel. I'm don't really know if openssh can use pre-shared symmetric keys. Pretty sure it can't. >>918 yes.

>>918 Yes, and existing symmetric encryption algorithms can still be used. Just make sure you have 256-bit of security to protect you against quantum computers.

>>919 The university of Purdue is working on a more stable quantum computer at this moment with the support of guess who? MICROSOFT :D (internal frowny face) >One of the challenges in quantum computing is that the qubits interact with their environment and lose their quantum information before computations can be completed," Manfra says. "Topological quantum computing utilizes qubits that store information “non-locally” and the outside noise sources have less effect on the qubit, so we expect it to be more robust." also at the end of 2016: >Engineers at the University of New South Wales (UNSW) have created a new quantum bit that remains in a stable superposition for 10 times longer than previously achieved, dramatically expanding the time during which calculations could be performed in a future silicon quantum computer. about countering quantum decryption http://www.etsi.org/news-events/news/947-2015-03-news-etsi-launches-quantum-safe-cryptography-specification-group china is working on quantum encryption, can any of you phsyics/ compsci folks explain if quantum encryption is equally as unbreakable to quantum computers as traditional encryption is to traditional computers?

>>933 >can any of you phsyics/ compsci folks explain if quantum encryption is equally as unbreakable to quantum computers as traditional encryption is to traditional computers? quantum encryption is pretty much unbreakable if certain assumptions hold. It relies on the fact that it's impossible to read a piece of quantum information without changing it, so in key exchange you just discard the bits that were modified and make that your key. http://swissquantum.idquantique.com/?Quantum-Key-Distribution-Protocols

http://csrc.nist.gov/groups/ST/toolkit/examples.html just waiting for NIST PQC to be added to the toolkit

>>917 Elepppptical Curve Crypto DIffie Hellmans Mayonnaise has NSA trapdoors esp on mobile networks where the certificate is smalleer so think they can break your crypt

>>2633 >ECDH has NSA backdoors any reason to believe this? Or do you mean in the implementation?

>>2633 >>2634 >ECDH has NSA backdoors This is soykaf. I have to elaborate and clarify it again and again, ad infinitum. Yes, NSA did implanted a backdoor inside Dual_EC_DRBG, a CSPRNG based on elliptic curve cryptography. And yes, the most (and probably only) widely used elliptic curve encryption standard is NIST P-256 (384, 521), also known as prime256v1/secp256r1. This NIST standard has problematic design choices, and mysterious constants for equations generated by random seeds that nobody can explain, this MAY be a backdoor (we'll never have evidence, and it may be not). Daniel J. Bernstein doesn't trust it, Bruce Schneier doesn't trust it neither. and the problems (besides the suspicion of backdoor) of NIST P-curve is almost the consensus in cryptography communities. https://safecurves.cr.yp.to/ But, please don't be mistaken here, ECC, a.k.a ELLIPTIC CRYPTOGRAPHY itself, in general, is not broken, is a legitimate field of cryptography, and does not has a backdoor. This is why we are adopting Curve25519/Curve448 as alternative ECC/ECDH/ECDSA/whatever standard, integrating it in Tor/i2p/OpenSSL/TLS, even Apple iOS. The media coverage only focused on the "breaking news" of the story, as always, and if you just read the title and abstract (like most people), seriously misinformation occurs. The reason that we keep using it, or even used to advocate NIST's version of ECC, is because there was not secure alternative. The classical DH is deployed on all of the systems many years ago, then people forget it! Those are all using DH-1024, with a SAME parameter on millions of systems! And it is highly likely that the NSA cracked this single parameter. Asking people to fix their servers (by using a >=DH-2048 parameter) is like kicking dead whales down the beach, browser decided the most effective fix is simply KILL DH and switch to ECDH (now GCM ciphers can be used only with ECDH, for this reason). Even you are using it right now to establish a secure connection to lainchan.org. https://tools.ietf.org/html/draft-ietf-tls-curve25519-01 It is NOW possible to use Curve25519 for ECDH, the standardization is (almost) finished now, supported by Firefox and Chromium, and it is expected to be even more widely adopted after TLSv1.3 is completed. Perhaps we can ask Appleman to deploy it on lainchan.org if some of our lainons are really paranoid? But hey, it is a POST-QUANTUM cryptography thread anyway! Let's shift back to the topic if my clarification is good enough.