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).
|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|
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.
Department of Defense Requirements
Although NIST guidance is well respected, the Department of Defense has stronger requirements for classified information. For the Defense Department, 128 bits is only good enough for protecting information classified SECRET. Use of RSA isn't approved, and TOP SECRET information requires use of AES-256, SHA-384 and ECC with a 384-bit key size. Furthermore, systems must use two separate encryption implementations for protection. For example, use both IPsec and TLS, so that the information is still protected by one layer if a flaw in the other is found. Although this may not be very practical for most Internet applications, it's interesting to see what the requirements are when security is paramount.
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.