Not Quite the Metric System: Symmetric and Asymmetric Key Systems

Cryptographic algorithms are broadly classified as either symmetric or asymmetric key systems.

Symmetric key cryptography

Symmetric key cryptography, also known as symmetric algorithm, secret key, single key, and private key cryptography, uses a single key to both encrypt and decrypt information. Two parties (for our example, Thomas and Richard) can exchange an encrypted message by using the procedure in Lab 8-2:

Lab 8-2 Exchanging an Encrypted Message with Symmetric Key Cryptography

1. The sender (Thomas) encrypts the plaintext message with a secret key known only to the intended recipient (Richard).

2. The sender then transmits the encrypted message to the intended recipient.

3. The recipient decrypts the message with the same secret key to obtain the plaintext message.

In order for an attacker (Harold) to read the message, he must guess the secret key (by using a brute-force attack, for example) or intercept the secret key during the initial exchange.

The following list includes the main disadvantages of symmetric systems:

Distribution: Secure distribution of secret keys is absolutely required either through out-of-band methods or by using asymmetric systems.

Scalability: A different key is required for each pair of communicating parties.

Limited functionality: Symmetric systems can’t provide authentication or non-repudiation (see the earlier sidebar “He said, she said: The concept of non-repudiation”).

Of course, symmetric systems do have many advantages:

Speed: Symmetric systems are much faster than asymmetric systems.

Strength: Strength is gained when used with a large key (128 bit, 256 bit, or larger).

Availability: There are many algorithms available for organizations to select and use.

Symmetric key algorithms include Data Encryption Standard (DES), Triple DES (3DES), Advanced Encryption Standard (AES), International Data Encryption Algorithm (IDEA), and Rivest Cipher 5 (RC5).

Symmetric key systems use a shared secret key.

Data Encryption Standard (DES)

In the early 1970s, the National Institute of Standards and Technology (NIST) solicited vendors to submit encryption algorithm proposals to be evaluated by the National Security Agency (NSA) in support of a national cryptographic standard. This new encryption standard was used for private-sector and Sensitive but Unclassified (SBU) government data. In 1974, IBM submitted a 128-bit algorithm originally known as Lucifer. After some modifications (the algorithm was shortened to 56 bits and the S-boxes were changed), the IBM proposal was endorsed by the NSA and formally adopted as the Data Encryption Standard. It was published in Federal Information Processing Standard (FIPS) PUB 46 in 1977 (updated and revised in 1988 as FIPS PUB 46-1) and American National Standards Institute (ANSI) X3.92 in 1981.

DES is a block cipher that uses a 56-bit key.

The DES algorithm is a symmetric (or private) key cipher consisting of an algorithm and a key. The algorithm is a 64-bit block cipher based on a 56-bit symmetric key. (It consists of 56 key bits plus 8 parity bits . . . or think of it as 8 bytes, with each byte containing 7 key bits and 1 parity bit.) During encryption, the original message (plaintext) is divided into 64-bit blocks. Operating on a single block at a time, each 64-bit plaintext block is split into two 32-bit blocks. Under control of the 56-bit symmetric key, 16 rounds of transpositions and substitutions are performed on each individual character to produce the resulting ciphertext output.

A parity bit is used to detect errors in a bit pattern. For example, if the bit pattern has 56 key bits (ones and zeros) that add up to an even number, an odd-parity bit should be a one, making the total of the bits — including the parity bit — an odd number. For an even-parity bit, if the 56 key bits add up to an even number, the parity bit should be a zero, making the total of the bits— including the parity bit — an even number. If an algorithm uses even parity and the resulting bit pattern (including the parity bit) is an odd number, then the transmission has been corrupted.

A round is a transformation (permutations and substitutions) that an encryption algorithm performs on a block of plaintext to convert (encrypt) it into ciphertext.

The four distinct modes of operation (the mode of operation defines how the plaintext/ciphertext blocks are processed) in DES are Electronic Code Book, Cipher Block Chaining, Cipher Feedback, and Output Feedback.

The four modes of DES are ECB, CBC, CFB, and OFB. ECB and CBC are the most commonly used.

The original goal of DES was to develop an encryption standard that could be used for 10 to 15 years. Although DES far exceeded this goal, in 1999, the Electronic Frontier Foundation achieved the inevitable, breaking a DES key in only 23 hours.

Electronic Code Book (ECB)

Electronic Code Book (ECB) mode is the native mode for DES operation and normally produces the highest throughput. It is best used for encrypting keys or small amounts of data. ECB mode operates on 64-bit blocks of plaintext independently and produces 64-bit blocks of ciphertext. One significant disadvantage of ECB is that the same plaintext, encrypted with the same key, always produces the same ciphertext. If used to encrypt large amounts of data, it’s susceptible to Chosen Text Attacks (CTA) (discussed in the section “Chosen Text Attack (CTA),” later in this chapter) because certain patterns may be revealed.

Cipher Block Chaining (CBC)

Cipher Block Chaining (CBC) mode is the most common mode of DES operation. Like ECB mode, CBC mode operates on 64-bit blocks of plaintext to produce 64-bit blocks of ciphertext. However, in CBC mode, each block is XORed (see the sidebar “The XORcist,” later in this chapter) with the ciphertext of the preceding block to create a dependency, or chain, thereby producing a more random ciphertext result. The first block is encrypted with a random block known as the initialization vector (IV). One disadvantage of CBC mode is that errors propagate. However, this problem is limited to the block in which the error occurs and the block that immediately follows, after which, the decryption resynchronizes.

Input A (Plaintext)	Input B (Key)	Output C (Ciphertext)
0	0	0
0	1	1
1	0	1
1	1	0

Cipher Feedback (CFB)

Cipher Feedback (CFB) mode is a stream cipher most often used to encrypt individual characters. In this mode, previously generated ciphertext is used as feedback for key generation in the next keystream. The resulting ciphertext is chained together, which causes errors to be multiplied throughout the encryption process.

Output Feedback (OFB)

Output Feedback (OFB) mode is also a stream cipher very similar to CFB. It is often used to encrypt satellite communications. In this mode, previous plaintext is used as feedback for key generation in the next keystream. Because the resulting ciphertext is not chained together, errors don’t spread throughout the encryption process.

Triple DES (3DES)

Triple Data Encryption Standard (3DES) effectively extended the life of the DES algorithm. In Triple DES implementations, a message is encrypted by using one key, encrypted by using a second key, and then again encrypted by using either the first key or a third key.

The use of three separate 56-bit encryption keys produces an effective key length of 168 bits. But Triple DES doesn’t just triple the work factor required to crack the DES algorithm (see the sidebar “Work factor: Force × effort = work!” in this chapter). Because the attacker doesn’t know whether he or she successfully cracked even the first 56-bit key (pick a number between 0 and 72 quadrillion!) until all three keys are cracked and the correct plaintext is produced, the work factor required is more like 256 x 256 x 256, or 72 quadrillion x 72 quadrillion x 72 quadrillion. (Don’t try this multiplication on a calculator; just trust us on this one.)

Double DES wasn’t a significant improvement to DES. In fact, by using a Meet-in-the-Middle Attack (see the section “Meet-in-the-Middle Attack,” later in this chapter), the work factor required to crack Double DES is only slightly greater than for DES. For this reason, Double DES isn’t commonly used.

Using Triple DES would seem enough to protect even the most sensitive data for at least a few lifetimes, but a few problems exist with Triple DES. First, the performance cost is significant. Although Triple DES is faster than many other symmetric encryption algorithms, it’s still unacceptably slow and therefore doesn’t work with many applications that require high-speed throughput of large volumes of data.

Second, a weakness exists in the implementation that allows a cryptanalyst to reduce the effective key size to 108 bits in a brute force attack. Although a 108-bit key size still requires a significant amount of time to crack (theoretically, several million millennia), it’s still a weakness.

Advanced Encryption Standard (AES)

In May 2002, NIST announced the Rijndael Block Cipher as the new standard to implement the Advanced Encryption Standard (AES), which replaced DES as the U.S. government standard for encrypting Sensitive but Unclassified data. AES was subsequently approved for encrypting classified U.S. government data up to the Top Secret level (using 192- or 256-key lengths).

See Chapter 6 for more on data classification.

The Rijndael Block Cipher, developed by Dr. Joan Daemen and Dr. Vincent Rijmen, uses variable block and key lengths (128, 192, or 256 bits) and between 10 and 14 rounds. It was designed to be simple, resistant to known attacks, and fast. It can be implemented in either hardware or software and has relatively low memory requirements.

AES is based on the Rijndael Block Cipher.

Until recently, the only known successful attacks against AES were side- channel attacks, which don’t directly attack the encryption algorithm, but instead attack the system on which the encryption algorithm is implemented. Side-channel attacks using cache-timing techniques are most common against AES implementations. In 2009, a theoretical related-key attack against AES was published. The attack method is considered theoretical because, although it reduces the mathematical complexity required to break an AES key, it is still well beyond the computational capability available today.

Blowfish and Twofish Algorithm

The Blowfish Algorithm operates on 64-bit blocks, employs 16 rounds, and uses variable key lengths of up to 448 bits. The Twofish Algorithm, a finalist in the AES selection process, is a symmetric block cipher that operates on 128-bit blocks, employing 16 rounds with variable key lengths up to 256 bits. Both Blowfish and Twofish were designed by Bruce Schneier (and others) and are freely available in the public domain (neither algorithm has been patented). To date, there are no known successful cryptanalytic attacks against either algorithm.

Rivest Ciphers

Drs. Ron Rivest, Adi Shamir, and Len Adleman invented the RSA algorithm and founded RSA Data Security (RSA = Rivest, Shamir, Adleman). The Rivest Ciphers are a series of symmetric algorithms that include RC2, RC4, RC5, and RC6 (RC1 was never published and RC3 was broken during development):

RC2: A block-mode cipher that encrypts 64-bit blocks of data by using a variable-length key.

RC4: A stream cipher (data is encrypted in real time) that uses a variable-length key (128 bits is standard).

RC5: Similar to RC2, but includes a variable-length key (0 to 2,048 bits), variable block size (32, 64, or 128 bits), and variable number of processing rounds (0 to 255).

RC6: Derived from RC5 and a finalist in the AES selection process. It uses a 128-bit block size and variable-length keys of 128, 192, or 256 bits.

IDEA Cipher

The International Data Encryption Algorithm (IDEA) Cipher evolved from the Proposed Encryption Standard and the Improved Proposed Encryption Standard (IPES) originally developed in 1990. IDEA is a block cipher that operates on 64-bit plaintext blocks by using a 128-bit key. IDEA performs eight rounds on 16-bit sub-blocks and can operate in four distinct modes similar to DES. The IDEA Cipher provides stronger encryption than RC4 and Triple DES, but because it’s patented, it’s not widely used today. However, the patents are set to expire in various countries between 2010 and 2012. It is currently used in some software applications, including Pretty Good Privacy (PGP) e-mail. (For more on PGP, read “E-mail Security Applications” later in this chapter.) There are currently no known practical cryptanalytic attacks against the IDEA Cipher.

Asymmetric key cryptography

Asymmetric key cryptography (also known as asymmetric algorithm cryptography or public key cryptography) uses two separate keys: one key to encrypt and a different key to decrypt information. These keys are known as public and private key pairs. When two parties want to exchange an encrypted message by using asymmetric key cryptography, they follow the steps in Lab 8-3:

Lab 8-3 Exchanging an Encrypted Message with Asymmetric Key Cryptography

1. The sender (Thomas) encrypts the plaintext message with the intended recipient’s (Richard) public key.

2. This produces a ciphertext message that can then be transmitted to the intended recipient (Richard).

3. The recipient (Richard) then decrypts the message with his private key, known only to him.

Only the private key can decrypt the message; thus, an attacker (Harold) possessing only the public key can’t decrypt the message. This also means that not even the original sender can decrypt the message. This use of an asymmetric key system is known as a secure message. A secure message guarantees the confidentiality of the message.

Asymmetric key systems use a public key and a private key.

Secure message format uses the recipient’s private key to protect confidentiality.

If the sender wants to guarantee the authenticity of a message (or, more correctly, the authenticity of the sender), he or she can sign the message by using the procedure described in Lab 8-4:

Lab 8-4 Signing a Message to Guarantee Authenticity

1. The sender (Thomas) encrypts the plaintext message with his own private key.

2. This produces a ciphertext message that can then be transmitted to the intended recipient (Richard).

3. To verify that the message is in fact from the purported sender, the recipient (Richard) applies the sender’s (Thomas’s) public key (which is known to every Tom, Dick, and Harry).

Of course, an attacker can also verify the authenticity of the message. This use of an asymmetric key system is known as an open message format because it guarantees only the authenticity, not the confidentiality.

Open message format uses the sender’s private key to ensure authenticity.

If the sender wants to guarantee both the confidentiality and authenticity of a message, he or she can do so by using the procedure in Lab 8-5:

Lab 8-5 Guaranteeing Confidentiality and Authenticity of a Message

1. The sender (Thomas) encrypts the message first with the intended recipient’s (Richard’s) public key and then with his own private key.

2. This produces a ciphertext message that can then be transmitted to the intended recipient (Richard).

3. The recipient (Richard) uses the sender’s (Thomas’s) public key to verify the authenticity of the message, and then uses his own private key to decrypt the message’s contents.

If an attacker intercepts the message, he or she can apply the sender’s public key, but then has an encrypted message that he or she can’t decrypt without the intended recipient’s private key. Thus, both confidentiality and authenticity are assured. This use of an asymmetric key system is known as a secure and signed message format.

A secure and signed message format uses the sender’s private key and the recipient’s public key to protect confidentiality and ensure authenticity.

A public key and a private key are mathematically related, but theoretically, no one can compute or derive the private key from the public key. This property of asymmetric systems is based on the concept of a one-way function. A one-way function is a problem that you can easily compute in one direction but not in the reverse direction. In asymmetric key systems, a trapdoor (private key) resolves the reverse operation of the one-way function.

Because of the complexity of asymmetric key systems, they are more commonly used for key management or digital signatures than for encryption of bulk information. Often, a hybrid system is employed, using an asymmetric system to securely distribute the secret keys of a symmetric key system that’s used to encrypt the data.

The main disadvantage of asymmetric systems is their lower speed. Because of the types of algorithms that are used to achieve the one-way hash functions, very large keys are required. (A 128-bit symmetric key has the equivalent strength of a 2,304-bit asymmetric key.) Those large keys, in turn, require more computational power, causing a significant loss of speed (up to 10,000 times slower than a comparable symmetric key system).

However, the many significant advantages of asymmetric systems include

Extended functionality: Asymmetric key systems can provide both confidentiality and authentication; symmetric systems can provide only confidentiality.

Scalability: Because symmetric key systems require secret key exchanges between all of the communicating parties, their scalability is limited. Asymmetric key systems, which do not require secret key exchanges, resolve key management issues associated with symmetric key systems, and are therefore more scalable.

Asymmetric key algorithms include RSA, Diffie-Hellman, El Gamal, Merkle-Hellman (Trapdoor) Knapsack, and Elliptic Curve, which we talk about in the following sections.

RSA

In 1978, Drs. Ron Rivest, Adi Shamir, and Len Adleman published the RSA algorithm, which is a key transport algorithm based on the difficulty of factoring a number that’s the product of two large prime numbers (typically 512 bits). Two users (Thomas and Richard) can securely transport symmetric keys by using RSA as described in Lab 8-6:

Lab 8-6 Securely Transporting Symmetric Keys with RSA

1. Thomas creates a symmetric key, encrypts it with Richard’s public key, and then transmits it to Richard.

2. Richard decrypts the symmetric key by using his own private key.

RSA is an asymmetric key algorithm based on factoring prime numbers.

Diffie-Hellman Key Exchange

In 1976, Drs. Whitfield Diffie and Martin Hellman published a paper, entitled “New Directions in Cryptography,” that detailed a new paradigm for secure key exchange based on discrete logarithms. Diffie-Hellman is described as a key agreement algorithm. Two users (Thomas and Richard) can exchange symmetric keys by using Diffie-Hellman as described in Lab 8-7:

Lab 8-7 Exchanging Symmetric Keys with Diffie-Hellman

1. Thomas and Richard obtain each other’s public keys.

2. Thomas and Richard then combine their own private keys with the public key of the other person, producing a symmetric key that only the two users involved in the exchange know.

Diffie-Hellman key exchange is vulnerable to Man-in-the-Middle Attacks, in which an attacker (Harold) intercepts the public keys during the initial exchange and substitutes his own private key to create a session key that can decrypt the session. (You can read more about these attacks in the section “Man-in-the-Middle Attack,” later in this chapter.) A separate authentication mechanism is necessary to protect against this type of attack, ensuring that the two parties communicating in the session are, in fact, the legitimate parties.

Diffie-Hellman is an asymmetric key algorithm based on discrete logarithms.

El Gamal

El Gamal is an unpatented, asymmetric key algorithm based on the discrete logarithm problem used in Diffie-Hellman (discussed in the preceding section). El Gamal extends the functionality of Diffie-Hellman to include encryption and digital signatures.

Merkle-Hellman (Trapdoor) Knapsack

The Merkle-Hellman (Trapdoor) Knapsack, published in 1978, employs a unique approach to asymmetric cryptography. It’s based on the problem of determining what items, in a set of items that have fixed weights, can be combined in order to obtain a given total weight. Knapsack was broken in 1982.

Knapsack is an asymmetric key algorithm based on fixed weights.

Elliptic Curve (EC)

In 1985, Neal Koblitz and Victor Miller proposed a new model for asymmetric algorithms based on elliptic curves (EC). Elliptic curves are far more difficult to compute than conventional discrete logarithm problems or factoring prime numbers. (A 160-bit EC key is equivalent to a 1,024-bit RSA key.) The use of smaller keys means that EC is significantly faster than other asymmetric algorithms (and many symmetric algorithms), and can be widely implemented in various hardware applications including wireless devices and smart cards.

Elliptic Curve is more efficient than other asymmetric key systems and many symmetric key systems because it can use a smaller key.