Last July, the National Security Agency (NSA) issued CNSS Advisory Memorandum 02-15, available at the Advisory Memoranda page, updating the list of cryptographic algorithms that can be used in National Security Systems (NSS). A subsequent document referred to the new algorithms as the Commercial National Security Algorithm Suite (CNSA Suite), which replaces Suite B. The transition to the CNSA Suite took place two months before a Suite B deadline to discontinue the use of RSA, DH and DSA and rely exclusively on ECC algorithms for public key cryptosystems. The subsequent document explained the motivation for the transition by saying that “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,” and announced “preliminary plans” for a future transition to quantum-resistant algorithms.
This abrupt change of course, following many years of promoting ECC, took the cryptographic community by surprise. A paper by Neal Koblitz and Alfred Menezes discussed six different theories that were proposed to explain the timing of the announcment and the changes in the approved list of algorithms. Matthew Green referred to that paper as tackling “one of the great mysteries of the year 2015. Namely: why did the NSA just freak out and throw its Suite B program down the toilet?.”
NSA has recently published a document in the form of a list of Frequently Asked Questions (FAQs) that tries to dispel the mystery and put to rest the conspiracy theories. It does a good job of that, except for one important detail: it does not explain the omission of DSA from the list of approved algorithms.
Background
Suite B, introduced by NSA in 2005, listed algorithms approved for use in classified or unclassified NSS. Originally, ECDH and ECDSA were the only public key algorithms on the list. Use of RSA, DH and DSA with a 2048-bit modulus was later allowed up to the SECRET level (whereas ECC algorithms were allowed up to the TOP SECRET level). However, CNSSP No. 15 (retrievable from the Policies page) referred to RSA, DH and DSA as “legacy” algorithms and required their use to be discontinued by October 1, 2015. (RSA, DH and DSA require larger keys than ECDH and ECDSA for mitigation on known attacks, and larger keys, in turn, require longer computations.)
The transition from Suite B to CNSA made the following changes to the approved use of cryptographic algorithms in NSS:
- It discontinued the use of AES-128 up to the SECRET level, retaining the use of AES-256 up to the TOP SECRET level.
- It discontinued the use of Curve P-256 for ECDH and ECDSA up to the SECRET level, retaining the use of Curve P-384 up to the TOP SECRET level. (The security strengths provided by P-256 and P-384 are 128 and 192 bits respectively, while the security strength provided by AES is equal to the bitlength of the key.)
- It discontinued the use of SHA-256 up to the SECRET level, retaining the use of SHA-384 up to the TOP SECRET level. (The security strengths provided by SHA-256 and SHA-384 are 128 and 192 bits respectively.) It also introduced an exception for UNCLASSIFIED data and “community of interest separation,” which allowed for the use of SHA-256.
- It discontinued the use of RSA and DH with a 2048-bit modulus up to the SECRET level (previously slated to expire on October 1, 2015), but reclassified RSA and DH as “supported” algorithms rather than “legacy” algorithms, and allowed their use with a 3072-bit modulus up to the TOP SECRET level. (A 2048-bit modulus provides a security strength of 112 bits for RSA and DH, while a 3072-bit modulus provides a security strength of 128 bits.) The exception for UNCLASSIFIED data and community of interest separation allowed the use of RSA and DH with a 2048-bit modulus in addition to the use of SHA-256.
- It omitted DSA altogether from the new list of approved algorithms.
- It permitted the use of key establishment without forward secrecy, which was prohibited in Suite B. This change was not explicitly stated in last summer’s announcements, but was implicit in the fact that the CNSA Suite allows the use of RSA for key establishment, whereas Suite B only allows the use of ECDH. While RSA, DH and ECDH can all be used for key establishment with or without forward secrecy, DH and ECDH key pairs are typically ephemeral and thus provide forward secrecy, whereas RSA key pairs are typically long term credentials that do not provide it. One of the questions in the FAQs document (first question on page 10) confirms that the CNSA Suite does intend to retreat from the forward secrecy requirement.
Explanations of the changes
Three major aspects of last summer’s announcements called for explanation: the new emphasis on transitioning to quantum-resistant cryptography; the abandonment of the requirement to switch to ECC by October 1; and the timing and abruptness of the announcements. Several details also deserved explanation: the elimination of a tier of algorithms that are only allowed up to the SECRET level; the inconsistent security strengths of the algorithms usable at the TOP SECRET level (256 bits for AES, 192 bits for ECDH, ECDSA and SHA, 128 bits for RSA and DH); the exception allowing RSA and DH with a security strength of only 112 bits and SHA with a security strength of 128 bits for UNCLASSIFIED data and community of interest separation; the retreat from the forward secrecy requirement; and the omission of DSA from the list of approved algorithms.
The announcements themselves provided some explanations, and the FAQs document do a more thorough job, failing only to explain the omission of DSA.
Regarding the emphasis on transitioning to quantum-resistant cryptography, the FAQs refer to “growing research in the area of quantum computing,” and to the long life-cycles of cryptographic algorithms used in NSS: “Algorithms often require 20 years to be fully deployed on NSS. NSS equipment is often used for 30 years or more. National security information intelligence value is often 30 years (sometimes more), although it may vary depending on classification, sensitivity, and subject.” Together, these two factors mean that, even though quantum computing may not be a threat in the near future, it may become a threat during the lifetime of algorithms that are provisioned in the near future.
The FAQs also mention the “maturity of quantum resistant algorithms” and says that “NSA looks to NIST to identify a broadly accepted, standardized suite of commercial public key algorithms that are not vulnerable to quantum attacks.” NIST has taken the hint and published a draft Report on Post-Quantum Cryptography that includes an announcement of a forthcoming standardization process.
The retreat from requiring exclusive use of NIST elliptic curves for public key cryptography is explained by a desire to save money: “NSA does not want to force NSS operators to pay for two cryptographic upgrades: first from RSA/Diffie-Hellman to ECC and then from ECC to quantum resistant cryptography.” But the FAQs also hint at other reasons, saying that “NSA has come to appreciate that some of these legacy systems will be around for much longer than we had planned,” and that “the external community appears to be shifting somewhat toward the use of other elliptic curves.”
Both the resistance to the adoption of ECC and the shift to other elliptic curves can be explained at least in part by the Snowden revelations, and in particular by the confirmation of the backdoor in the Dual Elliptic Curve DRBG. In a presentation on the Current State of ECDSA on the Web at last year’s NIST ECC workshop, Rick Andrews of Symantec cited “distrust in Suite B curve choices after Snowden, especially in Europe” as one factor holding back the market for ECDSA certificates.
Paradoxically, the Dual Elliptic Curve DRBG backdoor, which I described in the previous post by elaborating on slides by John Kelsey, does not exploit any weakness in the NIST curves, nor more generally in ECC. Dual Elliptic Curve DRBG makes use of a group of points of an elliptic curve, but a DRBG could be similarly implemented on any group where the discrete log problem is hard, and a backdoor could be similarly constructed on any such implementation.
The FAQs make three points to explain the timing of the announcements: that “consistent advances in quantum computing are being made,” that “there are many more proposals for potentially useful quantum resistant algorithms than were available 5 years ago,” and that “the mandatory change to elliptic curves that would have been required in October 2015 presented an opportune time to make an announcement,” in order to “move to quantum resistant symmetric key options” and “allow additional continued use of older public key options as a way to reduce modernization costs in the near term.” These points make sense, but cynics might add that making the announcements two months before the October deadline avoided the embarrassment of missing the deadline.
The details are explained as follows. The motivation to eliminate the SECRET tier is attributed to technological advances that reduce the need for less computationally demanding algorithms at the SECRET level and thus provide an opportunity to resolve interoperability problems caused by having two tiers. The requirement to use AES-256 rather than AES-192 is not explained in the announcements, but was explained in the 2005 Suite B Fact Sheet as an interoperability enhancement (AES-192 is rarely implemented). The use of RSA and DH with a 3072-bit modulus that only provides 128 bits of security is said to be due to “technology constraints.” (This is consistent with Table 2 of NIST SP 800-57, which lists RSA, DH and DSA as requiring a 7680-bit modulus to achieve a security strength of 192 bits, and marks them as excluded from NIST standards at that security strength “for interoperability and efficiency reasons..” However, the timings of modular exponentiation in JavaScript that we announced in an earlier post suggest that RSA, DH and DSA are practical at the 192-bit security strength.)
The July advisory memorandum attributed the exception that allows the use of RSA and DH with a 2048-bit modulus and the use of SHA-256 for UNCLASSIFIED data to the existence of large scale deployments of PKI systems that use 2048-bit RSA and, in July, were in the midst of transitioning from SHA-1 to SHA-256; and to the existence of equipment that is not able to use DH with moduli larger than 2048-bits.
The FAQs explain that key establishment without forward secrecy is permitted because it is being used in NSS equipment, and continued use of RSA without forward secrecy is allowed “for the ease of NSS operators.”
The omission of DSA
These explanations demystify the changes made last summer, but do not address the omission of DSA from the list of approved algorithms. I suppose it was omitted simply because it is not being used, and no explanation was provided because nobody asked for one. But if so, I’d like to argue that the omission of DSA is a mistake.
Historically, DSA has not been popular for several reasons. It was specified by NSA, and there were concerns that it might have a backdoor. It provided a patent-free alternative to RSA and was opposed by the RSA company, which owned the patent. (The RSA company was later acquired by Security Dynamics and is now part of EMC). It is encryption-free, whereas RSA can be used for both encryption and digital signature; for that reason it was viewed by some with hostility for being a weapon in the government’s war against encryption. It must be combined with DH for secure connection establishment, whereas RSA can be used by itself for key transport, which gives a great advantage in terms of simplicity. It is randomized, which was viewed by developers as complicating implementation. And it is slower than ECDSA.
In spite of all this, DSA was included in most cryptographic libraries and most security protocols. But now it has been omitted from the draft of TLS 1.3, and from the W3C’s Web Crypto API. This comes at the wrong time, now that most of the drawbacks of DSA are going away:
- After 30 years of public scrutiny, nobody suspects DSA of having a backdoor. (Intuitively, I find it hard to imagine where such a backdoor could be hidden, whereas there seem to be potential hiding places for backdoors in ECC.)
- The simplicity advantage of RSA over DSA for secure connection establishment is being erased in the private sector by a push to provide forward secrecy, which requires RSA to be combined with DH just like DSA. While the CNSA Suite is retreating from the Suite B requirement of forward secrecy, a growing number of web servers on the Internet provide it. According to the SSL Pulse survey published on February 2, 2016, only 21.9% of the top one million web sites do not support forward secrecy.
- And cryptographic random bit generators are becoming available to developers in all computing environments.
DSA is now the best option for cryptographic client authentication, and in particular for client authentication with an uncertified key pair, which is becoming popular as a password replacement. As noted above, contrary to RSA, DSA is encryption-free. This generated hostility in the nineties; but today it should be viewed as an advantage, because it means that DSA is not subject to the export restrictions on encryption software, which have been relaxed but are still burdensome. A DSA signature requires less computation than an RSA signature with a full-size private exponent, and less computation means more battery life in mobile devices. (RSA signatures can be sped up by using a less-than-full-size private exponent, but that forces a full-size public exponent on the verifier.) DSA is slower than ECDSA, but ECDSA now has two serious problems: lack of trust, and a proliferation of different curves that hinders interoperability.
I understand that NSA wants to move forward to quantum-resistant cryptography and is only allowing the use of RSA and DH to avoid disrupting existing practice in NSS. If DSA is not being used, nothing is disrupted by dropping it. But the standardization process announced in the NIST report on post-quantum cryptography will take time. According to the NIST report, it will allow 3 to 5 years of public scrutiny, after proposals of quantum-resistant algorithms are submitted late in 2017. Therefore standardized quantum-resistant algorithms may not be available until 2022. In the meantime, commercial systems using DSA may well appear in the commercial marketplace. I don’t see what NSA has to gain by forbidding their use in NSS.