Oct 12,
2015

A recent NSA update addressed the Suite B cryptographic algorithms approved by NSA for protecting U.S. Government data. If you skip ahead to its table of recommendations you will see that some old friends have disappeared — AES with a 128-bit key and SHA-256 have been quietly dropped. The more startling part is in the early “Background” section:

“IAD will initiate a transition to quantum resistant algorithms in the not too distant future.”

Quantum physics has two opposing applications in cryptography.

First, **quantum key distribution** or QKD is *defensive* technology used to maintain secrets. Quantum signaling with isolated photons can securely distribute keys. These could be 256-bit keys used for a symmetric cipher, or possibly even one-time pads for ultimate security.

Second, **quantum computing** is a potentially *offensive* technology used to break ciphers and expose secrets. If, or perhaps when, a general-purpose quantum computer becomes available, it might be useful to immediately break ciphers that are extremely strong against today’s best known attacks.

**Quantum resistant** algorithms would resist these new quantum attacks.

No one (so far) has devised an algorithm that would allow a quantum computer to rapidly discover the key used by a symmetric cipher. Grover’s algorithm shows that a quantum computer would have an advantage, but only a limited one defended against with an increase in key length.

The problem is that symmetric ciphers need shared secrets, and so we have no way with just symmetric crypto to establish new secure connections. Technology like TLS, used to secure HTTPS and most of the rest of secure Internet communication, uses public-key or asymmetric cryptography to authenticate the end points and establish the *session key* used with an efficient symmetric cipher for just this one connection.

Asymmetric cryptography involves key pairs — a public key and a private key. An attacker cannot use the public key to figure out the private key without solving a difficult math problem. The algorithms and key sizes are chosen to make the attack overwhelmingly difficult. For RSA, this means solving the **Factoring Problem,** finding the prime factors of a number hundreds of digits long. For Elliptic Curve Cryptography (or ECC), solving the **Elliptic Curve Discrete Logarithm Problem.** And for breaking Diffie-Hellman key agreement, used to negotiate shared secret keys, solving the **Discrete Logarithm Problem.**

These are *trapdoor functions*, math problems that are enormously more difficult to do in one direction than the other. Solving the difficult version is extremely difficult, so difficult that we assume that a reasonable adversary will either give up or take so long that we would no longer care about them finding the solution. But any solution is easy to verify. It is easy for a computer to multiply together two large prime numbers even if they have 150 digits each. It would take an enormous amount of work to start with their 300-digit product and work backward, discovering those two prime factors.

Prime numbers and factoring are part of number theory, a topic that has fascinated mathematicians since ancient Greece. We have a very good idea of what is possible and how much work it takes.

Shor’s algorithm is a way of immediately solving the factoring problem, thus rendering RSA suddenly insecure, *if* you have a general-purpose quantum computer. That threat pushed crypto development to other trapdoor functions, especially ECC for encryption. But that NSA announcement says:

“Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be.”

GCHQ, the UK equivalent to NSA, published a paper showing how other techniques once thought secure are susceptible to quantum attack.

It’s not common front-page news, but there is good news: alternative quantum-resistant cryptographic algorithms are now a rich field of study. The Post-Quantum Crypto conference series has been running since 2006, and there are other conferences and workshops. Key sizes will be large, at least several thousand bits and ranging up to several million bits for some algorithms, and much study remains to investigate their theoretical security. After that will come the work to make them practical, and then to produce software implementing them. But NSA and GCHQ say it’s time to start working!

If you don’t know about this field, it’s time for you to start learning! Learning Tree’s System and Network Security Introduction course explains the concepts and then lays out today’s toolkits. As for the coming post-quantum world, we’ll have to wait and see.

image sources

- Post-Quantum Cryptography: Bob Cromwell