What SSH keys should I generate with ssh-keygen to be safe in a quantum computer based world?

Question

What SSH keys should I generate with ssh-keygen to be safe in a quantum computer based world?

Answer 1

Quantum computing will make many of the currently hard problems solvable in polinomial time. In the view of the practical IT security, it will essentially mean that it will be able to crack most currently used encryption algorithms, including the ones currently supported by ssh-keygen (openssl).

However,

• It is true only for a broad range of problems, and not for all.
• Despite the strong development efforts, it is still unclear, if quantum computers will be ever practical reality.
• openssl is modular, it can be easily extended with new ciphers, and developing a new cipher for it is much more easier, than cracking it.

No currently used ssh key will be proven safe in the quantum computing world. But it is not a major problem, because this world is currently imaginary.

Answer 2

In June 2019, there are no Post Quantum key formats that are standardized, so there is no PQ key format you can use. Just use ed25519 keys.

There is an ongoing NIST PQ Crypto standardization effort, you can follow its progress. Eventually, PQ key formats will be recommended and standardized and openssh will implement them and you will be able to use them.

Unless this is done in secret by someone very well funded (billions of dollars) like the NSA, a real quantum computer that can break NIST P-256 will take a very long time, and we will be aware of progress in that field (increasingly more capable quantum computers will be demonstrated). So before they become real, we will know and we will switch to some PQ scheme.

Now, consider what happens if you know that one year from today, the adversary will have a quantum computer capable of breaking NIST P-256, and you're using P-256 ECDHE for key exchange and ECDSA P-256 for authentication (or replace X25519 and Ed25519 instead of P-256, doesn't matter).

Well, what can they do with your ECDSA cert? They can do MitM attacks. What if you revoke the cert one day before their quantum computer becomes available, and switch to PQ cert? They can't MitM anymore. Of course, you don't want to cut it that close, but that's the idea with auth - you can't retroactively MitM connections.

But consider key exchange. If the adversary is already recording intercepted traffic, they record the key exchange. As soon as their big quantum computer becomes available, they can break the ECDHE, compute the symmetric key and decrypt all the traffic. Suppose you had one year of warning. They have all your traffic recorded, and they can decrypt all of it that is more than one year old. Does it still contain useful secrets? If yes, you have a problem. So you want more than one year of warning.

This logic - the possibility of retroactive decryption of recorded traffic, is what worries people. For example, the intelligence community want to protect names of traitors (foreign assets) for decades. So everyone is more anxious about key exchange, not authentication. That is why Google Chrome work on PQ kex for TLS and openssh work on PQ kex for ssh.

A small thing that helps is that you usually have a single long term auth key but you use a new keypair for each DH handshake. So to do MitM, they need to break your long term auth key, but to decrypt recorded traffic they need to break every handshake (suppose the amount of work breaking ECDSA and ECDHE is the same) - potentially making it not worth it. With ratcheting protocols like Signal, where a DH happens on every roundtrip, this would be very expensive to crack (compared to TLS and ssh).