Elliptic Curve Cryptography

When it comes to public key cryptography, most systems today are still stuck in the 1970s. On December 14, 1977, two events occurred that would change the world: Paramount Pictures released Saturday Night Fever, and MIT filed the patent for RSA. Just as Saturday Night Fever helped popularize disco through its choreography and soundtrack, RSA helped popularize cryptography by allowing two parties to communicate securely without a shared secret.

Public key techniques, such as RSA, have revolutionized cryptography and form the basis for Web site encryption via SSL/TLS, server administration via SSH, secure e-mail and IP encryption (IPsec). They do this by splitting the shared secret key used in traditional cryptography into two parts: a public key for identifying oneself and a secret key for proving an identity electronically. Although the popularity of disco has waned, most Web sites today that use encryption still are using RSA.

Since the 1970s, newer techniques have been developed that offer better security with smaller key sizes than RSA. One major breakthrough is the development of cryptography based on the mathematical theory of elliptic curves, called ECC (Elliptic Curve Cryptography). Although ECC has a reputation for being quite complex, it has been integrated into popular open-source cryptographic software including OpenSSH and OpenSSL, and it's not inherently any more difficult to use than RSA. In this article, I describe ECC and show how it can be used with recent versions of OpenSSH and OpenSSL.

Not all cryptographic algorithms are equal. For a fixed key or output length, one algorithm may provide much more security than another. This is particularly true when comparing different types of algorithms, such as comparing public and symmetric key algorithms. To help make sense of this, the National Institute of Standards and Technology (NIST) reviews the academic literature on attacking cryptographic algorithms and makes recommendations on the actual security provided by different algorithms (see Table 1 from 2011).

Table 1. NIST Recommended Key Sizes

Bits of Security Symmetric Key Algorithm Corresponding Hash Function Corresponding RSA Key Size Corresponding ECC Key Size
80 Triple DES (2 keys) SHA-1 1024 160
112 Triple DES (3 keys) SHA-224 2048 224
128 AES-128 SHA-256 3072 256
192 AES-192 SHA-384 7680 384
256 AES-256 SHA-512 15360 512

Note: for new applications, I think AES-128 should be used over triple DES even if 128-bit security isn't needed. Attacks have been found on SHA-1, and NIST now estimates that SHA-1 provides only 69 bits of security in digital signature applications.

If the system you are designing is expected to protect information only until 2030, NIST recommends that you use cryptography providing at least 112 bits of security. For applications that need longer-term protection, NIST recommends at least 128 bits of security.

Just because NIST makes these recommendations, doesn't mean that applications follow them. Many Web sites, including on-line banks, still will use SHA-1 and pair it with AES 128 and a 1024- or 2048-bit RSA key. According to NIST, achieving true 128-bit security means that the RSA key should be at least 3072 bits—a size most Internet certificate authorities don't even offer. At present, Verisign will sell you an SSL certificate that it claims offers "256-bit security", because you can use it with AES-256. The signature itself uses SHA-1 and a 2048-bit RSA key.

At present, the security on the Internet is still sufficiently weak that it almost always will be easier to find a vulnerability that allows an attacker to bypass security rather than directly attack the encryption. However, it is still worthwhile to be aware of how much security the overall encryption implementation provides. In cryptography, more bits are usually better, but an implementation is only as strong as its weakest length. Both ECC and SHA-2 represent essential algorithms to getting real 128-bit or 256-bit security.

______________________

Joe Hendrix is a security researcher who works in Portland, Oregon, for Galois, Inc. His main interest is in applying formal verification techniques to real security problems.

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

interesting article!

anonymous's picture

To the author:

This is a very interesting article! Question - I saw in Star Trek TNG episode cmdr. Data used Fractal Algorithm for encryption.

Is it realistic to use such an algorithm in real life or was it totally made up?

Thanks.

The basis for Web site

MaureenGoodin's picture

The basis for Web site encryption via SSL/TLS, server administration via SSH, secure e-mail and IP encryption.

hello !!!

linda99's picture

I like your work a lot. On the same occasion I invite you to visit my website prefer

Voyance sérieuse par telephone

Several things wrong here...

MHW's picture

Over all, I found this article somewhat interesting (the ECC math part at least) and somewhat misleading (the recommendations part).

The table of key bit strengths is flat out wrong. It's really hand waving to compare bit lengths of symmetric algorithms with PK algol's in anything other than very general terms. It's really comparing apples and oranges and what tastes better.

DES key sizes, in particular, are not "recommended" and are, in fact, fixed by the algorithm and that table got them all very wrong. Single DES (insanely weak and not in the table) is a 56 bit key. 3-DES ede (triple DES encrypt-decrypt-encrypt aka 2 key DES) is 112 bits. Full blown 3-DES with three completely independent keys is 168 bits. There's no such thing as 80 bit DES (1 key, 2 keys, or 3 keys) even if you consider violating the parity in the key bytes. The original DES had 8 byte keys but only considered 7 bits per byte with the high order bit as a "parity" bit (harken back to ASCII tty days?). 8 bytes with 7 bits per byte was 56 bits, period. Two key DES utilized two 56 bits keys, first "encrypting" with one and then "decrypting" (reverse algo) with the other, and then reencrypting with the first key again. Sounds strange but, if you think about it, it makes sense for backwards compatibility with single DES where both keys are the same. 80 bits keys for DES in any form at all makes no sense at all.

No DES variants are recommended in the modern Internet environment.

It's also misleading to argue about the smaller key size of ECC having better security. It's generally been recognized that ECC is more processor intensive than an equivalent strength RSA key and ECC doesn't have the track records that RSA has.

RSA keys up to 2048 bits are well supported on common crypto hardware such as smartcards. ECC support is generally poor to non-existent at best, particularly in consumer grade smart-cards.

The editing remark in the middle of some of the math was "amusing". Doesn't anybody read these bloody things before posting??? Yes, it's in the middle of a pile of math that some people may find mind numbing (the real math is worse - I can quote RSA off the top of my head, it's that simple, but ECC is bad) but still... I actually found the math part to be the bright spot and the faux paux editor remark to be worth a belly laugh at least.

The article contained no references to double check to see if they are valid or even still current! In particular, I would love to review the corresponding NIST recommendation, in particular given how often NIST standards, in regards to security in particular, are behind the times and out of date or have been updated as the state of the art progresses.

People are still quoting out-of-date NIST standards that are no longer even supported by NIST and didn't make sense even back when NIST supported them. They eliminated the whole "7 pass overwrite erase" recommendation back in 2001 or there abouts and people STILL quote that ridiculous recommendation as if it were a standard.

Article feedback

Joseph Hendrix's picture

Hi MWH,

Thanks for the feedback. I just saw this comment.

The comparison of different key lengths comes from NIST 800-57 rev 3, which was published in July, 2012. Here's a link: http://csrc.nist.gov/publications/PubsSPs.html.

I'm sorry if some of the information in the table was confusing. The table was not meant to suggest that DES used 80bit or 112bit keys. You are correct that DES key sizes are 56bits, and using triple DES with 2 keys and 3 keys respectively would involve keys with 112 and 168bits respectively. However, due to known cryptanalysis techniques, they're are likely faster attacks than exploring the entire keyspace. Hence, many cryptographers feel that 3DES offers a lower level of security than the full key size would suggest.

Your point that ECC is newer than RSA, and hence less time has been taken to evaluate it is true, but ECC is almost 2 decades old, and has been subject to significant cryptoanalysis efforts. I don't think this article makes recommendations that are out of alignment with what NIST or the NSA have publicly stated. If so, I'll try to see that the article is corrected.

I disagree with your assertion that it's hand waving to compare key sizes of different algorithms. All the algorithms mentioned in this article have been extensively studied, and systems that use cryptography often use multiple algorithms in concert. For example, browsers use public key crypto for key exchange and digital signatures, symmetric key for encryption, and secure hash functions for digital signatures and identity.

Guidance from standards organizations such as NIST, helps system designers make informed decisions about what algorithms and keysizes to use.

Ehem

NightwishPT's picture

You editing notes as showing.

Garrick, in this paragraph and a few paragraphs down, there were some really long numbers. "

Webinar
One Click, Universal Protection: Implementing Centralized Security Policies on Linux Systems

As Linux continues to play an ever increasing role in corporate data centers and institutions, ensuring the integrity and protection of these systems must be a priority. With 60% of the world's websites and an increasing share of organization's mission-critical workloads running on Linux, failing to stop malware and other advanced threats on Linux can increasingly impact an organization's reputation and bottom line.

Learn More

Sponsored by Bit9

Webinar
Linux Backup and Recovery Webinar

Most companies incorporate backup procedures for critical data, which can be restored quickly if a loss occurs. However, fewer companies are prepared for catastrophic system failures, in which they lose all data, the entire operating system, applications, settings, patches and more, reducing their system(s) to “bare metal.” After all, before data can be restored to a system, there must be a system to restore it to.

In this one hour webinar, learn how to enhance your existing backup strategies for better disaster recovery preparedness using Storix System Backup Administrator (SBAdmin), a highly flexible bare-metal recovery solution for UNIX and Linux systems.

Learn More

Sponsored by Storix