 The Purpose of Cryptography
 SecretKey Cryptography
 PublicKey Cryptography
10.2 SecretKey Cryptography
In secretkey 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. SecretKey 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 26letter 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 twodimensional 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 bitlevel 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 fixedkey 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 fixedlength 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 FixedLength 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 FixedLength Key by XORing a Plaintext Block with Its Corresponding Ciphertext Block
Figure 10.9. CiphertextBlock XOR and PlaintextBlock 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 onetime 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 onetime 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 onetime 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 secretkey blockcipher 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 secretkey blockcipher 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:

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

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 strongestpossible 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 secretkey 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 64bit input plaintext block is transformed into a corresponding 64bit ciphertext output. DES uses a 56bit key expressed as a 64bit 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 bruteforce attack on several occasions, demonstrating its vulnerability to exhaustive searching of the key space.
TripleDES
TripleDES is the DES algorithm applied three times, using either two or three keys.

With two keys, TripleDES 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_{1} and k_{2} are the two TripleDES 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 threekey TripleDES, stronger than the twokey TripleDES, uses a separate key for each of the three steps described. With the notation that we have introduced, if k_{1}, k_{2}, and k_{3} 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 TripleDES, the second key is used for decryption rather than for encryption to allow TripleDES to be compatible with DES. A system using TripleDES can still initiate a communication with a system using DES by using only one key k. Formally, by choosing k_{1} = k_{2} =k_{3} = 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 TripleDES 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 64bit input blocks and for each, outputs a corresponding 64bit 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 128bit secret key and dominantly uses operations from three algebraic groups; XOR, addition modulo 2^{16}, and multiplication modulo 2^{16} + 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 wholebyte operations on single and 4byte words and requires a relatively small amount of memory for its implementation. It is suitable for implementations on a wide range of processors, including 8bit hardware, and power and spacerestricted 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.

The original message m is divided into n blocks m_{1}, m_{2}, ..., m_{n}.

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 blockcipher algorithm typically used for encryption is DES.

The ciphertext blocks c_{1}, c_{2}, ..., 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).

The original message m is divided into n blocks m_{1}, m_{2}, ..., m_{n}.

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.

The first ciphertext block, c_{1}, is obtained by XORing v with m_{1} and encrypting the result of the XOR operation with the secret key k. In other words,

c_{1} = E_{k}(v ⊕ m_{1})
where E_{k} is the encrypting function associated with the key k.


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}_{)}


The ciphertext blocks c_{1}, c_{2}, ..., 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 SecretKey Security Attributes
This section examines the security implications of using secretkey cryptography.
10.2.2.1 Key Space
The strength of modern secretkey 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 bruteforce 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 secretkey 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 secretkey cryptographic systems use unique, randomly generated, fixedsize 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 bruteforce search attacks.
10.2.2.2 Confidentiality
Using a secretkey 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 keysearch 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
Secretkey 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 secretkey 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 DataOrigin Authentication
At a much lesser cost than encrypting the entirety of a plaintext, data integrity and dataorigin 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. DataIntegrity 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^{n} 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 (SHA1) are the most widely used cryptographic hash functions. MD5 yields a 128bit (16byte) hash value, whereas SHA1 results in a 160bit (20byte) digest. SHA1 appears to be a cryptographically stronger function. On the other hand, MD5 edges SHA1 in computational performance and thus has become the de facto standard.
Hash functions alone cannot guarantee data integrity, because they fail in guaranteeing dataorigin 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. DataIntegrity Verification in the Presence of an Adversary
Dataorigin authentication is inherently supported by secretkey 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 secretkey cryptography alone. Various secretkeybased authentication protocols have been developed to address this limitation. Publickey 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 secretkey 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 dataorigin authentication.
Another simple solution to achieve data integrity and dataorigin authentication is to apply a regular hash function h, such as SHA1 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 secretkey blockcipher 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 TripleDES, resulting in DESMAC and TripleDESMAC, respectively. A MAC mechanism that uses a cryptographic hash function is also referred to as HMAC. HMAC is specified in RFC 2104.^{1}