More than just cryptography: The performance advantages of Suite B compliance

Story

May 09, 2008

Security is the objective of the National Security Agency's (NSA's) Suite B cryptosystem specification. But what about performance? Especially in military applications, where information has to be both secure and available right now, cryptographic protection can't be allowed to interfere with functionality.

Security is the objective of the National Security Agency's (NSA's) Suite B cryptosystem specification. But what about performance? Especially in military applications, where information has to be both secure and available right now, cryptographic protection can't be allowed to interfere with functionality.  The ciphers and other algorithms approved for Suite B cryptography achieve tremendous efficiency, holding the potential to enhance device performance. The author looks at how Suite B-compliant key agreement and authentication can be accelerated by capitalizing on the inherent efficiencies of Elliptic Curve Diffie-Hellman (ECDH), Elliptic Curve Menezes-Qu-Vanstone (ECMQV), and the Elliptic Curve Digital Signature Algorithm (ECDSA).

Security is always a balancing act. For proof, you need to look only as far as today's long airport lineups. On one hand, there‚s the requirement to screen passengers thoroughly; on the other, the need to get people onto planes and headed to their destinations. Stringency and efficiency trade off against each other.

Cryptographers have always been aware of the need for compromise in security. Their job is to encode and protect information in ways that present sufficient computational challenges to opponents but remain decipherable by friendly recipients - in a reasonable amount of time and using available resources.

That said, compromise is a relative concept. Today, especially for military embedded systems, what's acceptable in balancing security with functionality, performance, and cost is defined by clear and very high expectations. The compromise is to be as uncompromising as possible. Therefore, accelerating Suite B-compliant key agreement authentication is necessary and attainable through ECDH, ECMQV, and ECDSA.

Not for strength alone

The collection of commercial cryptographic primitives approved by the National Security Agency for protecting both Sensitive But Unclassified (SBU) and classified information - aka Suite B - sets the bar high: 128-bit security for SBU information and 256-bit security for classified. RSA, Diffie-Hellman, Triple DES, SHA-1, and other familiar security mechanisms don't make the cut. The approved primitives are ECC for asymmetric (public key) cryptography, AES for symmetric cryptography, and SHA-256/384 for hash operations.

These were chosen not only for their security strength, but also for their ability to deliver that strength efficiently. To match AES at 128 bits, RSA would require 3,072 bits - a computational burden to say the least, particularly compared with ECC's 256 bits for the equivalent strength. This is obviously crucial for embedded systems, such as remote sensors, which are typically resource constrained.

An example of a sensor network (Figure 1) may be helpful for making this discussion concrete in a military context. Consider deploying a series of remote, wireless sensors around a field camp to monitor the perimeter. Such an arrangement requires many independent devices to interact in a mesh architecture, all of them registering and exchanging information. Giving each sensor the autonomy it needs to do its duty essentially creates multiple access points - and therefore multiple points of vulnerability. To mitigate that vulnerability, each sensor must be authorized and authenticated individually. This has to be done in an economical way both computationally and in terms of power consumption, because the sensors must be compact and must also run on batteries.

 

Figure 1

(Click graphic to zoom by 1.9x)

 

How these hypothetical sensors generate and exchange authenticated keys, therefore, becomes a critical consideration. The primitives and protocols approved for Suite B enable these devices to perform all the necessary tasks leanly and with robust security.

Key agreement: The process in brief

By way of a refresher, key agreement protocols are schemes that require each communicating party to contribute material used in generating a final, secret key for encrypting and decrypting communications. The basic steps are explained in Figure 2.

 

Figure 2

(Click graphic to zoom by 2.0x)

 

The authentication piece is absolutely necessary. Participants in a key exchange who share only ephemeral keys cannot know the true identity of the person from whom a key is coming, because ephemeral keys are not bound to the parties in any way.

Suite B mandates that NSA-approved systems use either ECDH or ECMQV for key agreement and ECDSA for authentication.

About the protocols

ECDH can be used for key agreement between parties that have had no prior contact. ECMQV on the other hand, establishes shared secrets between entities that already have trusted copies of each other's public keys.

In ECMQV, both parties still generate and exchange ephemeral public keys, but on receipt each also calculates an implicit signature using their own long-term and ephemeral private keys and their other ephemeral public key (Figure 3). Shared secrets are then generated using the implicit signatures and the other party's ephemeral and long-term public keys. Agreement between the shared secrets can be taken as implicit verification that each was generated by the authentic party. If either party's public keys are not used in the process, the shared secrets won't agree.

 

Figure 3

(Click graphic to zoom by 2.0x)

 

ECDSA authenticates the long-term public keys of the ECDH/ECMQV key exchange through the use of signed certificates that identify and are bound to each participant in an exchange. To validate these certificates, each party uses the public ECDSA verification key of the trusted third party (called a certificate authority) that created the certificates.

Streamlining key computation and authentication

Typically, key establishment and authentication are performed as follows:

Key Establishment

Compute expression K := aB

K is the shared secret that will be used to generate the final shared secret key. Note that a is one party's private key (Party 1) and B is the other's public key (Party 2). The public keys in this scenario are derived from certificates issued to each user by a certificate authority within a Public Key Infrastructure (PKI). Using certificates provides greater control and management of the system as a whole.

The computational cost of this is a full-sized multiple of the unknown point B. Computational cost is the largest calculation required for a given function.

Key Authentication

Here (and later), we describe the calculations of fast ECDSA verification.

Evaluate expression s-1 (e G + r Q) - R = O

e is the hash value of certificate information (including Party 2, B); Q is the public key of the certificate authority; and(r, s) is the ECDSA signature across the certificate information.

The cost here is a linear combination of the known point G and the unknown point Q.

Significant economies can be gained, however, by combining key establishment and authentication into a single step.

Combined Key Establishment and Authentication

K := aB + λ (s-1(e G + r Q) - R)

Here, as above, aB is the key expression. λ is the randomizer, and s-1(e G + r Q) is the verification expression (which can also be indicated simply as ∆).

In fact, the entire equation can be generalized, boiled down to:

K := K + Œª ‚àÜ

This works because Party 1 can only compute K if the certificate is "correct" (for example, ∆ = O); otherwise, K will be random and therefore invalid.

The upshot of this is that a mechanism for implicitly authenticating keys is built right into the key establishment step, accelerating the entire key agreement process by eliminating half of what are known as point doubles: pairs of points along a curve. Computationally, the cost is the linear combination of known point G and unknown points B, Q, and R.

Working out the gains

Tables 1, 2, and 3 give a clear picture of the processing speed gained by combining key establishment and authentication. Further acceleration is achieved through the use of fast ECDSA verification. Ordinarily, EDCSA verification looks like this:

1. Compute e:= h(m)

 

Figure 4

(Click graphic to zoom by 2.0x)

 

2. Compute R’:= (e s-1) G + (r s-1) Q

 

Figure 5

(Click graphic to zoom by 2.0x)

 

3. Check that R’ maps to r

 

Figure 6

(Click graphic to zoom by 2.0x)

 

Fast verification speeds up the computation by reconstructing R from r in step 2 and then checking that R = (e s-1) G + (r s-1) Q. Tables 1 and 2 show the difference.

The overall total costs of acceleration are depicted in Table 3.

The label static ECDH in the charts refers to ECDH schemes that include authentication, as opposed to anonymous ECDH schemes, which do not.

A final comparison illustrates just how significant the efficiencies of the ECC-based protocols truly are - specifically ECDSA certificates compared to RSA certificates As Table 4 shows, the higher the security level, the greater the benefits of ECDSA both in size and speed.

 

Figure 7

(Click graphic to zoom by 2.0x)

 

Importantly, no measure of security is lost by streamlining key establishment and authentication: The end product is every bit as strong as that of the underlying DH-based key agreement scheme or ECDSA signature scheme. At the same time, computations for all NIST prime curves (designated for use by the U.S. National Institute of Standards and Technology) are accelerated through the converged process by 45 percent for ECDH in combination with ECDSA and 40 percent for ECMQV in combination for ECDSA. ECDSA itself is sped up by as much as 2.4 times the norm compared to situations in which it is used on its own.

All of these are advantageous enough, but the combined process affords the added benefit of stronger implementation security, providing simple side-channel resistance virtually for free, as a by-product.

Looking at the incremental cost of signature verification - the most valid metric for evaluating efficiency in this context - the formerly accepted advantage of combining RSA certificates with ECDH schemes is essentially nullified; even at 80-bit security, ECDSA takes the lead.

Back to the real world

How does all of this apply to our example of remote sensors monitoring a base-camp perimeter? By taking advantage of implicit verification through a streamlined key establishment and authentication process - and by capitalizing on the option of fast ECDSA verification - each sensor can perform all the processing needed to participate securely and independently in the mesh network. Due to the leanness of this key-agreement approach, system resources on each sensor device are conserved, security function processing is accelerated, and power demands are reduced. No sensor is a "weak link" in some larger security construct; each one upholds the mandatory security requirements for the whole.

Combining verification and key computation is applicable beyond the kind of key-agreement scenario described so far. It can also be used to execute key computation with ECDH schemes in ANSI X9.63, NIST SP800-56a [including Elliptic Curve Integrated Encryption Scheme (ECIES), Unified Model, STS, ECMQV, and ElGamal encryption]. Nonsecret ECC points can be calculated by the method described, provided that the correctness of the solution can be checked. The same is true for computing multiple ECC points.

The streamlined approach can also be used to verify multiple ECDSA signatures (called certificate chains) as well as any elliptic curve equation and even multiple elliptic curve equations in batches. Finally, it can be used to carry out operations in other algebraic structures, including hyper-elliptic curves and identity-based cryptosystems.

In the constant struggle for balancing security with functionality, the Suite B primitives and protocols give developers the freedom to load up the scales on both sides, allowing them to explore the full potential of their applications with the confidence of strong security.

William Lattin is chief technology officer of Certicom Corp. During the past nine years, he was the managing director of SecureField, an information security consultancy that specializes in cryptographic product design and network security. He is chair of the Standards for Efficient Cryptography Group (SECG), an industry consortium that develops commercial standards to facilitate the adoption of efficient cryptography and interoperability across a wide range of computing platforms. He holds a BSEE and an MSEE from Stanford University and UC Santa Barbara respectively. He can be reached at blattin@certicom.

Certicom Corp
650-655-3950
www.certicom.com