Sage Tool

Ch07Crypto7e.pptx

Home >Computer Science homework help >Sage Tool

Cryptography and Network Security

Seventh Edition

by William Stallings

Lecture slides prepared for “Cryptography and Network Security”, 7/e, by William Stallings, Chapter 7 – “Block Cipher Operation”.

Chapter 7

Block Cipher Operation

This chapter continues our discussion of symmetric ciphers. We begin with the topic of

multiple encryption, looking in particular at the most widely used multiple-encryption

scheme: triple DES.

The chapter next turns to the subject of block cipher modes of operation. We

find that there are a number of different ways to apply a block cipher to plaintext, each

with its own advantages and particular applications.

Because of its vulnerability to brute-force attack, DES, once the most widely used

symmetric cipher, has been largely replaced by stronger encryption schemes. Two

approaches have been taken. One approach is to design a completely new algorithm

that is resistant to both cryptanalytic and brute-force attacks, of which AES

is a prime example. Another alternative, which preserves the existing investment in

software and equipment, is to use multiple encryption with DES and multiple keys.

We begin by examining the simplest example of this second alternative. We then

look at the widely accepted triple DES (3DES) algorithm.

The simplest form of multiple encryption has two encryption stages and two keys

(Figure 7.1a).

Given a plaintext P and two encryption keys K1 and K2 , ciphertext C

is generated as

C = E(K2 , E(K1 , P ))

Decryption requires that the keys be applied in reverse order:

P = D(K1 , D(K2 , C ))

For DES, this scheme apparently involves a key length of 56 * 2 = 112 bits, resulting

in a dramatic increase in cryptographic strength. But we need to examine the

algorithm more closely.

it is reasonable to assume that if DES is used twice with different keys, it

will produce one of the many mappings that are not defined by a single application

of DES. Although there was much supporting evidence for this assumption, it was

not until 1992 that the assumption was proven [CAMP92].

Meet-in-the-Middle Attack

Thus, the use of double DES results in a mapping

that is not equivalent to a single DES encryption. But there is a way to attack this

scheme, one that does not depend on any particular property of DES but that will

work against any block encryption cipher.

The algorithm, known as a meet-in-the-middle attack , was first described in

[DIFF77].

The use of double DES results in a mapping that is not equivalent to a single DES encryption

The meet-in-the-middle attack algorithm will attack this scheme and does not depend on any particular property of DES but will work against any block encryption cipher

Triple-DES with Two-Keys

Obvious counter to the meet-in-the-middle attack is to use three stages of encryption with three different keys

This raises the cost of the meet-in-the-middle attack to 2112, which is beyond what is practical

Has the drawback of requiring a key length of 56 x 3 = 168 bits, which may be somewhat unwieldy

As an alternative Tuchman proposed a triple encryption method that uses only two keys

3DES with two keys is a relatively popular alternative to DES and has been adopted for use in the key management standards ANSI X9.17 and ISO 8732

An obvious counter to the meet-in-the-middle attack is to use three stages of encryption

with three different keys. This raises the cost of the meet-in-the-middle attack

to 2112 , which is beyond what is practical now and far into the future. However, it

has the drawback of requiring a key length of 56 * 3 = 168 bits, which may be

somewhat unwieldy.

As an alternative, Tuchman proposed a triple encryption method that uses

only two keys [TUCH79].

3DES with two keys is a relatively popular alternative to DES and has been

adopted for use in the key management standards ANSI X9.17 and ISO 8732.1

The first serious proposal came from Merkle and Hellman [MERK81]. Their

plan involves finding plaintext values that produce a first intermediate value of

A = 0 (Figure 7.1b) and then using the meet-in-the-middle attack to determine

the two keys. The level of effort is 256 , but the technique requires 256 chosen plaintext–

ciphertext pairs, which is a number unlikely to be provided by the holder of

the keys.

A known-plaintext attack is outlined in [VANO90]. This method is an improvement

over the chosen-plaintext approach but requires more effort. The attack

is based on the observation that if we know A and C (Figure 7.1b), then the problem

reduces to that of an attack on double DES. Of course, the attacker does not know

A , even if P and C are known, as long as the two keys are unknown. However, the

attacker can choose a potential value of A and then try to find a known (P , C ) pair

that produces A .

The attack proceeds as follows.

1. Obtain n (P , C ) pairs. This is the known plaintext. Place these in a table

(Table 1) sorted on the values of P (Figure7.2b).

2. Pick an arbitrary value a for A, and create a second table (Figure 6.2c) with entries

defined in the following fashion. For each of the 256 possible keys K1 = i,

calculate the plaintext value Pi that produces a:

Pi = D(i, a)

For each Pi that matches an entry in Table 1, create an entry in Table 2 consisting

of the K1 value and the value of B that is produced for the (P, C) pair from

Table 1, assuming that value of K1:

B = D(i, C)

At the end of this step, sort Table 2 on the values of B.

3. We now have a number of candidate values of K1 in Table 2 and are in a position

to search for a value of K2. For each of the 256 possible keys K2 = j, calculate

the second intermediate value for our chosen value of a:

Bj = D(j, a)

At each step, look up Bj in Table 2. If there is a match, then the corresponding

key i from Table 2 plus this value of j are candidate values for the unknown

keys (K1, K2). Why? Because we have found a pair of keys (i, j) that produce a

known (P, C) pair (Figure 7.2a).

4. Test each candidate pair of keys (i, j) on a few other plaintext–ciphertext

pairs. If a pair of keys produces the desired ciphertext, the task is complete. If

no pair succeeds, repeat from step 1 with a new value of a.

For a given known (P , C ), the probability of selecting the unique value of a

that leads to success is 1/264 . Thus, given n (P , C ) pairs, the probability of success for

a single selected value of a is n /264 .

Triple DES with Three Keys

Many researchers now feel that three-key 3DES is the preferred alternative

A number of Internet-based applications have adopted three-key 3DES including PGP and S/MIME

Although the attacks just described appear impractical, anyone using two-key 3DES

may feel some concern. Thus, many researchers now feel that three-key 3DES is

the preferred alternative (e.g., [KALI96a]). Three-key 3DES has an effective key

length of 168 bits and is defined as

C = E( K3, D( K2, E( K1, P)))

Backward compatibility with DES is provided by putting

K3 = K2 or K1 = K2

A number of Internet-based applications have adopted three-key 3DES, including

PGP and S/MIME, both discussed in Chapter 19.

Three-key 3DES has an effective key length of 168 bits and is defined as:

C = E( K3, D( K2, E( K1, P)))

Backward compatibility with DES is provided by putting:

K3 = K2 or K1 = K2

Modes of Operation

A technique for enhancing the effect of a cryptographic algorithm or adapting the algorithm for an application

To apply a block cipher in a variety of applications, five modes of operation have been defined by NIST

The five modes are intended to cover a wide variety of applications of encryption for which a block cipher could be used

These modes are intended for use with any symmetric block cipher, including triple DES and AES

A block cipher takes a fixed-length block of text of length b bits and a key as input

and produces a b -bit block of ciphertext. If the amount of plaintext to be encrypted

is greater than b bits, then the block cipher can still be used by breaking the plaintext

up into b -bit blocks. When multiple blocks of plaintext are encrypted using the

same key, a number of security issues arise. To apply a block cipher in a variety of

applications, five modes of operation have been defined by NIST (SP 800-38A).

In essence, a mode of operation is a technique for enhancing the effect of a cryptographic

algorithm or adapting the algorithm for an application, such as applying

a block cipher to a sequence of data blocks or a data stream. The five modes are

intended to cover a wide variety of applications of encryption for which a block

cipher could be used. These modes are intended for use with any symmetric block

cipher, including triple DES and AES.

The modes are summarized in Table 7.1 and described in this and the following sections.

The simplest mode is the electronic codebook (ECB ) mode, in which plaintext

is handled one block at a time and each block of plaintext is encrypted using the

same key (Figure 7.3). The term codebook is used because, for a given key, there is

a unique ciphertext for every b -bit block of plaintext. Therefore, we can imagine a

gigantic codebook in which there is an entry for every possible b -bit plaintext pattern

showing its corresponding ciphertext.

For a message longer than b bits, the procedure is simply to break the message

into b -bit blocks, padding the last block if necessary. Decryption is performed one

block at a time, always using the same key. In Figure 7.3, the plaintext (padded as

necessary) consists of a sequence of b -bit blocks, P1 , P2 , . . . , PN ; the corresponding

sequence of ciphertext blocks is C1 , C2 , . . . , CN . We can define ECB mode as

follows.

ECB Cj = E(K, Pj) j = 1, . . . , N Pj = D(K, Cj) j = 1, . . . , N

The ECB method is ideal for a short amount of data, such as an encryption

key. Thus, if you want to transmit a DES or AES key securely, ECB is the appropriate

mode to use.

The most significant characteristic of ECB is that if the same b -bit block of

plaintext appears more than once in the message, it always produces the same

ciphertext.

For lengthy messages, the ECB mode may not be secure. If the message is

highly structured, it may be possible for a cryptanalyst to exploit these regularities.

For example, if it is known that the message always starts out with certain

predefined fields, then the cryptanalyst may have a number of known plaintext–

ciphertext pairs to work with. If the message has repetitive elements with a

period of repetition a multiple of b bits, then these elements can be identified by the

analyst. This may help in the analysis or may provide an opportunity for substituting

or rearranging blocks.

Criteria and properties for evaluating and constructing block cipher modes of operation that are superior to ECB:

Overhead

Error recovery

Error propagation

Diffusion

Security

We now turn to more complex modes of operation. [KNUD00] lists the following

criteria and properties for evaluating and constructing block cipher modes of

operation that are superior to ECB:

• Overhead: The additional operations for the encryption and decryption

operation when compared to encrypting and decrypting in the ECB mode.

• Error recovery: The property that an error in the i th ciphertext block is inherited

by only a few plaintext blocks after which the mode resynchronizes.

• Error propagation: The property that an error in the i th ciphertext block is

inherited by the i th and all subsequent plaintext blocks. What is meant here is

a bit error that occurs in the transmission of a ciphertext block, not a computational

error in the encryption of a plaintext block.

• Diffusion: How the plaintext statistics are reflected in the ciphertext. Low

entropy plaintext blocks should not be reflected in the ciphertext blocks.

Roughly, low entropy equates to predictability or lack of randomness (see

Appendix F).

• Security: Whether or not the ciphertext blocks leak information about the

plaintext blocks.

To overcome the security deficiencies of ECB, we would like a technique in which

the same plaintext block, if repeated, produces different ciphertext blocks. A

simple way to satisfy this requirement is the cipher block chaining (CBC ) mode

(Figure 7.4). In this scheme, the input to the encryption algorithm is the XOR of the

current plaintext block and the preceding ciphertext block; the same key is used for

each block. In effect, we have chained together the processing of the sequence of

plaintext blocks. The input to the encryption function for each plaintext block bears

no fixed relationship to the plaintext block. Therefore, repeating patterns of b bits

are not exposed. As with the ECB mode, the CBC mode requires that the last block

be padded to a full b bits if it is a partial block.

For decryption, each cipher block is passed through the decryption algorithm.

The result is XORed with the preceding ciphertext block to produce the plaintext

block.

To produce the first block of ciphertext, an initialization vector (IV) is XORed

with the first block of plaintext. On decryption, the IV is XORed with the output

of the decryption algorithm to recover the first block of plaintext. The IV is a data

block that is the same size as the cipher block.

The IV must be known to both the sender and receiver but be unpredictable

by a third party. In particular, for any given plaintext, it must not be possible to

predict the IV that will be associated to the plaintext in advance of the generation

of the IV. For maximum security, the IV should be protected against unauthorized

changes. This could be done by sending the IV using ECB encryption. One reason

for protecting the IV is as follows: If an opponent is able to fool the receiver into

using a different value for IV, then the opponent is able to invert selected bits in the

first block of plaintext.

So long as it is unpredictable, the specific choice of IV is unimportant.

SP800-38A recommends two possible methods: The first method is to apply the

encryption function, under the same key that is used for the encryption of the plaintext,

to a nonce . The nonce must be a data block that is unique to each execution of

the encryption operation. For example, the nonce may be a counter, a timestamp, or

a message number. The second method is to generate a random data block using a

random number generator.

In conclusion, because of the chaining mechanism of CBC, it is an appropriate

mode for encrypting messages of length greater than b bits.

In addition to its use to achieve confidentiality, the CBC mode can be used for

authentication. This use is described in Chapter 12.

Cipher Feedback Mode

For AES, DES, or any block cipher, encryption is performed on a block of b bits

In the case of DES b = 64

In the case of AES b = 128

For AES, DES, or any block cipher, encryption is performed on a block of b bits. In

the case of DES, b = 64 and in the case of AES, b = 128. However, it is possible

to convert a block cipher into a stream cipher, using one of the three modes to be

discussed in this and the next two sections: cipher feedback (CFB) mode, output

feedback (OFB) mode, and counter (CTR) mode. A stream cipher eliminates the

need to pad a message to be an integral number of blocks. It also can operate in

real time. Thus, if a character stream is being transmitted, each character can be

encrypted and transmitted immediately using a character-oriented stream cipher.

One desirable property of a stream cipher is that the ciphertext be of the same

length as the plaintext. Thus, if 8-bit characters are being transmitted, each character

should be encrypted to produce a ciphertext output of 8 bits. If more than 8 bits

are produced, transmission capacity is wasted.

There are three modes that make it possible to convert a block cipher into a stream cipher:

Cipher feedback (CFB) mode

Output feedback (OFB) mode

Counter (CTR) mode

Figure 7.5 depicts the CFB scheme. In the figure, it is assumed that the unit of

transmission is s bits; a common value is s = 8. As with CBC, the units of plaintext

are chained together, so that the ciphertext of any plaintext unit is a function of all

the preceding plaintext. In this case, rather than blocks of b bits, the plaintext is

divided into segments of s bits.

First, consider encryption. The input to the encryption function is a b -bit shift

significant) s bits of the output of the encryption function are XORed with the

first segment of plaintext P1 to produce the first unit of ciphertext C1 , which is then

transmitted. In addition, the contents of the shift register are shifted left by s bits,

and C1 is placed in the rightmost (least significant) s bits of the shift register. This

process continues until all plaintext units have been encrypted.

For decryption, the same scheme is used, except that the received ciphertext

unit is XORed with the output of the encryption function to produce the plaintext

unit. Note that it is the encryption function that is used, not the decryption function.

Although CFB can be viewed as a stream cipher, it does not conform to the

typical construction of a stream cipher. In a typical stream cipher, the cipher takes

as input some initial value and a key and generates a stream of bits, which is then

XORed with the plaintext bits (see Figure 4.1). In the case of CFB, the stream of

bits that is XORed with the plaintext also depends on the plaintext.

In CFB encryption, like CBC encryption, the input block to each forward

Cipher function (except the first) depends on the result of the previous forward

Cipher function; therefore, multiple forward cipher operations cannot be performed

in parallel. In CFB decryption, the required forward cipher operations can be performed

in parallel if the input blocks are first constructed (in series) from the IV and

the ciphertext.

The output feedback (OFB) mode is similar in structure to that of CFB. For OFB,

the output of the encryption function is fed back to become the input for encrypting

the next block of plaintext (Figure 7.6). In CFB, the output of the XOR unit is fed

back to become input for encrypting the next block. The other difference is that the

OFB mode operates on full blocks of plaintext and ciphertext, whereas CFB operates

on an s -bit subset.

As with CBC and CFB, the OFB mode requires an initialization vector. In

the case of OFB, the IV must be a nonce; that is, the IV must be unique to each

execution of the encryption operation. The reason for this is that the sequence of

encryption output blocks, Oi , depends only on the key and the IV and does not depend

on the plaintext. Therefore, for a given key and IV, the stream of output bits

used to XOR with the stream of plaintext bits is fixed. If two different messages had

an identical block of plaintext in the identical position, then an attacker would be

able to determine that portion of the Oi stream.

One advantage of the OFB method is that bit errors in transmission do not

propagate. For example, if a bit error occurs in C1 , only the recovered value of P1 is

affected; subsequent plaintext units are not corrupted. With CFB, C1 also serves as

input to the shift register and therefore causes additional corruption downstream.

The disadvantage of OFB is that it is more vulnerable to a message stream

modification attack than is CFB. Consider that complementing a bit in the ciphertext

complements the corresponding bit in the recovered plaintext. Thus, controlled

changes to the recovered plaintext can be made. This may make it possible for an

opponent, by making the necessary changes to the checksum portion of the message

as well as to the data portion, to alter the ciphertext in such a way that it is not detected

by an error-correcting code. For a further discussion, see [VOYD83].

OFB has the structure of a typical stream cipher, because the cipher generates

a stream of bits as a function of an initial value and a key, and that stream of

bits is XORed with the plaintext bits (see Figure 4.1). The generated stream that is

XORed with the plaintext is itself independent of the plaintext; this is highlighted

by dashed boxes in Figure 7.6. One distinction from the stream ciphers we discuss

in Chapter 8 is that OFB encrypts plaintext a full block at a time, where typically a

block is 64 or 128 bits. Many stream ciphers encrypt one byte at a time.

Although interest in the counter (CTR) mode has increased recently with applications

to ATM (asynchronous transfer mode) network security and IP sec (IP security),

this mode was proposed early on (e.g., [DIFF79]).

Figure 7.7 depicts the CTR mode. A counter equal to the plaintext block

size is used. The only requirement stated in SP 800-38A is that the counter value

must be different for each plaintext block that is encrypted. Typically, the counter

is initialized to some value and then incremented by 1 for each subsequent block

(modulo 2b , where b is the block size). For encryption, the counter is encrypted and

then XORed with the plaintext block to produce the ciphertext block; there is no

chaining. For decryption, the same sequence of counter values is used, with each encrypted

counter XORed with a ciphertext block to recover the corresponding plaintext

block. Thus, the initial counter value must be made available for decryption.

As with the OFB mode, the initial counter value must be a nonce; that is, T1

must be different for all of the messages encrypted using the same key. Further,

all Ti values across all messages must be unique. If, contrary to this requirement, a

counter value is used multiple times, then the confidentiality of all of the plaintext

blocks corresponding to that counter value may be compromised. In particular, if

any plaintext block that is encrypted using a given counter value is known, then

the output of the encryption function can be determined easily from the associated

ciphertext block. This output allows any other plaintext blocks that are encrypted

using the same counter value to be easily recovered from their associated ciphertext

blocks.

One way to ensure the uniqueness of counter values is to continue to increment

the counter value by 1 across messages. That is, the first counter value of the

each message is one more than the last counter value of the preceding message.

Advantages of CTR

Hardware efficiency

Software efficiency

Preprocessing

Random access

Provable security

Simplicity

[LIPM00] lists the following advantages of CTR mode.

• Hardware efficiency: Unlike the three chaining modes, encryption (or decryption)

in CTR mode can be done in parallel on multiple blocks of plaintext or

ciphertext. For the chaining modes, the algorithm must complete the computation

on one block before beginning on the next block. This limits the maximum

throughput of the algorithm to the reciprocal of the time for one execution of

block encryption or decryption. In CTR mode, the throughput is only limited

by the amount of parallelism that is achieved.

• Software efficiency: Similarly, because of the opportunities for parallel execution

in CTR mode, processors that support parallel features, such as aggressive

pipelining, multiple instruction dispatch per clock cycle, a large number of

registers, and SIMD instructions, can be effectively utilized.

• Preprocessing: The execution of the underlying encryption algorithm does

not depend on input of the plaintext or ciphertext. Therefore, if sufficient

memory is available and security is maintained, preprocessing can be used to

prepare the output of the encryption boxes that feed into the XOR functions,

as in Figure 7.7. When the plaintext or ciphertext input is presented, then

the only computation is a series of XORs. Such a strategy greatly enhances

throughput.

• Random access: The ith block of plaintext or ciphertext can be processed in

random-access fashion. With the chaining modes, block Ci cannot be computed

until the i - 1 prior block are computed. There may be applications in

which a ciphertext is stored and it is desired to decrypt just one block; for such

applications, the random access feature is attractive.

• Provable security: It can be shown that CTR is at least as secure as the other

modes discussed in this section.

• Simplicity: Unlike ECB and CBC modes, CTR mode requires only the implementation

of the encryption algorithm and not the decryption algorithm.

This matters most when the decryption algorithm differs substantially from

the encryption algorithm, as it does for AES. In addition, the decryption key

scheduling need not be implemented.

Note that, with the exception of ECB, all of the NIST-approved block

cipher modes of operation involve feedback. This is clearly seen in Figure 7.8. To

highlight the feedback mechanism, it is useful to think of the encryption function

as taking input from a input register whose length equals the encryption block

length and with output stored in an output register. The input register is updated

one block at a time by the feedback mechanism. After each update, the encryption

algorithm is executed, producing a result in the output register. Meanwhile,

a block of plaintext is accessed. Note that both OFB and CTR produce output

that is independent of both the plaintext and the ciphertext. Thus, they are natural

candidates for stream ciphers that encrypt plaintext by XOR one full block

at a time.

XTS-AES Mode for Block-Oriented Storage Devices

Approved as an additional block cipher mode of operation by NIST in 2010

Mode is also an IEEE Standard, IEEE Std 1619-2007

Standard describes a method of encryption for data stored in sector-based devices where the threat model includes possible access to stored data by the adversary

Has received widespread industry support

In 2010, NIST approved an additional block cipher mode of operation, XTS-AES.

This mode is also an IEEE standard, IEEE Std 1619-2007, which was developed

by the IEEE Security in Storage Working Group (P1619). The standard describes

a method of encryption for data stored in sector-based devices where the threat

model includes possible access to stored data by the adversary. The standard has

received widespread industry support.

Tweakable Block Ciphers

XTS-AES mode is based on the concept of a tweakable block cipher

General structure:

Has three inputs:

Tweak need not be kept secret

Purpose is to provide variability

Produces

a ciphertext output

The XTS-AES mode is based on the concept of a tweakable block cipher , introduced

in [LISK02], which functions in much the same manner as a salt used with

passwords, as described in Chapter 22. The form of this concept used in XTS-AES

was first described in [ROGA04].

Before examining XTS-AES, let us consider the general structure of a tweakable

block cipher. A tweakable block cipher is one that has three inputs: a plaintext P ,

a symmetric key K , and a tweak T ; and produces a ciphertext output C . We can

write this as C = E(K , T , P ). The tweak need not be kept secret. Whereas the purpose

of the key is to provide security, the purpose of the tweak is to provide variability.

That is, the use of different tweaks with the same plaintext and same key

produces different outputs.

plaintext

A symmetric key

tweak

The basic structure of several tweakable clock ciphers

that have been implemented is shown in Figure 7.9.

Storage Encryption Requirements

The requirements for encrypting stored data, also referred to as “data at rest”, differ somewhat from those for transmitted data

The P1619 standard was designed to have the following characteristics:

The ciphertext is freely available for an attacker

The data layout is not changed on the storage medium and in transit

Data are accessed in fixed sized blocks, independently from each other

Encryption is performed in 16-byte blocks, independently from each other

There are no other metadata used, except the location of the data blocks within the whole data set

The same plaintext is encrypted to different ciphertexts at different locations, but always to the same ciphertext when written to the same location again

A standard conformant device can be constructed for decryption of data encrypted by another standard conformant device

The requirements for encrypting stored data, also referred to as “data at rest” differ

somewhat from those for transmitted data. The P1619 standard was designed to

have the following characteristics:

1. The ciphertext is freely available for an attacker. Among the circumstances

that lead to this situation:

a. A group of users has authorized access to a database. Some of the records in

the database are encrypted so that only specific users can successfully read/

write them. Other users can retrieve an encrypted record but are unable to

read it without the key.

b. An unauthorized user manages to gain access to encrypted records.

c. A data disk or laptop is stolen, giving the adversary access to the encrypted

data.

2. The data layout is not changed on the storage medium and in transit. The encrypted

data must be the same size as the plaintext data.

3. Data are accessed in fixed sized blocks, independently from each other. That is,

an authorized user may access one or more blocks in any order.

4. Encryption is performed in 16-byte blocks, independently from other blocks

(except the last two plaintext blocks of a sector, if its size is not a multiple of

16 bytes).

5. There are no other metadata used, except the location of the data blocks

within the whole data set.

6. The same plaintext is encrypted to different ciphertexts at different locations,

but always to the same ciphertext when written to the same location again.

7. A standard conformant device can be constructed for decryption of data encrypted

by another standard conformant device.

The P1619 group considered some of the existing modes of operation for use with

stored data. For CTR mode, an adversary with write access to the encrypted media can

flip any bit of the plaintext simply by flipping the corresponding ciphertext bit.

Next, consider requirement 6 and the use of CBC. To enforce the requirement

that the same plaintext encrypts to different ciphertext in different locations, the IV

could be derived from the sector number. Each sector contains multiple blocks. An

adversary with read/write access to the encrypted disk can copy a ciphertext sector

from one position to another, and an application reading the sector off the new

location will still get the same plaintext sector (except perhaps the first 128 bits).

For example, this means that an adversary that is allowed to read a sector from the

second position but not the first can find the content of the sector in the first position

by manipulating the ciphertext. Another weakness is that an adversary can flip

any bit of the plaintext by flipping the corresponding ciphertext bit of the previous

block, with the side-effect of “randomizing” the previous block.

XTS-AES Operation on Single Block

Figure 7.10 shows the encryption and decryption of a single block. The operation involves

two instances of the AES algorithm with two keys.

The plaintext of a sector or data unit is organized into blocks of 128 bits. Blocks are

labeled P0 , P1 , . . . , Pm . The last block my be null or may contain from 1 to 127 bits.

In other words, the input to the XTS-AES algorithm consists of m 128-bit blocks

and possibly a final partial block.

As can be seen, XTS-AES mode, like CTR mode, is suitable for parallel operation.

Because there is no chaining, multiple blocks can be encrypted or decrypted

simultaneously. Unlike CTR mode, XTS-AES mode includes a nonce (the parameter

i ) as well as a counter (parameter j ).

For encryption and decryption, each block is treated independently and

encrypted/decrypted as shown in Figure 7.10. The only exception occurs when

the last block has less than 128 bits. In that case, the last two blocks are encrypted/

decrypted using a ciphertext-stealing technique instead of padding.

Figure 7.11 shows the scheme.

Format-Preserving Encryption (FPE)

Refers to any encryption technique that takes a plaintext in a given format and produces a ciphertext in the same format

For example: credit cards consist of 16 decimal digits. An FPE that can accept this type of input would produce a ciphertext output of 16 decimal digits. (Note that the ciphertext need not be, and in fact in unlikely to be, a valid credit card number.) But it will have the same format and can be stored in the same way as credit card number plaintext.

Format-preserving encryption (FPE) refers to any encryption technique that takes

a plaintext in a given format and produces a ciphertext in the same format. For

example, credit cards consist of 16 decimal digits. An FPE that can accept this type of

input would produce a ciphertext output of 16 decimal digits. Note that the ciphertext

need not be, and in fact is unlikely to be, a valid credit card number. But it will have

the same format and can be stored in the same way as credit card number plaintext.

Table 7.2 Comparison of Format-Preserving Encryption and AES

A simple encryption algorithm is not format preserving, with the exception

that it preserves the format of binary strings. For example, Table 7.2 shows three

types of plaintext for which it might be desired to perform FPE. The third row

shows examples of what might be generated by an FPE algorithm. The fourth row

shows (in hexadecimal) what is produced by AES with a given key.

Motivation

FPE facilitates the retrofitting of encryption technology to legacy applications,

where a conventional encryption mode might not be feasible because it would disrupt

data fields/pathways. FPE has emerged as a useful cryptographic tool, whose

applications include financial-information security, data sanitization, and transparent

encryption of fields in legacy databases.

The principal benefit of FPE is that it enables protection of particular data

elements in a legacy database that did not provide encryption of those data elements,

while still enabling workflows that were in place before FPE was in use. With

FPE, as opposed to ordinary AES encryption or TDEA encryption, no database

schema changes and minimal application changes are required. Only applications

that need to see the plaintext of a data element need to be modified and generally

these modifications will be minimal.

Some examples of legacy applications where FPE is desirable:

■ COBOL data-processing applications: Any changes in the structure of a record

Typical code sizes involve hundreds of modules, each containing around 5,000–10,000

lines on average.

FPE facilitates the retrofitting of encryption technology to legacy applications, where a conventional encryption mode might not be feasible because it would disrupt data fields/pathways

FPE has emerged as a useful cryptographic tool, whose applications include financial-information security, data sanitization, and transparent encryption of fields in legacy databases

The principal benefit of FPE is that it enables protection of particular data elements, while still enabling workflows that were in place before FPE was in use

No database schema changes and minimal application changes are required

Only applications that need to see the plaintext of a data element need to be modified and generally these modifications will be minimal

Some examples of legacy applications where FPE is desirable are:

COBOL data-processing applications

Database applications

FPE-encrypted characters can be significantly compressed for efficient transmission

Difficulties in Designing an FPE

A general-purpose standardized FPE should meet a number of requirements:

The ciphertext is of the same length and format as the plaintext

It should be adaptable to work with a variety of character and number types

It should work with variable plaintext length

Security strength should be comparable to that achieved with AES

Security should be strong even for very small plaintext lengths

A general-purpose standardized FPE should meet a number of requirements:

1. The ciphertext is of the same length and format as the plaintext.

2. It should be adaptable to work with a variety of character and number types.

Examples include decimal digits, lowercase alphabetic characters, and the full

character set of a standard keyboard or international keyboard.

3. It should work with variable plaintext lengths.

4. Security strength should be comparable to that achieved with AES.

Security should be strong even for very small plaintext lengths.

Meeting the first requirement is not at all straightforward. As illustrated in

Table 7.2, a straightforward encryption with AES yields a 128-bit binary block that

does not resemble the required format. Also, a standard symmetric block cipher is

not easily adaptable to produce an FPE.

Figure 7.12 shows the Feistel structure used in all of

the NIST algorithms, with encryption shown on the left-hand side and decryption

on the right-hand side. The structure in Figure 7.12 is the same as that shown in

Figure 4.3 but, to simplify the presentation, it is untwisted, not illustrating the swap

that occurs at the end of each round.

The process of decryption is essentially the same as the encryption process.

The differences are: (1) the addition function is replaced by a subtraction function

that is its inverse; and (2) the order of the round indices is reversed.

To demonstrate that the decryption produces the correct result, Figure 7.12b

shows the encryption process going down the left-hand side and the decryption process

going up the right-hand side. The diagram indicates that, at every round, the

intermediate value of the decryption process is equal to the corresponding value of

the encryption process.

Character Strings

The NIST, and the other FPE algorithms that have been proposed, are used with plaintext consisting of a string of elements, called characters

A finite set of two or more symbols is called an alphabet

The elements of an alphabet are called characters

A character string is a finite sequence of characters from an alphabet

Individual characters may repeat in the string

The number of different characters in an alphabet is called the base (also referred to as the radix) of the alphabet

The NIST algorithms, and the other FPE algorithms that have

been proposed, are used with plaintext consisting of a string of elements, called

characters. Specifically, a finite set of two or more symbols is called an alphabet ,

and the elements of an alphabet are called characters . A character string is a finite

sequence of characters from an alphabet. Individual characters may repeat in the

string. The number of different characters in an alphabet is called the base , also

referred to as the radix of the alphabet.

The NIST document defines notation for specifying these conversions

(Table 7.3a).

Table 7.3

Notation and Parameters

Used in FPE Algorithms

Algorithm FF1 was submitted to NIST as a proposed FPE mode

[BELL10a, BELL10b] with the name FFX[Radix]. FF1 uses a pseudorandom function

PRFK (X ) that produces a 128-bit output with inputs X that is a multiple of 128

bits and encryption key K (Figure 7.13).

The FF1 encryption algorithm is illustrated in Figure 7.14.

Algorithm FF2 was submitted to NIST as a proposed FPE

mode with the name VAES3 [VANC11]. The encryption algorithm is defined in

Figure 7.15.

Algorithm FF3 was submitted to NIST as a proposed FPE mode

with the name BPS-BC [BRIE10]. The encryption algorithm is illustrated in

Figure 7.16

Summary

Multiple encryption and triple DES

Double DES

Triple DES with two keys

Triple DES with three keys

Electronic codebook

Cipher block chaining mode

Format-preserving encryption

Motivation

Difficulties in designing

Feistel structure

NIST methods

Cipher feedback mode

Output feedback mode

Counter mode

XTS-AES mode for block-oriented storage devices

Tweakable block ciphers

Storage encryption requirements

Operation on a single block

Operation on a sector

Chapter 7 summary.

E E

C X

Encryption

D D

P X

Decryption

(a) Double Encryption

E D E

K2 K1

K3 or

(3-key)

(2-key)

K3 or

(3-key)

(2-key)

C A B

Encryption

D E D

K2 K1

Decryption

(b) Triple Encryption

Figure 7.1 Multiple Encryption

B A

Figure 7.2 Known-Plaintext Attack on Triple DES

E D E

i j i

Ci a Bj

(a) Two-key Triple Encryption with Candidate Pair of Keys

Pi Ci

(b) Table of n known plaintext-ciphertext pairs, sorted on P

Bj key i

keys

Table 7.1 Block Cipher Modes of Operation

Figure 7.3 Electronic Codebook (ECB) Mode

Encrypt

P N

Encrypt

(a) Encryption

Decrypt

(b) Decryption

Figure 7.4 Cipher Block Chaining (CBC) Mode

Encrypt

CN–1

Encrypt

(a) Encryption

Decrypt

CN–1

Decrypt

(b) Decryption

Figure 7.5 s-bit Cipher Feedback (CFB) Mode

Encrypt

Select s bits

Discard b – s bits

(a) Encryption

C N–1

I N

O N

I2I1

O2O1

I N

O N

O2O1

(b) Decryption

s bits

s bits s bits C2

Encrypt

Select s bits

Discard b – s bits

s bits

s bitsb – s bits shift register

s bits C

P N

Encrypt

Select s bits

Discard b – s bits

s bits

s bitsb – s bits shift register

Encrypt

Select s bits

Discard b – s bits

C N–1

s bits C2

s bits C

s bits

s bits s bits P2

Encrypt

Select s bits

Discard b – s bits

s bitsb – s bits shift register

s bits P

Encrypt

Select s bits

Discard b – s bits

Figure 7.6 Output Feedback (OFB) Mode

(a) Encryption

P 1

C 1

Nonce

Encrypt

P 2

P N

C 2

Encrypt

C N

Encrypt

(b) Decryption

C 1

P 1

Nonce

Encrypt

C 2

C N

P 2

Encrypt

P N

Encrypt

I N

O N

I 2

I 1

O 2

O 1

I N

O N

I 2

I 1

O 2

O 1

Figure 7.7 Counter (CTR) Mode

(a) Encryption

Counter 1

Encrypt

Counter 2 Counter N

P2 PN

Encrypt

(b) Decryption

Counter 1

Encrypt

Counter 2 Counter N

C2 CN

Encrypt

Plaintext block

Encrypt

Input register

Output register

Ciphertext Ciphertext

(a) Cipher block chaining (CBC) mode

Key

Encrypt

Input register

Output register

Key

(b) Cipher feedback (CFB) mode

Plaintext block

Ciphertext

Key

Encrypt

Input register

Output register

Figure 7.8 Feedback Characteristic of Modes of Operation

Plaintext block

Ciphertext

Key

Encrypt

Input register

Output register

Counter

(d) Counter (CTR) mode

Figure 7.9 Tweakable Block Cipher

Hash

function

H()Tj)

Encrypt

(a) Encryption

Hash

function

Tj Cj

Decrypt

(a) Decryption

Figure 7.10 XTS-AES Operation on Single Block

Key 2

Key 1

AES

Encrypt

AES

Encrypt

(a) Encryption

(b) Decryption

Key 2

Key 1

AES

Encrypt

AES

Decrypt

Figure 7.11 XTS-AES Mode

XTS-AES block

encryption

Key

i, 0

XTS-AES block

encryption

Key

i, 1

CP XX

CPPmPm–1

XTS-AES block

encryption

Key

i, m–1

Cm–1

XTS-AES block

encryption

Key

i, m

Cm (a) Encryption

(b) Decryption

XTS-AES block

decryption

Key

i, 0

XTS-AES block

decryption

Key

i, 1

CPPm

CPCmCm–1

XTS-AES block

decryption

Key

i, m

Pm–1

XTS-AES block

decryption

Key

i, m–1

Credit Card Tax ID Bank Account Number Plaintext 8123 4512 3456 6780 219-09-9999 800N2982K-22 FPE 8123 4521 7292 6780 078-05-1120 709G9242H-35 AES (hex) af411326466add24

c86abd8aa525db7a 7b9af4f3f218ab25 07c7376869313afa

9720ec7f793096ff d37141242e1c51bd

Figure 7.12 Feistel Structure for Format-Preserving Encryption

Input (plaintext)

Output (ciphertext)

(a) Encryption (b) Decryption

R o u

n d

0 R

o u

n d

u characters v characters B0

n, T, 0

n, T, 1

A2 B1 B2 C1

+ FK

B1 C0 A1 B0

R o u

n d

r – 2

R o u

n d

r – 1

Ar–2

Cr–2

Cr–1

Br–2

n, T, r–2

n, T, r–1

Ar Br–1 Br Cr–1

+ FK

Br–1 Cr–2 Ar–1 Br–2

Output (plaintext)

Input (ciphertext)

R o u

n d

r – 1

R o u

n d

r – 2

A0 C0

u characters v characters B0 A1

n, T, 0

n, T, 1

A2 C2 B2 A3

– FK

–

B1 A2 A1 C1

R o u

n d

1 R

o u

n d

Ci–2

Cr–1

n, T, i–2

n, T, r–1

Ar Br

– FK

–

Br–1 Ar Ar–1 Cr–1

Ar–2 Cr–2 Br–2 Ar–1

Table 7.3 Notation and Parameters Used in FPE Algorithms

(a) Notation [x]s Converts an integer into a byte string; it is the string of s bytes that encodes the

number x, with 0 ≤ x < 28s. The equivalent notation is STR2 8s x( ).

LEN(X) Length of the character string X. NUMradix(X) Converts strings to numbers. The number that the numeral string X represents in

base radix, with the most significant character first. In other words, it is the non- negative integer less than radixLEN(X) whose most-significant-character-first representation in base radix is X.

PRFK(X) A pseudorandom function that produces a 128-bit output with X as the input, using encryption key K.

STRradix m x( ) Given a nonnegative integer x less than radixm, this function produces a

representation of x as a string of m characters in base radix, with the most significant character first.

[i .. j] The set of integers between two integers i and j, including i and j. X[i .. j] The substring of characters of a string X from X[i] to X[j], including X[i] and

X[j]. REV(X) Given a bit string, X, the string that consists of the bits of X in reverse order.

(b) Parameters radix The base, or number of characters, in a given plaintext alphabet. tweak Input parameter to the encryption and decryption functions whose confidentiality is

not protected by the mode. tweakradix The base for tweak strings minlen Minimum message length, in characters. maxlen Maximum message length, in characters. maxTlen Maximum tweak length

t Prerequisites: Approved, 128-bit block cipher, CIPH; Key, K, for the block cipher; Input: Nonempty bit string, X, such that LEN(X) = is a multiple of 128. Output: 128-bit block, Y Steps: 1. Let m = LEN(X)/128. 2. Partition X into m 128-bit blocks X1,…, Xm, so that X = X1 || …|| Xm

3. Let Y0 = [0] 16

4. For j from 1 to m: 4.i let Yj = CIPHK(Yj–1 ⊕ Xj). 6. Return Ym.

Figure 7.13 Algorithm PRF(X)

Prerequisites: Approved, 128-bit block cipher, CIPH; Key, K, for the block cipher; Base, radix, for the character alphabet; Range of supported message lengths, [minlen .. maxlen]; Maximum byte length for tweaks, maxTlen. Inputs: Character string, X, in base radix of length n such that n ∈ [minlen .. maxlen]; Tweak T, a byte string of byte length t, such that t ∈ [0 .. maxTlen]. Output: Character string, Y, such that LEN(Y) = n. Steps: 1. Let u = ⎣n/2⎦; v = n – u. 2. Let A = X[1 .. u]; B = X[u + 1 .. n]. 3. Let b = ⎡ ⎡v LOG2(radix)⎤ / 8⎤; d = 4 ⎡b/4⎤ + 4

4. Let P = [1]1 || [2]1 || [1]1 || [radix]3 || [10]1 || [u mod 256]1 || [n]4 || [t]4. 5. For i from 0 to 9: i. Let Q = T || [0](−t−b−1) mod 16 || [i]1 || [NUMradix(B)]

ii. Let R = PRFK(P || Q). iii. Let S be the first d bytes of the following string of ⌈d/16⌉ 128-bit blocks: R || CIPHK (R ⊕ [1]

16) || CIPHK (R ⊕ [2] 16) || …|| CIPHK (R ⊕ [⌈d/16⌉ – 1]

16). iv. Let y = NUM2(S).

v. If i is even, let m = u; else, let m = v. vi Let c = (NUMradix(A) + y) mod radix

vii. Let C = STRradix m c( ) .

viii. Let A = B. ix. Let B = C. 6. Return Y = A || B.

Figure 7.14 Algorithm FF1 (FFX[Radix])

Approved, 128-bit block cipher, CIPH; Key, K, for the block cipher; Base, tweakradix, for the tweak character alphabet; Range of supported message lengths, [minlen .. maxlen] Maximum supported tweak length, maxTlen. Inputs: Numeral string, X, in base radix, of length n such that n ∈ [minlen .. maxlen]; Tweak numeral string, T, in base tweakradix, of length t such that t ∈ [0 .. maxTlen]. Output: Numeral string, Y, such that LEN(Y) = n. Steps: 1. Let u = ⎣n/2⎦; v = n – u. 2. Let A = X[1 .. u]; B = X[u + 1 .. n]. 3. If t>0, P = [radix]1 || [t]1 || [n]1 || [NUMtweakradix(T)]

13;

else P = [radix]1 || [0]1 || [n]1 || [0]13. 4. Let J = CIPHK(P)

5. For i from 0 to 9: i. Let Q ← [i]1 || [NUMradix(B)]

15 ii. Let Y ← CIPHJ(Q). iii. Let y ← NUM2(Y). iv. If i is even, let m = u; else, let m = v. v. Let c = (NUMradix(A) + y) mod radix

vi. Let C = STRradix m c( ) .

vii. Let A = B. viii. Let B = C. 6. Return Y = A || B. Figure 7.15 Algorithm FF2 (VAES3)

Approved, 128-bit block cipher, CIPH; Key, K, for the block cipher; Base, radix, for the character alphabet such that radix ∈ [2 .. 216]; Range of supported message lengths, [minlen .. maxlen], such that minlen ≥ 2 and maxlen ≤ 2⎣logradix(2

96) ⎦.

Inputs: Numeral string, X, in base radix of length n such that n ∈ [minlen .. maxlen]; Tweak bit string, T, such that LEN(T) = 64. Output: Numeral string, Y, such that LEN(Y) = n. Steps: 1. Let u = ⌈n/2⌉; v = n – u. 2. Let A = X[1 .. u]; B = X[u + 1 .. n]. 3. Let TL = T[0..31] and TR = T[32..63]

4. For i from 0 to 7: i. If i is even, let m = u and W = TR, else let m = v and W =TL.

ii. Let P = REV([NUMradix(REV(B))] 12) || [W ⊕ REV([i]4]).

iii. Let Y = CIPHK(P).

iv. Let y = NUM2(REV(Y)).

v. Let c = (NUMradix(REV(A)) + y) mod radix m.

vi. Let C = REV( STRradix m c( ) ).

vii. Let A = B. viii. Let B = C. 5. Return A || B.

Figure 7.16 Algorithm FF3 (BPS-BC)