ECC Holds Key to Next-Gen Cryptography

ECC Holds Key to Next-Gen Cryptography

Scott Vanstone, Certicom Corporation
Mar 18, 2004 (6:00 AM)
URL: http://www.commsdesign.com/showArticle.jhtml?articleID=18400497

Almost 20 years ago, Whit Diffie predicted that the public-key cryptography being widely used at the time would be strong enough for generations to come. In an article, "The First Ten Years of Public Key Cryptology," he said, "Unless the available systems suffer a cryptanalytic disaster the very success of public-key cryptography will delay the introduction of new ones until the equipment now going into the field becomes outmoded for other reasons." Since then, the "other reasons" have happened with the advent of wireless technology, and more specifically computing devices with constrained computing, storage and battery life.

Secondly, in the past year, cryptanalytic advances have generated heightened discussion about public-key sizes and the security required. For example, in February 2003 Dr. Adi Shamir, the "S" in RSA, raised new concerns about the security of 1024-bit RSA. His paper describes a new hardware implementation for factoring that improves the running time of the number field sieve by three to four orders of magnitude over current implementations. With this hardware, Shamir estimates the factoring for 512-bit RSA can be completed in 10 minutes by a $10K device and 1024-bit RSA in less than one year with a $10 million device.

Although in his article, Diffie felt the current public-key cryptosystems were adequate he did refer to a "new" public-key scheme with a reference to the proceedings of Crypto '85, in which Victor Miller's article appeared which introduced a new public-key scheme, called elliptic curve cryptography (ECC).

Twenty years ago, ECC was still a new cryptosystem and researchers did not know if ECC schemes could be implemented efficiently and securely. Since then, researchers have studied ECC and determined it is a stronger, more efficient technology that is ideally suited for resource-constrained environments such as smart cards, cell phones, and personal digital assistants (PDAs). Moreover, because of the apparent hardness of the underlying elliptic curve discrete logarithm problem (ECDLP), ECC systems are also well suited for applications that need long-term security requirements.

This was proven last year when the U.S. National Security Agency adopted ECC for protecting information classified as mission-critical by the U.S. government. This decision by the world's leading codemakers and codebreakers not only validated the strength of ECC, it created the opportunity for ECC to be widely adopted. It seems very likely that other government agencies and the commercial sector will follow suit and adopt ECC for strong security across a wide variety of applications and devices.

This article will show why ECC is the next generation of public-key cryptography. Additionally, this article will show that ECC allows designers to build communication devices that do not compromise security to address performance concerns.

Matching Public Key Sizes
Public-key schemes are typically used to transport or exchange keys for symmetric-key ciphers. A well-designed symmetric-key algorithm that uses an m-bit key should provide m bits of security. That is, to find the key being used would require the adversary to search exhaustively through the key space that has 2^m keys in it.

We know many organizations understand key strength when looking at symmetric ciphers because they are moving from 3DES to AES; even if they only moved from DES a couple of years ago. At the same time, these same organizations implement the 1024-bit RSA for key transport because they feel that it's good enough. Clearly, the 1024-bit RSA does not match the 128-bit security level now used for symmetric ciphers.

Those who are reluctant to migrate from 1024-bit RSA to the larger keys sizes now required defend these inadequate RSA key sizes by arguing that memory limitations and other costs will protect these keys. This is a very dangerous approach because the security of the public-key system must be matched with the symmetric cipher used; this is only common sense.

In fact, the U.S. National Institute of Standards and Technology (NIST) notes in FIPS 140-2: Security Requirements for Cryptographic Modules that "Compromising the security of the key establishment method (e.g., compromising the security of the algorithm used for key establishment) shall require at least as many operations as determining the value of the cryptographic key being transported or agreed upon." This means that the modulus lengths of the public-key must be enforced for use with AES.

One could argue that it's okay to use 1024-bit RSA to deliver a 128-bit AES key if the desired security level is only 80 bits. On the other hand, if one could deliver that same 128-bit key with a public-key mechanism that has a security level equivalent to 128 bits then one should do it.

Public-Key Families
With the above in mind, let's look at the industry-standard public-key cryptographic systems that can be considered secure, efficient, and commercially viable. These systems, classified according to the mathematical problem on which they are based, are: integer factorization systems (of which RSA is the best known example), discrete logarithm systems (such as the U.S. Government's DSA), and ECC (Table 1). The two major benchmarks when comparing these systems are security and efficiency.

Table 1: Underlying Mathematical Problem
for Public-Key Schemes

The security of the system is directly tied to the relative hardness of the underlying mathematical problems. In each case, there are well known methods for solving these three distinct mathematical problems. Because the best-known way to solve ECDLP is fully exponential, you can use substantially smaller key sizes to obtain equivalent strengths. Hence, ECC provides the most security per bit of any public-key scheme known (Table 2).

Table 2: Run Times for Different Public-Key Schemes

The Benefits of ECC
The absence of a sub-exponential time algorithm for the ECDLP means that significantly smaller parameters can be used in ECC than with DSA or RSA. The advantages that can be gained from smaller parameters include speed and smaller keys or certificates. These advantages are especially important in environments where at least one of the following resources is limited:

Processing power

Storage space

Bandwidth

Power consumption

The result is that ECC is especially well suited for constrained environments such as smart cards, cellular phones, PDAs, digital postage marks, to name a few.
Furthermore, research on ECDLP has led to many important results including curve selection, whereby parameters that are known to be weak are intentionally avoided. A well-known result is the Menezes-Okamoto-Vanstone (MOV) attack showing that super-singular curves should not be used (although Boneh et al has found that super-singular curves can be useful for ID based schemes provided the key size is large enough).
Another noteworthy result shows that Pollard's rho method, the best generic attack known on the ECDLP, can be sped up for certain elliptic curves having efficiently computable endomorphisms.
Research has resulted in the development of efficient ECC implementations and stronger, faster security protocols. A case in point is the discovery in 1996 of an efficient and authenticated public-key agreement scheme, now referred to as MQV. NIST currently has a draft standard, referred to as SP 800-56, that specifies an elliptic curve version of MQV as the key agreement mechanism for U.S. Government use. On October 24, 2003 the U.S. Government's National Security Agency (NSA), in an unprecedented move, licensed MQV and related intellectual property for the U.S. Government's mission-critical national security applications. This solidifies the U.S. Government's intention to move all key management to ECC and in particular, MQV.
Relative Public-Key Sizes
So what does this mean in practice? NIST has recommended that 128-bit protection is necessary to achieve relatively lasting security (to the year 2036 and beyond). This means moving from 3DES to AES.
To avoid compromising the security of the system, NIST's FIPS 140-2 standard indicates that keys for symmetric ciphers such as AES must be matched in strength by public-key algorithms such as RSA and ECC. For example, a 128-bit AES key demands an RSA key size of 3,072 bits for equivalent security but for the same strength, the ECC key size is only 256 bits.
As you can see in Table 3, while ECC key sizes scale linearly, RSA does not. The result is that the gap between systems grows as the key sizes increase. This is especially relevant to implementations of AES where at 256-bit security you need an RSA key size of 15,360 bits compared to 512 bits for ECC.

Table 3: NIST Guidelines for Public-Key Sizes
with Equivalent Security Levels

This will have a significant impact on a communication system as the relative computational performance advantage of ECC versus RSA is not indicated by the key sizes but by the cube of the key sizes. The difference becomes even more dramatic as the greater increase in RSA key sizes leads to an even greater increase in computational cost. So going from 1024-bit RSA key to 3072-bit RSA key requires about 27 times (3³) as much computation while ECC would only increase the computational cost by just over 4 times (1.6³).
Even in systems that use 1024-bit RSA, this has important design implications. For example, ECC-160 has a 6X smaller key-size than RSA-1024 and can generate a signature 12 times faster on StrongARM7. The performance advantage of ECC stands out even more when we look at higher security levels or when looking at hardware implementations.
Table 4 makes clear the relative advantages of ECC on the hardware side of things, in terms of speed and gate count.

Table 4: Hardware Implementations of ECC and RSA

Standards Involving ECC
The main goal of security standards is to facilitate the widespread use of cryptographically sound and well-accepted techniques, promote interoperability and help ensure ongoing detailed analysis by cryptographers through clear, complete, and public specification of baseline techniques.
Over last 10 years, a great deal of work has taken place to ensure that ECC meets these goals and is specified in an ever-increasing number of standards. It started with the IEEE P1363 in 1994 (becoming a standard in 2000), and now includes many accredited standards organizations:

ISO (in ISO 14888-3: ECDSA and other ECC-based signature schemes)

IEEE (in IEEE 1363-2000 for public-key cryptography)

The American National Standards Institute (in ANSI X9: cryptography for financial-services industry).

NIST also specifies ECC in FIPS 186-2: Federal Information Processing Standards ECDSA and SP 800-56: Special Publication on Key management. While in Europe, BSI in Germany also specifies ECC.
Currently, there are ongoing efforts within a number of communication application standards bodies have included ECC as a required or recommended security mechanism. These efforts include:

IEEE 802.15 Wireless Personal Area Networks

IETF: Internet Engineering Task Force

ATM Forum

Wrap Up
Since ECC is an extremely efficient compact algorithm, it makes fewer processing demands on resource-constrained devices than RSA. In addition, it is standardized, ensuring interoperability between devices. And, as a well-researched and proven system, it answers manufacturers' concerns about reliability.
Ultimately, the benefits of ECC are many: linear scalability, a small software footprint, low hardware implementation costs, low bandwidth requirements, and high device performance. For these reasons, ECC has gained the support of a number of leading companies and recently received a strong validation from the NSA.
It's clear that security is an essential component of communication today and will continue to be so for the long term. As this article has shown, ECC is a superior algorithm when it comes to enabling that security. Since it offers the highest strength-per-bit of any public-key cryptography system known today, there should be no doubt that ECC is the next generation of public-key cryptography.
About the Author
Scott Vanstone is the founder and executive vice president of strategic technology at Certicom. He is also a professor of mathematics and computer science at the University of Waterloo. Scott holds a Ph.D. from the University of Waterloo and can be reached at svanstone@certicom.com.

Copyright © 2003 CMP Media, LLC | Privacy Statement