The Theory of Cryptography

This chapter is from the book 

10.2 Secret-Key Cryptography

In secret-key cryptography, a sequence of bits, called the secret key, is used as an input to a mathematical function to encrypt a plaintext message; the same key is also used to decrypt the resulting ciphertext message and obtain the original plaintext (see Figure 10.3). As the same key is used to both encrypt and decrypt data, a secret key is also called a symmetric key.

Figure 10.3. Secret-Key Encryption and Decryption

10.2.1 Algorithms and Techniques

In this section, we examine the most common cryptographic algorithms that are based on the use of a secret key.

10.2.1.1 Substitutions and Transpositions

Some very early cryptographic algorithms manipulated the original plaintext, character by character, using the techniques of substitution and transposition.

• A substitution, or permutation, replaces a character of the input stream by a character from the alphabet set of the target ciphertext.

• A transposition replaces a character from the original plaintext by another character of that same plaintext. This results in shuffling yet still preserving the characters of the original plaintext.

An example of a substitution is the famous Caesar Cipher, which is said to have been used by Julius Caesar to communicate with his army. The Caesar Cipher replaces each character of the input text by the third character to its right in the alphabet set. In Figure 10.4, the value 3 is added to the position of the input character; then modulo 26 is taken to yield the replacement character. If we assign numerical equivalents of 0–25 to the 26-letter alphabet A–Z, the transformation sends each plain character with position P onto the character with position f(P) := P + 3 (mod 26).

Figure 10.4. The Caesar Cipher

A transposition cipher consists of breaking the original plaintext into separate blocks first. A deterministic procedure is then applied to shuffle characters across different blocks. For example, a transposition can split the secret message "PHONE HOME" into the two separate blocks "PHONE" and " HOME". Then, characters are cyclically shuffled across the two blocks to result in the ciphertext of "POMHE HOEN". Another example of a simple transposition cipher consists of writing the plaintext along a two-dimensional matrix of fixed rows and columns and then simply transposing the matrix, as shown in Figure 10.5.

Figure 10.5. Transposition Matrix

Generally, transposition ciphers are easy to break. However, composing them by setting the result of one transposition as the input of another one greatly enhances the ciphering against attacks.

With the age of computers, early modern cryptography carried on these same concepts, using the various elementary transformations that we have listed. The primary difference is that these transformations now apply at the bit level of the binary representation of data instead of characters only.

10.2.1.2 The XOR Operation

A common transformation is the exclusive OR (XOR) operation, denoted by the symbols XOR, or ⊕. XOR is a bitwise function that maps an element of {0, 1} × {0, 1} onto the set {0, 1}, as shown in Figure 10.6. If we interpret the second operand as a key value, the XOR operation can be thought of as a bit-level substitution based on the bit values of the key. With such an assumption, XOR sends a 0 or 1 to itself when the corresponding key bit is 0 and inverts a 0 into a 1 and a 1 into a 0 when the corresponding key bit is 1.

Figure 10.6. The XOR Operation Table

The last property implies that when using a fixed-key value, the XOR operation can be applied to encipher a plaintext, which can then be recovered by simply applying the XOR operation to the ciphertext with the same key value. This property has led to the proliferation of many variants of weak encryption methods that rely solely on the simple XOR operation and thus are easily breakable.

Figure 10.7 shows how to XOR blocks of some plaintext P with a fixed-length key K, leading to ciphertext P′. The figure also shows that if P′ is then XORed with K, the original plaintext P is produced.

Figure 10.7. XORing Plaintext Blocks with a Fixed-Length Key

Knowing a block of plaintext and its XOR transformation directly leads to K, by way of XORing the plaintext with the corresponding ciphertext, as shown in Figure 10.8. Similarly, by knowing two ciphertext blocks P′ and Q′ alone, one can XOR them together to yield the XOR of the corresponding plaintext blocks P and Q, as in Figure 10.9.

Figure 10.8. How to Get the Fixed-Length Key by XORing a Plaintext Block with Its Corresponding Ciphertext Block

Figure 10.9. Ciphertext-Block XOR and Plaintext-Block XOR Equality

Therefore, examining the bit patterns of P ⊕ Q can easily result in recovering one of the plaintexts by knowing some information about the other. The plaintext can then be XORed with its ciphertext to yield the keystream, where the keystream is the key used to encipher the plaintexts.

Despite the simplicity of the XOR operation and the weakness of encryption algorithms that use it with fixed keys, there is a way to make the sole use of such basic operation result in a perfect encryption scheme. A one-time pad is a key of randomly generated digits that is used only once. Use of such a key yields a perfect cipher. Such a cipher is provably secure against attacks in which a code breaker has knowledge of a set of ciphertexts.

The security of the one-time pad stems from the fact that the uncertainty in attempting to guess the keystream is equal to that of directly guessing the plaintext. Note, however, that the length of the keystream for the one-time pad is equal to that of the plaintext being encrypted. Such a property makes it difficult to maintain and distribute keys, which could be very long. This difficulty has led to the development of stream ciphers whereby the key is pseudorandomly generated from a fixed secret key.

10.2.1.3 Stream Ciphers

Stream ciphers are geared for use when memory buffering is limited or when characters are individually transformed as they become available for transmission. Because stream ciphers generally transform plaintext bits independently from one another, error propagation remains limited in the event of a transmission error. For example, the XOR operation lends itself to be used as a stream cipher.

10.2.1.4 Block Ciphers

Block ciphers divide a plaintext into identically sized blocks. Generally, the blocks are of length greater than or equal to 64 bits. The same transformations are applied to each block to perform the encryption.

All the widely known secret-key block-cipher algorithms exhibit the cryptographic properties desired in a block cipher. Foremost of these is the fact that each bit of the ciphertext should depend on all key bits. Changing any key bit should result in a 50 percent chance of changing any resulting ciphertext bit. Furthermore, no statistical relationships should be inferrable between a plaintext and its corresponding ciphertext. In the reminder of this section, we present the most common secret-key block-cipher algorithms.

Feistel Ciphers

A Feistel cipher uses a noninvertible function f, obtained as a sequence of substitutions and transpositions. A Feistel cipher consists of the following basic steps:

1. A plaintext message m is divided into two separate blocks of equal size: the left block, L, and the right block, R.

2. The original message, m, is transformed into an intermediate message, m′ in which the left block, L′, is the same as R, and the right block, R′, is L ⊕ f(R), where the symbol ⊕, as usual, denotes the XOR operation.

These two steps are shown in Figure 10.10. Even though f is a noninvertible function, this design permits recovering m from m′ by concatenating R′ ⊕ f(L′) = R′ ⊕ f(R) = L with L′ = R.

Figure 10.10. Basic Steps of a Feistel Cipher Algorithm

Steps 1 and 2 must be iteratively repeated a number of times for a Feistel cipher to be secure. The number of iterations depends on the strength of the function f. It is possible to prove that, even with the strongest-possible function f, the iterations must be at least three in order for the Feistel cipher to be reliable.

DES

One of the most widely recognized secret-key block ciphers is the Data Encryption Standard (DES) algorithm. DES was developed by IBM cryptographers in the early 1970s and was adopted as a U.S. government standard in 1976. DES is intended for the protection of sensitive but unclassified electronic information. Because it uses the same key for both encryption and decryption, the algorithm is referred to as a symmetric cipher.

DES is a block cipher in which a 64-bit input plaintext block is transformed into a corresponding 64-bit ciphertext output. DES uses a 56-bit key expressed as a 64-bit quantity in which the least relevant bit in each of the 8 bytes is used for parity checking. DES is a Feistel algorithm that iterates over the data 16 times, using a combination of permutation and substitution transformations along with standard arithmetic and logical operations, such as XOR, based on the key value.

For many years, the DES algorithm withstood attacks. Recently, as the result of increased speed of computing systems, DES has succumbed to brute-force attack on several occasions, demonstrating its vulnerability to exhaustive searching of the key space.

Triple-DES

Triple-DES is the DES algorithm applied three times, using either two or three keys.

• With two keys, Triple-DES proceeds by using the first key to encrypt a block of data. The second key is then used to decrypt the result of the previous encryption. Finally, the first key is once more used to encrypt the result from the second step. Formally, let us indicate the encrypting and decrypting functions based on a given key k with E_k and D_k, respectively. If k₁ and k₂ are the two Triple-DES keys and if m is the message to be encrypted, the encrypted message m′ is obtained as

  

  To decrypt m′ and obtain the original plaintext m, it is necessary to compute

  

• The three-key Triple-DES, stronger than the two-key Triple-DES, uses a separate key for each of the three steps described. With the notation that we have introduced, if k₁, k₂, and k₃ are three distinct keys, a plaintext message m is encrypted into its corresponding ciphertext message m′ by

  

  To decrypt m′ and obtain the original plaintext m, it is then necessary to compute

  

In Triple-DES, the second key is used for decryption rather than for encryption to allow Triple-DES to be compatible with DES. A system using Triple-DES can still initiate a communication with a system using DES by using only one key k. Formally, by choosing k₁ = k₂ =k₃ = k, the ciphertext m′ corresponding to a plaintext message m is obtained from

• E_k(D_k(E_k(m))) = E_k(m)

By contrast, m is obtained from m′ by computing

• D_k(E_k(D_k(m'))) = D_k(m')

This shows that Triple-DES with only one key reduces itself to DES.

IDEA

Although less visible than DES, the International Data Encryption Algorithm (IDEA) has been classified by some contemporary cryptographers as the most secure and reliable block algorithm. Like DES, IDEA encrypts plaintext data organized in 64-bit input blocks and for each, outputs a corresponding 64-bit ciphertext block. IDEA uses the same algorithm for encryption and decryption, with a change in the key schedule during encryption. Unlike DES, IDEA uses a 128-bit secret key and dominantly uses operations from three algebraic groups; XOR, addition modulo 2¹⁶, and multiplication modulo 2¹⁶ + 1. These operations are combined to make eight computationally identical rounds, followed by an output transformation resulting in the final ciphertext.

Rijndael

Recently chosen as the Advanced Encryption Standard (AES), a replacement of DES by the U.S. government, Rijndael is an iterated block cipher with a variable block length and a variable key length, both of which can independently be 128, 192, or 256 bits. The strong points of Rijndael are its simple and elegant design and its being efficient and fast on modern processors. Rijndael uses only simple whole-byte operations on single- and 4-byte words and requires a relatively small amount of memory for its implementation. It is suitable for implementations on a wide range of processors, including 8-bit hardware, and power- and space-restricted hardware, such as smart cards. It lends itself well to parallel processing and pipelined multiarithmetic logic unit processors.

A major feature of the Rijndael algorithm is that it presents a departure from the traditional Feistel ciphers. In such ciphers, some of the bits in the intermediate states of a cipher are transposed unchanged. The Rijndael algorithm does not adopt the Feistel structure. Instead, each round of transformations is composed of three distinct invertible subtransformations that treat each bit of the intermediate state of the cipher in a uniform and similar way.

10.2.1.5 Modes of Operation

Modes of operation are cryptographic techniques using block ciphers to encrypt messages that are longer than the size of the block. The most common modes of operation are electronic codebook (ECB) and cipher block chaining (CBC).

ECB

With the ECB mode of operation, a message is divided into blocks of equal size. Each block is then encrypted using a secret key. Figure 10.11 shows how ECB works, assuming the following.

1. The original message m is divided into n blocks m₁, m₂, ..., m_n.

2. For all i = 1, 2, ...n, the plaintext block m_i is encrypted into a ciphertext block c_i with a secret key k. The encryption function associated with k is indicated with E_k. In ECB mode, the block-cipher algorithm typically used for encryption is DES.

3. The ciphertext blocks c₁, c₂, ..., c_n are concatenated to form the ciphertext c corresponding to the message m.

Figure 10.11. ECB Mode

ECB presents some limitations because each ciphertext block depends on one plaintext block only, not on the entire message.

CBC

Given a secret key k, the CBC mode of operation works as follows (see Figure 10.12).

1. The original message m is divided into n blocks m₁, m₂, ..., m_n.

2. A randomly chosen block of data is selected as the initial vector v. This initial vector must be known to the receiver as well. Therefore, a possibility is for both the sender and the receiver to be able to generate v independently as a function of the key k.

3. The first ciphertext block, c₁, is obtained by XORing v with m₁ and encrypting the result of the XOR operation with the secret key k. In other words,

   • c₁ = E_k(v ⊕ m₁)

   where E_k is the encrypting function associated with the key k.

4. For all i = 2, ..., n, the ciphertext block c_i is obtained by XORing the plaintext block m_i with the ciphertext block c_i-1 and encrypting the result of the XOR operation with the secret key k. In other words,

   • c_i = E_k(c_i-1 ⊕ m_i)

5. The ciphertext blocks c₁, c₂, ..., c_n are concatenated to form the ciphertext c of the message m.

Figure 10.12. CBC Mode

One of the key characteristics of CBC is that it uses a chaining mechanism that causes the decryption of a block of ciphertext to depend on all the preceding ciphertext blocks.

10.2.2 Secret-Key Security Attributes

This section examines the security implications of using secret-key cryptography.

10.2.2.1 Key Space

The strength of modern secret-key encryption methods no longer rests in the secrecy of the algorithm being used but rather in the secrecy of the encryption key. Breaking such cryptographic systems, therefore, can be achieved using a brute-force attack, the process of exhaustive searches over the key space. The latter is the set of all possible key values that a particular enciphering method can take.

For example, a generalization of the Caesar Cipher is an arbitrary permutation over the English alphabet. This results in 26! (factorial) possible keys corresponding to each of the permutations. Further constraining the permutation method to one that simply maps each letter in the alphabet to one at a fixed number of positions to its right (with a wraparound) and by enciphering each letter at a time (block length = 1), the key space narrows down to the much smaller set of the first 26 integers, {1, 2, … , 26}. It should be noted, however, that the level of a secret-key encryption algorithm's security is not necessarily proportional to the size of the key space. For example, even though 26! is a very large number, it is possible to break the generalization of the Caesar Cipher by means of statistical analysis.

Most common secret-key cryptographic systems use unique, randomly generated, fixed-size keys. These systems can certainly be exposed to the exhaustive search of the key space. A necessary, although not sufficient, condition for any such cryptographic systems to be secure is that the key space be large enough to preclude exhaustive search attacks using computing power available today and for the foreseeable future. As ironic as it may sound, efficiency of enciphering methods will aid in the exhaustive brute-force search attacks.

10.2.2.2 Confidentiality

Using a secret-key algorithm to encipher the plaintext form of some data content allows only entities with the correct secret key to decrypt and hence retrieve the original form of the disguised data. Reliability of the confidentiality service in this case depends on the strength of the encryption algorithm and, perhaps more important, the length of the key used. The long lifetime of a secret key also might help diminish assurance in such a confidentiality service. Increasing the frequency with which a key is used increases the likelihood that an exhaustive key-search attack will succeed. Most modern systems make use of secret keys that remain valid for only the lifetime of a particular communication session.

10.2.2.3 Nonrepudiation

Secret-key cryptography alone is not sufficient to prevent the denial of an action that has taken place, such as the initiation of an electronic transaction. Although one can apply data privacy in such a scenario, the fundamental flaw of a nonrepudiation scheme based on secret-key cryptography alone is inherent in the fact that the secret key is dispensed to more than one party.

10.2.2.4 Data Integrity and Data-Origin Authentication

At a much lesser cost than encrypting the entirety of a plaintext, data integrity and data-origin authentication can be afforded by a secret cryptographic scheme using a message authentication code (MAC) function. The basic idea is to attach to each message m that is sent across a network the result h(m) of a mathematical function h applied to the message m itself. If an error has occurred during the message transmission, such that the received message a is different from the message m that was originally sent, the message receiver will be able to detect the anomaly by independently computing h(a) and comparing it to h(m) (see Figure 10.13).

Figure 10.13. Data-Integrity Verification: Basic Scenario

The main component of a MAC function is a hash digest function (see Figure 10.14). Hash digest functions are considered one of the fundamental primitives in modern cryptography. By definition, a hash digest function is a deterministic function that maps a message of arbitrary length to a string of fixed length n. Typically, n is 128 or 160 bits. The result is commonly known as a message digest. As the original data is often longer than its hash value, this result is sometimes also referred to as the original message's fingerprint.

Figure 10.14. Producing a Message Digest with a Hash Function

Of course, a hash digest function is inherently noninjective. This simply means that multiple messages will be mapping to the same digest. In fact, the universe of the messages that can be digested is potentially unlimited, whereas the universe of all the message digests is limited by the set of the 2ⁿ strings with n bits. However, the fundamental premise is that, depending on the strength of the hashing algorithm, the hash value becomes a more compact representation of the original data. This means that, although virtually possible, it should be computationally infeasible to produce two messages having the same message digest or to produce any message having a given, prespecified target message digest.

Message Digest V5 (MD5) and Secure Hash Algorithm V1 (SHA-1) are the most widely used cryptographic hash functions. MD5 yields a 128-bit (16-byte) hash value, whereas SHA-1 results in a 160-bit (20-byte) digest. SHA-1 appears to be a cryptographically stronger function. On the other hand, MD5 edges SHA-1 in computational performance and thus has become the de facto standard.

Hash functions alone cannot guarantee data integrity, because they fail in guaranteeing data-origin authentication, defined as the ability to authenticate the originator of a message (see Figure 10.15). The problem with digest functions is that they are publicly available. If a message m is intercepted by an adversary after being transmitted by Alice, the adversary can change m into a different message, m′, compute h(m′), and send Bob the pair (m′μ h(m′)). By simply applying the function h to the received message m′, Bob has no means of detecting that an adversary has replaced m with m′.

Figure 10.15. Data-Integrity Verification in the Presence of an Adversary

Data-origin authentication is inherently supported by secret-key cryptography, provided that the key is shared by two entities only. When three or more parties share the same key, however, origin authenticity can no longer be provided by secret-key cryptography alone. Various secret-key-based authentication protocols have been developed to address this limitation. Public-key cryptography, described in Section 10.3 on page 359, provides a simpler and more elegant solution to this problem.

In contrast to using a pure and simple hash function to digest a message, a MAC function combines a hash digest fuction with secret-key encryption and yields a value that can be verified only by an entity having knowledge of the secret key. This way, a MAC function takes care of the problem described in Figure 10.15 and enables both data integrity and data-origin authentication.

Another simple solution to achieve data integrity and data-origin authentication is to apply a regular hash function h, such as SHA-1 or MD5, but rather than hashing the message m alone, the message is first concatenated with the key k, and then the result of the concatenation is hashed. In other words, the sender attaches to the message m the tag h(k, m). This solution, however, exposes some theoretical weaknesses. A more reliable solution consists of attaching the tag h(k, h(k, m)).

A MAC can even be computed by using solely a secret-key block-cipher algorithm. For example, the last ciphertext block, encrypted in CBC mode, yields the final MAC value. This is a good choice for a MAC because one of the key characteristics of CBC is that it uses a chaining mechanism that causes the decryption of a block of ciphertext to depend on all the preceding ciphertext blocks. Therefore, the MAC so defined is a compact representation of the entire message that can be computed only by an entity having knowledge of the secret key. Known instances of this procedure use DES and Triple-DES, resulting in DES-MAC and Triple-DES-MAC, respectively. A MAC mechanism that uses a cryptographic hash function is also referred to as HMAC. HMAC is specified in RFC 2104.¹