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

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.

Elliptic Curve Cryptography has a reputation for being complex and highly technical. This isn't surprising when the Wikipedia article introduces an elliptic curve as “a smooth, projective algebraic curve of genus one”. Elliptic curves also show up in the proof of Fermat's last theorem and the Birch and Swinnerton-Dyer conjecture. You can win a million dollars if you solve that problem.

To get a basic understanding of ECC, you need to understand four things:

Essentially, elliptic curves are points on that satisfy an equation with the form:

y² = x³ + ax + b

Figure 1 shows a picture of an elliptic curve over the real numbers where a is –1 and b is 1. Elliptic curves satisfy some interesting mathematical properties. The curve is symmetric around the x axis, so that if (x,y) is a point on the curve, then (x,–y) is also on the curve. If you draw a line between any two points on the line with different x coordinates, they will intersect the line at a unique third point. Finally, for each point on the curve, if you draw a straight line tangent to the cover from that point, it will intersect the curve once again at another point.

Figure 1. Elliptic Curve over Real Numbers

Mathematicians use these properties to form a structure called a group from the points on the elliptic curve. A group consists of a set of elements containing a special point (denoted 0), an operation for negating an element (denoted –x), and an operation for adding two elements (denoted x + y). The elements in the group defined by an elliptic curve consist of the points on the curve plus an additional point for 0 that is not on the curve, but as you'll see below is easiest to visualize as a line on the x-axis. To negate a point, you just negate the y-coordinate of the point, and adding a point to its negation is defined to return 0 (Figure 2). To add two points P and Q with different x-coordinates, draw a line connecting the two points and extending beyond them. This line should intersect the curve at a third point. The sum R = P + Q is the negation of the third point. Finally, to add a point P to itself, draw the line tangent to P (Figure 3). The sum R = 2P is the negation of the point that line intersects (Figure 4).

Figure 2. Negating a Point

Figure 3. Adding Two Points

Figure 4. Doubling a Point

Once the group is defined, we can talk about scalar multiplication—the fundamental operation that makes elliptic curves useful in cryptography. The kth scalar multiple of P is the point obtained by adding P to itself k times. This can be done efficiently by representing k as a binary number and using a double-and-add multiplication method. If you are familiar with RSA, scalar multiplication plays a similar role in ECC that modular exponentiation plays in RSA.

The real numbers used in diagrams for explaining ECC are not practical to use in actual implementations. Real numbers can have an arbitrary number of digits, and computers have only a finite amount of memory. Most applications, including OpenSSL, use elliptic curves over coordinates that use modular arithmetic, where the modulus is a large prime number. Figure 5 shows the elliptic curve with the same equation as in Figure 1, but where arithmetic is performed modulo 19.

Figure 5. Elliptic Curve over Prime Field (mod 19)

For the different key sizes in Table 1, NIST recommends a specific elliptic curve with a prime modulus for that key size (see the Binary Fields sidebar). For each key size, NIST specifies three things:

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 = 2²⁵⁶ – 2²²⁴ +2¹⁹² +2⁹⁶ – 1

The base point is G=(x_G,y_G) and defined by:

x_G = 48439561293906451759052585252797914202762949526041747995844080717082404635286

y_G = 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 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” (www.hyperelliptic.org/HEHCC) has yet to let me down.

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.