The secrets of encryption and decryption revealed
Communicating over any untrusted medium, particularly through distributed network and e-commerce applications, requires cryptography, the process of enciphering and deciphering secret code. Cryptography provides the following security functionality, which is necessary for secure client/server and application-to-application communication:
- Authentication—proves one's identity
- Privacy/confidentiality—ensures that only the intended receiver can read the message
- Message integrity—assures the receiver that the received message hasn't been altered from the original
- Nonrepudiation—proves that the sender sent the message
In this article, I discuss the different cryptographic algorithms, how to apply them, and how Windows NT uses cryptography.
You can classify cryptographic algorithms by the number of keys employed for encryption and decryption. Secret key cryptography uses one key for both encryption and decryption. Public key cryptography uses one key for encryption and a different key for decryption. Hash functions use a mathematical transformation, rather than a key, to irreversibly encrypt plaintext into ciphertext, as Figure 1, page 98, shows.
Secret key cryptography. Using this cryptographic algorithm, the sender uses a key to encrypt plaintext, then sends the ciphertext to the receiver. The receiver applies the same key to decrypt the ciphertext and recover the original message in plaintext.
In secret key cryptography, both sender and receiver must know the key. The greatest challenge of this method is the secure distribution of the key. The strength of a secret key cryptographic system is the length of the key. With limited computing power, the only way to attack a cryptographic system is to break the algorithm. As computers get faster and cheaper, brute-force attacks, in which an intruder tests every possible key combination, become increasingly affordable and common. Thus, to stave off a brute-force attack, you must use large keys that make computational attacks infeasible (a 90- to 100-bit key should be adequate for the next 10 years).
The most commonly used secret key cryptography scheme is the Data Encryption Standard (DES), which IBM designed in the 1970s and the US government subsequently adopted. Using a complex set of rules and transformations that IBM designed to yield fast hardware implementations and slow software implementations, DES uses a 56-bit key to encrypt 64-bit blocks of data. At the time, IBM also proposed a 128-bit key for DES, which the government rejected.
Experts in the cryptographic community claimed that DES wasn't sufficient to protect government, financial, medical, and other crucial information. In July 1998, the Electronic Frontier Foundation (EFF) announced a $220,000 hardware device that used brute-force methods to find a DES key in an average of 4-and-a-half days. Soon thereafter, the US government recommended that new DES implementations use Triple DES. 3DES employs three DES encryption and decryption steps and lets you use one, two, or three 56-bit keys, which makes a 168-bit key length possible.
Additional secret key cryptography algorithms are currently in use, including RC, which Ronald Rivest of RSA Data Security developed. To replace DES, RSA Data Security designed RC2, which operates on 64-bit blocks and uses a variable-length key. Although RC2's code isn't public, many companies, including Microsoft, have licensed RC2 for use in their products. RC4, which also uses variable key length, is a stream cipher (i.e., the algorithm contains a feedback mechanism to ensure that the algorithm encrypts blocks of data differently). Many commercial cryptographic products use RC4; however, vendors can export from North America only products that use short keys (e.g., 40- or 56-bits long).
In addition, since 1997, the US government has been looking for an official successor to DES. The government will select the successor, the Advanced Encryption Standard (AES), by the end of 2000.
Public key cryptography. In 1976, Stanford University professor Martin Hellman and graduate student Whitfield Diffie first publicly described public key cryptography. The Diffie-Hellman scheme solves secret key cryptography's key exchange problem by employing two keys: one to encrypt plaintext and the other to decrypt ciphertext. A year later, MIT mathematicians Rivest, Adi Shamir, and Leonard Adleman developed RSA, the first implementation of the Diffie-Hellman scheme.
In public key cryptography, one of the keys is the public key, which means the owner advertises the key. The other key is the private key, which means the owner keeps this key a secret. To send a message, the sender uses the receiver's public key to encrypt information and the receiver uses his or her private key to decrypt the ciphertext message. The order in which you apply the keys doesn't matter—one key encrypts, and you need the other key to decrypt. Although the two keys are mathematically related, you can't determine the second key by knowing the first.
RSA is the most common public key cryptography implementation, and hundreds of software products use it, primarily for key exchange. RSA uses a variable-size encryption block and a variable-size key, usually as many as 1024- to 2048-bits long. RSA derives a key-pair from a very large number, n, that is the product of two prime numbers. Each of these primes can be more than 100 digits in length, yielding an n value that contains approximately twice as many digits as the prime factors. This n value maintains RSA's security. The public key includes n and a derivative of one of the factors of n. This information doesn't reveal the prime factors of n to an intruder, so the private key remains secure.
Hash functions. Hash functions (e.g., message digests) are algorithms that don't use a key. Instead, hash functions mathematically alter plaintext so that the receiver can't recover the content and length of the original message. Hash functions rely on the fact that different plaintext strings are unlikely to yield the same hash value. Hash algorithms provide a digital fingerprint of a file's contents, which ensures that an intruder or virus hasn't altered the file. Many OSs also employ hash functions to encrypt passwords.
Message Digest (MD) algorithms are popular hash functions among commercial cryptographic applications. Rivest developed this family of byte-oriented schemes that produces a 128-bit hash value from an arbitrary-length message. Request for Comments (RFC) 1320 describes MD4, which Rivest designed for fast software processing using little memory. RFC 1231 describes MD5, which Rivest developed after users reported potential weaknesses in MD4. MD5 is similar to MD4 but slower because it manipulates the original data more than MD4 does. In 1996, users also discovered several weaknesses in MD5.
The Secure Hash Algorithm (SHA) is another hash code that commercial products commonly use. The National Institute of Standards and Technology (NIST) developed this hash function, which produces a 160-bit hash value.
Applications of Cryptographic Algorithms
Why not use one encryption and decryption method for all your cryptographic needs? Each cryptographic algorithm is optimal for specific functions:
- Secret key cryptography is ideal for encrypting messages. The sender generates a session key (per message) to encrypt the message, and the receiver uses the same session key to decrypt the message.
- Cryptographers use public key cryptography primarily for key exchange. You can also use asymmetric schemes for nonrepudiation: If the receiver obtains the session key encrypted with the sender's private key, only that sender could have sent the message. Theoretically, you can also use public key cryptography to encrypt data; however, secret key encryption is much faster than public key encryption is, so cryptographers rarely employ this function.
- Hash functions are well suited for ensuring data integrity. If an intruder or virus changes the content of a message, the receiver calculates a different hash value from the hash value the sender transmitted.
When you combine these cryptographic functions, you can create secure, private, authenticated communication between two users. For example, Alice uses secret key cryptography through a randomly generated session key to encrypt a message. She then uses Bob's public key to encrypt the session key. Together, the encrypted message and encrypted session key form a digital envelope. On receiving the message, Bob uses his private key to recover the session key and decrypts the encrypted message.
Alice's message also includes a digital signature, which assures Bob that Alice sent the message and that an intruder or virus hasn't altered her message. To create the digital signature, Alice's software computes the hash value of her message and uses her private key to encrypt the hash value. When Bob receives the digital signature, he recovers the hash value that Alice calculated by using Alice's public key to decrypt the digital signature. Next, Bob calculates the hash value of the message. If Bob's calculated hash value differs from Alice's hash value, Bob knows that something altered Alice's message. If the hash values match, Bob knows that the message is identical to the message that Alice sent. In addition, the matching hash value proves that Alice sent this message because only she could have used her private key to encrypt the hash value.
Key Distribution and Trust
These cryptographic methods exist within a larger framework of secure communication systems, such as Kerberos and public key certificates. These systems both rely on trusted third parties.
Developed at MIT, Kerberos is a cryptographic scheme that OSs and applications commonly use for authentication over the Internet. Kerberos uses a client/server architecture to provide user-to-server authentication in which every host on a network has a secret key, and a Key Distribution Center (KDC) is the trusted third party that manages keys for all the hosts within a realm. In this setup, when a new node comes online, you must configure only the KDC and the new node with the node's key.
RFC 1510 specifies Kerberos version 5 (V5), which is the most common version in use. Kerberos is scalable, and it's an effective key sharing and distribution scheme. However, the Kerberos server must have prior knowledge of all client systems before any transactions can occur. This requirement makes e-commerce client/server relationships infeasible. For more information about Kerberos, see Jan De Clercq, "Kerberos in Win2K," October 1999.
Public key cryptography uses public key certificates, which provide a global method for users to prove their identity. Public key cryptography is ideal for e-commerce applications because a Web site visitor can easily obtain the Web server's public key and use it for secret key cryptography key exchange. However, this process creates concerns: How do the client and server build a trust relationship without prior contact? How does a recipient determine whether a public key belongs to the sender? When does a public key expire?
A certificate is a digital document that contains a serial number, a digital signature algorithm identifier, the issuer's name, the validity period, the subject's name, and public key information. A certificate's primary role is to establish identity and define what actions certificate holders can take. Most certificates comply with the International Telecommunications Union Telecommunication Standardization Sector (ITU-T) Recommendation X.509 version 3 specification. A user obtains a certificate from a Certificate Authority (CA), which is any organization that issues digital certificates (e.g., a company that issues certificates to its employees or a university that issues certificates to its students). CAs for e-commerce applications need to be reputable; well-known commercial CAs include AT&T, GTE CyberTrust, Nortel Entrust, and VeriSign. Certificate recipients must trust the CA before they accept a public key. CAs must also have certificates, which creates a certificate chain that leads to a trusted root CA.
The basic concept of certificates and certificate chains is similar to a driver's license. For example, the state of Vermont issued my license, which means that I am allowed to drive certain motor vehicles. All US states accept my license because they recognize Vermont's authority to issue driver's licenses. When I go to other countries, they might also accept my license, not because Vermont issued it but because they accept licenses recognized as valid in the US.
Screen 1, page 100, shows a sample certificate that Microsoft shipped with Internet Explorer (IE) 4.0. GTE CyberTrust issued this root-level certificate, which many vendors ship with common browsers. When a user connects to a secure Web site, the site's Web server sends its certificate to the user's system. The user's browser then checks the Web server's signature against the CA's public key. If they match, the user's system accepts the certificate as valid and trusts the Web site. The policies and procedures of establishing a secure method for exchanging information, including certificates and CAs, form a public key infrastructure (PKI).
In the early 1990s, as the use of public key cryptography increased, RSA Laboratories recognized that effective use of this technology in a multivendor environment could succeed only if interoperable standards were in place. Therefore, RSA Laboratories created the following set of Public Key Cryptography Standards (PKCS):
- PKCS #1, which RFC 2437 specifies, outlines the RSA encryption standard, the construction of digital signatures and envelopes, and the syntax of public and private keys. The PKCS #1 public key syntax is identical to the syntax of X.509.
- PKCS #7, which RFC 2315 specifies, illustrates the syntax of data to which you can apply cryptography and describes aspects of certificate-based key management.
- PKCS #10, which RFC 2314 specifies, shows the syntax of certificate request messages.
How NT Uses Cryptography
NT employs cryptographic schemes in the OS and in server applications. For example, NT uses cryptography for network-logon passwords, tunneling in VPNs, secure Internet transactions, software authentication, and local file encryption.
Passwords for network logon. Like most OSs, NT doesn't store passwords on the system in plaintext. NT stores all user-related authentication information, such as usernames and passwords, in the SAM portion of domain controllers' Registries. SAM doesn't store the actual NT passwords, which can be as many as 14-characters in length and are case-sensitive, but stores two 16-byte hash values of the password.
When clients log on to an NT network, the workstation and domain controller never exchange passwords. Instead, NT uses a challenge/response scheme called Challenge Handshake Authentication Protocol (CHAP). When a user logs on to a client system, the system calculates a 16-byte hash value of the user's password. When the client connects to a server, the client system sends the username across the network in plaintext. The server generates a nonce, a random 8-byte value, and sends it to the client system. This value is the challenge.
The client system uses three DES keys to encrypt the 8-byte (64-bit) challenge. The first key contains the first 7 bytes (56 bits) of the password's hash value. The second key contains the next 7 bytes in the password's hash; and the third key contains the remaining 2 bytes of the password's hash, appended with 5 zero-filled bytes. The client system applies each key to the nonce so that the 8-byte challenge results in three 64-bit outputs, which is the 24-byte response.
After the server generates a nonce and sends the challenge, it looks up the user's password hash value in the SAM database. The server then creates an expected response by performing the same calculation that the client system performs using the nonce and hash value. If the server's expected response matches the client's actual response, the server authenticates the user.
This logon model will expand in Windows 2000 (Win2K). NT Server 4.0 and earlier can't forward user identification to remote servers. Win2K's distributed security model will use Kerberos V5 and X.509 public key certificates to provide this capability.
Tunneling in VPNs. To create VPNs, NT uses PPTP to build tunnels between clients and a RAS server. PPTP tunnels let a user transport and encrypt protocols, such as IP and IPX, over the Internet. PPTP uses cryptography for user authentication and data encryption. If the user is on a Windows 3.x or later client system and the user is connecting to an NT RAS server, PPTP will use Microsoft CHAP (MSCHAP) for authentication.
For data encryption, PPTP uses the Microsoft Point-to-Point Encryption (MPPE) protocol, which uses RC4 secret key encryption. If either the server or the client is using exportable PPTP software, PPTP employs a 40-bit key. If the server and the client are using the domestic (i.e., North American) PPTP software, PPTP uses a 128-bit key for encryption. However, PPTP doesn't provide the strength inherent in a 128-bit key space because PPTP derives the key from a user's password, which creates two potential weaknesses. First, passwords aren't truly random; second, the characters in most users' passwords don't employ the 256 possibilities of each byte. This key derivation weakens PPTP's key choice.
In 1998, renowned cryptographer Bruce Schneier criticized Microsoft's PPTP implementation and publicized that the original version of MPPE is vulnerable to attack. If a user doesn't change his or her password, MPPE uses the same key to encrypt every message. If output-feedback stream ciphers, such as RC4, use the same key to encrypt two or more messages, intruders can recover the key by acquiring any two of the messages. Microsoft fixed this weakness by modifying the algorithm so that PPTP adds a unique nonce to the password before key generation. If you use PPTP, be sure you're using the most recent version.
Secure Internet transactions. Netscape Communications developed the Secure Sockets Layer (SSL) protocol to provide application-independent security over the Internet, primarily for HTTP. SSL 3.0 is currently the most commonly used version of SSL, although some SSL 2.0 implementations are still in use. IE 4.0, Microsoft Internet Information Server (IIS), and Microsoft Proxy Server support both SSL versions.
SSL employs RSA during an initial handshake to authenticate the server (client authentication is optional), identify the secret key cryptography algorithm for the session, and distribute the session secret key. After the server and client agree on the session encryption scheme, the client and server both switch to this encryption scheme. The following steps walk you through a simplified SSL message exchange, which Figure 2 shows:
- When a user enters a Web address that specifies https://, the client establishes a connection to the SSL server, which listens on TCP port 443. The SSL client initiates the connection by sending a ClientHello message that includes the SSL version number and the secret key cryptography schemes that the client supports (secret key cryptography choices include DES, RC2, RC4, and 3DES).
- The server responds with a ServerHello message that includes the secret key cryptography scheme that the client will use for this session. The server also sends its X.509 public key certificate, which contains the server's RSA public key (ES).
- The client verifies that the server's certificate is valid, then extracts the server's public key from the certificate. Next, the client generates a session secret key (K) and sends it to the server encrypted in the server's public key. The client also signals to the server that it will use the specified secret key cryptography algorithm, and ends the transmission with a Finished message.
- The server tells the client that it agrees to use the encryption scheme and sends a Finished message.
- The client and server exchange encrypted data.
In 1997, users reported several weaknesses in SSL 3.0. However, the IETF had already started developing a new SSL version called Transport Layer Security (TLS, which RFC 2246 defines). TLS extends SSL by adding support for 3DES secret key cryptography, SHA hashes, and Diffie-Hellman key exchange. Another addition to SSL/TLS is Microsoft Server Gated Cryptography (SGC). Until recently, the US government tightly regulated exports that employed secret key cryptography keys longer than 40 bits. Today, the government limits cryptographic exports to 56-bit keys; only domestic cryptography products can employ strong (128-bit) keys. However, vendors can export financial products that use secret key cryptography keys of any length to the worldwide financial community, including online merchants. SGC is an SSL extension that supports international use of strong cryptography. Both the client and the server must implement SGC, and the server must have a valid SGC certificate. During the initial handshake, the bank's server tells the client that the server has SGC capability and supplies its certificate. If the certificate is valid, the client can request use of 128-bit RC2 or RC4, 56-bit DES, or 168-bit 3DES. IE 4.0 and IIS 4.0 support TLS; IE 4.0, IIS 4.0, and Microsoft Money 98 support SGC.
In addition to SSL and TLS, Microsoft uses several protocols and mechanisms to secure financial Internet transactions. In the mid-1990s, Microsoft and Visa developed Private Communications Technology (PCT) for credit card validation. PCT supports Diffie-Hellman and RSA for key exchange, and DES, RC2, RC4, and 3DES for encryption. IIS 4.0 supports PCT. In addition, IIS 4.0 supports the Secure Electronic Transaction (SET) specification, which is a companion to PCT. This specification uses DES and RC4 for encryption and RSA for key exchange and public key encryption of bankcard numbers. The protocols and servers that Microsoft employs for secure communication all rely on certificates. To create and verify certificates, you can use Microsoft Certificate Server, which employs X.509 V1 and V3, PKCS #7, and PKCS #10.
Software authentication. The Internet has been a boon for software distributors—and for virus and Trojan horse distributors. When you download an executable from the Internet, a major concern is always, "Do I trust the author? If so, how can I be sure that this code is the original code that the author wrote?"
Microsoft developed Authenticode to address these concerns. Software publishers obtain a certificate and assign an identifier and digital signature to their software. After downloading the file but before installation, users can use Authenticode to confirm the author's identity and the file's integrity. Authenticode employs X.509 certificates, the SHA hash scheme, and MD5 encryption.
Local file encryption. Win2K will introduce the Encrypting File System (EFS), an addition to NTFS that automatically encrypts individual files and directories on the local hard disk the same way that NT 4.0 NTFS automatically compresses files. EFS uses public key cryptography methods, so it is easy to manage and transparent to the user. EFS also provides a data-recovery process that lets a user decrypt files without revealing the sender's private key. (For more information about EFS, see Zubair Ahmad, "Windows 2000 EFS," http://www.winntmag.com, InstantDoc ID number 5006.)
In addition to the previous applications, Microsoft uses cryptography in many products. For example, Win2K will provide support for the IP Security (IPSec) protocol. IPSec uses a host of cryptographic schemes to provide authentication and encryption of IP packets. (For more information about IPSec, see Tao Zhou, "Internet Protocol Security in NT 5.0," August 1998.)
Microsoft has also made its cryptographic and certificate management capabilities available to third-party vendors via its Cryptographic API (CryptoAPI), which lets programmers use simple procedure calls to access cryptographic functions rather than rewrite code that Microsoft has already developed and debugged. CryptoAPI-supported functions ensure interoperability with Win32 applications and let application developers easily encrypt and decrypt data, sign messages, calculate hash values, and manage certificates and public keys. Microsoft began shipping CryptoAPI with IE 3.0 and NT 4.0.
Just the Basics
This article introduces basic cryptographic terms and concepts so you can read documentation about cryptographic applications and make sense of what the product or service does and how the product or service does this. In addition, when you shop for a cryptographic product, be wary of products that vendors base on proprietary cryptographic algorithms. Although cryptographic-product developers perform much of their work in secret, the best algorithms are well known and well documented—as a result, they're well tested. Time is the best test of good cryptography. Corrections to this Article:
- "Deciphering Cryptography" incorrectly states that Microsoft's Authenticode employs X.509 certificates, the SHA hash scheme, and Message Digest 5 (MD5) encryption. MD5 is a hashing scheme, not an encryption scheme. We apologize for any inconvenience this error might have caused.