Cryptography
public-key elliptic-curves standards nsa
Updated Fri, 20 May 2022 02:26:06 GMT

Why is the P-521 elliptic curve not in Suite B if AES-256 is?


In the NSA's document, "The Case for Elliptic Curve Cryptography" (archived), we have

+---------------+-------------------------+-----------------+
| Symmetric Key | RSA and Diffie-Hellman  | Elliptic Curve  |
| Size (bits)   |      Key Size (bits)    | Key Size (bits) |
+---------------+-------------------------+-----------------+
|       80      |            1024         |       160       |
|      112      |            2048         |       224       |
|      128      |            3072         |       256       |
|      192      |            7680         |       384       |
|      256      |           15360         |       521       |
+---------------+-------------------------+-----------------+
             Table 1: NIST Recommended Key Sizes

In NSA Suite B, we do have AES-256 (for TOP SECRET); however, the ECC is limited to P-384:

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.

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.

Despite P-521 being officially codified in NIST FIPS-186-4, an entropic choke point appears to have been introduced, as if we have a cryptographic "pipeline".

Example: If we're doing ECDH with P-384 keys and then use AES-256 to encrypt, we're effectively passing just 192 bits of keying entropy into the AES-256 engine.

Reading the only known response (that I know) on this IETF thread, the statement reads

Regarding NSA's omission of P-521, P-256 and P-384 will satisfy all of the U.S. Government's requirements so only these are included in Suite B. We don't have a requirement that warrants the inclusion of P-521.

I'm unable to put these seemingly contradictory pieces of information together, so I thought I'd ask other people here. Why was P-521 excluded? Was it technical or non-technical? Any additional info would be appreciated.

EDIT:

This is not very directly related, but I checked some empirical testing results. Seems computation times roughly double going from P-256 => P-386 => P-521, for almost any EC operation. Take for example signing a short (1200 bytes) message.

P-256:  8ms ( 64 byte signature) 
P-384: 15ms ( 96 byte signature)
P-521: 30ms (132 byte signature)

It's not directly representative of the entropic bottleneck above, more aligned towards the "good enough" line of thought. But then again, AES-192 should have also sufficed...




Solution

The real question isn't "Why doesn't Suite B use P-521?" It is, "Why doesn't Suite B use AES-192?" NSA were only interested in 192-bit security for Suite B, but they chose to use AES-256 because AES-192 wasn't widely supported.

"In fact we had wanted to use AES -128 and AES-192, but a quick survey of AES implementations (hardware centric, I believe) showed that there were very few implemented AES-192, whence the decision to go with AES-128 and AES-256 in Suite B, paired with P256 and P384. All of the crypt purists grumbled endlessly about the mismatch betwixt AES-256 and P384."

-- Kevin M. Igoe, NSA

(I am choosing to take his explanation at face value, but you never know with intelligence agencies.)





Comments (1)

  • +0 – Makes sense, thanks for the reference. Although by the timing Kevin might put me in the crypto purist group, I excuse myself from it as a crypto pragmatist. The question comes to (my) mind less as grumbling but more as a crypto anomaly design curiosity ... — May 07, 2015 at 03:28