Original: January 7, 1998
Update: January 13, 1998
(updated by adding Sections 3.3 and 3.4; modified chart in Sec. 5)
These KAT and MCT tests are based on tests specified in the draft NIST Special Publication 800-17, Modes of Operation Validation System (MOVS): Requirements and Procedures [MOVS], which describes tests for the DES and Skipjack algorithms (two examples of block cipher algorithms). Each of the tests for which values are required in the submission packages is described below. In addition, example files are included which specify the exact syntax and format which submitters are required to use when submitting their KAT and MCT values.
Figure 1: Electronic Codebook (ECB) Mode
The Electronic Codebook (ECB) Mode is diagramed in Figure 1. In ECB encryption, a plaintext data block (D1, D2, ..., D128) is used directly as the input block (I1, I2, ..., I128). The input block is then processed through the algorithm in the encrypt state. The resulting output block (O1, O2, ..., O128) is used directly as ciphertext (C1, C2, ..., C128).
In ECB decryption, a ciphertext block (C1, C2, ..., C128) is used directly as the input block (I1, I2, ..., I128). The input block is then processed through the algorithm in the decrypt state. The resulting output block (O1, O2, ..., O128) produces the plaintext (D1, D2, ..., D128). The ECB decryption process is the same as the ECB encryption process except that the decrypt state of the algorithm is used rather that the encrypt state.
The above processes for encryption and decryption in ECB mode are independent of key size.
Figure 2: Cipher Block Chaining (CBC) Mode
As diagramed in Figure 2, the Cipher Block Chaining (CBC) mode begins processing by dividing a
plaintext message into blocks. In CBC encryption, the first input block (I1, I2, ..., I128) is formed
by exclusive-ORing the first plaintext data block (D1, D2, ..., D128) with a 128-bit initialization
vector IV, i.e., (I1, I2, ..., I128) = (IV1 D1,
IV2
D2, ..., IV128
D128). The input block is
processed through the algorithm in the encrypt state, and the resulting output block is used as the
ciphertext, i.e., (C1, C2, ..., C128) = (O1, O2, ..., O128). This first ciphertext block is then
exclusive-ORed with the second plaintext data block to produce the second input block, i.e., (I1, I2,
..., I128) = (C1
D1, C2
D2, ...,
C128
D128). Note that I and D now refer to the second block.
The second input block is processed through the algorithm in the encrypt state to produce the second
ciphertext block. This encryption process continues to "chain" successive cipher and plaintext blocks
together until the last plaintext block in the message is encrypted.
In CBC decryption, the first ciphertext block of an encrypted message is used as the input block and
is processed through the algorithm in the decrypt state, i.e., (I1, I2, ..., I128) = (C1, C2, ..., C128).
The resulting output block, which equals the original input block to the algorithm during encryption,
is exclusive-ORed with the IV (which must be the same as that used during encryption) to produce
the first plaintext block, i.e., (D1, D2, ..., D64) = (O1 IV1,
O2
IV2, ..., O128
IV128). The
second ciphertext block is then used as the next input block and is processed through the algorithm
in the decrypt state. The resulting output block is exclusive-ORed with the first ciphertext block to
produce the second plaintext data block, i.e., (D1, D2, ..., D128) = (O1
C1,
O2
C2, ..., O128
C128).
Note that again the D and O refer to the second block. The CBC decryption process
continues in this manner until the last complete ciphertext block has been decrypted. Ciphertext
representing a partial data block must be decrypted in a manner as specified for the application.
The above processes for encryption and decryption in CBC mode are independent of key size.
The above shall be repeated for each of the three minimum key sizes (128, 192, and 256 bits). See the example file "ecb_vk.txt" [TESTS] for the required formatting and syntax of submitted test values. To test the algorithm's decrypt state, the ciphertext shall be input into the algorithm (in the decrypt state) with the corresponding key value (basis vector), and the result must equal the zero plaintext value.
The above shall be repeated for each of the three minimum key sizes (128, 192, and 256 bits). See the example file "ecb_vt.txt" [TESTS] for the required formatting and syntax of submitted test values. To test the algorithm's decrypt state, the ciphertext shall be input into the algorithm (in the decrypt state) with the key initialized to zero, and the result must equal the corresponding plaintext value.
See the example file "ecb_tbl.txt" [TESTS] for the required formatting and syntax of submitted test values. As indicated in the example file, the submitter shall also include a brief description of what tables are being tested.
To test the algorithm's decrypt state, the ciphertext shall be input into the algorithm (in the decrypt state) with the corresponding key value, and the result must equal the corresponding plaintext value. For those candidate algorithms which do not use tables, the tests and requirements specified in this section do not apply.
The file(s) containing values for the Intermediate Values KAT shall have filenames which are appropriate, and shall contain a description of what is being tested. The file(s) shall also have a format that is as similar to that of the example KAT files as possible; the exact information included in the file(s) will likely depend on the algorithm, and therefore no example file is given for this KAT.
For those candidate algorithms which do not calculate intermediate values, the tests and requirements specified in this section do not apply.
Note that the initial plaintext and IV values used in the submitted file shall be determined by the submitter. The values contained in the example file are only meant to demonstrate the proper syntax and format for the submission - they are NOT required for use by the submitter in generating values.
Each Monte Carlo Test consists of four million cycles through the candidate algorithm implementation. These cycles are divided into four hundred groups of 10,000 iterations each. Each iteration consists of processing an input block through the candidate algorithm, resulting in an output block. At the 10,000th cycle in an iteration, new values are assigned to the variables needed for the next iteration. The results of each 10,000th encryption or decryption cycle are recorded and included by the submitter in the appropriate file.
Initialize KEY0, PT0 FOR i = 0 TO 399 { Record i, KEYi, PT0 FOR j = 0 TO 9999 { IBj = PTj Perform algorithm in encrypt state, resulting in CTj PTj+1 = CTj } Record CTj KEYi+1 = KEYi |
Figure 3: Monte Carlo Test - ECB Encryption
As summarized in Figure 3, the Monte Carlo Test for the ECB Encrypt state shall be performed as follows:
For cases when the size of KEY is 192 or 256 bits, CT shall be expanded in length to
192 or 256 bits (as appropriate) before the new KEY can be formed. This expansion
shall be accomplished by concatenating the 64 or 128 rightmost bits of the previous
CT (CT9998) with the 128 bits of the current CT (CT9999).
This value shall then be exclusive-ORed with the current KEY to form the new KEY;
e.g., if the size of KEY is 192 bits,
(KEY1i+1, KEY2i+1, ..., KEY192i+1) =
(KEY1i CT659998,
KEY2i
CT669998, ...,
KEY64i
CT1289998,
KEY65i
CT19999,
KEY66i
CT29999, ...,
KEY192i
CT1289999).
NOTE: The recorded output for this test shall consist of 400 sets of (i, KEY, PT, CT).
Initialize KEY0, CT0 FOR i = 0 TO 399 { Record i, KEYi, CT0 FOR j = 0 TO 9999 { IBj = CTj Perform algorithm in decrypt state, resulting in PTj CTj+1 = PTj } Record PTj KEYi+1 = KEYi |
Figure 4: Monte Carlo Test - ECB Decryption
As summarized in Figure 4, the Monte Carlo Test for the ECB Decrypt state shall be performed as follows:
For cases when the size of KEY is 192 or 256 bits, PT shall be expanded in length to
192 or 256 bits (as appropriate) before the new KEY can be formed. This expansion
shall be accomplished by concatenating the 64 or 128 rightmost bits of the previous
PT (PT9998) with the 128 bits of the current PT (PT9999).
This value shall then be exclusive-ORed with the current KEY to form the new KEY;
e.g., if the size of KEY is 192 bits,
(KEY1i+1, KEY2i+1, ..., KEY192i+1) =
(KEY1i PT659998,
KEY2i
PT669998, ...,
KEY64i
PT1289998,
KEY65i
PT19999,
KEY66i
PT29999, ...,
KEY192i
PT1289999).
NOTE: The recorded output for this test shall consist of 400 sets of (i, KEY, CT, PT).
Initialize KEY0, IV, PT0 FOR i = 0 TO 399 { IF (i == 0) CV0 = IV Record i, KEYi, CV0, PT0 FOR j = 0 TO 9999 { IBj = PTj |
Figure 5: Monte Carlo Test - CBC Encryption
As summarized in Figure 5, the Monte Carlo Test for the CBC Encrypt state shall be performed as follows:
For cases when the size of KEY is 192 or 256 bits, CT shall be expanded in length to
192 or 256 bits (as appropriate) before the new KEY can be formed. This expansion
shall be accomplished by concatenating the 64 or 128 rightmost bits of the previous
CT (CT9998) with the 128 bits of the current CT (CT9999).
This value shall then be exclusive-ORed with the current KEY to form the new KEY;
e.g., if the size of KEY is 192 bits,
(KEY1i+1, KEY2i+1, ..., KEY192i+1) =
(KEY1i CT659998,
KEY2i
CT669998, ...,
KEY64i
CT1289998,
KEY65i
CT19999,
KEY66i
CT29999, ...,
KEY192i
CT1289999).
NOTE: The output for this test shall consist of 400 sets of (i, KEY, IV, PT, CT). At the beginning of each of the 400 loops for i, the chaining value CV0 shall be recorded in the position for the set (see the example file, "cbc_e_m.txt" [TESTS]). Essentially, the value of IVi equals the final value of CV0 from loop i-1.
Initialize KEY0, IV0, CT0 FOR i = 0 TO 399 { IF (i == 0) CV0 = IV0 Record i, KEYi, CV0, CT0 FOR j = 0 TO 9999 { IBj = CTj Perform algorithm in decrypt state, resulting in OBj PTj = OBj |
Figure 6: Monte Carlo Test - CBC Decryption
As summarized in Figure 6, the Monte Carlo Test for the CBC Decrypt state shall be performed as follows.
For cases when the size of KEY is 192 or 256 bits, PT shall be expanded in length to
192 or 256 bits (as appropriate) before the new KEY can be formed. This expansion
shall be accomplished by concatenating the 64 or 128 rightmost bits of the previous
PT (PT9998) with the 128 bits of the current PT (PT9999).
This value shall then be exclusive-ORed with the current KEY to form the new KEY;
e.g., if the size of KEY is 192 bits,
(KEY1i+1, KEY2i+1, ..., KEY192i+1) =
(KEY1i PT659998,
KEY2i
PT669998, ...,
KEY64i
PT1289998,
KEY65i
PT19999,
KEY66i
PT29999, ...,
KEY192i
PT1289999).
NOTE: The output for this test shall consist of 400 sets of (i, KEY, IV, CT, PT). At the beginning of each of the 400 loops for i, the chaining value CV0 shall be recorded in the IV position for the set (see the example file, "cbc_d_m.txt" [TESTS]). Essentially, the value of IVi equals the final value of CV0 from the loop i-1.
Filename | Mode | Test | Key Sizes (bits) |
ecb_vk.txt | ECB | Variable Key KAT | 128, 192, 256 |
ecb_vt.txt | ECB | Variable Text KAT | 128, 192, 256 |
ecb_tbl.txt (if applicable) | ECB | Tables KAT | 128, 192, 256 |
? (possibly multiple files) (if applicable) | ECB | Intermediate Values KAT | 128, 192, 256 |
Filename | Mode | Test | Key Sizes (bits) |
ecb_e_m.txt | ECB | Encrypt MCT | 128, 192, 256 |
ecb_d_m.txt | ECB | Decrypt MCT | 128, 192, 256 |
cbc_e_m.txt | CBC | Encrypt MCT | 128, 192, 256 |
cbc_d_m.txt | CBC | Decrypt MCT | 128, 192, 256 |