On August 11th, the National Security Agency (NSA) announced their preliminary plans for transitioning to quantum resistant algorithms and away from the Suite B cryptographic algorithms specified by the National Institute of Standards and Technology (NIST). They even said vendors that haven’t yet switched to Suite B algorithms should not do so at this point, and instead use their resources “to prepare for the upcoming quantum resistant algorithm transition.” They then went on to say “Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy.”
I laud the NSA for this public recognition of the quantum computing threat. Quantum computing is a real threat to the Public Key Infrastructure (PKI) that is in place today and needs to be addressed.
For those of you not familiar with the threat, quantum computers are able to execute Shor’s Algorithm, which has been proven to be able to break RSA and ECC, the two most popular crypto algorithms used in PKI and digital signatures. Quantum computers of sufficient strength to run Shor’s Algorithm do not yet exist, but there has been significant progress in academic and corporate research (and probably government as well), including:
- Researchers move quantum computing to silicon
- Google launches Quantum Artificial Intelligence Lab
- Snowden documents state the NSA is running a $79.7 million research program with the aim of developing a quantum computer capable of breaking encryption
- IBM scientists achieve critical steps to building first practical quantum computer
- Breakthrough opens door to affordable quantum computers
The impact of breaking RSA and ECC is significant, as they are the backbone of most of the world’s secure network communications, including HTTPS websites, software updates, eCommerce, etc. With broken RSA and ECC, we will no longer be sure our information isn’t being intercepted, changed, or that anyone we exchange information with is who they say they are.
But as the NSA mentions, there are a few cryptographic algorithms resistant to all known quantum computing attacks, including NTRU, a lattice-based asymmetric (public/private key) cryptosystem from Security Innovation and the leading alternative to RSA and Elliptic Curve Cryptography . In a report titled Quantum Resistant Public Key Cryptography: A Survey, NIST wrote, "Of the various lattice based cryptographic schemes that have been developed, the NTRU family of cryptographic algorithms appears to be the most practical...smallest key size...highest performance.”
Replacing RSA and ECC with a quantum safe algorithm is not an easy task and will take time. This is likely the reason the NSA is pushing for this transition now, before powerful quantum computers exist. There is some reluctance by those in charge of a company’s crypto infrastructure to change, as it is perceived as a costly and time-consuming effort – it’s better to leave the problem for their successor. But we have recently submitted an Internet Draft to the Internet Engineering Task Force (IETF) for a Quantum Safe Hybrid (QSH) that allows users to protect their network traffic with any conventional algorithm (like RSA) AND a quantum safe algorithm (like NTRU). This allows for an easier transition to post-quantum security while still maintaining current crypto schemes until they gain trust in the new post-quantum crypto solutions. It could also protect internet traffic from being collected and stored now and being harvested once quantum computers are available. And in most cases, the post quantum crypto is so fast relative to RSA that the performance penalty is negligible.
The NSA is right to get in front of the issue and boost the public’s awareness of the quantum computing threat. An unprepared company could be devastated once quantum computers arrive. I hope that the public heeds this warning and pushes for companies and governments take appropriate counter-measures.
To learn more about NTRU, visit our FAQ page for commonly ask questions on benefits, how it works, and how it can help solve your business security problems.
Note: Original post post adapted from Embedded.com.
