In August 2015 the NSA released a major policy statement on the need for post-quantum cryptography, updating its Suite B recommendations in the process.

The announcement surprised most of the crypto community with inconsistencies in the recommendations and interrogations about whether or not the threat posed by quantum computers was overblown.

In their “A Riddle Wrapped in an Enigma” paper, N. Koblitz & Alfred Menezes speculated about NSA freaking out about the adoption of ECC. Matthew Green also critically blogged about the paper.

Earlier this month, the IAD quietly posted a FAQ document providing some more details about the changes in the recommendations. Here are some highlights.

Compliance

In the NSA COMSEC Guide it was revealed that NSA was highly interested in collaborating with the industry so that industry could provide more “integrated” encryption solutions and NSA wouldn’t have to layer crypto on top of commercial products. Therefore, the FAQ document is mostly targeted for these “NSS” (national security systems) vendors.

Timing

The FAQ claims that the timing of the Suite B updates was an opportune moment to make the announcement about Quantum resistance but no particular breakthrough motivated the update of the recommendations.

Primitives

The current Suite B recommendations are:

  • RSA 3072-bit or larger
  • DH 3072-bit or larger
  • ECDH and ECDSA with NIST P-384
  • SHA-384
  • AES-256

with the note:

NSA prefers the use of ECDH with P-384 and 3072-bit DH for key establishment.

And the document explicitly says the following primitives should no longer be used for NSS:

  • ECDH and ECDSA with NIST P-256
  • SHA-256
  • AES-128
  • RSA with 2048-bit keys
  • DH with 2048-bit keys

Threat of Quantum Computing

The document says that it takes up to 20 years for algorithms to be fully deployed on NSS, and the equipment is often used for 30 years or more. NSA refers to “many experts” that predict a quantum computer capable of effectively breaking public key crypto within that timeframe and that it is important to address that concern.

Choosing the right time to champion the development of quantum resistant standards is based on 3 points: forecasts on the future development of a large quantum computer, maturity of quantum resistant algorithms, and an analysis of costs and benefits to NSS owners and stakeholders. NSA believes the time is now right—consistent advances in quantum computing are being made, there are many more proposals for potentially useful quantum resistant algorithms than were available 5 years ago, and the mandatory change to elliptic curves that would have been required in October 2015 presented an opportune time to make an announcement. NSA published the advisory memorandum to move to quantum resistant symmetric key options and to allow additional continued use of older public key options as a way to reduce modernization costs in the near term. In the longer term, NSA is looking to all NSS vendors and operators to implement standards-based, quantum resistant cryptography to protect their data and communications.

NSA on NIST

NSA will continue to support NIST in the standardization process and will also encourage work in the vendor and larger standards communities to help produce standards with broad support for deployment in NSS. NSA believes that NIST can lead a robust and transparent process for the standardization of publicly developed and vetted algorithms, and we encourage this process to begin soon. NSA believes that the external cryptographic community can develop quantum resistant algorithms and reach broad agreement for standardization within a few years.

Does the fact NSA is making this change today mean a quantum computer exists?

NSA does not know if or when a quantum computer of sufficient size to exploit public key cryptography will exist. The cryptographic systems that NSA produces, certifies, and supports often have very long life-cycles. NSA has to produce requirements today for systems that will be used for many decades in the future, and data protected by these systems will still require cryptographic protection for decades after these solutions are replaced. There is growing research in the area of quantum computing, and enough progress is being made that NSA must act now to protect NSS by encouraging the development and adoption of quantum resistant algorithms.

QKD

NSA briefly mentions QKD as a possible solution. I haven’t seen any QKD scheme myself that has the desired no-MITM property that it claims it has. Most schemes make the unreasonable assumption that there exists a public classic channel between Alice and Bob and that Eve would only mess with the qubits. This assumes that the classical channel is already authenticated so it doesn’t really solve the post-quantum crypto problem since they already have a secure communication channel (symmetric crypto is not believed to be vulnerable to QC if key sizes make a Grover search unfeasible).

NSA says they have no plans to use quantum cryptography, it wouldn’t be realistic to do so.

On the RSA/DH recommendation

NSA wants to keep supporting these “legacy” algorithms because of cost effectiveness, suggesting that asking those vendors to move to ECC, only to move to a post-quantum algorithm in a few years would be a waste of effort.

NSA makes it clear that they still encourage vendors to move to ECC, but if the vendors can’t comply to the new advisory within a limited timeframe, they can just transition to the quantum resistant cryptography, whenever that comes.

Conclusion

The document brings light to some of the questions the crypto community had been wondering about since the announcement. Not all recommendations are equal. Nuancing that some algorithms (DH & RSA) are now being transitioned towards “legacy” status but are still in the recommendation for giving vendors more time to transition is an important clarification.

I believe ECC isn’t going away anytime soon, especially for systems at scale. Some HTTPS reverse-proxies serve millions of users and the move to quantum resistant crypto would make that impractical due to increased key sizes. Therefore, suggesting that vendors can just bump RSA key size waiting for a post-quantum standard sounds unwise.

It’s exciting to see more people looking at NTRU or McEliece and working on better implementations than the naive academic ones but there is still a long way to go before large scale deployments.

Probably see you on a NIST, CFRG or PQCrypto mailing list to discuss this further!