NSA removed EC-256 and SHA-256 from CNSA recently--should we be alarmed by this?
No.
There is one overwhelming reason why, as stated in the document:
The cryptographic systems that NSA produces, certifies, and supports often have very long lifecycles. 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.
NSA standards and NIST standards for "industry" are not the same from an implementation perspective, if you want your web server to start using a 512-bit curve instead of 256, you may need to upgrade openssl, but usually it only takes less than a day to make the change once authorized. An NSA certified hardware device used by operatives in deep cover on the other hand, not nearly so easy to replace. Also milspec radios, satellite communications, comm hardware installed in a submarine.... none of those are replaced often and may have more than a decade of testing after design is complete. Same thing with key rotation intervals, and the amount of time data may need to remain confidential, all much longer for national security.
With the "industry" sun-setting of security levels below 128-bits in about 8 years, and perhaps levels below 160 bits a decade later, doing the math you can imagine that NSA standards may require about 2 decades of security beyond industry... and this is in fact mentioned in the document:
New cryptography can take 20 years or more to be fully deployed to all National Security Systems.
So now it makes perfect sense, they are simply trying to be ahead of the already well documented and understood trends regarding key sizes for use in the future, but need to act NOW because of the long timeframes involved in validating, purchasing, and replacing new hardware and software.
Dropping SHA-256 for SHA-384 can be seen as logical for several reasons. The first and foremost, you MUST use a 384-bit curve or larger, second is performance on 64-bit platforms, and third is it shares a common code base with the larger SHA-512 for asymmetric implementations still targeting 256-bit security.
So that brings us back to dropping of P-256... is that a big deal at this point? In 2041, 20 years from now, it certainly won't be, and that is why we should NOT be alarmed in the slightest, I would expect 160-bit security to be the minimum, even for low security civilian applications. For AES now that means 192-bits or larger, with a matching 384-bit signature scheme, and that is what is specified in the document.
If you recall the AES competition, the target lifespan was until 2030, so it may be the case that in 2041, we will already be using a fancy new block cipher from another competition. Of course, AES has held up extremely well to practical attacks on its mathematics.
Reading through the document, it appears these standards are not just for the public sector or private contractors handling classified documents, but rather everyone (public and private).
Not really, this is specifically in regards to commercial products implementing encryption for use by the US government, that implement non-classified algorithms from the CNSA suite. Commercial here can mean off the shelf, or developed by a contractor to fulfill a government requirement. These products still must be validated using other criteria, but they must implement the listed algorithms while NOT implementing algorithms that do not need the minimum security requirement (citation needed on that one), though they may still implement the Suite B algorithms with strong security, at least for now.
So focus instead on how the document engages the quantum threat: Use symmetric algorithms or wait until the CNSA suite is updated with quantum resistant asymmetric algorithms (almost certainly lattice based) after NIST publishes a draft standard, sometime between next year and 2024.
If they were really freaking out about quantum attacks, it would be because they themselves had developed a practical attack, and were concerned China/Russia/Iran would not be far behind, and would be taking drastic steps at great expense.
I pulled up the NIST SP 800-56A Rev3 to gather more information and that document essentially states that even unclassified data seems to be a no-go when it comes to curves below EC-384.
Where do you see that? Under Table 24: Approved elliptic curves for ECC key-agreement., even 224-bit curves and 2048-bit prime groups are still listed, though they are very clear about the targeted security strength. It just so happens that CNSA cherry pics the algos that meet their security, implementation, flexibility, and interoperability requirements.
The NIST standards are more about saying you are allowed to use this now, and the NSA doc is more about what you are allowed to start using now, there is overlap but purpose is very different, nothing seems out of the ordinary, in fact I would consider NOT mandating larger key sizes than given in the doc to be the most telling about how we should not panic... so don't panic.
