Throwing Cryptography A Curve BallThrowing Cryptography A Curve Ball

A quick look back through the history of cryptography makes one thing perfectly clear: Security is never absolute. New technologies, new threats, and new practical demands are constantly emerging, reshaping expectations—and sometimes even redefining what 'security' means in the first place.

As a result of this ongoing evolution, cryptographic algorithms that once reigned supreme—DES, RSA and the like—have begun to show their limitations (and in the case of DES, have reached them). This has implications for manufacturers and security engineers building devices today, because the level of security they choose to build into their equipment will have a direct impact on the real-world lifecycle of that equipment. If security functionality can't stand up to the test of time, the longevity of the device itself is compromised.

Elliptic curve cryptography (ECC), once the young upstart of cryptographic algorithms, has now been shown to meet the most stringent long-term security requirements. The NSA has adopted ECC, and it has been recognized by accredited standards bodies such as the American National Standards Institute (ANSI) and the International Standards Organization (ISO).

But what is ECC, and what will it mean for the software industry?

Public-Key Cryptography

Throughout history, encryption has been used to protect the confidentiality of data. In the 1970s, the Data Encryption Standard (DES) was designed, and in a few years became a worldwide de facto standard. DES is an example of a 'symmetric-key' algorithm, so called because the two communicating parties need to share a secret key—this key is used to encrypt data as well as to decrypt it. DES can also be used to authenticate data, so that a recipient can be assured of the source of the data. Again, the two communicating parties need to share a secret key in order to be able to authenticate data sent to each other.

There are some difficulties inherent to deploying symmetric-key cryptography on a large scale. First, there is the difficulty of establishing a secret key. This can be done using the services of a trusted courier or by a face-to-face meeting in a secure location, but obviously such solutions don't scale well. Second, each pair of users needs to share its own unique secret key. Thus, in a system with 1,000 users there are about 500,000 keys to protect, a very difficult task indeed. Lastly, non-repudiation, whereby the recipient of a message can convince any third party (such as a judge) of the origins of the message, is difficult to achieve with symmetric-key techniques. This is because the two communicating parties share the same secret key, and so while the recipient of an authenticated message is certain who the sender of the message is, the recipient cannot convince a judge of this—because from the judge's point of view, the recipient could have sent the message to himself!

Public-key cryptography was invented by Whitfield Diffie, Martin Hellman, and Ralph Merkle in 1975 to overcome these deficiencies with symmetric-key cryptography. The idea is very simple, but extremely powerful. In public-key systems, each user generates two keys: a "public key" and a corresponding "private key." As the nomenclature suggests, the public key is available for everyone to use, while the private key is kept secret by that user. Now, anyone can use Alice's public key to encrypt messages for Alice, but only Alice can decrypt the message using her private key. Note that the first two problems with symmetric-key cryptography have been overcome because Alice does not need to share a secret key with anyone else, and because each user has only two keys. Furthermore, non-repudiation can be achieved—Alice uses her private key to generate a "signature" for a message and anyone else (including a judge) can use Alice's public key to verify that Alice did indeed generate that signature.

The Origins of ECC

Among the early public-key mechanisms designed were the Diffie-Hellman (DH) key agreement scheme that can be used to establish secret keys, and the Rivest-Shamir-Adleman (RSA) scheme for public-key encryption and signatures. The security of these schemes is based, respectively, on the intractability of the discrete logarithm problem (DLP) and the integer factorization problem (IFP). This means that the keys used in DH and RSA should be sufficiently large so that the corresponding instances of the DLP and IFP are intractable using the best methods known and the fastest available computers.

While the DLP and IFP are believed to be hard problems, several breakthrough discoveries have been made which render the problems significantly easier than previous believed. The most prominent of these new attacks was the Number Field Sieve (NFS) that was discovered in the early 1990s and is still being refined today. Of course these faster attacks do not mean that Diffie-Hellman and RSA have been broken—it just means that one has to use larger keys in order to circumvent them. Unfortunately a direct implication of using larger keys is slower performance, and this can be a critical problem, especially in the world of small electronic devices.

In 1985, Neal Koblitz and Victor Miller recognized that the so-called elliptic curve discrete logarithm problem (ECDLP) appeared to be inherently harder than the DLP and IFP. They reasoned that the techniques developed to accelerate the resolutions of the IFP and DLP could not be effectively applied to find faster ECDLP solvers. Koblitz and Miller showed how cryptographic protocols for key agreement, public-key encryption and signatures could be designed in such a way that their security was based on the hardness of the ECDLP. ECC was born.

The ECDLP has now been studied for twenty years by the cryptographic research community around the world. There is now general consensus that this problem is inherently harder than the DLP and IFP. In particular, the powerful NFS attacks do not carry over to the ECDLP setting. What this means in practice is that ECC public and private keys can be significantly smaller that DH and RSA systems for a given security level. In fact, ECC provides the most security per bit of any known public-key scheme.

For a full mathematical explanation of the elliptic curve discrete logarithm problem, see http://www.certicom.com/index.php?action=ecc,ecc_tut_1_0.

Where ECC Fits

Even though symmetric-key schemes have several deficiencies, they do have one distinct advantage over their public-key counterparts—they are much faster, perhaps by a factor of 1,000. In practice, symmetric and public-key schemes are used together. The former are used for bulk data encryption and the latter for key management and digital signatures. When used together, it is imperative that the symmetric-key and public-key components have equivalent levels of security. Otherwise, an attacker could gain an advantage by compromising the weaker component.

As mentioned earlier, the Data Encryption Standard, with keys of only 56 bits in length, has now reached the end of its life. The U.S. government's National Institute for Standards and Technology (NIST) recognized this and embarked on a project to develop a symmetric-key encryption scheme that would be secure for the foreseeable future. The result was the Advanced Encryption Standard (AES), a symmetric-key encryption scheme with keys of 128, 192 or 256 bits in length. The AES is now being deployed in security products around the world, and is expected to serve our security needs for at least the next 50 years.

RSA and DH are very poor companions to the AES. They both require 3072-bit public keys in order to match 128-bit AES keys. The situation is even worse at higher strengths—8192-bit RSA and DH keys are needed to match 192-bit AES keys, while 15360-bit RSA and DH keys are needed for 256-bit AES keys. These large keys sizes can greatly penalize system performance, particularly on resource constrained devices such as smart cards.

ECC, on the other hand, is ideally suited as a companion to AES. It can match the security of 128-, 192- and 256-bit AES, respectively, with key sizes that are only 256, 384 and 512 bits. These relatively small key sizes also means that ECC can be implemented to meet the highest security requirements, without degrading system performance.

ECC Deployment

Three developments in recent years have caused security professionals to take notice of the benefits of ECC. The first was the standardization of ECC protocols by accredited standards bodies such as ANSI, ISO, and NIST. Such standards are crucial before large-scale deployment occurs in the security world, because they foster trust in the technology, promote the widespread use of cryptographically sound ECC protocols, and ensure interoperability of devices manufactured by different vendors.

The second development was the deployment of ECC by leading corporations such as Motorola (for cell phone communications), Research in Motion (for securing Blackberry communications), and Pitney Bowes (for digital postal marks).

The third and most significant milestone in ECC acceptance was the announcement in November 2003 that the U.S. government's National Security Agency (NSA) would be using ECC to secure mission-critical national security information. More recently, the NSA announced at the RSA 2005 conference in February 2005 that ECC would be their public-key technology of choice in their list of 'Suite B' algorithms for protecting sensitive but unclassified US government communications.

These endorsements from the world's premier code-breaking organization have not gone unnoticed. Many companies that supply cryptographic equipment to the U.S. government are incorporating ECC into their products. These products are also making their way to non-government markets, thus further accelerating the adoption of ECC.

In a relative short period of time since its introduction, ECC has moved from the province of pure mathematics into the mainstream of cryptography. It has proven to be extremely well suited to the unique demands of resource-constrained environments, where processing power is at a premium, and at the same time is capable of meeting stringent security requirements. And ECC deployment will most likely continue to grow as governments and commercial organizations around the world mandate the use of the AES for symmetric-key encryption.

Of course, activity continues in the research community. Each year the Centre for Advanced Cryptographic Research (CACR) at the University of Waterloo, Ontario sponsors an ECC workshop attended by over 100 top cryptographers to discuss advances in the field of elliptic curve cryptography. ECC 2005 will be held September 19-21 in Copenhagen, Denmark. Certicom also sponsors an ECC conference: The Certicom ECC Conference 2005 will be held October 3-5 in Toronto, Canada.

The Certicom ECC Challenge, begun in November 1997 and still continuing, offers an opportunity for people around the world to create new methods of attacking the algorithm and exposing any weaknesses. Security-conscious developers can learn more at http://www.certicom.com/index.php?action=ecc,ecc_challenge.