Elliptic Curve Cryptography

To see how big the numbers for a 256-bit curve are, the NIST P-256 curve equation has the coeffients a=–3 and b = 41058363725152142129326129780047268409114441015993725554835256314039467401291.

The coordinates are in a prime field modulo p_256 where:

p_256 = 2256 – 2224 +2192 +296 – 1

The base point is G=(xG,yG) and defined by:

xG = 48439561293906451759052585252797914202762949526041747995844080717082404635286

yG = 36134250956749795798585127919587881956611106672985015071877198253568414405109

If these numbers look big to you, just think that the 256-bit elliptic curve is equivalent to RSA with 3072-bit numbers. RSA public keys contain more than 12 times the number of digits.

If you'd like to learn more about Elliptic Curve Cryptography, there are many references available. Certicom, a company founded by some of the inventors of ECC, hosts an on-line tutorial at http://www.certicom.com/ecc-tutorial. For a more comprehensive understanding of cryptography, the book Understanding Cryptography by Christof Paar, Jan Pelzl and Bart Preneel has a chapter about ECC and also covers the AES and SHA. I've just touched the basic definitions here, and I've not discussed the optimizations used to make a high-performance implementation like the one in OpenSSL. For a quite comprehensive reference on fast ECC algorithms, the "Handbook of Elliptic and Hyperelliptic Curve Cryptography" (http://www.hyperelliptic.org/HEHCC) has yet to let me down.

Using Elliptic Curve Cryptography in OpenSSH

A little more than a year ago, OpenSSH 5.7 added support for ECC-based cryptography. Although it's still not in every Linux distribution, support for ECC finally is becoming widespread enough that it's starting to be worth considering a migration. Support for ECC requires OpenSSH version 5.7 or later and OpenSSL version 0.9.8g or later. OpenSSH can use ECC both to help you authenticate that you really are talking to the server you want and to help the server perform key-based authentication of users.

Host authentication is used by the client to authenticate the server. It is used to detect man-in-the-middle attacks and normally is set up automatically and used by OpenSSH. When OpenSSH is installed, it should create one or more host keys, which normally are stored in /etc/ssh. The ECC private key normally is named ssh_host_ecdsa_key, and the corresponding public key normally is named ssh_host_ecdsa_key.pub. See the man pages for sshd_config if you would like to change this path. Just make sure that the private key can be read only by authorized admins; anybody with access to the host private key potentially could impersonate the server.

Client authentication is used to authenticate the client against the server. Using keys to authenticate rather than passwords is both more convenient (because you can use ssh-agent or another program to cache the key) and more secure (because the password is never sent in plain text to the server). If you have used SSH for significant work in the past, you've probably set this up using RSA keys, and the exact same process, namely using ssh-keygen, is used to create ECC keys. The only difference is to pass -tecdsa to create the key. The man page for ssh-keygen will have more details, and there are many tutorials for setting up SSH keys available on-line if you need a walk-through.

For most people, once encryption software supporting ECC is more widely deployed, converting to ECC should be quick and painless. RSA still is probably "good enough" for most applications, but ECC is significantly more secure, and it may be essential to getting strong security on tiny, low-power, networked devices that are becoming more widespread. Its introduction into open-source tools like OpenSSL and OpenSSH is definitely a great step toward gaining more widespread use.

______________________

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. "

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState