35C3 - The year in post-quantum crypto

This talk by djb and Tanja Lange is a good overview of the NIST candidates and the current state of pqcrypto: [VIDEO]

They're using a mixture of Streamlined NTRU Prime 4591^761 and X25519. [LINK] Note that this is still considered "experimental" and probably won't be enabled by default. I'd advise checking out some of the recent DJB and Tanja Lange talks for further detail on how research on these algorithms is progressing: [VIDEO] There's also the older but still relevant PQCHacks: [LINK] Haven't seen any talk of post quantum signatures in changelogs yet at least, but research is happening rapidly in this field and OpenSSH has really upped their game in recent years.

AES-256 is believed to be quantum-resistant. The only known quantum attack on AES-256 is utilizing Grover's algorithm, which is an universal approach. As for assymetric crypto, the ones we have now are susceptible to quantum attacks. There are a bunch of proposals for quantum-proof algorithms but nothing officially standardized yet. There is a NIST competition going on right now that is trying to find a new suite of assymetric cryptographic algorithms [1]. You can find an awesome talk on the topic here [2]. If quantum computers are possible, we should switch to quantum proof algorithms now rather than later, because then we'd reduce the traffic that can be decrypted at a later point in time. It's quite dangerous right now considering that basically everything is protected by quantum-non-resistant ciphers. [1]: [LINK] [2]: [VIDEO]

The problem is that the largest QCs that we know of in the public are so ridiculously weak that I find it incredibly improbable that any government is anywhere close to having large enough QCs to break anything. The largest QCs are on the order of tens of qubits, but in order to run Shor's algorithm (to break RSA, or the discrete-log equivalent to break Diffie-Hellman) you need hundreds or thousands of stable qubits -- and the current generation of qubits are unstable. You can make stable qubits out of unstable ones by using error correction, but that requires you to have ~1000 unstable qubits to make one stable qubit. So there's at least 5-6 orders of magnitude separating the current state-of-the-art and when classic public-key crypto will be broken. > Does signal use the quantum-proof variety of encryption? No, there is currently no trusted post-quantum encryption (though the real issue is finding a replacement for public-key crypto because that seems to be the weakest link where quantum computers appear to have the most power). It's being worked on but is a very new field. In addition most post-quantum systems require keys that are kilobytes or even gigabytes in size (elliptic curve keys are tens of bytes). djb (a very well-known cryptographer) and his colleagues give quite a few talks about this[1]. Funnily enough it appears that elliptic curves (which are harder for classic computers to break, and can be easier for classic computers to compute safely) are actually easier

> Google and others have experimented with it for https and it worked fine To be clear, Google didn't experiment with actually using post-quantum crypto. Their experiment was to figure out what was the largest key sizes that browsers and networks would accept before you start degrading connections. Their "post-quantum keys" were just padding bytes. This was gone through in the Bernstein and Lange talk this year at 35C3[1]. This is a good thing, given the history of the security of post-quantum candidates[2]. [1]: [VIDEO] [2]: [VIDEO]

PQ-Crypto is still a very young research area. There is no widespread (or even niche) use of PQ-Crypto algorithms, no consensus on how safe any of the proposed algorithms are (and many proposals were found to be exceptionally broken -- on classical hardware -- within weeks of their submission[1]). I'm not really sure it's fair to say that just because there are some on-paper algorithms (which have no usage outside academia at the moment ) that might solve the problem that it's false to say that "all modern PK crypto is broken with quantum attackers". But if you prefer, you could imagine that I said "all modern PK crypto [that is actually in use today] is broken". Because, at the end of the day, that's all that really matters. [As an aside, for RSA the security is provided by the hardness of factorisation which also breaks under QC attackers, not discrete log (it's discrete log for DH, and EC discrete log for ECDH).] [1]: [VIDEO]