FIPS PUB 74

results in output O" and "Deciphering the output O using key K results in input I." Given the same I and K, the same O always results. Likewise, given the same O and K, the same I results.

If the input at time t is called It, then the output is called Ot. A sequence of input blocks to the DES may be denoted as I1, I2, I3 The outputs are similarly denoted as O1, O2, O3, ...On.

The DES specifies only the functions E and D. Other considerations will define the input and how the output is used. Many different possibilities exist but the application generally dictates which ones are feasible. In order to provide compatibility between devices which are able to communicate, four modes of operation are specified in FIPS PUB 81.

5.3.1 The Electronic Codebook (ECB) Mode

The simplest mode of operation, the Electronic Code book (ECB), is the DES algorithm specified in FIPS PUB 46. The ECB mode is shown in figures 5.1 through 5.3, and tables 5.1 through 5.4. In the ECB mode of operation, the algorithm is independent of time and is called a memoryless system. Given the same data and the same key, the resultant cipher will always be the same. This characteristic should be considered when designing a cryptographic system using the ECB mode. The output block Ot is not dependent on any of the previous inputs, Ii, 12 I...,. It is important to note that the full 64-bits of the Ot must be available in order to obtain the original input It.

A general guideline for using the DES in this mode is that all possible inputs should be allowed and used whenever possible. Since the security of the data in this mode is based on the number of inputs in the code book, this number should be maximized whenever possible. In particular this mode should never be used for enciphering single characters (e.g., 8-bit ASCII characters by entering them in a fixed 8-bit position and filling the other 56 bits with a fixed number). Two to the 64th inputs are possible in this mode and as large a subset as feasible should be used. Random information should be used to pad small blocks and the random information discarded when the block is deciphered.

Data should be entered into the input register so that the first character of input appears on the left, the second character to the right of it, etc., and the last character on the far right. Using shift register technology, the characters should enter on the right and be shifted left until the register is full. Similarly, the output of the DES should be taken from left to right when being transmitted or stored in character serial mode. Using shift register technology, the characters should exit from the left and the register shift left until the register is empty.

5.3.2 The Cipher Block Chaining (CBC) Mode

A method of using the DES algorithm in which the blocks of cipher are chained together is called the Cipher Block Chaining (CBC) mode. Figure 5.4 demonstrates how the CBC mode is used to encrypt a message. The input to the DES at time t is defined to be the exclusive or (represented by ) of the data at time t and the cipher at time t-1. The cipher at time O is defined to be a quantity called the initialization vector or W. The CBC mode requires complete blocks of 64 bits until the final block is to be enciphered.

The final (terminal) data block of a message or record may not contain exactly 64 bits when processing in the CBC mode. When this occurs, either the terminal block must be padded to 64 bits or the terminal block must be enciphered in a way that yields the same number of bits as the input. The first technique is called padding and the second is called truncation.

When a sequence of characters is being enciphered and the terminal block contains less than the maximum number of characters (e.g., eight in the case of 8-bit characters), then padding may be used to format the final input block in the following way. Suppose P padding characters are needed to fill out the block. If P equals one, the character representing the number one should be put in the last byte position. If P is greater than one, the character representing the number P should be put in the last byte and zeros should be put in the remaining P-1 byte positions. (See fig. 5.4.) In most coding schemes, the last three bits of the character representing a digit are the same as the binary representation of the digit (e.g., the ASCII representation of the character 4 is a hexadecimal 34). One bit may be used in the header block of a message packet to signify a padded message (i.e., that the final block of the packet is padded) or some other method must be devised.

Truncation may be used in the CBC mode when the number of cipher bits must be the same as the number of input bits. It may be necessary that an enciphered tape contain the same number of

16

FIPS PUB 74

records and the same number of characters per record as the unenciphered tape. This requirement also occurs in some message switching systems in which the record length is fixed. In these cases the following method can be used to encipher the terminal block which does not contain 64 bits.

The short terminal block is enciphered by encrypting the previous cipher block in the ECB mode and exclusive OR'ing the result to the terminal data block. (See fig. 5.5.) The receiver must detect the short cipher block and perform the same operation, i.e., encrypt the previous complete cipher block and perform the exclusive OR operation to obtain the original plaintext block. If a short terminal block contains B bits, then the leftmost B bits of the enciphered cipher block are used. This technique normally provides adequate security for the final block, but it should be noted that if the last B bits of plaintext are known to an active wiretapper, he or she may alter the last B bits of cipher so that they will decrypt to any desired plaintext. This is because, if only the last B bits are altered, the same value will be exclusive OR'ed to the short cipher block upon decryption.

One or more bit errors within a single cipher block will affect the decryption of two blocks (the block in which the error occurs and the succeeding block). If the errors occur in the tth cipher block, then each bit of the tth plaintext block will have a average error rate of 50 percent. The (t+1)st plaintext block will have only those bits in error which correspond directly to the cipher bits in error, and the (t+2)nd plaintext block will be correctly decrypted. Thus, the CBC mode synchronizes itself one block after the error.

5.3.3 The Cipher Feedback (CFB) Mode

The Cipher Feedback (CFB) mode of operation may be used in applications which require chaining to prevent substitution or where blocks of 64 bits cannot be used efficiently. Most computer data that are to be transmitted or stored are coded in 6- to 8-bit codes. FIPS PUB 1 [9] requires the use of the 7-bit ASCII code for interchange. In many communications protocols the units of data are bits or characters rather than blocks. The Cipher Feedback Mode of using the DES satisfies a requirement for encrypting data elements of length K where 1 < K < 64.

The CFB mode of operation is shown in figure 5.6. The input to the DES algorithm is not the data itself but rather the previous 64 bits of cipher. The first encryption uses an initialization vector (IV) as its IO input. In the CFB mode both the transmitter and the receiver of data use only the encryption operation of the DES. The output at time t is the 64-bit block Ot. The cipher at time t is produced by exclusive OR'ing the K bits of plaintext Pt to the leftmost K bits of Ot. This cipher Ct is transmitted and also is entered on the right-side of the input register after the previous input is shifted left K bit positions. The new input is used for the next encipherment.

A 64-bit IV is generated at time O and put into the input register. From that time on, the cipher text will depend on this initial input. In order to fill the receiver's input register, one of two events must occur:

1.	The receiver must independently generate the identical

initial fill.

2.	The transmitter must transmit sufficient data to fill

the receiver's input register.

A guideline is that the transmitter generates a pseudorandom number (48 to 64 bits) and transmits it as the IV: The transmitter and the receiver shall use this number (with the high order bits of the 64. bit DES input padded with "0" bits if necessary) as the 64-bit IV. Using a higher number of bits provides higher security but also results in higher transmission overhead. It is desirable that no two messages enciphered with the same key use the same IV. The DES may be used as a pseudorandom number generator to generate the IV. Start-stop (asynchronous) communications devices should transmit the IV as characters with appropriate start-stop bits appended.

In the CFB mode, errors within a K-bit unit of cipher will affect the decryption of the garbled -cipher and also the decryption of succeeding cipher until the bits in error have been shifted out of the DES input block. The first affected K-bit unit of plaintext will be garbled in exactly those places where the cipher is in error. Succeeding decrypted plaintext will have an average error rate of 50 percent until all errors have been shifted out of the input block. Assuming no additional errors are encountered during this time, the correct plaintext will then be obtained. Thus, the CFB mode is selfsynchronizing.

17

FIPS PUB 74

The CFB mode of operation is also useful for the encryption of stored data. For maximun efficiency 64-bit data elements are used. If the terminal data block does not contain a full 64 bits of data, the remaining bits are padded before encryption. However, the cipher block may be truncated so that only the cipher bits corresponding to the unpadded bits are used. In this case the number of cipher bits will equal the number of data bits.

When using the K-bit CFB mode the last K bits of cipher can be altered by an active wiretapper who knows the last K bits of plaintext so that the final K bits will decrypt to any desired K bits of plaintext. This is the same threat that applies to the CBC mode with terminal block truncation. If this is a significant threat, it is recommended that the final K bits of plaintext be a function of the previous plaintext bits (i.e., a parity or sum check).

5.3.4 The Output Feedback (OFB) Mode

The Output Feedback (OFB) mode like the CFB mode operates on data units of length K where K is an integer from l to 64. However, the OFB mode does not chain cipher from one time to the next. A one bit error in cipher text causes only one bit of the decrypted plaintext to be in error. Therefore, this mode can be useful in applications where no error propagation is required.

Figure 5.7 illustrates the OFB mode. The first encryption uses an initialization vector (IV) as its IO input, and both the transmitter and receiver use only the encryption operation of the DES. The cipher at time t is produced by exclusive OR'ing the K bits of plaintext to the leftmost K bits of the output Ot. The same K bits of the DES output block are fed back to the right side of the input register after the previous input is shifted left K bit positions, and the new input is used for the next encipherment.

The output of the OFB mode is independent of both plaintext and cipher. Therefore, the OFB mode does not have the self-synchronization property of the CBC and CFB modes. If synchronization is lost then a new IV must be established between the transmitter and receiver.

5.3.5 Relationship of CBC and 64-bit CFB

Like CBC, the CFB mode of operation can be used to encrypt 64-bit blocks. In this case the entire 64 bits of Ot are exclusive OR'ed with 64 bits of plaintext at each encryption time. This is called the 64-bit CFB mode of operation.

Let M1 be a 64-bit CFB machine with key schedule, KS = (K1,K2 K16), on each of the 16 encryption rounds. (Figure 5.3 shows the generation of a DES key schedule.) In CFB mode the same schedule is also used for decryption. Let M2 be a CBC machine with a key schedule of KR =(K16,K15,...,K1) for encryption (i.e., the DES decipher operation), and (K1,K2 K16 for decryption (i.e., the DES encipher operation). If M1 encrypts the 64-bit plaintext blocks P1, P2, and P3 with initialization vector IV to form cipher C1, C2, and C3; then M2 will encrypt P:3, P2, and P1 with initialization vector C3 to form cipher C2, C1, IV. Similarly while M1 will decrypt C1, C2, and C3 (using initialization vector IV) to P1, P2, and P3; M2 will decrypt C2, C1, and IV (using initialization vector C3) to P3, P2, and P1. Thus by reversing (IV,C1,C2,C3) to (C3,C2,C1,IV) we may decrypt cipher generated by M1 with M2.

To see that the above statements are true let E[S](X) represent the encryption of X in the ECB mode using key schedule S, and let D[S](X) be the ECB decryption of X under schedule S. Note that S is the key schedule and not the key itself. Decryption uses the key schedule in the reverse order of encryption. Thus, E[KS](X) = D[KR](X). The encryption of P1, P2, and P3 by M1 using IV may be described by three equations.

P1 E[KS] (IV)	=	P1 O1 = C1

P2 E[KS] (C1)	=	P2 O2 = C2

P3 E(KS] (C2)	=	P3 O3 = C3

18

FIPS PUB 74

O1, O2, and O3 represent ECB encryption, with key schedule KS, of inputs IV, C1, and C2 respectively. is a 64-bit exclusive or operator. The encryption of P3, P2, and P1 by M2 using C3 as the initialization vector may also be described by three equations.

E[KR] (P3 C3)	=	E[KR] (O3)	=	D[KS] (O3)	=	C2

E[KR] (P2 C2)	=	E[KR] (O2)	=	D[KS] (O2)	=	C1

E[KR] (P1 C1)	=	E[RR] (O1)	=	D[KS] (O1)	=	IV

By reversing the key schedules, the inputs, and the outputs we have obtained equivalent machines. Similar equations may be derived for decryption, and the relationship holds for an arbitrary length stream of 64-bit plaintext blocks.

5.4	CBC and CFB for Data Authentication

The DES can be used for data (message) authentication. A Message Authentication Code (MAC) is computed as a Cryptographic function of the data (message). The MAC is then stored or transmitted with the data. Only those knowing the secret key can recompute the MAC for the received data and verify that the data has not been modified by comparing the computed MAC with the stored or transmitted MAC. An unauthorized recipient of the data who does not possess the key cannot modify the data and generate a new MAC to correspond with the modified data. This technique is useful in applications which require maintaining data integrity but which do not require protecting the data from disclosure. For example, computer programs may be stored in plaintext form with a computed MAC appended to the program file. The program may be read and executed without decryption. However, when the integrity of the program is questioned, a MAC can be computed on the program file and compared with the one stored in the file. If the two MAC's compare, and the cryptographic key used to generate the MAC has been protected, then the program file has not been modified.

A MAC may be computed using either the CBC or the CFB mode. In CBC authentication, a message is encrypted in the normal CBC manner but the cipher is discarded. If the number of data bits is not a multiple of 64, then the last data bit is appended with zeros on the right to form an integral number of blocks. The most significant M bits of the final output block are used as the MAC.

In CFB authentication, a message is encrypted in the normal CFB manner except that the cipher text is discarded. After encrypting the final K bits of data and feeding the resulting cipher text back into the DES input block, the DES device is operated one more time and the most significant M bits of the resulting DES output block are used as the MAC.

In both CBC and CFB authentication, a MAC should be used that is as long as practical. Since a MAC is an error detection code (which is computed using Cryptographic techniques), a long MAC is desirable. Bit manipulation within a message will be detectable with a probability of 1 1/2M) Saying that a message is authentic or concluding that it has not been modified is based upon this probability. The proposed Federal Standard 1026 requires M to be at least 24 for Federal telecommunication applications. Financial transaction application standards are recommending M to be 32. Application designers should select M to optimize security and efficiency requirements.

In ADP communications security applications a message numbering and verifying system should be used to detect the insertion of false messages, the deletion of valid messages, and the replay of previously valid messages. The combined use of a Message Identifier (MID) and a MAC achieves these security objectives and protects against modification. If the data source MAC and the data destination MAC are in agreement and if the MID ages with the value expected by the receiver, then the message is accepted. The MID should be unique and deterministic for each message transmitted between a sender and receiver. The uniqueness may be achieved through the use of a nonrepeating binary counter.

5.5	System Implementation

FIPS PUB 46 specifies that the basic implementation of the DES be done in hardware, However, the type of hardware used and the placement of the hardware will depend on the system and the requirements for speed and security. The DES device may also be interfaced to a computer system

19

FIPS PUB 74

and an application program. This subsection will describe one possible implementation and the software interface used on the experimental Data Encryption Testbed at NBS. The mention of the specific product brands does not constitute or imply an NBS endorsement.

The two TTL implementations of the DES and the two PROLOG microprocessor computers have been interfaced to an asynchronous communication line between a computer (PDP 11/45) and a terminal (CRT ASCII Try compatible). The line will operate at 300, 1200 and 2400 bits per second. Seven-bit ASCII characters with a parity bit are transmitted in an 11-bit, start-stop format (one bit for start and two bits for stop). RS-232C electrical and mechanical interfaces are used at all Data Terminal Equipment (DTE) and Data Circuit-terminating Equipment (DCE) interfaces. Universal Asynchronous Receive/Transmit (UART) chips are used to receive and transmit data on both sides of each of the PROLOG computers. A full duplex communication system is supported with only a small delay encountered at the PROLOG computer.

When the two PROLOG/DES units are inserted into the communication line, the line is divided into three parts. (See fig. 5.8.) One part is between the terminal and the TSU (Terminal Security Unit), the second is between the TSU and the CSU (Computer Security Unit), and the third is between the CSU and the computer. The data is in plaintext form on parts 1 and 3 and is in ciphertext form on part 2. It is assumed that the terminal and the TSU are colocated in a secure facility and that the CSU and the computer are colocated in a secure facility.

The PROLOG computers have 1K of Read Only Memory (ROM) and 2K of Random Access Memory (RAM). Programs are written for the PROLOG computers on the PDP 11/45 using a UNIX operating system. NBS personnel have written a cross assembler program on the PDP 11 to assemble the programs of several microprocessors. The cross assembler is written in the C programming language and outputs a listing of the assembled program and a core image to the PDP 11 files.

20

FIPS PUB 74

Table 5.1 Electronic Codebook (ECB) Mode-E Bit-Selection Table

21

32	1	2	3	4	5

4	5	6	7	8	9

8	9	10	11	12	13

12	13	14	15	16	17

16	17	18	19	20	21

20	21	22	23	24	25

24	25	26	27	28	29

28	29	30	31	32	1

22

23

24

25

26