/&*.£00-&> COMPUTER SCIENCE & TECHNOLOGY: VALIDATING THE CORRECTNESS OF HARDWARE IMPLEMENTATIONS OF THE NBS DATA ENCRYPTION STANDARD *<°' e * \ \ V*u of * NBS Special Publication 500-20 U.S. DEPARTMENT OF COMMERCE National Bureau of Standards NATIONAL BUREAU OF STANDARDS The National Bureau of Standards 1 was established by an act of Congress 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 pro- mote public safety. The Bureau consists of the Institute for Basic Standards, the Institute for Materials Research, the Institute for Applied Technology, the Institute for Computer Sciences and Technology, the Office for Information Programs, and the Office of Experimental Technology Incentives Program. THE INSTITUTE FOR BASIC STANDARDS provides the central basis within the United States of a complete and consist- ent system of physical measurement; coordinates that system with measurement systems of other nations; and furnishes essen- tial services leading to accurate and uniform physical measurements throughout the Nation's scientific community, industry, and commerce. The Institute consists of the Office of Measurement Services, and the following center and divisions: Applied Mathematics — Electricity — Mechanics — Heat — Optical Physics — Center for Radiation Research — Lab- oratory Astrophysics 2 — Cryogenics 2 — Electromagnetics 2 — Time and Frequency 8 . THE INSTITUTE FOR MATERIALS RESEARCH conducts materials research leading to improved methods of measure- ment, standards, and data on the properties of well-characterized materials needed by industry, commerce, educational insti- tutions, and Government; provides advisory and research services to other Government agencies; and develops, produces, and distributes standard reference materials. The Institute consists of the Office of Standard Reference Materials, the Office of Air and Water Measurement, and the following divisions: Analytical Chemistry — Polymers — Metallurgy — Inorganic Materials — Reactor Radiation — Physical Chemistry. THE INSTITUTE FOR APPLIED TECHNOLOGY provides technical services developing and promoting the use of avail- able technology; cooperates with public and private organizations in developing technological standards, codes, and test meth- ods; and provides technical advice services, and information to Government agencies and the public. The Institute consists of the following divisions and centers: Standards Application and Analysis — Electronic Technology — Center for Consumer Product Technology: Product Systems Analysis; Product Engineering — Center for Building Technology: Structures, Materials, and Safety; Building Environment; Technical Evaluation and Application — Center for Fire Research: Fire Science; Fire Safety Engineering. THE INSTITUTE FOR COMPUTER SCIENCES AND TECHNOLOGY conducts research and provides technical services designed to aid Government agencies in improving cost effectiveness in the conduct of their programs through the selection, acquisition, and effective utilization of automatic data processing equipment; and serves as the principal focus wthin the exec- utive branch for the development of Federal standards for automatic data processing equipment, techniques, and computer languages. The Institute consist of the following divisions: Computer Services — Systems and Software — Computer Systems Engineering — Information Technology. THE OFFICE OF EXPERIMENTAL TECHNOLOGY INCENTIVES PROGRAM seeks to affect public policy and process to facilitate technological change in the private sector by examining and experimenting with Government policies and prac- tices in order to identify and remove Government-related barriers and to correct inherent market imperfections that impede the innovation process. THE OFFICE FOR INFORMATION PROGRAMS promotes optimum dissemination and accessibility of scientific informa- tion generated within NBS; promotes the development of the National Standard Reference Data System and a system of in- formation analysis centers dealing with the broader aspects of the National Measurement System; provides appropriate services to ensure that the NBS staff has optimum accessibility to the scientific information of the world. The Office consists of the following organizational units: Office of Standard Reference Data — Office of Information Activities — Office of Technical Publications — Library — Office of International Standards — Office of International Relations. 1 Headquarters and Laboratories at Gaithersburg, Maryland, unless otherwise noted; mailing address Washington, D.C. 20234. 2 Located at Boulder, Colorado 80302. COMPUTER SCIENCE & TECHNOLOGY: Validating the Correctness of Hardware Implementations of the NBS Data Encryption Standard Jason Gait Systems and Software Division Institute for Computer Sciences and Technology National Bureau of Standards Washington, D.C. 20234 ^ T 0F e« \ 4?A % ^e4u of *' % V) J c o U.S. DEPARTMENT OF COMMERCE, Juanita M. Kreps, Secretary Dr. Sidney Harman, Under Secretary Jordan J. Baruch, Assistant Secretary for Science and Technology NATIONAL BUREAU OF STANDARDS, Ernest Ambler, Acting Director Issued November 1977 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 publication. National Bureau of Standards Special Publication 500-20 Nat. Bur. Stand. (U.S.). Spec. Publ. 500-20, 46 pages (Nov. 1977) CODEN: XNBSAV Library of Congress Catalog Card Number: 77-16067 U.S. GOVERNMENT PRINTING OFFICE WASHINGTON: 1977 For sale by the Superintendent of Documents. U.S. Government Printing Office, Washington, D.C. 20402 Price $1.60 - Stock No. 003-003-01861-9 TABLE OF CONTENTS Page 1 . INTRODUCTION 1 2. DESCRIPTION OF ALGORITHM 2 2. 1 The Permutations 3 2 . 2 The S-boxes 3 2.3 The Key Schedule 4 3 . COMPONENTS OF THE TEST BED 4 4. THE DEVICE VALIDATION PROCEDURE 13 4.1 The Device/Test-bed Interface 13 4.2 Validating the Implementation 14 4.2.1 Test Procedure 14 4.2.2 DES Test Set 15 4.3 Monte-Carlo Testing 16 4.4 Procedure for Requesting Validation Service .. 18 5. PREPARATION OF DEVICE VALIDATION REPORT 20 6. Appendix A: The DES Algorithm Specification 22 7. Appendix B: The DES Test Set 28 8. Appendix C: Interface Specifications 34 -in- LIST OF FIGURES page 1. One Round of DES 6 2 . A Sample S-box 7 3 . The Key Schedule 8 4 . Sample Round Outputs 9 5. The Testbed 10 6. Chip and Testbed 11 7. Sample Validation Report 12 Al. Sixteen Rounds of DES 27 CI. Interface Line Specifications 36 C2. Interface Logic Diagram 37 C3. Interface Input Byte Numbering 3 8 C4. Interface Output Byte Numbering 3 9 i -IV- Validating the Correctness of Hardware Implementations of the NBS Data Encryption Standard Jason Gait This publication describes the design and operation of the NBS testbed that is used for the validation of hardware implementations of the Federal Information Processing Data Encryption Standard (DES). A particular implementation is verified if it correctly performs a set of 291 test cases that have been defined to exercise every basic element of the algorithm. As a further check on the correctness of the implementation an extensive Monte-Carlo test is performed. This pub- lication includes the full specification of the DES algorithm, a complete listing of the DES test set and a detailed description of the interface to the testbed. Key words: Communications security; computer security; cryptography; encryption standard; interface requirements; Monte-Carlo testing; testbed; test cases; validating correctness. 1. INTRODUCTION test of t dard tat i perf The down prog manu is i DES the The bed he F (D on o ormi NBS str e ram fact nter unit NBS Nat io facil ederal ES) [3 f the ng an DES un am-loa ( curre urer s faced and i DES un nal ity Inf ]. DES en it i ded ntly ubmi to a ts c it. Burea to va ormat The f built crypt s con with runn t s a micr orrec The d u of lida ion acil by ion trol th ing DES ocom tnes evic Sta te m Proc ity NBS or d led e t on a devi pute s is e an ndard anuf a essin inclu in TT ecryp by a est PDP ce f o r in eval d the s has cture g Dat des a L log t ion micr progr -1 1/4 r val paral uated NBS built r ' s imp a Encry hardwa ic and in 8 mi ocomput am by a 5 ** idation lei wi by com DES un a har lementa pt ion re impl capabl cro-sec er , whi t ime-s ) . Wh , the d th the par ison it are dware tions Stan- emen- e of onds . ch is hared en a evice NBS with run ** The designations of computer products contained in this report are included for technical accuracy and completeness. The National Bureau of Standards does not endorse the products of any particular computer manufacturer . 1- simultaneously and synchronously as the test cases are puted . com- Nineteen encryptions and comparisons are required to fully exercise the non-linear substitution tables, or S- boxes. The key schedule is exercised by presenting 56 basis vectors for both encryption and decryption, an additional 112 tests. The initial and final permutations are tested by presenting to each permutation 64 basis vectors, for 128 more tests during which the expansion operator E is automat- ically verified. The permutation P is verified by performing 32 more encryptions. Thus, a total of 235 encryptions and 56 decryptions are used in the DES test set. At his option, a manufacturer of a DES implementation may provide an interface to the DES testbed when he submits his device for validation, or NBS will construct the inter- face from a full specification of device characteristics provided by the manufacturer. If the submitter elects to provide his own interface, he should design it in accordance with the specifications given in this document. DESCRIPTION OF ALGORITHM The Standard non-linea to effic been soft standard to hardwa bits of p action of initial connect io figure 1 determine dif f erenc cal to on bits; the tor E to round ke blocks, e resulting two halve put for Fede publ r cip ient ware and re ve laint a 56 and n of Ea d by e in e ano 32-b 48 bi y; t ach o 32 b s are the r ral In ished her ing hardwa impleme they a rsions ext to -bit ke final sixteen ch roun a key s the rou ther . it righ ts and he 48 f which its are interc ound. S formation on Januar algorithm re impleme ntations , re general [6]. The produce 64 ying param permutatio rounds , o d uses 48 chedule. W nd keys, t Each round t half is the result bit sum determine added mod hanged, th ixteen rou Processing Data Encryption y 15, 1977 [33 is a complex that was designed with a view ntation. Although there have they do not comply with the ly quite inefficient compared DES algorithm operates on 64 bits of ciphertext under the eter. With the exception of ns , the algorithm is a series ne of which is depicted in hits of the key in a sequence ith the exception of this he sixteen rounds are identi- receives an input of 64 expanded by the linear opera- is mod two added to the is divided into eight 6-bit s a 4-bit S-box entry; the two to the left half and the us producing 64 bits of out- nds connected in series, each -2- 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 64-bit block on the NBS DES unit takes 6 micro-seconds. Guidelines on the proper usage of the DES are published in [8]. An example of round-by-round encryption for a given key and plaintext is shown in figure 4. Appendix A contains a complete functional description of the DES algorithm parame- ters, i. e., permutations, S-boxes and key schedule. 2.1 The Permutations Th data bi Most of hardwar permuta compute time to forming put to The pe S-box s The pe among t ut il iza than 12 e ro ts s the e r tion r o tak a p a 48 rmut ubst rmut he r tion t im le o o th per eali s ar utpu e ad ermu bit atio itut atio ound . . . n es . f th ey c muta zati e by ts vant tati out n P ion ns key o ke e per annot t ions on . te or data age o on , t put t inte in a in th s in y bit muta be hav In p ient to f th he o hat rmix comp e ke such is t ions traced e been art icu ed , an the DE is f ea perato is add es the lex wa y-sche a way used m is t bac de lar , d th S ha ture r E ed m bit y to dule as ore o tho k thr signe the e co rdwar . In expan od 2 s tha prev inte to than roug ough d f init ntro e ei addi ds i to t t re ent rmix equa 15 t hly the or ial llin ght tion ts 3 he r suit bit the lize imes mix S-b effi and g m bits to 2 bi ound fro tra key ke nor the oxes . cient final icro- at a per- t in- key . m the cing. bits y-bit less Each permutation is a linear operator, and so can be thought of as an n x m matrix and can be completely validat- ed if it operates correctly on an appropriate set of basis vectors. The set of tests for the permutation operators is founded on this principle, and the test cases have been con- structed to present a complete set of basis vectors to each operator . 2.2 The S-boxes The non-linear substitution tables, or S-boxes, con- stitute the most important part of the algorithm. The pur- pose of the S-boxes is to ensure that the algorithm is not linear, and hence too weak to stand up under cryptanaly tic attack [1,2]. Each of the eight S-boxes, such as is shown in -3- figure 2, contains 64 entries, organized as a 4x16 matrix. Each entry is a four bit binary number, represented as 0-15 in figure 2, so the output of the parallel connection of eight S-boxes is 32 bits. A particular entry in a single S-box is selected by six bits, two of which select a row and four select a column. The entry in the corresponding row and column is the output for that input. Each row in each S-box is a permutation of the numbers 0-15, so no entry is repeated in any one row. There is no obvious small set of inputs that could be used to verify the S-boxes, so an extensive series of Monte-Carlo experiments was performed to discover a rela- tively small set of inputs that would exercise every S-box entry at least once. Nearly 200 separate trials were made, and among these were several test sets of 19 inputs which exercised every S-box entry. One of these sets is used as the DES test set for the S-boxes. 2.3 The Key Schedule thor 3 sh roun is 1 ing comp on on r quir to t simi weak The ough ows h d ke inear 56 aring left ight ed to he se lar er , e purp inte ow t ys f , so basi wit shi shif tes curi algo ven ose rmix he k rom its s v h kn fts ts , t th ty o rith if t of ing ey s the imp ecto own in t so a is . f th ms w hey the of t ched 56-b leme rs outp he k n ad The e al i tho have ke he k ule it e ntat as k ut . ey s diti key gori ut k muc y s ey b dete ncry ion eys, The ched onal sche thm : ey s h la ched its rmin pt io can enc encr ule , 56 dule it ched rger ule for es t n ke be v rypt ypti but de is has ules key is to each ro he six y. The erif ied ing kno on proc decryp cry ptio extreme been sh are su s . pro und . teen key s by p wn in ess tion ns a ly im own [ bstan vide a Figure 48-bit chedule r esent- put and depends depends re re- portant 4] that stial ly 3. COMPONENTS OF THE TEST BED The data encryption testbed has been established within the Institute for Computer Sciences and Technology at the National Bureau of Standards. In order to provide a valida- tion service for DES implementations, the testbed was -4- conceived and developed as a joint effort of ICST's Systems and Software Division and the Computer Systems Engineering Division . The data encryption testbed was developed in three phases. During phase one the DES algorithm was implemented in readily available TTL hardware technology. Two units are presently in operation. Phase two incorporated these units in a communication channel between a high speed computer terminal and the 1CST Computer Facility. A microcomputer is used to interface the NBS DES unit to the data communica- tions channel, as in figure 5. Phase three provided a method of validating commercial data encryption devices implement- ing the DES. algo perf and unlo the ment vali a mi ice oper pute usin a s perm test oper soft in-h The rith orms tak ad c ord at io dati croc an ator r ( g th mall it d da ator ware ouse mos m i an es iphe er o ns . on o ompu d i • s t PDP- e UN mon owns ta ' s t wa cro t impo mpleme encryp 2 6 mi rtext . f 30-1 Figure f a ma ter , t t s in ermina 1 1/45) IX ope i tor p tr eam- f rom ermina s writ SS-3SS rtan nted tion cro- Thi 00 m 6 s nuf a he N terf 1 (C . Th rati rogr load ( P 1. T ten o m W 1 t com in or d secon s is illi- hows cture BS DE ace RT) a e lat ng sy am in ing o DP-1 1 he cu and c ponent stand ecrypt ds to in con second the DE r ' s DE S unit to th nd a c ter op stem . r ead- f the /45) rrent ompile of ard ion load tras s fo te de th m S S > e onne erat The only va file vers d on the t TTL 1 in ei key t to r kno stbed vice . e pro icroc ct ion es in micr memo lidat s un ion o the estbe ogic . gnt m or pi execu wn so set The priet omput to t time ocomp ry t h ion der c f th PDP-1 d is Th icro aint tion f twa up tes ary er he -sha uter at i soft ontr e v 1/45 the is d -sec ext t im re i for tbed DES port NBS ring con s us ware ol o alid usi DES evice onds , or to es on mple- the uses dev- , an com- mode tains ed to and f the ation ng an -5- HD— *4 *- R n+1 S-boxes ^ L n+1 Figure 1 . One of sixteen rounds of the DES. The sixteen rounds are connected in series and have an initial and final permutation . A key schedule determines the round keys -6- Figure 2: One of the eight S-boxes in the DES. An S-box en- try is determined by a six bit input, four of which deter- mine a column and two determine a row. The output is the four bit S-box entry specified by the row and column. The eight S-boxes are connected in parallel, and are used in each of the sixteen rounds of the DES. s l 14 4 13 1 2 15 11 8 3 10 6 12 5 9 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 -7- •*n pc 1 r left shift C P > 3 co (< 3 CO • CO S-, CD cd P cO CO c u CO 3 W p CO T3 TJ Q o 3 Sh CD T3 CO CO 00 £-. S-, CQ jC pa J- CO 2 2 O x: J O CD H 0) CO X! H £5 CD w P H x: o a 4-> CO -H •

•o •H W -10- Microcomputer Prolog 8080 serial I/O port T DES port to PDP-11/45 DES port - \ serial I/O port CRT interface to commercial DES device Commercial DES device Figure 6 . Current architecture of the validation testbed. The interface can be provided to NBS with the hardware, or it can be built by NBS at cost from specifications of the proprietary hardware. -11 Figure 7: Sample validation certificate. This certificate is provided by NBS for encryption hardware implementing the DES that has been tested successfully. A prospective vendor of DES encryption equipment to Federal agencies must obtain a certificate of validation. VALIDATION CERTIFICATE The National Bureau of Standards has tested an encryption device, identified as manufactured by in accordance with the specifications of the Data Encryption Standard (FIPS Pub 46) and in accordance with the procedures specified in NBS Special Publication 500-20. The device has passed the DES test set, and in addition has passed a Monte Carlo test that lasted four million itera- tions. For the Monte Carlo test the initial value of the key was and the initial value of the input was The final value of the key was and the final value of the output was Devices bearing the same identification and manufactured to the same design specifications may be labeled as complying with the standard. No reliability test has been performed and no warranty of the devices by the National Bureau of Standards is either expressed or implied. Dated. Signed (Chief, Systems and Software Division Institute for Computer Sciences and Technology, National Bureau of Standards) -12- 4. THE DEVICE VALIDATION PROCEDURE The device validation procedure verifies that the manufacturer's hardware design of the DES correctly performs the algorithm. To do this a manufacturer submits a single device from his production line for testing. The validation procedure confirms that the device submitted correctly per- forms the DES algorithm. Quality control of devices from the production line is the responsibility of the manufactur- er. NBS does not certify the reliability of DES devices, only the correctness of the way they implement the DES. An interface can be provided by NBS for the device sub- mitted or the manufacturer can provide his own interface. The device runs under microcomputer control while performing the encryptions and decryptions of the DES test set, the results being compared to known results in the microcomput- er. This test takes less than five minutes. The Monte Carlo test is performed by the commercial device and the NBS dev- ice in parallel. This test may run as long as eight hours. The successful completion of the tests will result in the issuance of a validation certificate for the manufacturer's implementation of the DES, and Federal agencies may then purchase identical devices from the manufacturer which are in conformity with the standard. 4.1 The Device/Test-bed Interface An interface must be designed specifically for each proprietary implementation submitted for validation. This is the most time consuming aspect of the testbed procedure and the manufacturer is required to submit detailed charac- teristics of his device with regard to voltage levels and operating requirements to facilitate this phase. The NBS microcomputer interface is designed for use with the NBS DES unit, which uses TTL MSI logic. Firms with commercial implementations of the algorithm that are to be validated by NBS may, at their option, have NBS design and build the necessary interface logic and make necessary software changes to the microcomputer program or they may design their own interface logic that will make their device appear to be identical to the NBS device. In the former case, it will be necessary to supply ade- quate documentation to NBS on the operation of the commer- cial device so that NBS can design the necessary interface logic and software modifications. This documentation should -13- include a definition of all I/O leads, their pin numbers and a narrative description of the operation of the device and of the particular signals needed to operate it. Signal specifications should include the technology to be used by the external circuits (TTL, CMOS, etc.) , any external pull- up resistors required, fan out limitations and any unique voltage levels. All power supply voltages needed should be specified. If any of this information is proprietary , this should be so noted. Full details of the interfacing requirements are in- cluded as Appendix C. 4.2 Validating the Implementation The testbed verifies the correctness of an implementa- tion by performing a series of tests on the device submit- ted. The tests are chosen to present basis vectors to each of the matrix operators in the algorithm and to exercise every element in each S-box. 4.-2.-A Test Procedure . The NBS standard test consists of 291 individual sets of key, plaintext, and ciphertext. The data are stored in a (PDP-11/45) file with each line in the file containing one individual test, e. g., K0101010101010101 P13213AB764588787 S8000000000000000 . The source text of the test program currently resides on a PDP-11/45, and must first be cross-assembled for the PROLOG microcomputer . The resulting object module is downstream loaded into the PROLOG microcomputer via an RS-232 inter- face. The down- stream loading occurs using a special, al- most transparent 10 handler on the PROLOG which reads a character from one port (the terminal) and passes it through to the other port (PDP-11/45) and vice versa. Currently, a program on the PDP-11/45 is executed which starts a process on the PROLOG by sending a special character that starts execution of the test program. The (PDP-11/45) process sends the PROLOG the test data one line at a time. The data is sent in hexadecimal ASCII format Each line is separated into three sections by tabs and spe- cial control characters appear at the beginning of each of these sections. A 'K' at the beginning of the first column indicates that the following 16 characters represent the key. The control character in the second column indicates which operation is to be performed, a 'P' for encryption and a 'S' for decryption. The control character in the third column is the complement of that in the second, indicating -14- that the data following is plaintext or ciphertext. Once the data has been received, the microcomputer pro- gram then loads the test device with the key, followed by the data, and initiates the test. It receives the encrypted or decrypted data back from the test device, and compares it with the expected result. Any deviation in the comparison results in an error message being printed at the console, indicating which individual test failed. The rest of the test is continued. The normal execution time of this test is 3-5 minutes, but it is mainly dependent on the transfer time of the test data, which is transmitted to the PROLOG microcomputer at 2400 bits per second. j4.2^.2 PES Test Set . The tests have been constructed to validate each of the following components of the algorithm: 1. Initial permutation, IP 2. Inverse permutation, IP~1 3. Expansion matrix, E 4. Data Permutation, P 5. Key Permutation, PCI 6. Key Permutation, PC2 7. Substitution tables: S,,S„,...,S TEST 1: Set Key=0 and encrypt the 64-bit data vectors e 1 : i=l,...,64; a set of basis vectors. Basis vectors have all zeros except for a single 1 in the ith position. Compare the resulting cipher c 1 with the known results . CONCLUSIONS: Correct operation verifies the initial permu- tation, IP. As a full set of basis vectors is also present- ed to the expansion matrix, E, this operation is also veri- fied . TEST 2: Set Key=0 and encrypt the results c* obtained in TEST 1 . CONCLUSIONS: As the set of basis vectors are recovered, each ei is presented to the inverse permutation, IP~1, thus verifying it. TEST 3: To test the permutation operator P, set the plain- text to zero and process the 32 keys in PTEST. This presents a complete set of basis vectors to P. TEST 4: part 1: Set Data=0 and use the keys e 1 : i=l,...,64 ignoring i=8, 16, . . . , 64. -15- Since the 56 possible basis vectors which yield unique keys are used, this is a complete set of basis vec- tors for PCI. Compare the results to the known values. CONCLUSIONS: The key permutation, PCI, is verified. Since the key schedule consists of left shifts, as i ranges over the index set, a complete set of basis vectors is also presented to PC2, so this is verified. Part 2: set data=ci from part 1 and use the keys e 1 : i=l,...,64 ignoring i=8, 16, . . . 64. Then decipher. This tests the right shifts in the key schedule during decipher- ing . TEST 5: Set Data and Key equal to the inputs defined in the Substitution Table test. These are a set of 19 key-data pairs that result in every entry of all eight substitution tables being used at least once. Compare the results to the known values. CONCLUSIONS: The eight substitution tables of 64 entries each are verified. Appendix B contains a listing of the complete set of standard tests described above. 4.3 Monte-Carlo Testing Since the test set is known to all, an additional series of tests is performed using pseudo-random data to verify that the device has not been designed just to pass the test set. In addition a successful series of Monte Carlo tests give some assurance that an anomalous combination of inputs does not exist that would cause the device to hang or otherwise malfunction for reasons not directly due to the implementation of the algorithm. While the purpose of the DES test set is to insure that the commercial device per- forms the DES algorithm accurately, the Monte Carlo test is needed to provide assurance that the commercial device was not built expressly to satisfy the announced tests. -16- Each device that is submitted for testing is subjected to a Monte-Carlo test on pseudo-random data that will run for a fixed number of iterations for all proprietary devices submitted. An additional purpose of this test is to verify- that no undesirable condition within the device will cause the key or plaintext to be exposed in place of ciphertext due to a design error. The Monte-Carlo test is not a relia- bility test but merely checks for the presence of an ap- parent operational error. The pseudo-random data is ini- tialized by the test operator at the console, and the test is terminated after a predetermined number of iterations un- less there is a failure, in which case the data causing the failure is displayed at the console. The pseudo-random in- puts required for the test are produced by the DES itself, used as a pseudo-random number generator. It was shown in [5] that the DES is a statistically good pseudo-random number generator, and the likelihood of cycling is very low during observable time periods. tion two mill unit Each on b ciph comp seco with the text time cryp prec cons has unti curr and cons The s an encry ion t , wit ind oth t er ing ar ing nd e the out p , as a ne t ion eding ole i been 1 an ent the r ole . Mont e- d four ptions ests i h comp ividua he NBS the these ncrypt first ut of this p w key that o grou ndicat comp error key, esul t The e Carl mil mak s ru aris 1 t and cip res ion ciph the roce is g ccur P o ing lete is d the from rror o t es lion ing u n on ons est c test h e r t e ul ts , on ertex seco ss is enera red i f tes that d. T etect plain the mess t CO deer P a both bein onsi dev xt the the t . nd e rep ted n t ts . the his ed . text test age nsis ypti sing the g m st s ices on b n de tes The ncry eate from he A m nth seri If , th dev stat t s o ons , le t tes ade of e , CO oth ciph t de key ptio d 1 the 10,0 essa grou es r an e e re ice es f ei wit est . t de aft ncip mpar the erin vice rema n be 0,00 out 00th ge i p of uns rror suit is p whet ght h on Eac vice er heri ing NBS g th , an ins come t put it s pr 10 unti is fro r int her milli e dec h of and each ng th the r and t e out d com the s s the imes . of th erati int ed ,000 1 com det m the ed o the e on rypt th the ope e pi esul est put pari ame , new A e fi on out i te plet ecte NBS ut rror encryp- ion and e four NBS DES ration . aintext ts, en- device, of the ng this while plain- t this rst en- of the at the rations ion , or d , the device at the was in -17- the first encryption, the second encryption or t ion . the decryp- This test is allowed to run until four million complete tests, comprising 8 million encipherments and 4 million de- cipherments , have been generated on the test device. Each group of 10,000 iterations takes approximately one minute to complete, but there will be variations from one proprietary device to another. 4.4 Procedure for Requesting Validation Service The general policy for validation test procedures is specified in Part 200 of title 15, Code of Federal Regula- tions, and in the publication "Calibration and Test Services of the National Bureau of Standards" (NBS Special Pub. 250 [7]). Procedures for formally requesting validation ser- vices, shipping, testing and preparation and use of the validation certificate are included. Specific instructions for a manufacturer desiring a formal DES validation are pro- vided below. A formal request for a validation should be sent prior to the time a device is shipped to NBS. This should provide clear identification of the device being submitted, identif- ication of the individual acting as technical representative for the test (i. e., name, address and telephone no.) and instructions for the return of the device. The formal re- quest should also contain authorization to operate the dev- ice and authorization to charge for the test. The name and address of the individual to whom the bill should be sent should also be included. The request for validation, complete specifications of the device to be tested (sufficient for interfacing the device to the DES testbed) and the device itself should be sent to : Chief, Systems and Software Division Institute for Computer Sciences and Technology A-247 Technology Building National Bureau of Standards Washington, D. C, 20234 -18- The three items should be sent under separate cover. In- quiries regarding the test should be similarly addressed(or tel. 301-92 1-3531). The request and specifications should be sent first and the device shipped only after NBS has responded with an estimated cost of validation and a tenta- tive testing schedule. Insofar as possible, NBS personnel will work jointly with the manufacturer's technical representative in perform- ing a timely test. Special provisions for testing devices that have been integrated into larger electronics equipment will be made as appropriate. Validation of DES devices only assures that the devices correctly implement the DES. The validation procedures do not include reliability test- ing . Any device shipped to NBS should be sent in a reuseable container packed to minimize the potential for damage in transit. Shipping and insurance costs must be paid by the manufacturer. NBS will assume no responsibility for damage during shipment, handling or in testing. A validation certificate will be issued to the manufac- turer when the tests are successfully completed. Notifica- tion will be made to the technical representative if the tests for any reason cannot be carried out. The tests may be terminated at the request of the manufacturer at any time prior to completion and a bill for costs will be issued. NBS does not approve, recommend or endorse any commer- cial product. NBS in no way guarantees that devices similar to the device validated can or will pass the validation tests. However, a manufacturer may certify that devices identical to and bearing the same identification as the dev- ice validated implement the DES. Such a claim will make the devices eligible for procurement and use by government agen- cies. However, no expressed or implied agreement for such procurement is made by NBS. 275a form clud vali Labo prog will appl NBS. NBS. the In ace ) , fee ed by t e the c dation r cost ramming be d icable Trave Bills tes t . ordan s ar he Na ost o tests s wi pers eterm overh 1 co will A v ce w e c tion f la and 11 onne ined ead . st s , be i alid ith Fe harged al Bur bor an in is includ 1 part by th Mater when ssued at ion dera for eau d ma suin e a icip e co ials nece upon cer 1 la all of S ter i g a dmin at in st o cos ssar com tifi w ( 1 mea tand als va istr g in f th t wi y, w plet cate 5 Uni surem ards . used lidat at ive the e per 11 be ill b ion o wil ted ent Fe in p ion , en test sonn act e ac r te 1 b Sta serv es erf o cer gine . La el, ual tual rmin e is tes ices will rming tif ic ering bor r inclu cost cost at ion sued Code per- in- the ate . and ates ding to s to of upon -19- receipt of payment. 5. PREPARATION OF DEVICE VALIDATION REPORT vali the test miss the Gove side dati the give Mont futu fica Eac dati resu ion par rnme red on c man the e-Ca re s te i h ma on Its The of a t o nt i by ert i uf ac sta rlo houl s sh nuf at will of th succe prop f th n all a Fed f icat turer rt ing test , d any own i urer rece e sta ssful erly e ma case eral e wil sat par so t ques n fig who ive a ndard perf o comple nuf act s whe agency 1 stat isf ied ameter he tes tion a ure 7 . submit valida test rmance ted v urer re pr or de e that the D s and t can rise . s an tion ce and o of the alidati is requ ocureme partmen the de ES test final be exac A sampl impl rtif f t tes on ired nt t . vice set re tiy e va emen icat he ts a cert by is A ty su , an suit repe lida tati e de Mont nd t if ic the bein pica bmit d wi s f ated tion on for tailing e-Carlo he sub- ate on Federal g con- I vali- ted by II also or the in the cert i- ACKNOWLEDGEMENTS Dana Grubb and Lou Palombo, of the Computer Systems En- gineering Division, designed and constructed the NBS DES unit. Joe Sokol, of the Systems and Software Division, was responsible for the production of the testbed software. Wil- liam Truitt, of the Computer Systems Engineering Division , adapted and interfaced the microcomputer for the testbed. Dennis Branstad, of the Systems and Software Division, was responsible for the conception and overall design of the DES testbed. Seymour Jeffery, Chief of the Systems and Software Division, has provided consistent support for the project since its inception. Thomas N. Pyke, Jr., Chief of the Computer Systems En- gineering Division, provided guidance on the design of the validation certificate. Gordon Fields, Staff Attorney in the NBS Legal Office, provided many suggestions. -20- APPENDICES -21- 6. 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 58 of the input and bit two is bit 50, etc.) The result is separated into two 32 bit registers, L and R, and then passed through the sixteen rounds as in figure Al. The final 64 bit result is operated on by the inverse of IP, IP" 1 : 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 26 33 1 41 9 49 17 57 25 -22- The round keys K are determined by the key schedule that is diagrammed in figure 3. There are three parameters to be specified, PCI, PC2 and the shift 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 46 38 30 22 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 26 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 46 42 50 36 29 32 and the shift schedule is: Iteration Number of shifts 1 1 2 1 3 2 4 2 -23- 5 2 6 2 7 2 8 2 9 1 10 2 11 2 12 2 13 2 14 2 15 2 16 1 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 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 There remain only the S-boxes -24- (S, is figure 2. ) 15 1 8 14 6 11 3 4 9 3 13 4 7 15 2 8 14 12 14 7 11 10 4 13 1 5 13 8 10 1 3 15 4 2 11 7 2 13 12 1 10 6 8 12 6 9 6 7 12 5 10 9 11 5 3 2 15 5 14 9 10 9 14 13 7 9 13 6 4 9 1 10 13 6 3 15 5 1 13 12 7 11 4 2 8 3 4 6 10 2 8 5 14 12 11 15 1 8 15 3 11 1 2 12 5 10 14 7 6 9 8 7 4 15 14 3 11 5 2 12 7 13 14 3 6 9 10 1 2 13 8 11 5 6 15 3 4 7 10 6 9 12 11 7 13 15 1 3 15 6 10 1 13 8 9 4 8 5 11 12 4 15 2 12 1 10 14 9 3 14 5 2 8 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 3 14 11 8 12 7 1 14 2 13 6 15 9 10 4 5 3 12 1 10 15 9 2 6 8 13 3 4 14 7 5 11 -25- 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 S 7 4 11 2 14 15 8 13 3 12 9 7 5 10 6 1 13 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 5 9 2 6 11 13 8 1 4 10 7 9 5 15 14 2 3 12 S 8 13 2 8 4 6 15 11 1 10 9 3 14 5 12 7 1 15 13 8 10 3 7 4 12 5 6 11 14 9 2 7 11 4 1 9 12 14 2 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 3 5 6 11 The reader is referred to [3] for the official specifi- cation of these parameters. -26- Cipher , J 1 T3 c 3 O c o t h • • • 1 3 O a; ^ C o > 1 Jj 73 C 3 O c o 1 I M >> a; JO L rt •o • H CD CD 0} cd C t* ■a c •rH CD c ■H S ■C 3 Cm U 3 o CD CD u TJ -P CO c CD rH cd cd -a CD .c H t-t CD •o cd S- CD • •H cd -Q CO p •H W •H co S-, Q c >> O •H a> CO CD j^ CD JS _C T3 -P -P T3 •H C CO > a a CD a> c S-, it .c o CD H o Q. cd CD t, 3 bO ■H Plain -27- 7. Appendix B: The DES Test Set IP AND E TEST KEY PLAIN CIPHER 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 95F8A5E5DD31D900 DD7F121CA5015619 2E8653104F3834EA 4BD388FF6CD81D4F 20B9E767B2FB1456 55579380D77138EF 6CC5DEFAAF04512F 0D9F279BA5D87260 D9031B0271BD5A0A 424250B37C3DD951 B8061B7ECD9A21E5 F15D0F286B65BD28 ADD0CC8D6E5DEBA1 E6D5F82752AD63D1 ECBFE3BD3F591A5E F356834379D165CD 2B9F982F20037FA9 889DE068A16F0BE6 E19E275D846A1298 329A8ED523D71AEC E7FCE22557D23C97 12A9F5817FF2D65D A484C3AD38DC9C19 FBE00A8A1EF8AD72 750D079407521363 64FEED9C724C2FAF F02B263B328E2B60 9D64555A9A10B852 D106FF0BED5255D7 E1652C6B138C64A5 E428581186EC8F46 AEB5F5EDE22D1A36 E943D7568AEC0C5C DF98C8276F54B04B B160E4680F6C696F FA0752B07D9C4AB8 CA3A2B036DBC8502 5E0905517BB59BCF 814EEB3B91D90726 4D49DB1532919C9F 8000000000000000 4000000000000000 2000000000000000 1000000000000000 0800000000000000 0400000000000000 0200000000000000 0100000000000000 0080000000000000 0040000000000000 0020000000000000 0010000000000000 0008000000000000 0004000000000000 0002000000000000 0001000000000000 0000800000000000 0000400000000000 0000200000000000 0000100000000000 0000080000000000 0000040000000000 0000020000000000 0000010000000000 0000008000000000 0000004000000000 0000002000000000 0000001000000000 0000000800000000 0000000040000000 0000000200000000 0000000100000000 0000000080000000 0000000040000000 0000000020000000 0000000010000000 0000000008000000 0000000004000000 0000000002000000 0000000001000000 -28- 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 0101010101010101 25EB5FC3F8CF0621 AB6A20C0620D1C6F 79E90DBC98F92CCA 866ECEDD8072BB0E 8B54536F2F3E64A8 EA51D3975595B86B CAFFC6AC4542DE31 8DD45A2DDF90796C 1029D55E880EC2D0 5D86CB23639DBEA9 1D1CA853AE7C0C5F CE332329248F3228 8405D1ABE24FB942 E643D78090CA4207 48221B9937748A23 DD7C0BBD61FAFD54 2FBC291A570DB5C4 E07C30D7E4E26E12 0953E2258E8E90A1 5B711BC4CEEBF2EE CC083F1E6D9E85F6 D2FD8867D50D2DFE 06E7EA22CE92708F 166B40B44ABA4BD6 0000000000800000 0000000000400000 0000000000200000 0000000000100000 0000000000080000 0000000000040000 0000000000020000 0000000000010000 0000000000008000 0000000000004000 0000000000002000 0000000000001000 0000000000000800 0000000000000400 0000000000000200 0000000000000100 0000000000000080 0000000000000040 0000000000000020 0000000000000010 0000000000000008 0000000000000004 0000000000000002 0000000000000001 -29- PCI AND PC2 TEST KEY PLAIN CIPHER 8001010101010101 0000000000000000 95A8D72813DAA94D 4001010101010101 0000000000000000 0EEC1487DD8C26D5 2001010101010101 0000000000000000 7AD16FFB79C45926 1001010101010101 0000000000000000 D3746294CA6A6CF3 0801010101010101 0000000000000000 809F5F873C1F0761 0401010101010101 0000000000000000 C02FAFFEC989D1FC 0201010101010101 0000000000000000 4615AA1D33E72F10 0180010101010101 0000000000000000 2055123350C00858 0140010101010101 0000000000000000 DF3B99D6577397C8 0120010101010101 0000000000000000 31FE17369B5288C9 0110010101010101 0000000000000000 DFDD3CC64DAE1642 0108010101010101 0000000000000000 178C83CE2B399D94 0104010101010101 0000000000000000 50F636324A9B7F80 0102010101010101 0000000000000000 A8468EE3BC18F06D 0101800101010101 0000000000000000 A2DC9E92FD3CDE92 0101400101010101 0000000000000000 CAC09F797D031287 0101200101010101 0000000000000000 90BA680B22AEB525 0101100101010101 0000000000000000 CE7A24F350E280B6 0101080101010101 0000000000000000 882BFF0AA01A0B87 0101040101010101 0000000000000000 25610288924511C2 0101020101010101 0000000000000000 C71516C29C75D170 0101018001010101 0000000000000000 5199C29A52C9F059 0101014001010101 0000000000000000 C22F0A294A71F29F 0101012001010101 0000000000000000 EE371483714C02EA 0101011001010101 0000000000000000 A81FBD448F9E522F 0101010801010101 0000000000000000 4F644C92E192DFED 0101010401010101 0000000000000000 1AFA9A66A6DF92AE 0101010201010101 0000000000000000 B3C1CC715CB879D8 0101010180010101 0000000000000000 19D032E64AB0BD8B 0101010140010101 0000000000000000 3CFAA7A7DC8720DC 0101010120010101 0000000000000000 B7265F7F447AC6F3 0101010110010101 0000000000000000 9DB73B3C0D163F54 0101010108010101 0000000000000000 8181B65BABF4A975 0101010104010101 0000000000000000 93C9B64042EAA240 0101010102010101 0000000000000000 5570530829705592 0101010101800101 0000000000000000 8638809E878787A0 0101010101400101 0000000000000000 41B9A79AF79AC208 0101010101200101 0000000000000000 7A9BE42F2009A892 0101010101100101 0000000000000000 29038D56BA6D2745 0101010101080101 0000000000000000 5495C6ABF1E5DF51 0101010101040101 0000000000000000 AE13DBD561488933 0101010101020101 0000000000000000 024D1FFA8904E389 -30- 0101010101018001 0101010101014001 0101010101012001 0101010101011001 0101010101010801 0101010101010401 0101010101010201 0101010101010180 0101010101010140 0101010101010120 0101010101010110 0101010101010108 0101010101010104 0101010101010102 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 D1399712F99BF02E 14C1D7C1CFFEC79E 1DE5279DAE3BED6F E941A33F85501303 DA99DBBC9A03F379 B7FC92F91D8E92E9 AE8E5CAA3CA04E85 9CC62DF43B6EED74 D863DBB5C59A91A0 A1AB2190545B91D7 0875041E64C570F7 5A594528BEBEF1CC FCDB3291DE21F0C0 869EFD7F9F265A09 -31- PTEST KEY PLAIN CIPHER 1046913489980131 0000000000000000 88D55E54F54C97B4 1007103489988020 0000000000000000 0C0CC00C83EA48FD 10071034C8980120 0000000000000000 83BC8EF3A6570183 1046103489988020 0000000000000000 DF725DCAD94EA2E9 1086911519190101 0000000000000000 E652B53B550BE8B0 1086911519580101 0000000000000000 AF527120C485CBB0 5107B01519580101 0000000000000000 0F04CE393DB926D5 1007B01519190101 0000000000000000 C9F00FFC74079067 3107915498080101 0000000000000000 7CFD82A593252B4E 3107919498080101 0000000000000000 CB49A2F9E91363E3 10079115B9080140 0000000000000000 00B588BE70D23F56 3107911598080140 0000000000000000 406A9A6AB43399AE 1007D01589980101 0000000000000000 6CB773611DCA9ADA 9107911589980101 0000000000000000 67FD21C17DBB5D70 9107D01589190101 0000000000000000 9592CB4110430787 1007D01598980120 0000000000000000 A6B7FF68A318DDD3 1007940498190101 0000000000000000 4D102196C914CA16 0107910491190401 0000000000000000 2DFA9F4573594965 0107910491190101 0000000000000000 B46604816C0E0774 0107940491190401 0000000000000000 6E7E6221A4F34E87 19079210981A0101 0000000000000000 AA85E74643233199 1007911998190801 0000000000000000 2E5A19DB4D1962D6 10079119981A0801 0000000000000000 23A866A809D30894 1007921098190101 0000000000000000 D812D961F017D320 100791159819010B 0000000000000000 055605816E58608F 1004801598190101 0000000000000000 ABD88E8B1B7716F1 1004801598190102 0000000000000000 537AC95BE69DA1E1 1004801598190108 0000000000000000 AED0F6AE3C25CDD8 1002911598100104 0000000000000000 B3E35A5EE53E7B8D 1002911598190104 0000000000000000 61C79C71921A2EF8 1002911598100201 0000000000000000 E2F5728F0995013C 1002911698100101 0000000000000000 1AEAC39A61F0A464 -32- 19 Key data pairs which exercise every S-box entry. KEY PLAIN CIPHER 7CA110454A1A6E57 0131D9619DC1376E 07A1133E4A0B2686 3849674C2602319E 04B915BA43FEB5B6 0113B970FD34F2CE 0170F175468FB5E6 43297FAD38E373FE 07A7137045DA2A16 04689104C2FD3B2F 37D06BB516CB7546 1F08260D1AC2465E 584023641ABA6176 025816164629B007 49793EBC79B3258F 4FB05E1515AB73A7 49E95D6D4CA229BF 018310DC409B26D6 1C587F1C13924FEF 01A1D6D0 5CD54CA8 0248D438 51454B58 42FD4430 059B5E08 0756D8E0 762514B8 3BDD1190 26955F68 164D5E40 6B056E18 004BD6EF 480D3900 437540C8 072D43A0 02FE5577 1D9D5C50 30553228 39776742 3DEF57DA 06F67172 2DDF440A 59577FA2 51CF143A 774761D2 29BF486A 49372802 35AF609A 4F275232 759F5CCA 09176062 6EE762F2 698F3CFA 77075292 8117F12A 18F728C2 6D6F295A 690F5B0D9A26939B 7A389D10354BD271 868EBB51CAB4599A 7178876E01F19B2A AF37FB421F8C4095 86A560F10EC6D85B 0CD3DA020021DC09 EA676B2CB7DB2B7A DFD64A815CAF1A0F 5C513C9C4886C088 0A2AEEAE3FF4AB77 EF1BF03E5DFA575A 88BF0DB6D70DEE56 A1F9915541020B56 6FBF1CAFCFFD0556 2F22E49BAB7CA1AC 5A6B612CC26CCE4A 5F4C038ED12B2E41 63FAC0D034D9F793 : -33- 8. Appendix C: Interface Specifications A manufacturer providing his own interface logic should use the following description and attached diagrams . In some cases, it will be relatively easy to provide hardwired logic that will make the device appear to be identical to the NBS device. However, there may be cases where it will not be feasible to make the device appear identical without software modifications in the microcomputer. In these cases, NBS personnel will make the necessary changes on a cost reimbursable basis. Interface Design The interface uses TTL logic levels (high-level output voltage of at least plus 2.4 volts and low-level of not more than plus 0.4 volts). The cabling normally provides a twisted pair return on three control lines to minimize the effect of noise. If further noise problems should arise, there are connector pins already allocated for twisted pair returns on the other lines. The connector uses an ELCO plug, part number 00-8016-056-000-819. In most cases it will be easier if NBS provides the connector plug and wires it as per the pin assignments of the proprietary device. If desired, the submitter may use a different connector, provided that he supplies NBS with a mate to the connector for cabling to the ELCO on the NBS microcomputer. xi The lines used in the interface are shown in figure CI and salient interface logic in figure C2. These lines are used for transferring a byte of data or key into the device from the microcomputer, for transferring a byte of data from the device back to the microcomputer and for various other control functions. The mode of operation is controlled by the two lines: DATA/KEY and ENCIPHER/DECIPHER DATA. These levels will be stationary during a given operation. Thus, the proprietary device may either sample them at the time the first byte is loaded (data or key) or merely use them as levels for con- trol of the process. (NBS uses the first alternative in its implementation to avoid the chance of any noise on the lines causing a malfunction.) The DATA/KEY line is low when a block of data is to be enciphered or deciphered. It is high when the key is entered. The ENCIPHER/DECIPHER DATA line is examined by the device only when data is to be enciphered or deciphered; otherwise it must be ignored. The key is -34- always loaded in the clear in the validation tests, so any proprietary features for enciphering or deciphering of the key should be inactive during the tests. (However, each op- tion of the proprietary device may be tested by making spe- cial arrangements with NBS.) The RESET EXCEPT KEY level is set by the microcomputer program and then reset by a subsequent instruction. It is used to reset the controls in the device. It may, optional- ly, be used to reset the LR Register, though this is not necessary. The RESET ALL signal (level) was used in the NBS implementation as a convenience for demonstration purposes and need not be implemented. PARITY ERROR is a level from the proprietary device that indicates that one or more bytes of the key have even parity. However, it does not have to be implemented. Some devices may have available additional status indicators like BUSY and CONTROL ERROR. The tests do not make use of these indicators . The lines for loading a byte of data or key into the device are DATA READY 1, its twisted pair return and the 8 INPUT lines. The NBS microcomputer sets up the 8 INPUT lines and, in a subsequent instruction, fires a one shot to give an approximate one microsecond pulse for DATA READY 1. The device should use DATA READY 1 to strobe the 8 INPUT lines into the device. No response from the device to the microcomputer is needed. The 8 INPUT lines should be loaded as data or as key depending on the status of the DATA/KEY control line described previously. This process is repeated for each of the 8 bytes required for the 64 bits of data or key to be loaded into the device. The lines for transferring a byte of data back to the microcomputer are DATA READY 2, ACCEPT 2, their twisted pair returns, and the 8 OUTPUT lines. This transfer is asynchro- nous due to the much slower speed of the microcomputer. The sequence is: DATA READY 2 goes active (high) from the device after the 8 OUTPUT lines are stabilized; the DATA READY 2 line is polled by the program; a subsequent instruction fires a one shot to give an approximately one microsecond pulse for ACCEPT 2 (active low) to the device; and the dev- ice brings DATA READY 2 inactive (low) in response to ACCEPT 2. This process is repeated for each of the 8 bytes re- quired for a 64 bit block transfer. The input data, input key and output data byte number- ing are shown in the figures C3 and C4. -35- Z e o u u O -P U d) C c o o e f A C E H K M P S KK LL k m P s u w y AA h J a c u w EE LL -data ready 1 -data ready 1 tw.* pair ground- +input 1- 2 ■ 3 4 5 6 7 8 +data ready 2 +data ready 2 tw . * pair ground +output 1 2 3 4 . . -accept 2 - accept 2 tw.* pair ground -reset except key - reset all -data/+key (level) -encipher/+decipher data (level)- +parity error (level) ground T3 CD T3 > X! O A-> (D O •H > Q * twisted Figure CI . Interface line specifications data encryption testbed. or the NBS Cable pluy; ELCO 00-8016-056-000-819 Chassis socket: ELCO 00-8016-056-000-707 -36- -data ready 1 -out decode 7442 one sh 74123 1 micr QJ adr { 1 ^ VqJ O > CD •o O — out adr { decode 7442 o — - -P . >. > CD ^! Sh c +input 1 1 O FF 74175 clock r^ CO 1 -P data ( ] out I ! U J f. / i bus ) J LJ -dr2 823 4 +data ready 2 "\ K- / VJtJOOQ^v^y' -LW decode 7442 f CD a adr 0— — > nS i-" +output 1 / e ) o ' Sh data ( r °\ \ r ' O CO ■P cd bus ) -flp.ppnt. 5 •» V / decode 7442 y ■ ■■ c one sh 74123 1 micr ^ ^-^JH^^^^--^ X adr l _^ « w „ ^u -in adr { decode 7442 o c o •H data FF 74175 clock I 4-3 1 o out bus -reset except key /=n c f D r -reset all fS^ ) H -data/ + key \-<. o Sh 1 4_3 - e n c i p h e r / + d e c i p h e r ^-^ V c f o Figure C2 . The logic diagram for the NBS data encryption testbed interface. -37- DATA . .... 1 TWDITT T fe. 57 49 41 33 25 17 9 1 2 3 1 UNcU J. -L *• 58 3 >- 59 60 4 4-*. 61 62 5 6 • 5 ->- D •*" TO DEVICE 63 7 / '*" 64 56 48 40 32 24 16 8 8 > KEY 50 43 36 29 22 15 8 1 51 2 52 3 53 4 54 5 55 6 56 49 42 35 28 21 14 7 # 1 is the leftmost, high order bit of the word . JUtXlJULk + INPUT 1- 2 3 4 5' 6 7- GENERATE BYTE PARITY TO DEVICE L +INPUT 8 Figure C3 . Input data and input key byte numbering for the NBS data encrypt ion standard testbed interface. -38- +OUTPUT i . 1 >2 9 17 25 33 41 49 57 58 X z -> 3 4 59 60 J 4 FROM DEVICE 5 61 5 r L 6 7 62 63 "7 1 P 8 16 24 32 40 48 56 ^ 64 \1 is the leftmost, high order bit of the 64-bit data block. Fiqure C4 . Output data byte numbering for the NBS data encryption testbed interface. -39- 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-6. 3. Data Encryption Standard, FIPS PUB 46, 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 ., 1976, 113-23. 7. Calibration and Test Services of NBS , Spec .Pub. 250,1970. 8. DES Guidelines, NBS Special Publication 500-xx (In preparation). -40- NBS-114A (REV. 7-73) U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA SHEET 1. PUBLICATION OR REPORT NO. NBS SP 500-20 2. Gov't Accession No. 3. Recipient's Accession No. 4. TITLE AND SUBTITLE COMPUTER SCIENCE & TECHNOLOGY: Validating the Correctness of Hardware Implementations of the NBS Data Encryption Standard 5. Publication Date November 1977 6. Performing Organization Code 7. AUTHOR(S) Jason Gait 8. Performing Organ. Report No. 9. PERFORMING ORGANIZATION NAME AND ADDRESS NATIONAL BUREAU OF STANDARDS DEPARTMENT OF COMMERCE WASHINGTON, D.C. 20234 10. Project/Task/Work Unit No. 11. Contract/Grant No. 12. Sponsoring Organization Name and Complete Address (Street, City, State, ZIP) Same as Number 9. 13. Type of Report & Period Covered 14. Sponsoring Agency Code 15. SUPPLEMENTARY NOTES Library of Congress Catalog Card Number: 77-16067 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 and operation of the NBS testbed that is used for the validation of hardware implementations of the Federal Information Processing Data Encryption Standard (DES). A particular implementation is verified if it correctly performs a set of 291 test cases that have been defined to exercise every basic element of the algorithm. As a further check on the correctness of the implementation an extensive Monte-Carlo test is performed. This publication includes the full specification of the DES algorithm, a complete listing of the DES test set and a detailed description of the interface to the testbed. 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; encryption standard; interface requirements; Monte-Carlo testing; testbed; test cases; validating correctness. 18. AVAILABILITY (X Unlimited I For Official Distribution. Do Not Release to NTIS 1 X 1 Order From Sup. of Doc, U.S. Government Printine Office Washington, D.C. 20402, SD Cat. No. CI 3 « 10: 500-20 I I Order From National Technical Information Service (NTIS) Springfield, Virginia 22151 19. SECURITY CLASS (THIS REPORT) UNCLASSIFIED 20. SECURITY CLASS (THIS PAGE) UNCLASSIFIED 21. NO. OF PAGES 46 22. Price $1.60 USCOMM-DC 29042-P74