Elliptic Curve Cryptography
For each bit size, NIST also recommends two other elliptic curves over a type of field called a binary field. Although prime fields are more common in software, binary fields are common when implementing ECC in low-power hardware. I focus on prime curves in this article, because that's what OpenSSL uses, and there are a lot more patents on binary curve implementations than prime curves. Unless you have some specific hardware needs and also money to spend on lawyers to deal with patents, I'd recommend sticking to prime curves.
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
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
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.
- High-Availability Storage with HA-LVM
- DNSMasq, the Pint-Sized Super Dæmon!
- March 2015 Issue of Linux Journal: System Administration
- Localhost DNS Cache
- Real-Time Rogue Wireless Access Point Detection with the Raspberry Pi
- Days Between Dates: the Counting
- The Usability of GNOME
- PostgreSQL, the NoSQL Database
- Linux for Astronomers
- You're the Boss with UBOS