[Cryptography] NSA and cryptanalysis

Jerry Leichter leichter at lrw.com
Mon Sep 2 00:06:21 EDT 2013

On Sep 1, 2013, at 6:06 PM, Perry E. Metzger wrote:
> We know what they spec for use by the rest of the US government in
> Suite B.
> http://www.nsa.gov/ia/programs/suiteb_cryptography/
>  AES with 128-bit keys provides adequate protection for classified
>  information up to the SECRET level. Similarly, ECDH and ECDSA using
>  the 256-bit prime modulus elliptic curve as specified in FIPS PUB
>  186-3 and SHA-256 provide adequate protection for classified
>  information up to the SECRET level. Until the conclusion of the
>  transition period defined in CNSSP-15, DH, DSA and RSA can be used
>  with a 2048-bit modulus to protect classified information up to the
>  SECRET level.
>  AES with 256-bit keys, Elliptic Curve Public Key Cryptography using
>  the 384-bit prime modulus elliptic curve as specified in FIPS PUB
>  186-3 and SHA-384 are required to protect classified information at
>  the TOP SECRET level. Since some products approved to protect
>  classified information up to the TOP SECRET level will only contain
>  algorithms with these parameters, algorithm interoperability between
>  various products can only be guaranteed by having these parameters as
>  options.
> We clearly cannot be absolutely sure of what they actually use, but
> we know what they procure commercially. If you feel this is all a big
> disinformation campaign, please feel free to give evidence for that. I
> certainly won't exclude the possibility, but I find it unlikely.
I'll make just a couple of comments:

- Given the huge amount of material classified these days, SECRET doesn't seem to be a very high level any more, whatever its official definition.  TOP SECRET still means a great deal though.  But the really important stuff is compartmented (SCI), and Suite B is not approved for it - it has to be protected by unpublished Suite A algorithms.

- To let's look at what they want for TOP SECRET.  First off, RSA - accepted for a transition period for SECRET, and then only with 2048 bit moduli, which until the last year or so were almost unknown in commercial settings - is completely out for TOP SECRET.  So clearly they're faith in RSA is gone.  (Same for DH and DSA.)  It looks as if they are betting that factoring and discrete logs over the integers aren't as hard as people had thought.

The whole business of AES-128 vs. AES-256 has been interesting from day one.  Too many recommendations for using it are just based on some silly idea that bigger numbers are better - 128 bits is already way beyond brute force attacks. The two use the same transforms and the same key schedule.  The only clear advantage AES-256 has is 4 extra rounds - any attack against the basic algorithm would almost certainly apply to both.  On the other hand, many possible cracks might require significantly heavier computation for AES-256, even if the same fundamental attack works.  One wonders....

NSA also wants SHA-384 - which is interesting given recent concerns about attacks on SHA-1 (which so far don't seem to extend to SHA-384).

I don't want to get into deep conspiracy and disinformation campaign theories.  My read of the situation is that at the time NSA gave its approval to this particular combination of ciphers, it believed they were secure.  They seem to be having some doubts about RSA, DSA, and DH, though that could be, or could be justified as, ECC being as strong with much smaller, more practical, key lengths.

Now, imagine that NSA really did find a way in to AES.  If they were to suddenly withdraw approval for its use by the government, they would be revealing their abilities.  A classic conundrum:  How do you make use of the fruits of your cryptanalytic efforts without revealing that you've made progress?  England accepted bombing raids on major cities to keep their crack of Enigma secret.  So the continuation of such support tells us little.  What will be interesting to see is how long the support continues.  With work under way to replace SHA, a new version of the NSA recommendations will eventually have to be produced.  Will it, for example, begin a phase-out of AES-128 for SECRET communications in favor of requiring AES-256 there as well?  (Since there's no call so far to develop a cipher to replace AES, it would be difficult for NSA to recommend something else.)

It's indeed "a wilderness of mirrors", and we can only guess.  But I'm very wary of using NSA's approval of a cipher as strong evidence, as the overall situation is complex and has so many tradeoffs.
                                                        -- Jerry

More information about the cryptography mailing list