PQCrypto
Post-Quantum Cryptography (PQCrypto)
In ~10 years Quantum Computers will break todays common asymmetric public-key cryptography algorithms used for web encryption (https), e-mail encryption (gnupg...), ssh and others. |
Contents
Quantum Computers[edit]
Quantum computers are based on the phenomena of quantum mechanics as opposed to classical computers familiar to everyone today. They are made up of qubits that can express many different states simultaneously, solving some types of mathematical problems in near instant time. Assembling a quantum computer is now an engineering problem rather than one impeded by laws of physics - a theoretically imperfect machine can still yield useful results. Such a computer is sought after by every heavy-weight adversary because of implications for public-key cryptography systems widely used today. Ciphertext unbreakable by today's classical computers will be shredded into ribbons by a large quantum computer. The Snowden documents reveal that every piece of encrypted data traversing the internet is intercepted and stored indefinitely for decryption should there be a breakthrough. A global arms race by the United States, EU, Russia, China and Israel has ensued.
The academic and corporate world estimate that a large quantum computer will be built in 10-15 years from now (as of 2016). It is safe to assume the time is even less for intelligence communities.
Broken and Impacted Cryptographic Algorithms[edit]
The US National Institute of Standards and Technology has recently summarized the impact of quantum computing on common cryptographic algorithms. The table below summarizes these findings.
Cryptographic Algorithm | Type | Purpose | Quantum Computer Impact |
---|---|---|---|
AES-256 | Symmetric Key | Encryption | Larger Key Sizes Needed |
SHA-256. SHA-3 | - | Hash Functions | Larger Output Needed |
RSA | Public Key | Signatures, Key Establishment | No Longer Secure |
ECDSA, ECDH ^{[1]} | Public Key | Signatures, Key Exchange | No Longer Secure |
DSA ^{[2]} | Public Key | Signatures, Key Exchange | No Longer Secure |
The emergence of quantum computers would break all asymmetric public-key cryptography and signature algorithms used today - the type of cryptography that protects communications over the internet. The size (strength) of symmetric keys is also halved, meaning 256-bit keys drop down to 128-bit. This is the type of cryptography used for Full Disk Encryption (encrypting data with a passphrase).
All current generation symmetric cryptographic authenticated modes such as CBC-MAC, PMAC, GMAC, GCM, and OCB are completely broken and this also applies to many CAESAR competition candidates: CLOC, AEZ, COPA, OTR, POET,OMD, and Minalpher. ^{[3]}
For more details visit https://pqcrypto.org/
What now?[edit]
The answer is Post-Quantum (PQ) Cryptography. It is a drop in replacement for crypto libraries deployed now except it uses different types of math problems known to be "quantum hard" meaning it is just as difficult for a Quantum Computer to solve as it is for Classical ones.
Competent cryptographers are in the process of improving performance of PQ Crypto and designing cipher-suites efficient for everyday use. The Tor Project are planning to migrate to quantum resistant ciphers by version 0.2.9.x.
Tor tickets for the transition can be followed here.
Initial recommendations for PQ Crypto algorithms were published September 2015.
Software[edit]
This is a listing of Free Software known to known to resist quantum computers and not an endorsement for any particular tool. You are better off setting up arbitrary protocols over Tor Onion Services once PQ crypto is deployed to mitigate exposure in case of unknown implementation failures in each and every other tool (with the exception of one-time pads that are information theoretically secure).^{[4]}
Informal adoption checklist:^{[5]}
- Quantum-resistant algorithms have withstood susbstantial cryptanalytic efforts.
- Crypto libraries written by competent cryptographers and audited for correct implementation.
- Widely adopted for better blending in.
Setup Guides[edit]
Codecrypt[edit]
This is a GnuPG-like unix program for encryption and signing that uses only quantum-computer-resistant algorithms:^{[6]}^{[7]}
- McEliece cryptosystem (compact QC-MDPC variant) for encryption
- Hash-based Merkle tree algorithm (FMTSeq variant) for digital signatures
Codecrypt is free software. The code is licensed under terms of LGPL3 in a good hope that it will make combinations with other tools easier.
Installation and Usage[edit]
Codecrypt is now included by default within Whonix 14. See the manual page for common use-cases.
Message Formatting[edit]
It is still possible to format your messages to account for replies without direct Thunderbird support. However pay attention to prevent mistakenly sending unencrypted replies. TorBirdy disables syncing drafts with your e-mail host's server however its advised to disable your internet connection temporarily in case you hit send without encrypting the message in Codecrypt.
Steps:
- Click reply in Thunderbird and copy the string "John Doe:"
- Format what your correspondent said as a reply by pasting it like so:
Edit
->Paste As Quotation
- Copy the result to the text editor window and continue composing your message with your replies interspersed between the quotes then save and encrypt
- Paste the ciphertext into the Thunderbird reply window, completely replacing what was there
- Re-enable internet then send.
OneTime[edit]
OneTime^{[8]} is a program that sets up a one-time pad on your computer and protects from reusing pads and shooting yourself in the foot. OneTime is available in Debian.^{[9]} One-time pads are the only provably unbreakable encryption scheme ever invented (assuming a functional/non-backdoored RNG).^{[10]}^{[11]}
OneTime can encrypt any kind of file -- it doesn't matter if the file's contents are Base64-encoded or not, because OneTime is not interpreting the contents of the file. It just treats the file as a string of bits. (The same is true of just about all encryption software, by the way; OneTime is not unique in this regard.)
One-time pads should be secure against cryptographic attacks by quantum computers for the same reason they're secure against any other kind of attack: if the encryption key is truly random, and the key is as long as the message, then all possible plaintexts are equally likely. Quantum computers are not telepathic, so there shouldn't be any way they can attack a message properly encrypted with a one-time pad. Indeed, there really is no possible cryptographic attack against such a message. (Of course, using the system in practice can be difficult, due to the logistics of key exchange, but quantum computing won't affect that.)^{[12]}
Limitations:
- The message and the key are identical in size - but with large hard-disks these days this is not a problem.
- There is no way to securely contact someone you don't know - you must exchange the pad file in person or by other trustworthy peers. Sending the pad online makes it as strong as the asymmetric crypto you are using.
- No message integrity. There is no way for the recipient to discover if the ciphertext has been tampered with during transit.
- You must never ever reuse the pad to encrypt another message. Doing so breaks the the encryption.^{[13]}
Misc[edit]
Footnotes[edit]
- ↑ Elliptic Curve Cryptography.
- ↑ Finite Field Cryptography.
- ↑ Breaking Symmetric Cryptosystems using Quantum Period Finding
- ↑ https://en.wikipedia.org/wiki/Information_theoretic_security
- ↑ https://forums.whonix.org/t/post-quantum-cryptography-pqc/2011/17
- ↑ https://github.com/exaexa/codecrypt
- ↑ http://e-x-a.org/codecrypt/
- ↑ https://github.com/kfogel/OneTime
- ↑ https://packages.debian.org/search?searchon=names&keywords=onetime
- ↑ https://en.wikipedia.org/wiki/One-time_pad
- ↑ http://users.telenet.be/d.rijmenants/en/onetimepad.htm
- ↑ https://github.com/kfogel/OneTime/issues/14#issuecomment-218038898
- ↑ https://en.wikipedia.org/wiki/Venona_project#Decryption
Did you know that Whonix could provide protection against backdoors? See Verifiable Builds. Help is wanted and welcomed.
This is a wiki. Want to improve this page? Help is welcome and volunteer contributions are happily considered! See Conditions for Contributions to Whonix, then Edit! IP addresses are scrubbed, but editing over Tor is recommended. Edits are held for moderation.
Whonix is a licensee of the Open Invention Network. Unless otherwise noted, the content of this page is copyrighted and licensed under the same Libre Software license as Whonix itself. (Why?)