NSA and quantum cryptography
12:00 Wednesday, 29 September 2021
UK Cyber Security Council
It’s 2021 and we are now at the point where the previously mythical concept of Quantum Computers is beginning to become a tangible, solid reality. This has brought with it the predictable raft of questions: will this new technology enable cyber-criminals to slip with ease through the security mechanisms – particularly the cryptography technology – that we use today? Well, in August 2021 the US National Security Agency produced a fascinating document containing its answers to some of the Frequently Asked Questions (FAQs) that people as around quantum tech and cyber security.
First off, the FAQ points out that current quantum computers are very small and generally based in research laboratories and are hence not what is deemed “cryptographically relevant” – that is, big enough to be a threat in terms of codebreaking. If a Crytographically Relevant Quantum Computer (CRQC) could be built, this would definitely present a threat according to the NSA.
Interestingly, though, the primary threat is to systems that use so-called “public key” cryptography, in which two endpoints establish a secure connection by exchanging public “keys” (security tokens) that interact with undisclosed private (secret) keys in order to encrypt and decrypt traffic. Public key cryptography relies for its security on the fact that a particular mathematical process is “intractable” – that is, it is believed to be possible but really, really difficult and inordinately time-consuming to compute. The mathematical process in question is “prime factorisation” – given a massively high number that was calculating by multiplying together two prime numbers, working out what those two prime numbers were. The belief is that quantum computers are likely to be quite good at prime factorisation, so if a quantum computer could reduce the time taken to calculate prime factors from several centuries to a few days or even hours, public key crypto as we know it is dead in the water.
Ironically, one example of a way to beat the quantum computer – a “quantum-resistant” mechanism as it’s termed – is to use a good old shared key. If two endpoints are given a massively long and complex key that they use to encrypt and decrypt data, there is no prime factorisation to be done – the quantum computer will, just like any other hacking device, simply need to run a brute-force attack (one that guesses every possible solution) and so the only thing that will help it is any basic raw speed benefit the quantum machine has over a traditional processor.
Is the NSA worried about quantum computers? “NSA does not know when or even if a quantum computer of sufficient size and power to exploit public key cryptography (a CRQC) will exist”, they say. In other words: they don’t know. They do, however, note that deploying new crypto technology to existing systems can take up to 20 years, which implies that if a CRQC can be built in the meantime, the threat will be tangible.
With regard to new quantum-resistant cryptography techniques, the FAQ is more than a little gloomy. There is a new technique called Quantum Key Distribution (QKD) which uses quantum technology for the key distribution element of a public key infrastructure. Sadly, says the NSA, none of the QKD systems that have actually been implemented have been proven to be secure, and that “NSA does not consider QKD a practical security solution for protecting national security information”.
Is the report all doom, gloom and despondency? No, because the NSA does have some positive points. It lists the current-day algorithms and techniques that it considers acceptable, and achieves this acceptability by hiking the size of the keys that must be used: for example, for key exchange it requires a 3,072-bit key if you’re using the Diffie-Hellman algorithm.
And NSA’s view on which quantum crypto algorithm is best for us to use to protect ourselves when a CRQC winks into existence? Don’t ask us, they say, go and see the National Institute of Standards and Technology (NIST) which is presently examining the options that have been produced so far.
The full FAQ is on the US government’s web site.