3 ■ I O '• 50b - L I COMPUTER SCIENCE & TECHNOLOGY MAINTENANCE TESTING FOR THE DATA ENCRYPTION STANDARD NBS Special Publication 500-61 U.S. DEPARTMENT OF COMMERCE National Bureau of Standards NATIONAL BUREAU OF STANDARDS The National Bureau of Standards' was established by an act ot Congress on March 3, 1901. The Bureau's overall goal is to strengthen and advance the Nation's science and technology and facilitate their effective application for public benefit. To this end, the Bureau conducts research and provides: (1) a basis for the Nation's physical measurement system, (2) scientific and technological services for industry and government, (3) a technical basis for equity in trade, and (4) technical services to promote public safety. The Bureau's technical work is per- formed by the National Measurement Laboratory, the National Engineering Laboratory, and the Institute for Computer Sciences and Technology. THE NATIONAL MEASUREMENT LABORATORY provides the national system of physical and chemical and materials measurement; coordinates the system with measurement systems of other nations and furnishes essential services leading to accurate and uniform physical and chemical measurement throughout the Nation's scientific community, industry, and commerce; conducts materials research leading to improved methods of measurement, standards, and data on the properties of materials needed by industry, commerce, educational institutions, and Government; provides advisory and research services to other Government agencies; develops, produces, and distributes Standard Reference Materials; and provides calibration services. The Laboratory consists of the following centers: Absolute Physical Quantities 2 — Radiation Research — Thermodynamics and Molecular Science — Analytical Chemistry — Materials Science. THE NATIONAL ENGINEERING LABORATORY provides technology and technical ser- vices to the public and private sectors to address national needs and to solve national problems; conducts research in engineering and applied science in support of these efforts; builds and maintains competence in the necessary disciplines required to carry out this research and technical service; develops engineering data and measurement capabilities; provides engineering measurement traceability services; develops test methods and proposes engineering standards and code changes; develops and proposes new engineering practices; and develops and improves mechanisms to transfer results of its research to the ultimate user. The Laboratory consists of the following centers: Applied Mathematics — Electronics and Electrical Engineering 2 — Mechanical Engineering and Process Technology 2 — Building Technology — Fire Research — Consumer Product Technology — Field Methods. THE INSTITUTE FOR COMPUTER SCIENCES AND TECHNOLOGY conducts research and provides scientific and technical services to aid Federal agencies in the selection, acquisition, application, and use of computer technology to improve effectiveness and economy in Government operations in accordance with Public Law 89-306 (40 U.S.C. 759), relevant Executive Orders, and other directives; carries out this mission by managing the Federal Information Processing Standards Program, developing Federal ADP standards guidelines, and managing Federal participation in ADP voluntary standardization activities; provides scientific and technological advisory services and assistance to Federal agencies; and provides the technical foundation for computer-related policies of the Federal Government. The Institute consists of the following centers: Programming Science and Technology — Computer Systems Engineering. 'Headquarters and Laboratories at Gaithersburg, MD, unless otherwise noted; mailing address Washington, DC. 20234. 'Some divisions within the center are located at Boulder, CO 80303. COMPUTER SCIENCE & TECHNOLOGY: Maintenance Testing for the Data Encryption Standard Jason Gait Center for Programming Science and Technology Institute for Computer Sciences and Technology •National Bureau of Standards Washington, DC 20234 f W *> \ U.S. DEPARTMENT OF COMMERCE, Philip M. Klutznick Secretary Luther H. Hodges, Jr., Deputy Secretary Jordan J. Baruch, Assistant Secretary for Productivity, Technology and Innovation LI NATIONAL BUREAU OF STANDARDS, Ernest Ambler, Director 3 Issued August 1980 Reports on Computer Science and Technology The National Bureau of Standards has a special responsibility within the Federal Government for computer science and technology activities. The programs of the NBS Institute for Computer Sciences and Technology are designed to provide ADP standards, guidelines, and technical advisory services to improve the effectiveness of computer utilization in the Federal sector, and to perform appropriate research and development efforts as foundation for such activities and programs. This publication series will report these NBS efforts to the Federal computer community as well as to interested specialists in the academic and private sectors. Those wishing to receive notices of publications in this series should complete and return the form at the end of this publicaton. National Bureau of Standards Special Publication 500-61 Nat. Bur. Stand. (U.S.), Spec. Publ. 500-61, 28 pages (Aug. 1980) CODEN: XNBSAV Library of Congress Catalog Card Number: 80-600105 U.S. GOVERNMENT PRINTING OFFICE WASHINGTON: 1980 For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C. 20402 Price $2.00 (Add 25 percent for other than U.S. mailing) TABLE OF CONTENTS Page 1 . INTRODUCTION 1 1.1 Validation vs Maintenance Testing 2 1.2 The Maintenance Tests 3 1.3 The Values for the Parameters of the Test 6 2. DESCRIPTION OF THE DES ALGORITHM 6 2.1 The Permutations and E Operator 7 2.2 The S-boxes 7 2.3 The Key Schedule 8 2.4 Maintaining the Correctness of DES Devices .... 8 2.4.1 DES Tests 8 2.4.2 Relationship to Validation Tests 9 3. TESTING PHILOSOPHY 9 3.1 Stuck-faults in Cipher Feedback Mode 9 3.2 Generating the Pseudo-random Tests 10 3.3 Description of Tests 11 4. SUMMARY AND CONCLUSIONS 12 5. Appendix A: The DES Algorithm Specification 14 6. Appendix B: The Gram-Schmidt Algorithm 19 7. Appendix C: Pseudo-random Testing of Linear Devices . 21 -in- Digitized by the Internet Archive in 2013 http://archive.org/details/maintenancetestiOOgait Maintenance Testing for the Data Encryption Standard Jason Gait This publication describes the design of four maintenance tests for the Federal Information Pro- cessing Data Encryption Standard (DES) . The tests consist of an iterative procedure that tests the operation of DES devices by using a small program and minimum data. The tests are designed to be independent of implementation and to be fast enough to test devices during actual operation. The tests are defined as four specific stopping points in a general testing process and satisfy four testing requirements of increasing degree of completeness depending on the thoroughness of testing desired. Key words: Communications security; computer security; cryptography; data encryption standard; in-service testing; maintenance tests; Monte-Carlo testing; stuck-fault testing; test cases. 1. INTRODUCTION The Federal Information Processing Data Encryption Standard (DES) is the standard cryptographic algorithm for use within the Federal Government for protecting non- classified transmission and storage of computer data. The DES algorithm is normally implemented in hardware and com- mercial DES devices are presently available from eight dif- ferent sources. The National Bureau of Standards has vali- dated the designs of the various hardware implementations with a validation test, i. e., a collection of input-key- output triplets which, when applied as a test to a device, and if successfully executed, insures that the device being tested in fact correctly executes the DES algorithm. A Monte-Carlo test using random data is also a part of this test [8], -1 A small maintenance test, residing in read only memory and executed by the same microprocessor that controls the DES device provides a means of testing the operation of the DES hardware in the field. Since one criterion for a field test is that it be economical, the tests are designed so that only a partial test may be needed in a given applica- tion. The test is so designed that a full functional test can be executed if it is convenient and desirable to do so. The maintenance test provides results which are a com- bination of the validation test and of the Monte-Carlo test described in [8]. The maintenance test uses an initial fixed input-key pair and the resulting ciphertext is then fed back as input or as key, as in the Monte-Carlo test, and this cycling process is repeated. By simply checking the output of this process against four known results the test determines if the DES algorithm is properly functioning. A maximum of 192 cycles has been determined to test completely the DES device but three earlier check points are defined which result in specific partial tests. In all, four ca- tegories of tests have been defined. They range from a sim- ple test for stuck-faults of the 64 output bits of the DES to a complete functional test. 1.1 Validation vs Maintenance Testing The maintenance tests described here replicate the functionality of both the validation test and the Monte- Carlo test procedure used to validate implementations of the DES [8,9]. In fact, by taking advantage of the pseudo- random nature of the DES output, we are able to describe a smaller, more efficient test procedure that is equivalent to the test previously described in [8], although the extensive Monte-Carlo test is not reproduced. -2- 1.2 The Maintenance Tests The maintenance tests depend only on the functionality of the algorithm and not on any particular implementation. The tests can be performed with a short program whose two inputs consist of an initial plaintext and an initial key and whose output is a final ciphertext. The test program creates a cycling process that tests the complete func- tionality of the DES algorithm as well as testing for stuck-at-one and stuck-at-zero faults at the various input and output interfaces. Stuck-at-one or stuck-at-zero faults occur due to a circuit failure, e. g., an open circuit. The device is known to be performing correctly if the observed final ciphertext matches the expected result. The cycling process consists of a maximum of 192 encipherments and deci- pherments intermixed in such a way as to test all aspects of the algorithm. The execution of the test program requires little time and hence the test can be used on-line to exam- ine the functionality of a device in-service as well as for other testing purposes. The complete test is determined by the following re- currence relation: K x = 5555555555555555 P, = FFFFFFFFFFFFFFFF C. = E(K., P.) C i + 1 = E(K., C ) *i + 3 " ^i+2 P i+3 " C i where K . , P. and C. denote key, input and output at time n, with trie value of i determined from the equation i = 3(n-l)+l for n-1,2,3,..., TESTLENGTH. Here the symbol E denotes the DES encryption operation and D denotes the DES decryption operation. The initial values of key and plain- text, K. and P,, are 64 bit numbers represented in hexade- cimal notation with correct parity for each 8-bit byte of the key. The test can be used in any of four modes depending on the degree of certainty required and the time available to perform the test. In each of the four modes only the final ciphertext differs, initial plaintext and key remain the -3- same. Test 1: Tests all output bits for stuck-at-one and stuck- at-zero faults; the P and E matrices used by the DES algo- rithm are also tested. Test 2: Includes Test 1, tests the S-boxes and includes a test for stuck-faults at all the key and input bits except one input bit. Test 3: Includes Test 2, a complete test for stuck-faults and a test of the IP~ matrix. Test 4: Tests all aspects of the algorithm. The following table provides a concise display of the various tests, the number of iterations required for each test, the number of encryption or decryption operations per- formed during each test, the final output for each test and the specific properties of the DES algorithm that are tested during each test. -4- Table 1. Properties of the Four Maintenance Tests testl test2 test3 test4 i terations 64 enc/dec ops 9 18 24 192 final output BF1FF37B C46CC2CA 1DFCF1C8 44E84A9B 00B82CBB E58DBB9F 246E9DB9 C550381A props tested output stuck test 1 and faults, P, E S-boxes test 2 and complete input stuck test faults -5- 1.3 The Values for the Parameters of the Test The efficacy of the testing procedure depends largely on the effectiveness of the DES as a pseudo-random number generator [5]. The number of iterations needed to satisfy each test requirement could not be determined in advance. However an upper-bound value for TESTLENGTH was determined from a Markov chain model of the full testing procedure. The results were that if pseudo-random input vectors are presented to a linear device with n inputs, then the expect- ed number of tests required to test completely the device for sufficiently large n is approximately n+2. Since n is the minimum number required, the distribution has a very small standard deviation. Hence we need to examine at most n+3 or n+4 pseudo-random input vectors to be sure of obtain- ing a maximal linearly independent set (=basis) of appropri- ate dimension. See Appendix C for the details of the calcu- lation. 2. DESCRIPTION OF THE DES ALGORITHM The Federal Information Processing Data Encryption Standard published on January 15, 1977 [3] is a complex non-linesr ciphering algorithm that was designed for effi- cient hardware implementation. Although there are software implementations, they do not comply with the standard and are generally quite inefficient compared to hardware ver- sions [6]. The DES algorithm operates on 64 bits of input to produce 64 bits of output under the action of a 56-bit keying parameter. With the exception of initial and final permutations, the algorithm is a series connection of six- teen rounds. Each round uses 48 bits of the key in a se- quence determined by a key schedule. With the exception of this difference in the round keys, the sixteen rounds are identical to one another. Each round receives an input of 64 bits; the 32-bit right half is expanded by the linear operator E to 48 bits and the result is mod 2 added to the round key; the 48 bit sum is divided into eight 6-bit blocks, each of which determines a 4-bit S-box entry; the resulting 32 bits are added mod 2 to the left half and the two halves are interchanged', thus producing 64 bits of out- put for the round. Sixteen rounds connected in series, each using a different round key as determined by the key schedule, together with initial and final permutations make up the DES algorithm. Despite its complexity the DES is ca- pable of operating at high speed when implemented in hardware. For example, an encryption or decryption of one -6- 64-bit block on the NBS DES unit takes 9 microseconds. Ap- pendix A contains a complete functional description of the DES algorithm parameters, i. e., permutations, S-boxes and key schedule. 2.1 The Permutations and E Operator The role of the permutation P is to mix thoroughly the data bits. The operator E expands its 32 bit input to . a 40 bit output that is added mod 2 to the round key. The permu- tations in the key-schedule, PCI and PC2, intermix the key bits among the round keys in such a way as to equalize key- bit utilization. No key bit is used more than 15 times nor less than 12 times. The initial and final permutations, IP and IP , are byte oriented for efficient hardware implemen- tation. Each permutation is a linear operator, and so can be thought of as an n x m matrix and can be validated complete- ly if it operates correctly on an appropriate maximal linearly independent set of input vectors, i. e., a suitable basis. 2.2 The S-boxes The non-1 stitute an im the S-boxes is [1,2] . Each of ized as a 4x16 number, repre connection of in a single select a row a correspond ing Each row in ea so no entry is inear subs portant pa to ensure the eight matrix. E sented as eight S-bo S-box is nd four se row and ch S-box i repeated titution tabl rt of the alg that the alg S-boxes cont ach entry i 0-15, so the xes is 32 bit selected by lect a column column is the s a permutati in any one ro es, or S or ithm. orithm i ains 64 e s a fou output o s . A par six bits . The output f on of the w. -boxes The pu s not ntr ies r bit f the ticula , two entry or tha numbe , con- rpose of 1 inear , organ- binary parallel r entry of which in the t input, rs 0-15, -7- 2.3 The Key Schedule The pu thorough in key schedul fied by p independent process us tion uses r required f tant to the that simila substantial rpose of the key sched termixing of the key bits e is linear, so its implem resenting 56 basis vector set for this operator) as es left shifts in the key ight shifts, so an additio or testing. The key sched security of the algorithm r algorithms without simil ly weaker even if they hav ule is to provide a for the algorithm. The entation can be veri- s (= a maximal linearly keys. The encryption schedule while decryp- nal 56 decryptions are ule is extremely impor- : it has been shown [4] ar key schedules may be e much larger keys. 2.4 Maintaining the Correctness of DES Devices The test program verifies the correct operation of an implementation by performing one of several optional series of tests on the device during operation. The pseudo-random tests have been examined to be sure that a basis of vectors is presented to each of the matrix operators in the algo- rithm, thus verifying their correct implementation as linear operators, and to exercise every element in each S-box. 2.4.1 DES Tests. The tests are designed to assure the correctness of each of the following components of the algo- rithm (see Appendix A): 1. Initial permutation, 2. Inverse permutation, 3. Expansion matrix, E 4. Data Permutation, P 5. Key Permutation, PCI 6. Key Permutation, PC2 7. Substitution tables: 8. Mod 2 adders IP IP -1 In addition the tests protect against the possibility of stuck-faults at the interfaces between any of the above ele- ments as well as at the input, key and output of the DES it- self . -8- 2.4.2 Relations test of DES d discrete input- tered into th operation is pe known correct rithm, e . g . , P presenting to The maintenance on the pseudo- a basis, but no each linear el they are tested in such a wa tested simultan information pr location of a f simply to ver rather than to hip to Validation Tests evices consists of oper key-output triples. The e DES device, an en rformed and the result output. Each linear a , E, and so forth, is t it a standard unit ba test performs an equiv random nature of the DE t necessarily the stan ement of the algorithm, completely. The mainte y that various aspect eously and the tester d ovided by the validat ailure. However the pur ify that the DES devic isolate the location of ._ The NBS validation ating on a sequence of input and key are en- cryption or decryption is compared with the spect of the DES algo- ested independently by sis to be operated on. alent test by relying S algorithm to present dard unit basis, to thereby insuring that nance test is set up s of the algorithm are oes not receive the ion test regarding the pose of these tests is e is working correctly fa ilures. 3. TESTING PHILOSOPHY The DES h many different DES should be a to implementat designed only t self at the we output. While maintenance, i maintenance tes It was also pherments and d more practical between transmi as been implement techniques. To b pplicable to all ion. The mainte o test the functi 11 defined interf the NBS validatio t does not meet t for minimizing desired to minimi ecipherments duri in an on-line ssions. ed by many vendors using e most useful a test for the DES devices without regard nance tests are therefore onality of the algorithm it- aces, such as input, key and n test could be used for the desirable criterion of a the amount of data stored, ze the total number of enci- ng the test to make the test environment during intervals 3.1 Stuck-faults in Cipher Feedback Mode One of the modes of operation of the DES is cipher feedback, where the output of the DES is added mod 2 to the plaintext to produce ciphertext. If the output of the DES is subject to stuck-faults, either at one or at zero, then some part of the plaintext, or its complement, is being transmit- ted in the clear. It is therefore desirable that the device be tested for stuck-faults, preferably during all encipher- ment operations, while being used in cipher feedback mode. -9- 3.2 Generating the Pseudo-random Tests Since the DES is known to be a good pseudo-random number generator [5], the maintenance test was designed to use the output of the DES fed back as data or as key-text alternatively. Both encryption and decryption operations are used in order to exercise all parts of the algorithm. When all the cycles of each test have been completed, the final output is compared with a single stored value. If the two values are the same, then the device has passed the test, otherwise the device should be rendered inoperable. The following program is used to do this: key = 5555555555555555 input = FFFFFFFFFFFFFFFF for(n=l; n>i Test 2 Parameters: TESTLENGTH = 6 LASTCIPHER = 1DFCF1C844E84A9B Test 3 Parameters: TESTLENGTH = 8 LASTCIPHER = 00B82CBBE58DBB9F Test 4 Parameters: TESTLENGTH = 64 LASTCIPHER = 246E9D89C550381A 3.3 Description of Tests Test 1 uses three cycles of the program, corresponding to nine encryptions or decryptions. Test 1 is useful as a maintenance test for the DES when used in cipher feedback mode to ensure that no stuck-faults in the output will ex- pose plaintext. It is a short test and can be practically executed on-line between transmissions. Note that for this test each bit of the output is both zero and one at least once. Test 2 pherments o pletely the stuck fault text bit 54 test) . Two required to 3 tests fo algorithm el boxes, the outputs of t uses si r deci S-boxes s and a is stuc more c unstick r stuc ement , shi f ts he mod x cycl pherme , the lmost k-at-o ycles, data k-faul i . e. , in 2 adde es, corresponding to eighteen enci- nts, which are enough to test com- P and E matrices, all outputs for all inputs for stuck-faults (plain- ne throughout this part of the actually five more operations, are bit 54, and carry out test 3. Test ts at the input and output of every IP, P, E, IP" 1 , PCI, PC2, the S- the key-schedule and the inputs and rs. Test 4 is a complete test of the functionality of the algorithm. The verification of both tests 2 and 4 requires examination of the inputs to each of the linear elements of the algorithm to ensure that a basis, i. e., a maximal linearly independent set of vectors of appropriate dimen- sion, is presented to each, thus ensuring that all matrix entries are fully exercised. The DES validation test -11- presents standard unit basis vectors to these linear ele- ments, while the maintenance test presents random inputs. Thus the inputs have been checked, not for the standard unit basis, for which we would have to wait a long time, but for any basis of the proper dimension. This is equivalent to the standard unit basis in terms of testing linear elements. A variant of the Gram-Schmidt orthogonal ization process was used to do this, as described in Appendix B. The applica- tion of this process shows that the first 32 vectors applied to P are linearly independent, thus testing P completely; this corresponds to just two encipherments, since P is used 16 times during each encryption or decryption operation, or one cycle of the program. Similarly, the first 34 vectors applied to E contain a maximal linearly independent set (the 17th and 33rd vectors are dependent on the others); again the first cycle of the program suffices to test E. Hence test set 1 for stuck-faults tests P and E as well. The first 66 encipherments, corresponding to 22 cycles of the program, test completely IP~ ; the first 87 encipher- ments, corresponding to 29 program cycles, test the entire key schedule for both encipherment and decipherment; and 64 complete cycles are required to test IP. It is this re- quirement of testing the initial permutation that fixes the value of TESTLENGTH for test 4 at 64, or 192 encipherments or decipherments. 4. SUMMARY AND CONCLUSIONS A variety of maintenance tests for DES devices in the field have been described, ranging from testing for stuck- faults in the output to a full test of the DES device. The tests are simple and efficient and can be executed from a small ROM program on-board with the DES. Recommended testing environments include: 1. manufacturer's assembly-line checkout for DES devices, 2. user acceptance test for newly acquired and recently repaired devices, 3. field-maintenance service testing, and -12- 4. in-service testing of DES devices to maintain tegrity of the encryption system. the m- Users of DES devices can choose one of the four tests described, depending on their evaluation of which test is most convenient and meaningful in the given operational en- vironment. However test 4, the complete functionality test, encompasses all the other tests and is hence the best test to use whenever practicable. During each test there is no verification of intermedi- ate values, just a check of the final output for correct- ness. Thus there is a possibility for undetected, self- cancelling double errors that these tests are not designed to detect. Many such errors will be detected if they occur in different functional units of the DES, but the user of these tests should be alert to the possibility, however re- mote, that such errors might not be detected. -13- 5. Appendix A: The DES Algorithm Specification For the convenience of the reader, this appendix con- tains a complete specification of the parameters involved in the definition of the DES algorithm. The DES acts on a 64 bit block of plaintext, which is first permuted by IP: IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 (e. g., bit one of the output is bit two is bit 50, etc.) 58 of the input and bit The result is separated into two 32 bit registers, L and R, and then passed through the sixteen rounds. The final 64 bit result is operated on by the inverse of IP, IP~ : IP -1 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 2 6 33 1 41 9 49 17 57 25 The round keys K are determined by the key schedule. There are three parameters to be specified, PCI, PC2 and the shift -14- schedule: PCI 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 4 6 33 30 2 2 14 6 61 53 45 37 29 21 13 5 28 20 12 4 PC 2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 2 6 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 4 6 4 2, 50 36 29 32 and the shift schedule is: •15- Iteration 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Number of shifts For a single round the expansion operator E and the permuta- tion P need to be specified: 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 2 21 20 21 22 23 2 4 25 24 25 26 27 28 29 28 29 30 31 32 1 16 29 1 5 2 32 19 22 7 12 15 18 8 27 13 11 20 28 23 31 24 3 30 4 21 17 26 10 14 9 6 25 -16- There remain only the S-boxes: 14 4 13 1 2 15 11 8 3 10 6 12 5 o 7 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 15 12 8 2 4 9 1 7 5 11 3 14 10 6 13 15 1 8 14 6 11 3 4 S 2 9 7 2 13 12 5 10 3 13 4 7 15 2 8 14 12 1 10 6 9 11 5 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 7 12 5 14 9 10 9 14 5 3 15 5 1 13 12 7 11 4 2 8 13 7 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 11 1 2 12 5 10 14 7 1 10 13 6 9 8 7 4 15 14 3 11 5 2 12 7 13 14 3 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 3 4 7 2 12 1 10 14 9 10 6 9 12 11 7 13 15 1 3 14 5 2 8 4 3 15 6 10 1 13 8 9 4 5 11 12 7 2 14 2 12 4 1 7 10 11 6 8 5 3 15 13 14 9 14 11 2 12 4 7 13 1 5 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 J 14 11 8 12 7 1 14 2 13 6 15 9 10 4 5 3 -17- S 6 12 1 10 15 9 2 6 8 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 11 3 8 9 14 15 5 2 8 12 3 7 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 8 13 4 11 2 13 11 1 4 11 6 11 13 14 7 13 8 15 4 12 1 8 1 7 10 13 10 14 7 3 14 10 9 12 3 15 5 7 12 8 15 5 2 14 10 15 1 6 2 12 13 1 7 2 2 15 11 1 8 13 4 14 6 10 9 4 15 3 12 10 11 7 14 1 4 2 13 10 12 15 9 5 6 12 3 6 10 9 14 11 13 5 15 3 14 3 5 12 7 9 2 5 8 6 11 The reader is referred cation of these parameters. to [3] for the official specifi- -18- 6. Appendix B: The Gram-Schmidt Algorithm Given an arbitrary set ^,, ^ 2 , ^^, will kn' k,,... of n-dimensional vectors, we will constructs maximal linearly-independent subset of vectors using the Gram-Schmidt process. The method is to assume that the vectors k. are linearly independent and to use the Gram-Schmidt process to construct an orthogo- nal set as follows. We will use the notation for a column vector, for inner product and |x| for the norm of a vector. Let = k 2 = k 2 - /l Uj | u l u~ = u-, = k 3 - /| u 1 | Uj^ - /iu 2 r u 2 etc . If at any stage in this process then omit k. and u^ is equal to zero continue. This process will construct a linearly independent subset of the original set, which may not necessarily be maximal, but if the original set is suf- ficiently large the process will terminate after n vectors have been selected, and the subset is thus maximal. The required theorem is as follows. Theorem. j is the also depends coefficient of Thus the sum on u. in the J expansion of k. in the vectors u • . the terms subtracted from k. in the Gram- Schmidt process actually equals k. , so u. = 0. -19- In this form the Gram-Schmidt test is used to ensure that sufficiently many pseudo-random vectors have been presented to each linear element of the DES to guarantee complete testing. Appendix C addresses the question of how many random vectors must be examined on the average in order to ensure that we have a maximal linearly independent set. -20- 7. Appendix C: Pseudo-random Testing of Linear Devices A Markov-chain model is used to compute the mean and standard deviation of the number of pseudo-random input vec- tors that must be presented to a linear device to ensure that a basis has been presented to the device, thus testing it completely. The f non-zero set, while block. obtain ano set. Howev zero block ar ises , s vector air those aire lem will b is a fini minate [7; basis. irst block o block. In th in the firs nee we hav ther one, in er we may al With two ince the nex eady in the ady in the s e represente te, ergodic theorem 3 . 3 f input may be e second case t t we repeat unt e a non-zero bl which case we so obtain the s vectors in the t vector may be set or a new ve et. In general d by a k+1 stat absorbing Marko . 5] , hence , in either a ze he block will il we obtain a ock, we repeat have two vecto ame block agai set a new zero, or a re ctor in the , a k-dimensio e Markov chai v process, so due course, we r o or a be in the non-zero until we rs in the n, or the s i tua t ion peat of a span of nal prob- n. This must ter- obtain a Theorem 1. For the Markov chain described above, the transi- tion probability state i to state i is 1/2 (k-i) . Proof. Let N(i) denote the number of vectors not in the linearly independent set and not zero, but in the span of the set. It suffices to show that N(i) = 2 1 - i - 1. It's immediate that N(i) = 1 + j = 2, i-D 0, where () denotes the en j at a time, and The inductive step 1.2.6DO) ] . number of combinations of i things tak- the argument follows by induction on i. uses the additive formula [10; In the next theorem we compute the mean number of transitions for this Markov chain to be absorbed. Theorem 2. The expected number of transitions to absorption for the above Markov chain is, for k>l, E.= S.+ [l/(2 k - 1)] + 1, -21- where S k = SUM(i=l, k-l)[ 2 1 /(2 1 - 1)]. Proof. By induction on k. For the case k=2, we have 4/3 2 (I-Q)" 1 2, so, assuming a start with a non-zero element, the expected number of transitions to absorption S. is the sum of the last row of the fundamental matrix, or Z. The inductive step follows from the definition of the Markov chain. Now E. is equal to one for the first state plus the probability or starting without a non-zero element times the mean number of transitions to absorption given a start without a non- zero element plus the probability of starting with a non- zero element times the mean number of transitions given a start with a non-zero element, or E k = S k + [l/(2 k -1)] + 1, where all the states except the first are lumped to give a two state Markov chain with transition matrix 1 1-1/2 K l/2 k with Q = 1 - l/2 k , so the fundamental matrix is 2 k /(2 k -l). This is precisely the mean number of transitions required to get out of the zero state. We now derive an asymptotic estimate to the above formula. Theorem 4. The average number of vectors that must be exam- ined to obtain a basis is asymptotically log n + c + 0(l/n), where k is the number of non-zero vectors required to define the system, n = 2 and c is a constant. Proof. Rewrite S, as S k = SUM(i=l, k-l){l/[l- (1/2 1 )]}, to see that, apart from the first few terms, each new term just adds one as k increases, so asymptotically, for some constant c, we have S k =c+k, and we see that the asymptotic value = log n + c + 0(l/n). The value of c is given in [11; 5. 2. 3 (19) ] , the computation being attributed to J. W. Wrench, as approximately 1.606. -22- Hence if the dimension of the systen is k, we need to look at k+2 random vectors on the average to obtain a maxi- mal linearly independent sot. We now compute the standard deviation, realizing that the difference between the average and the minimum value of the parameter is just 1.606, so the standard deviation must be smaller than this. Reference to [7; theorem 3.3.5] shows that the standard deviation is approximately 1.414 for all values of k, as expected. Thus the distribution has a very small variance and we expect to examine about k+3 or k+4 vectors to obtain a k-dimensional basis in a set of k- dimensional random vectors, provided the dimension k is suf- ficiently large. -2 3- REFERENCES 1. Meyer, C, Enciphering Data for Secure Transmission, Com- puter Design, (April, 1974)129-34. 2. Meyer, C. and W. Tuchman, Pseudo-random Codes Can Be Cracked, Elect. Design, vol. 23(1972)74-5. 3. Data Encryption Standard, FIPS PUB 45, Jan. 15, 1977 4. Grossman, E. and B. Tuckerman, Analysis of a Feistel-like Cipher Weakened by Having No Rotating Key, IBM Rpt c6375, 1977. 5. Gait, J., A New Non-Linear Pseudo-random Number Genera- tor, IEEE Transactions on Software Engineering, Sept., 1977. 6. Bright, H. and R. Ennison, Cryptography Using Modular Software Elements, National Computer Conf., 1975, 113-23. 7. Kemeny, J. and J. Snell, Finite Markov Chains, Van Nos- trand, Princeton, N J , 1965. 8. Gait, J., Validating the Correctness of Hardware Imple- mentations of the NBS Data Encryption Standard, NBS Special Pub. 500-20, 1977. 9. Gait, J., Encryption Standard: Validating Hardware Tech- niques, NBS Dimensions, July, 1978, 22-23. 10. Knuth, D. , Fundamental Algorithms, Addison Wesley, 1958, Reading, Mass. -24- 11. Knuth, D. , Sorting and Searching, Addison Wesley, Reading, Mass. 1973, -25- NBS-114A (REV. 9-76) :-.w:~^ :,-■-■ U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA SHEET 1. PUBLICATION OR REPORT NO. NBS SP 500-61 5. Reciptent's Accession No. .•y ■._';'. .v;; :-:;r ; x ;.:. -. , 4. TITLE AND SUBTITLE COMPUTER SCIENCE & TECHNOLOGY: MAINTENANCE TESTING FOR THE DATA ENCRYPTION STANDARD 7. AUTHOR(S) Jason Gait 5. Publication Date August 1980 T~5T7T"" 8. Performing Organ. Report No. 9. PERFORMING ORGANIZATION NAME AND ADDRESS NATIONAL BUREAU OF STANDARDS DEPARTMENT OF COMMERCE WASHINGTON, DC 20234 asfc /Work Unit No. 11. Contract/Grant No. 12. SPONSORING ORGANIZATION NAME AND COMPLETE ADDRESS (Street, City, state, zip) Same as above 13. Type of Report & Period Covered Final ^Spfensoring Age^cy'Sep! 15. SUPPLEMENTARY NOTES Library of Congress Number: 80-600105 | | Document describes a computer program; SF-185, FIPS Software Summary, is attached. 16. ABSTRACT (A 200-word or less factual summary of most significant information. If document includes a significant bibliography or literature survey, mention it here.) This publication describes the design of maintenance tests for the Federal Information Processing Data Encryption Standard (DES) . The test consists of an iterative procedure that completely tests the operation of DES devices by using a small program and minimum data. The tests are designed to be independent of implementation and to be fast enough to test devices during actual operation. The tests are defined as four stopping points in a general testing process, and satisfy four testing requirements depending on the thoroughness of testing desired. 17. KEY WORDS (six to twelve entries; alphabetical order; capitalize only the first letter of the first key word unless a proper name; separated by semicolons) Communications security; computer security; cryptography; data encryption standard; in-service testing; maintenance tests; Monte-Carlo testing; stuck- fault testing; test cases; validation vs maintenance 18. AVAILABILITY [5Q Unlimited | | For Official Distribution. Do Not Release to NTIS jjT] Order Fr ° m Su P- ° f Doc -. u - s - Government Printing Office, Washington, DC 20402 n° rder From National Technical Information Service (NTIS), Springfield, VA. 22161 19. SECURITY CLASS (THIS REPORT) UNCLASSIFIED 20. SECURITY CLASS (THIS PAGE) UNCLASSIFIED 21. NO. OF PRINTED PAGES 29 22. Price $2.00 USCOMM-DC