Encryption 101 - The Choices
Ramón J. Hontañón
In the late 1980s and early 1990s, there was a clear separation between "private" and "public" networks. Those companies that engaged in early electronic commerce did so while ensuring that all transactions took place over "secure" (read "dedicated") lines. Confidentiality was achieved by physically protecting the communication medium. With the advent of the public Internet, the electronic commerce model changed dramatically. The network can no longer be trusted to be a private medium, so steps must taken to ensure that sensitive information will not be compromised when it falls into hostile hands. Encryption technology, once the realm of spies and secret government operations, became of great interest to conventional businesses. This article provides a summary view of the major encryption alternatives currently available, with the aim of helping you make the choice that is right for your environment.
Encryption, of course, refers to the process by which sensitive information is modified using a cryptographic algorithm and a "seed" value, typically known as a "key". A similar algorithm can be applied to the encrypted data to recover the original information, using a decrypting key. The strength of an encryption algorithm lies in the difficulty of decrypting a block of encrypted data (typically referred to as "cyphertext") without having prior knowledge of the encrypting key. Not surprisingly, key length is a determining factor of algorithm strength: the longer the key, the harder it is to "crack" the algorithm.
The following sections organize the cryptographic choices by the nature of the key, secret or public, and examine various forces that may influence your choice of an encryption strategy that is appropriate for your needs.
Secret Key Cryptography: Encrypting the Data
Data Encryption Standard (DES)
The DES algorithm was developed at IBM in 1977, under the sponsorship of the National Bureau of Standards (now known as the National Institute of Standards and Technology, NIST), to be used for both commercial and government (unclassified) applications. DES works by mapping 64-bit blocks of cleartext data into cypherblocks of the same size. The actual encryption takes place by an iterative process whereby each block of cleartext goes through a complex set of permutations and substitutions, after which the results are exclusive-OR'd with the original input. This process is repeated 16 times for each block of data to be encrypted, using a different bit ordering for the key at each iteration.
The basic DES algorithm uses a 56-bit key, which was believed to provide an appropriate level of security back in 1977. Twenty years later, DES remains the most widely used secret-key algorithm, but its strength has been brought into question even by its original authors. In June of 1997, it took a team of programmers just over four months to break a 56-bit DES key, using a cluster of thousands of computers scattered all throughout the Internet, after trying about 25% of the 72 quadrillion possible keys.
At the writing of this article, NIST is already taking steps to find a replacement for DES (See "Emerging Technologies" below).
International Data Encryption Algorithm (IDEA)
Originally known as IPES ("Improved Proposed Encryption Standard"), IDEA was developed in 1991 at the Swiss Federal Institute of Technology, in Zurich. The principal advantage of IDEA over DES is the longer key size (128 bits), and the fact that the basic IDEA algorithm it is much easier to implement on software than DES.
IDEA is a relatively new secret-key algorithm, and as such, it has not yet been widely implemented. However, IDEA was chosen over DES for the PGP ("Pretty Good Protection") encryption suite, a popular electronic mail security application. I will discuss PGP in more detail in an upcoming section.
Introduced by Bruce Schneier in 1993, the Blowfish algorithm is similar to DES in nature, except that it uses variable-length keys. Whereas DES is limited to 56-bit keys, Blowfish keys can be anywhere from 32 to 448 bits long. The idea was to design a drop-in replacement for DES, but unlike its predecessor, Blowfish would include free source code and would require no license to implement. The result was a much faster, efficient protocol. As a matter of fact, most Blowfish implementations will typically outperform both DES and IDEA given the same key size. Performance aside, the main advantage of Blowfish is its flexibility. By accommodating variable size keys, the algorithm can be used for exportable applications (typically up to 40 bits) and also for stronger, domestic-grade encryption. Not surprisingly, Blowfish is commonly found in public domain security applications, especially in the Windows95 and NT arena.
Public Key Cryptography: Managing the Keys
The Diffie-Hellman algorithm
In 1976, Whitfield Diffie and Martin Hellman published a paper called "New Directions in Cryptography". This work, now widely regarded as a "classic", was the first to introduce the notion of public-key cryptography, a concept used by the majority of information security systems in place today.
The basic idea behind public-key cryptography is surprisingly simple: consider an exchange between a sender (Alice) and a receiver (Bob). If Alice is concerned about confidentiality and wishes to protect her message to Bob, she simply encrypts the message text using Bob's public key. By doing this, she ensures that only Bob can decrypt the message, using his private (secret) key. This type of mechanism is known as asymmetric cryptography, as the key used to encrypt the data is not the same one used to decrypt it. Note that we assume that Alice and Bob know each other's public key before the exchange takes place.
Public-key cryptography can also be used to ensure authentication of a message, whereby the receiver can be assured that the message really originated from the apparent sender. Consider the following scenario: Alice wants to send a message to Bob, and wants to assure Bob that she was indeed the author of the message. Alice simply uses her own private key to append a digital signature to the message. This signature is simply a few lines of text included at the end of the cleartext message. To verify the identity of the sender, Bob uses Alice's public key to verify her signature, which validates her identity as the author of the message.
Along with the concept of public-key cryptography, Diffie and Hellman's landmark paper also introduced the concept of a "key agreement algorithm". In order for the sender and receiver to be able to use symmetric data encryption, they must first establish a "session" key, known only by both parties. This will serve as the secret encrypting key for all subsequent traffic exchanges.
The Diffie-Hellman key agreement algorithm uses two large prime numbers, p and q, which must have been previously shared by both parties (this can be done on-line). The sender chooses a random 512-bit number, and applies a simple mathematical function to it, using both p and q. The receiver then does the same. Both parties can then safely exchange these numbers, and raise them to the power of their own secret numbers, which will yield the same number for both sender and receiver. This common number can then be used as their shared, secret session key.
Named after its inventors (Ron Rivest, Adi Shamir, and Leonard Adleman), the RSA algorithm is widely used for both confidentiality and authentication. RSA is a public-key based technique, whereby the user creates a private key, which she never reveals to anyone, and a public key, which can be made available to everyone.
One of the most attractive features of RSA is the fact that the same key pair can be used for encryption (confidentiality) and digital signatures (authentication), and both can be achieved without the need to exchange secret key information. RSA technology is widely deployed in the security industry, with applications ranging from email privacy (PGP, S/MIME) to protocols supporting secure financial transactions (SET).
The "Simple Key-management Internet Protocol" was designed by Sun Microsystems' Ahsar Aziz and Whitfield Diffie in 1994. SKIP provides the tools necessary to establish a secure point-to-point session, by encrypting all end-to-end traffic using a secret session key. Available for SunOS, Solaris, and Windows platforms, SKIP works with the existing TCP/IP stack by encrypting (and optionally, authenticating) network packets just below the IP layer. This makes SKIP operation totally transparent to the user, to the network applications, and even to the existing TCP/IP stack.
Key agreement between parties is achieved via the Diffie-Hellman protocol, with public keys ranging in length from 512 to 2048 bits. Once the session key has been established, packets can be encrypted using a variety of algorithms, including 40-bit RC2, 40-bit RC4, 56-bit DES, 56-bit Triple-DES, and 128-bit SAFER. A working implementation of SKIP for both Sun Solaris and Windows95 is available for download from Sun Microsystems.
Encryption Applications: Using Encryption in the "Real World"
In the age of electronic commerce, how can Alice be sure that she is really buying goods from Bob? The answer may very well lie in Digital Certificates. Similar in nature to physical identification cards, digital certificates aim to positively identify the certificate holder by including a third party's certification of the holder's identity. This third party is referred to as the "certification authority" (CA). The digital certification process is similar in nature to the Department of Motor Vehicle's certifying a driver's identity on a driver's license card. Several private companies, like VeriSign, BelSign, Internet Publishing Services, and Thawte Consulting are already offering commercial digital certificate services. Web browsers such as Netscape Navigator and Microsoft Internet Explorer ship with several of these certificates built into the software distribution.
A typical digital certificate will include a number of details about the certificate holder, as well as the holder's public key and a certificate expiration date. The whole certificate is then digitally signed with the CA's private key; so at any time, the certificate's validity can be verified against the CA's public key (which should be publicly available). Note that a digital certificate is only as reputable as the CA. Ideally, a good choice of CA would be a government agency, such as the U.S. Postal Service, or the U.S. Treasury Department. There is extensive work currently underway to build a public key infrastructure that will be able to support a fully scalable certification hierarchy.
Designed by Netscape Communications as an open security standard, the Secure Sockets Layer (SSL) provides data encryption, server authentication, message integrity, and optional client authentication for a TCP connection. SSL uses RSA public-key cryptography for both privacy and authentication of messages, typically exchanged between a Web browser and a Web server. SSL works over the existing TCP/IP stack, positioning itself just below the application layer, and has been widely deployed in electronic commerce applications to protect sensitive data, such as credit card numbers and username/password combinations, from "sniffer" attacks. A reference implementation of SSL is available for download from Netscape Communications for non-commercial use.
Virtual Private Networks: IPsec
The concept of Virtual Private Networks (or VPNs) is relatively new. Until a few years ago, the only secure way to connect branch office LANs to the corporate headquarters was to lease a dedicated line from the telephone company, or to set up a dial-on-demand link over the plain old telephone system. But with the Internet explosion of the mid '90s, the idea of routing private packets over the public Internet is gaining momentum. Although the business case is easy to make (leased lines often carry prohibitive costs), security is still a major concern. Enter cryptography.
Secret key technology is at the core of VPN success. By encrypting every packet that originates at the branch office and is bound for the corporate LAN (and vice versa), we are assuring the confidentiality and integrity of our corporate data, even over inherently unsecure communication lines. In fact, VPN technology is so popular, that most vendors are incorporating encryption capabilities into network routers, which allows encryption to take place on hardware, rather than software, with the corresponding performance gain.
To ensure interoperability among VPN vendors, the Internet Engineering Task Force (IETF) is actively pursuing a standard protocol for virtual private networks. The IP Security (IPsec) specification extends the functionality of the IPv4 packet, in order to accommodate both encryption and authentication at the IP layer. IPsec support will be mandatory for IPv6 implementation, and most vendors are already shipping IPsec-capable products, even on IPv4 stacks.
Developed at MIT as part of the Athena project, Kerberos is a secret-key based mechanism used for authentication of users to network servers and other resources. Kerberos also provides a mechanism for distribution of public and secret keys, as well as the generation of special Kerberos "tickets", a digital token that authenticates a user to a server. The Kerberos Key Distribution Center (KDC) acts as the supreme network authority, which must be trusted by all parties. The KDC contains the secret key of all the users as well as all the servers, and it is through the use of these keys that a user can request authorization to access a specific server, under the auspices of the KDC.
When a user wants to access a resource that lives on one of the servers, it must first negotiate with the KDC in order to obtain a ticket granting ticket (TGT). This ticket will authenticate the user to the KDC for all future exchanges. The next step is for the user to request an actual Kerberos ticket, to be used for authentication for a specific server. Upon successful examination of the TGT, the KDC grants the user a ticket for a specific service, which can be presented to the appropriate server for access. This ticket can be reused multiple times until it reaches its expiration date.
The original Kerberos implementation (version 4) provided a convenient, secure framework for authentication, but it suffered from scalability problems, as the KDC had to maintain key information on all users and services in the entire network. To get around this problem, Kerberos v.5 introduced a hierarchical authentication structure, where each KDC is in charge of a specific Kerberos "realm". A typical enterprise Kerberos installation will include several realms, and redundant KDCs for each realm.
Kerberos has been widely implemented on UNIX platforms, and the upcoming release of Windows NT 5.0 is slated to include Kerberos support.
Philip Zimmerman is to public-key cryptography what Linus Torvalds is to the UNIX operating system. By introducing the first version of Pretty Good Privacy (PGP) back in 1991, Zimmerman provided a free solution to the problem of privacy and authentication of electronic mail. PGP included a suite of tools that allowed users to encrypt messages with the recipient's public key (for privacy), and with the sender's own private key (for authentication). The package also included utilities to manage public keys using the concept of a public "key-ring".
PGP uses both public and private key cryptography. When a sender encrypts a message using the recipient's public key, the message itself is encrypted using an IDEA key, which is appended to the message, and encrypted using the recipient's public key. Once the message is delivered, the PGP agent at the recipient's end simply recovers the IDEA key using the recipient's private key, and the message text is then decrypted using the IDEA key. By using this approach, PGP combines the convenience of public-key technology with the performance advantages of secret-key encryption.
The U.S. Government filed a lawsuit against Phil Zimmerman, alleging that by releasing PGP into the public domain, it was being placed into the hands of potential enemies to the United States. The lawsuit was eventually dropped after the public expressed their opposition. However, export of PGP encryption is still tightly regulated by federal authorities.
There are both free and commercial PGP implementations available for most operating systems in use, including UNIX, Windows95/NT, Macintosh, OS/2, AmigaOS, and even Atari and VAX/VMS.
While the U.S. government imposes no limits on encrypting key length for domestic products, there are laws in place that regulate the export of software containing strong cryptography. Since 1992, the International Trafficking in Arms Regulations (ITAR) restricts the export of products with keys longer than 40 bits. In October of 1996, the Department of Commerce announced that it would allow export of 56-bit crypto on a case-by-case basis, and for a limited time. These exceptions are typically only awarded to those vendors willing to comply with strict "key escrow" requirements, by which the government, or an appointed third party reserves the right to keep a copy of all keys used for data encryption. This key could be used at the discretion of law enforcement agencies. Foreign governments are typically less restrictive in their crypto export policies, so 128-bit secret key products are readily available from vendors outside the United States.
At the writing of this article, there is a bill pending before Congress that seeks to remove the barriers imposed on the export of strong encryption. Sponsored by Bob Goodlatte (R-VA) and Zoe Lofgren (D-CA), the "Security and Freedom Through Encryption Act" (SAFE, HR695) would also remove the "key escrow" condition that is often placed on the export of cryptography software. The SAFE act is scheduled to come before the full House of Representatives sometime this summer.
Several grass-roots organization are also actively working to reverse the current U.S. Government policy on encryption. If you share this point of view, I encourage you to visit the Americans for Computer Privacy (ACP) Web site at www.computerprivacy.org. ACP is a broad-based coalition that enjoys the support of corporations such as Microsoft, Sun Microsystems, Netscape Communications, and America Online, to name a few. Its main focus is opposition to federal restrictions on the use of encryption products both domestically and overseas. By joining the ACP (membership is free), private citizens can voice their collective opinion before the elected officials.
A fair amount of debate on both sides of this issue can also be found in the USENET group "talk.politics.crypto" (FLAME WARNING: the sci.crypt.* groups are reserved for topics in cryptography research, and are not for policy discussions).
Advanced Encryption Standard (AES)
The DES standard goes through a formal revision process every five years. In 1993, DES was declared to be appropriate for commercial use. In 1998, NIST is sponsoring an open competition to come up with a replacement for the aging DES standard.
The search for the so-called Advanced Encryption Standard (AES) has already attracted some of the leading vendors of cryptography products, such as Cylink, and RSA Data Security. Others are likely to follow suit before the June 15th entry deadline. Once the winner is announced by the NIST, the standard selected will probably not be implemented until the turn of the century.
Elliptic Curve Cryptography
The mathematical principles supporting public-key cryptography have remained essentially unchanged during the past twenty years. Most crypto systems use fixed-size keys, and stronger encryption typically requires longer key sizes, with the corresponding increase in computation time. In recent years, cryptography researchers have been busy studying elliptical curve functions as an alternative to the standard exponential algorithms used for cryptography today. Elliptic curve algorithms tend to be less computationally intensive than conventional ones, due to the fact that the key size can be made much smaller, yet they can achieve the same degree of security as exponential algorithms that use much larger keys. Elliptic curve cryptography is now considered a mature technology, and commercial implementations should be available before the turn of the century.
What if you are not allowed to send encrypted data at all? Well, then hide it! The Greek word steganography translates literally as "covered writing". This is a loaded term, which encompasses a whole array of techniques concerned with concealing a message within another message, typically a digital image representation. The purpose of steganography is not only to hide the content of the message, but to hide the fact that the message is being sent at all. It is important to note that steganography is not intended to replace cryptography, but rather complement it. By hiding a message, we reduce the likelihood that the message will be detected, but cryptography adds an extra layer of protection in case the message is indeed discovered.
At least three commercial vendors offer steganography implementations, and there are several packages available from the public domain as well, mostly for Microsoft Windows platforms.
Which "Crypto" Is Right For Me?
Simply ask yourself the following two questions:
1. How fast and how often is the data going to be exchanged?
The real cost of data encryption is processing time. Even with today's increasingly inexpensive processing power, certain applications have timing requirements that do not tolerate the overhead associated with encryption. For instance, it would be impractical to use public key encryption to protect the payload of IP packets, as network performance would degrade noticeably, especially on high-speed transport mediums like Fast Ethernet or ATM. This type of real-time network encryption is typically only carried out using a secret-key based approach, like 56-bit DES, IDEA, or Blowfish.
Using longer keys results in longer encryption/decryption times. That's why public-key encryption is commonly employed in asynchronous applications with no real-time requirements, such as electronic mail, data archival, and digital signatures.
2. How long is the data going to be stored?
The longevity of the data to be encrypted is an important factor in deciding the appropriate encryption methodology. Most electronic commerce transactions are short-lived in nature: a complete funds transfer only takes a few seconds, and a malicious attack would have to be carried out within a fairly small time window, since the secret "session" key is only active for the duration of the transaction.
On the other hand, a customer's personal and financial records archived at a financial institution will be subject to attacks for many years. A determined attacker with access to the encrypted data would have (literally) a lifetime to try and break the code! This type of data should be protected accordingly, and the encryption mechanism used for longterm archives should be re-evaluated periodically to reflect the changes in available processing power. With the recent advances in semiconductor design, that "lifetime" is getting shorter at exponential speeds.
Digital Certificates: http://www.verisign.com
Elliptic Key Cryptography: http://www.certicom.com/ecc
About the Author
Ramón J. Hontañón is a network security consultant, currently working in the areas of virtual private networking and secure remote access for large enterprise networks. He lives in Ashburn, VA with his wife, Stacia, and a black labrador retriever named "Toro". He welcomes your comments and questions at email@example.com.