Hardware based encryption for the personal computer using the data encryption standard

Material Information

Hardware based encryption for the personal computer using the data encryption standard
Wiles, Gary Scott
Publication Date:
Physical Description:
xii, 82 leaves : illustrations ; 29 cm


Subjects / Keywords:
Data protection ( lcsh )
Microcomputers -- Access control ( lcsh )
Data protection ( fast )
Microcomputers -- Access control ( fast )
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )


Includes bibliographical references (leaves 81-82).
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Electrical Engineering.
Statement of Responsibility:
by Gary Scott Wiles.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
30839185 ( OCLC )
LD1190.E54 1993m .W55 ( lcc )


This item is only available as the following downloads:

Full Text


HARDWARE BASED ENCRYPTION FOR THE PERSONAL COMPUTER USING THE DATA ENCRYPTION STANDARD by Gary Scott Wiles B.S., Kansas State University, 1989 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Electrical Engineering 1993


This thesis for the Master of Science degree by Gary Scott Wiles has been approved for the Department of Electrical Engineering by Tamal Bose Douglas Ross I( jrojr.s Date


Wiles, Gary Scott (M.S., Electrical Engineering) Hardware Based Encryption for the Personal Computer Using the Data Encryption Standard Thesis directed by Assistant Professor Shelly Goggin ABSTRACT With the growing world of network and remote computing, computer security is increasing in importance and visibility. The need is emerging for a low-cost, efficient hardware encryption_ system for the Personal Computer (PC) similar to the system developed here. Before presenting the hardware and software implementations, current encryption algorithms, such as the DES, DSS, and RSA, are examined along with the new Clipper and capstone Chips presented by the u.s. government. The relative merits and demerits of each particular system are outlined along with current that incorporate them. Encryption in the ISOOSI Seven Layer Model and the Kerberos authentication iii


system is also discussed. A detailed discussion of the Data Encryption Standard and its implementation is presented along with hardware and software performance. The hardware implementation performs at levels suitable for "on the fly" encryption and decryption with high modems. The performance achieved by the hardware implementation shows that further development is warranted. A future version could deliver economical, hardware based DES encryption for the PC, making remote computing more attractive and practical for business. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. iv


DEDICATION I would like to dedicate this to my family for all their help as I've worked towards this degree. My parents Gary and Carolyn Wiles, and my mother-and father-in-law Phil and Gloria Herzig provided their time, encouragement, and support over the past three years. Without my wife Melissa, this would have never been finished, She tirelessly brought me food and drink. She listened to my complaining and picked up wire-wrap scraps from all over the house. While I hibernated with my computer and books, she carried and delivered our first child. She did everything possible to remove the roadblocks in my way, real or imagined. I only hope I will have the opportunity to make it up to her. v


ACKNOWLEDGEMENTS I would like to thank the Motorola University Support Program for furnishing all my LS integrated circuits. I would like to thank Dr. Bose and Dr. Ross for :serving on my thesis committee. I am especially indebted to Dr. Shelly Goggin for her help and guidance throughout this thesis. She has been a tremendous help since I moved out of the area, going above and beyond the call of duty. vi


CONTENTS Chapter Introduction 1 Motivation of Thesis 1 1.0 1.1 1.2 1. 2.1 Literature Review .. . . 2 Encryption Methods DES Development and History .. RSA Background . Data Signature Standard. 2 3 5 7 1. 2 .. 1. 1 1. 2. 2 1. 2. 3 Encryption in Communication. . 8 1.3 1.4 ISO/OS! Seven-Layer Model. Kerberos Authentication ... Current Topics in Encryption Import/Export Regulations .. Clipper/Capstone Chips Current Products Summary of Findings ... . 9 11 1 7 17 18 22 . 25 2.0 Hardware Algorithm Design and Implementation 28 2.1 Generic Algorithm. 28 vii


2 .1.1 2 .1. 2 2 .1. 3 2.2 2. 2. 1 2. 2.:2 2.2.3 . 29 Key Generation Data Encryption. Data Decryption. . . 30 .. 3 3 Hardware Algorithm Implementation. . Addressing Implementation Hardware Key Generation Data Encryption/Decryption . 34 34 40 . 42 2.2.4 Execution of Key Data Generation 44 2.2.5 Execution of Data Encryption/Decryption 46 3.0 Software Algorithm Design and Implementation 48 3 1 3.2 4.0 4.1 4. 1.1 4 .1. 2 4 .1. 3 Software Emulator. . 49 Graphical User Interface 49 System Performance and-Improvements 53 System Performance 53 Key Initialization 54 Eight Byte Encryption. 54 File Encryption .. 55 4.1.4 Performance Overview 56 4.2 Possible Improvements .. 5.0 5.1 5 .1. 2 Conclusion Criteria Performance. . viii . . 58 60 60 . 60


5.1.3 Application. 5.1.4 Scalability. 5.1.5 Economics. 5.2 Conclusion Appendices DES Algorithm Details. 1. 2. 3 DES Implementation Details Performance Results. .. Bibliography. ix 61 63 63 64 66 75 80 81


Figure 1.1. Al.l A1.2 A1.3 A2.1 A2.2 A2.3 A2.4 A2.5 FIGURES Kerberos Authentication Process. Key Generation Diagram Encryption Diagram Function F Diagram Addressing Logic . Addressing Logic Continued Key Generation Logic . Encryption I Decryption Logic Control Register Logic X 16 66 67 . 68 7 5 7 6 77 7 8 79


Table 1.1. 2.1 A1.1 A1.2 A1.3 A1.4 A1.5 Al. 6 A1.7 A1.8 A1.9 A1.10 A1.11 A1.12 A1.13 A1.14 TABLES The ISO/OSI Seven Layer Model. . 9 I/0 Address Mapping . . Permuted Choice 1 Matrix Left Shift Table .. Permuted Choice 2 Matrix . . .35 69 6 9 70 Initial Permutation Matrix . 70 E Bit Selection Matrix . . 71 S1 Block Permutation Table ... 71 S2 Block Permutation Table S3 Block Permutation Table . S4 Block Permutation Table S5 Block Permutation Table S6 Block Permutation Table . S7 Block Permutation Table . sa Block Permutation Table . p Bit Selection Matrix . . xi 71 7 2 7 2 .72 .73 .73 .73 .74


A1.15 A3.1 Inverse Initial Permutation Matrix Mean Encryption Time xii .74 . 80


Chapter 1 Introduction This chapter examines the motivation of the thesis. The chapter also examines the current algorithms, products, and issues in cryptology today, 1.1 Motivation of Thesis The purpose of this thesis is to create a hardware based encryption system for IBM compatible AT Personal Computers. Although many software encryption products exist for the PC, hardware encryption for the PC is rare. People desire hardware encryption because it is much quicker than software based encryption. This is important for encrypting data passed over networks or communication links. The primary goal of this thesis is to develop a system that operates quickly enough to encrypt and decrypt data "on the fly" while using a high speed modem. Secondary goals are to keep the costs low 1


and to use easily available parts. 1.2 Literature Review It is important to check the current standards and literature to make sure a suitable design and implementation are chosen. This section will examine the current methods of encryption and authentication, along with products that are available today. There is much discussion going on about "Information Super Highways" and "Global Networking." When examining such a program or article, the thrust is the benefits people will gain and the facilities and data they can access. Usually at the end is a small statement about security and how that issue still needs resolution. Many of these security issues will involve encryption in one form of the other. 1.2.1 Encryption Methods Most encryption algorithms fall under one of two methods: public key or private key encryption. Private key encryption is based on a secret password needed for both encryption and decryption. The algorithm may or may 2


not be public knowledge, but the key must be kept secret. An example of a private key encryption method is the Data Encryption Standard (DES). Public key encryption is based on two separate keys, one'known by each party in the data exchange. The sender encrypts the data with one key and the receiver decrypts the data with the other and vice versa. Knowledge of only one key is necessary to be a participant in the data and that knowledge will not reveal the second key. The Rivest, Shamir, and Adelman (RSA) algorithm, named for its inventors, is an example of a public key encryption algorithm. DES Development and History International Business Machine (IBM) personnel created the forerunner to the Data Encryption Standard. It was a product called Lucifer designed for Lloyds of London. This algorithm processed data in 128 bit blocks with a key length of 112 When the National Bureau of Standards (NBS) requested submissions for a standard government encryption algorithm for sensitive unclassified data in 1973, IBM submitted a variation of 3


the Lucifer algorithm. NBS then published Federal Information Processing Standards Publication 46 (FIPS PUB 46), as the Data Encryption Standard after extensive testing by the National Security Agency (NSA) [3 pp. 256-257]. The DES has had a controversial history. While most people agree that DES will defeat all but the most capable of aggressors, there is concern over the amount of control the NSA may have wielded in the Lucifer to DES [3 pp. 262-263]. Changing the key length from 112 bits to 56 bits reduced the number of possible key values from approximately 5.19 x 1033 to 7. 20 x 1016 possible key values. Assuming no trap doors exist in the algorithms allowing trivial decryption, brute force decryption is the only method left for defeating the algorithm. The key length change reduced the time needed for this type of decryption. The DES is still a very secure system. Assuming an opponent had a dedicated computing machine able to process a trillion possible keys a second, it would take over twenty computer hours to process all possible keys [3 p. 257]. On average, the proper key would be found in 4


half that time, your opponent would still need ten hours of time on this proposed system to break the algorithm. Any organization that could afford to design and construct such a machine would only be interested in attacking the most valuable of targets. RSA Background Professors Ron Rivest, Adi Shamir, and Ken Adelman of MIT developed the RSA public key encryption system 'named for them in 1976. The algorithm is not publicdomain. A firm founded by the three men, RSA Data Security Inc., owns and markets the algorithm. A simplified example of encryption/decryption using RSA follows: Two agents, Mr. Foo and Mr. Bar need to trade information. Foo selects two prime numbers, 5 and 7. Foo the two numbers together, resulting in 35. Foo then selects the random number 17. Foo then sends 17 and 35 to Bar as the public key, Bar must communicate the message 33 to Foo without revealing it. Bar raises the message to the first number, modulo the second number ((3317)mod 35), This 5


results in the encrypted message 3. Meanwhile, Foo has been computing the secret key. Foo subtracts 1 from each of the two original prime numbers (5-1=4, 7-1=6) and finds the lowest common multiple (LCM) of the two numbers. For 4 and 6, the LCM is 12. The secret key is the random number selected modulo the LCM of the two altered primes (17 mod 12=5). When Foo receives the encrypted message 3, he raises it to the power of the secret key and performs a modulo 35 on the result (35 mod 35 = 33), This returns the original message value of 33 [3 p. 265]. Even with a simplified version of the RSA algorithm, the math is quite complex. The result of 3317 is a 28-digit number, and most appl.ications of the RSA algorithm deal with prime numbers between fifty and 200 hundred digits in length [3 p. 265]. These numbers can only easily be found and handled by sophisticated hardware and software equipment. Computing prime factors of these large numbers is where the strength of the algorithm exists. The RSA algorithm is an asymmetric system (one key is used for encryption and another for decryption). For 6


use in network computer security systems, a directory containing one member of each matched key pair indexed by the username is kept on the system. A user sends an authenticator encrypted with the other key in the RSA key pair when they need to access the system. If the system can decrypt the authenticator with the user's other key, the .user is authenticated. Data Signature Standard The Data Signature Standard (DSS) is the National Institute of Standards and Technologies (NIST) answer to public key encryption. A "hashing'' algorithm processes the message, creating a numeric signature. This signature is encrypted using a public key encryption method. The server sends the message (plain text) and the signature to the destination. At the destination, the hashing algorithm processes the message, resulting in the same signature as above. The encrypted signature is decrypted using the other key in the pair. The receiver compares the decrypted signature and the locally generated one. If they match, the receiver can validate the creator and the message 7


contents. If someone alters the message in transmission, the hashing algorithm would generate a different signature. This allows the receiver to verify the message has not been altered and authenticate the sender. What it does not do is encrypt the actual message. The DSS is similar to a clear plastic envelope enclosing your message, Resolution of many lawsuits will be necessary prior to broad DSS implementation. Many companies, including RSA, claim the encryption portion of the DSS is stolen technology from their various algorithms [12 pp. 42-43]. 1.2.2 Encryption in Communication Networking, tele-commuting, and mobile commuting has driven many corporations, schools, and government agencies to place their systems on-line with dial-up modems and other remote access methods. This has caused analysts to look at integrating features such as authentication and encryption into their system architecture. 8


1. 2 2.1 ISO/OS! Seven-Layer Model Standardized architectures were needed as networked computer systems arrived. In 1977, the International Standardization Organization (ISO) chartered a subcommittee (called the Open Systems Interconnection committee or OS!) to develop this framework. This committee was to develop a structure to define the functionality needed for computer network communications. This resulted in the ISO/OS! seven layer model for network communication. The seven layers are as follows: Application ( 7) Presentation ( 6 ) Session ( 5 ) Transport ( 4) Network ( 3 ) Data Link ( 2) Physical ( 1 ) Table 1.1: The ISO/OS! Seven Layer Model 9


Many complete papers have been written about the seven layermodel, [see 19] so a quick overview is all we will present here. Each layer receives processing requests from the layer above it, while relying on the layer below it to provide it the services necessary to perform its mission. (Layer seven deals directly with the application program and layer one is the physical layer concerned with bit representation, connections, etc.) Generally layers seven through five ,provide direct support to the application program. Layers one, two, and three are concerned with the direct transmission and reception of data, leaving layer four to bridge the gap between the network and the application. Network systems do not require all seven layers. However, any application without layers one, two, and seven would not be practical. Encryption would generally take place at layer six, the presentation layer. Layer six interprets the transmitted data for the application layer. This may include language translation, data compression I decompression, and encryption and decryption [19 p. 54]. 10


Encryption is sometimes added at layer one instead of layer six. This is often the case when using encryption devices that encrypt all network control data and information data. Generally the data passes through cryptography equipment just prior to traveling through the transmission media. This type of encryption I decryption is invisible to the network protocol. The U.S. government and military use such devices. Kerberos Authentication The Massachusetts Institute of Technology (MIT) developed Kerberos, naming it for the mythical three headed dog guarding the gates of Hell. It is a subsystem of the Project Athena distributed computing environment. Kerberos provides a secure method of authentication between a user and a service from an unsecured terminal using the DES. Users sign on at the terminal by entering their username. The terminal resident program sends the username and the name of a server called the Ticket Granting Server (TGS) to the Kerberos server. Kerberos scans its user database and finds the entry containing the username and the password. It then 11


generates a random DES session key for use with the TGS. It also generates a ticket for the user to request system services called a Ticket Granting Ticket (TGT). This ticket contains the user's name, the current time, the duration of the ticket, the network address, and the random session key. The ticket is then encrypted with a key known only by Kerberos and the TGS. The encrypted TGT and a plain-text copy of the random session key are encrypted using a DES key based on the user's password. The user's terminal receives this encrypted information and prompts the user for their password. The terminal program uses the password as a key to decrypt the encrypted information. (This password never leaves the local terminal.) The terminal then stores the TGT, still encrypied by a key known only by Kerberos and the TGS, along with the session key for further use. Users and user applications are now ready to request services. Each service requires a separate ticket from the user. The TGS grants all tickets using the TGT. To access the file server, the user would first send a request to the TGS. This request would include the TGT, the name of the file server, and an authenticator. The 12


authenticator includes the users name, network address, and time of day encrypted with the TGS random session key passed by TGS first decrypts the TGT using the key known only by Kerberos and itself, (Remember, the user's name, the network address, the user/TGS session key, the time the ticket was granted and its duration form the TGT,) If the ticket has not expired (granting time + duration >= current time) the authenticator is decrypted using the session key. TGS authenticates the user if the name and the network address in the authenticator match those in the TGT and the authenticator_time is within parameters. The TGS can then perform access control verification on the user name. (For this example, assume the user has authorization for the file server.) : TGS then generates a ticket for the user to access the named file server. The file server ticket contains all the information that is in the TGT except the user/file server key replaces the user/TGS session key. This ticket is encrypted using a key known only by the TGS and the file server. This encrypted ticket and a plain text copy of the user/file server key are encrypted 13


using the user/TGS key. The terminal program then receives this data where it decrypts it using the user/TGS key. The user's terminal program then builds an authenticator encrypted with the user/file server session key. This authenticator and the ticket are sent to the file server. The file server decrypts the authenticator and then the ticket, verifying the user's identity in the same manner as the TGS. The file server may then grant the user access to the appropriate files [11 pp. 46-51]. Throughout this involved process there are a few things to remember: 1) The user was only required to enter the password once. 2) Plain text passwords are never sent over the network. 3) The user's various tickets have a time limit and will expire. 4) Upon expiration, new tickets must be granted by the TGS or Kerberos if the TGS ticket expires. 14


5) Kerberos only provides authentication to various services, all other security mechanisms such as access control lists must still be provided. 6) Password security is vital, Kerberos will be defeated by poor password practices. 7) The users cannot change their own passwords, it must be done by a system manager. 8) The Kerberos server needs to be kept physically secure. 9) All services to be protected must be modified to support Kerberos. 15


..... 0) User name User name and password Ticket-granting ticket (TGl) TGTand Service requested User ) 't Server Figure 1.1: Kerberos Authentication Process (11, p. 51]


1.2.3 Current Topics in Encryption Almost all discussion on encryption lately has concerned the government's new encryption chips, Clipper and Capstone. Along with this was hope that the Clinton administration would relax export standards for existing encryption methods. President Bush with his CIA background was considered sympathetic to the intelligence agencies' case for regulating overseas traffic of this technology [20 pp. 1-2]. Import/Export Regulations Currently, the U.S. government has prohibited export of the encryption systems discussed in this paper. Under U.S. government laws, the DES, RSA, and Kerberos systems are all treated as munitions and require an exemption to ship overseas [3 p. 268]. This is damaging to business as corporations who use these systems in their products must create different versions with weaker algorithms for export. Meanwhile, foreign firms easily implement these "protected" algorithms that are nothing more than applied mathematics. Many textbooks openly discuss these algorithms and published standards exist. 17


This costs U.S. firms business and profits as they cannot compete in this field overseas. I have found programs based on the DES algorithm developed by an English programmer on an American bulletin board. However, I could not place my version.on an English bulletin board without violating u.s. laws. President Clinton has yet to change these export laws. However, until the Clipper/Capstone issues are resolved, no decision will likely be made concerning export laws. Clipper/Capstone Chips Many people were looking for a government update to the DES and a standard government public key encryption system similar to RSA The government supplied the Clipper and Capstone chips. Telephones, fax machines, computers and modems are targets for these new chips. Although at first glance they may be what people were looking for, the computer world reaction has not been positive. The Clipper Chip is a hardware system developed by the NSA as the new government standard for private key 18


encryption. This system functions like the DES algorithm where one key encrypts and decrypts data. The Capstone Chip is the NSA developed public key encryption system. It uses the same base algorithm as the Clipper Chip and would be analogous to the RSA algorithm where two keys encrypt and decrypt data passed between them. Capstone will also provide an electronic signature capability similar to the DSS. Currently, the NSA has no plans to release the Clipper/Capstone algorithms to the public. They will release the algorithm to a select group of academics to verify its validity. According to the NSA, releasing the algorithm will not compromise-its security, but the agency refuses to publish it [13 p. 9]. The secrecy surrounding the algorithm has disappointed many. "The secret process up until now has been. destructive to public trust," said William Murray, Information Systems consultant at Deloitte & Touche, in Wilton, Connecticut [10 p. 103]. Citicorp filed a statement with the Computer Systems Security and Privacy Advisory Board complaining the algorithm "will undergo inadequate scrutiny and hurried review'' [2 p. 21]. This 19


could result in missed errors allowing access to data. The U.S. government will license corporations to build the system. These corporations will then have to furnish keys to the government to be kept in "escrow accounts." Government agencies would hold portions of the keys. Law enforcement agencies could then obtain a court order allowing them access to these keys to listen in on transactions, much like wiretaps today, This has raised a ruckus with various corporations and agencies. If the government mandates this as a standard, most large corporations dealing with government agencies would have to support it. This would cost corporations large sums of money to convert existing systems to the new equipment. Many question the security of the system. "If the government can de-encrypt it, we have to assume competitors can as well," stated Bob Holmes, research analyst at Southern California Gas, in Los Angeles [10 p. 103]. "It is only a matter of time before hackers figure out a back door to de-encrypt it," said Sheldon Laube, national director of information and technology at Price 20


Waterhouse, in Menlo Park, California [10 p. 103]. The U.S. government will allow export of the Clipper/Capstone based systems. .However, most foreign countries, corporations, or citizens will not want to purchase a system the U.S. government can access. Corporations still must generate different lines of equipment for foreign and domestic sales. This has lead the Computer and Business Equipment Manufacturers Association (CBEMA) (which includes such corporations as Apple, Compaq, IBM, and Hewlitt Packard) to testify against this standard to the U.S. Commerce department [10 p. 103]. Since criminals and terrorists would be foolish to use this system, there is fear that the government will attempt to ban all encryption methods other than Clipper/Capstone. Raymond Kammer, acting NIST director has acknowledged that a ban on existing techniques would be considered. "But my personal opinion is, I can't see doing anything that would take away any freedoms we now enjoy," Kammer said [2 p. 21]. Clint Brooks, adviser to the director of the NSA claims, "We tried to come up with a technique that would 21


not require legislation." He feels it will be years before criminal use of encryption would require consideration of such methods. "Let's wait and see if legislation is needed," he said [2 p. 21]. Civil liberties groups, such as the Electronic Fr9ntier Foundation (EFF), feel that this system violates the constitutional protection against search and seizure. They also feel that the government should not be the sole source for encryption chips. They are organizing forums of vendors and users under its Digital and Security Working Group to discuss Clipper/Capstone [13 p. 9 1 1.3 Current Products Many companies are producing encryption products for the personal computer marketplace. Some is hardware based, but most is software based to reduce costs. Of course, software based encryption is slower than hardware encryption, but for many PC users, the speed requirements are not as important as the price. The Eracom PC Encryptor is an eight bit add on board for IBM PC's. It provides DES encryption support at the 22


operating system level. All data written to floppy and hard drives can be encrypted on the fly. Its software drivers allow applications to access the encryption functions. An individual key is mounted in the hardware that combines with the key entered by the user for encryption/decryption. This obviates the need for the user to enter a full eight byte key [3 pp. 258-259]. The DES-LOCK operating system utility from Oceanics (an English company) is a software implementation of the DES algorithm. It is command line based similar to other utilities such as COPY or MOVE [3 p. 259]. RAC/M from Okiok Data Ltd. is another DES encryption product for IBM compatibles. In addition to encryption, RAC/M provides access control and scheduling, audit trails, key and password management and other security features. It is designed for local area networks and client server operations [3 p. 259]. Mailsafe is an electronic mail encryption program by Fischer International Inc. It provides DES and proprietary private key encryption and RSA public key encryption for E-mail transmissions [22 p. 62]. PC/DACS from Mergent International Inc. provides 23


various security features. PC/DACS uses DES and proprietary private key encryption and features boot and anti-virus protection along with audit trails and access controls [22 p. 62]. Maverick Software Inc. sells Procrypt 2.0. This program encrypts individual files using DES and proprietary private key encryption [22 p. 62]. The Open Computing Security Group provides Kerberos Authentication software for LAN files and communications. It is expensive at $5,000 $10,000 for the server software and $195-$500 per client [22 p. 62]. Semaphore Communications Corporation has introduced a hardware/software product called the Network Security System. It provides authentication and encryption for network operations. Sensitive data is encrypted on the server before being shipped to the workstation. Any data will be unusable due to the encryption [5 p. 48] VinCrypt is one of the more interesting products available. Self-proclaimed "hackers" and underground programmers created this product. They claim all applications based on the DES and RSA algorithms are 24


insecure since the NSA reviewed their algorithms. The creators of this product refuse to reveal the algorithm. Experts are leery of any system that is not open to examination by the cryptology community. Many companies are wary of trusting their security to these "hackers," likening it to hawks guarding the hen house [4 p.6]. 1.4 Summary of Findings An examination of the literature shows two algorithms of choice: the DES private key algorithm and the RSA public key algorithm. Both algorithms have their strong points, but the DES algorithm was chosen for implementation for the following reasons. The DES algorithm is more prevalent due to its government standard status. Companies wishing to do business with the federal government are more likely to support DES rather than RSA. DES is less computationally intensive than the RSA algorithm. The RSA algorithm is slower due to its reliance on complicated mathematics [22 p.62]. Hardware implementation of the DES algorithm is straightforward. The DES algorithm uses exclusive or 25


operations, left shifts, and bit permutations. These building blocks are easily implemented with 74LSXX technology. RSA with its mathematical basis is more complex and requires mathematical processors with tremendous resolution. The DES algorithm is public-domain. RSA licenses their technology. For a graduate student, licensing makes all the difference in the world. In addition, this must be passed on to consumers causing higher prices. The decision to implement DES in hardware was based on these reasons. In addition to the hardware, software is needed to interface with the board. An object oriented graphical user interface using C++ will be used. The design and implementation of this board showed the feasibility of hardware encryption on the PC. Encryption can be supported at speeds much faster than the current crop of high speed modems. This allows "on the fly" encryption and decryption as data is transferred between systems. Commercial applications similar to this may help more people work out of the home without risking compromise of their employers' data. The following chapters outline the algorithm, the 26


details of the implementation, performance, and conclusions. 27


Chapter 2 Hardware Algorithm Design and Implementation The Data Encryption Standard (DES) was the algorithm chosen for implementation. It was chosen for its widespread use, amount of reference material, and soundness of design. The design was chosen due to the extensive use of common 74LSXX integrated circuits and common memory devices. A review of the generic DES algorithm follows and then the specific implementation will follow. 2.1 Generic Algorithm The DES algorithm takes a sixty four bit key and sixty four bits of data and returns 64 bits of encrypted or decrypted data. Since the DES algorithm is a private key algorithm, the same key is used for encryption and decryption. The algorithm can be broken up into three segments; key generation, encryption, and decryption. The algorithm consists of various permutations, Exclusive OR's, left shifts, and non-linear 'S-block' 28


transpositions. A permutation consists taking bit x0 of the input and placing it in the first bit of the output for theN bit permutation matrix.[X1 x2 x3 X 4 ... XN]. Exclusive OR's refer to the combining of two binary outputs to yield one binary output that is only true (1) if one input is false (0) and the other is true (1). Left shifts are self-explanatory. An input of 11011000 yields an output of 10110001 when left shifted. All bits slide one position to the left and the leftmost bit becomes the rightmost bit. The 'S-block' transpositions are the heart of the algorithm and will be described in detail in the context of data encryption and decryption. See Appendix 1 for an overview of the algorithm. 2.1.1 Key Generation Only fifty-six bits of the sixty-four bits of key data are used. Bits eight, sixteen, twenty-four, thirtytwo, forty, forty-eight, fifty-six, and sixty-four are omitted as the data passes through permutation Permuted Choice 1 (see Appendix 1). The fifty-six bit output is divided into two twenty-eight bit words, KL0 and KR0 29


Each of these words is shifted one or two bits to the left according to the iteration number as shown in Appendix 1. The leftmost bit of.each word is wrapped around to the far right bit of each word for each shift. After the requisite number of left shifts have been performed for a particular iteration (one for the first iteration), the new words KL1 and KR1 result. The two new twenty-eight bit sub-keys then pass through permutation Permuted Choice 2 (see Appendix 1) where it is reduced from fifty-six bits to forty-eight bits. These forty-eight bits are sub-key one. This value is kept for encryption and decryption use. The two twenty-eight bit sub-keys KL1 and KR1 are then left shifted according to iteration number (see Appendix 1) to produce KL2 and KR2 These are used to create sub-key two via Permuted 2. This process is repeated until all sixteen sub-keys are generated. See Appendix 1 for an overview of key generation. 2.1.2 Data Encryption Data encryption is accomplished by passing through eighteen stages: The initial permutation, the sixteen 30


iterative stages, and the inverse initial permutation. These stages are discussed in greater detail in the following paragraphs. The sixty-four bits of data passed in are passed through permutation Initial Permutation (IP -See Appendix 1). This is the end of the first stage and the iterative stages now begin. The output of the IP block is broken into two thirty-two bit blocks, L 0 and R 0 The rightmost thirty two bits (R0 ) are passed through function F. Function F consists of first passing the thirty-two bits through permutation E (see Appendix 1) where they are expanded from thirty-two to forty-eight bits. These forty-eight bits are Exclusive OR'ed with the sub-key one from the previous step. The forty-eight bit output of this operation is then through the array of eight, six bit input S-blocks. The S-blocks are non-linear six bit to four bit permutations. Each block is different from the other seven. Appendix 1 shows the eight S-block values. The output terms are referenced by a row and column system. The row value is determined by the far left and far right 31


bits. The are combined together to form a two bit row value with the far left bit as the most significant bit. The middle four bits are treatedas a four bit column value. For example, if the six bit input to S-block one is 110101, the row value is 11 (three decimal) and the column value is 1010 (ten decimal). By cross referencing the S-block one table for row three, column ten an output value of three is found. This results in a four bit output of 0011 for S-block number one. The forty-eight bit input to the S-blocks result in a thirty-two bit output which is input to permutation P (see Appendix 1). This thirty-two bit input I thirty-two bit output permutation is the final step of function F. The final step of the .iterative stage is Exclusive OR'ing the thirty-two bit function F output with 1 0 This output then becomes R1 R0 is then inserted directly as 11 This process is repeated for all Ln and Rn for n = [1 ... 16] using the corresponding key value for each iteration. When 116 and R16 are established, the left and right thirty-two bits are exchanged. This in effect changes L16R16 to R16116, and is called the Preoutput block. 32


The sixty-four bit Preoutput block is then passed through the Inverse Initial Permutation (see Appendix 1) yielding a final sixty-four bit encrypted output of the original sixty-four bit data. This is the eighteenth and final stage of the encryption process. 2.1.3 Data Decryption Decryption of the sixty-four bit encrypted data is very similar to the encryption process. The same eighteen stages are followed with only minor differences. The sixty-four bits of encrypted data are input to the system for decryption in just the same way the original data was input for decryption. Every step in the decryption process is the same as the encryption process except the sub-keys are used from sub-key sixteen to sub-key one for decryption. (They are used sub-key one to sub-key sixteen for encryption.) This makes the DES very easy to implement since the same hardware or software for encryption can be used for decryption as long as the ability to invert the order the sub-keys are used is incorporated. 33


2.2 Hardware Algorithm Implementation To build a hardware based encryption system, my goal was to use simple 74LSXX integrated circuits to reduce cost and allow logic probe access to the data at many given points for debugging. Programmable logic devices were chosen for addressing and simple ROM and RAM chips were used in other areas, but the rest of the design was 74LSXX and wire wrap. This choice of basic building blocks also made it fairly easy to change the design and fix errors as the implementation matured. Obtaining parts was much easier when common component were used. See Appendix 2 for hardware schematics and flow charts. 2.2.1 Addressing Implementation The hardware implementation was designed to take advantage of the Industry Standard Architecture (ISA) sixteen bit bus. (Often referred to as the AT bus.) This bus allows eight or sixteen bit data transfers from the motherboard to the bus card at eight Mhz. The bus allows for mapping the addresses in the data or I/0 address spaces. 34


The inputs and outputs of the DES board consisted of four sixteen bit data inputs for the sixty-four bits of key data, four sixteen bit data-inputs for the sixty-four bits of encrypted\decrypted data input, four sixteen bit data outputs for the sixty-four bits of decrypted\ encrypted data output, and two x eight bit data input for processing control. The inputs and outputs are mapped in the I/0 address space as shown below. Encrypt/Decrypt Data In Encrypt/Decrypt Data Out Key Data In Data Processing Control Key Processing Control OxFFlO OxFF17 OxFFlO OxFF17 OxFF20 OxFF27 OxFFOO OxFFOl Table 2.1: I/0 Address Mapping As you can see, the encrypt/decrypt data-in and data-out have the same address space. This is possible because they are each separate register banks. The data-in bank is accessed when the I/0 write line is active and the data out bank is accessed when.the I/0 read line is active. To the software and the motherboard they appear at the same address space. 35


All of the inputs and outputs (key data, encrypt/decrypt data, and key and data processing control) are passed to the board and stored in 7415373 chips. These chips are eight bit, level triggered registers with output selectively enabled and disabled. To load the inputs (encrypt/decrypt data inputs, key data, and processing control) the correct addresses must be active along with the I/0 write line. This logic is controlled by three GA120V8 chips (Al, A2, and A3) and three 741502 quad input NOR chips (A4, A5, and A6). Chip Al is programmed to take ISA bus address lines A23 -A8 as inputs and output an active low output when the correct high order address lines are passed. (This output is referred to as !HIGH.) Originally, I mistakenly assumed the I/0 address space was as large as the memory space on the ISA bus (twenty-four address lines). I had placed the addresses at the OxFFFFXX area. I then found the address bus lines from A23 -A16 are inactive when working in the I/0 address space. So those inputs to chip Al were wired high to ensure the output is active when the correct inputs (OxFFXX) are received from A15 As. 36


!HIGH = ( 2. 1 ) (Chip Al Formula) Chip A2 is programmed to take !SA bus address lines A 1 -A 1 and chip Al output !HIGH as inputs. This chip has eight active low output !D4, !D3, !D2, !Dl, !K4, !K3, !K2, and !Kl. Outputs !D4 and !K4 are active when the address space for the sixteen most significant bits of the encrypt/decrypt and key data is accessed respectively. Outputs !D3 and !K3 enable the next sixteen most significant bitsand so on with !Dl and !Kl enabling the sixteen least significant bits. The Key .and Encrypt/Decrypt data can only be accessed sixteen bits at a time. That is why there is no Ao input to the chips. This limitation causes OxFFlO and OxFFll to both access the sixteen most significant data bits, since the Ao _line would not be noticed by the DES board. !D4 = !HIGH & A7 & 'As !D3 = !HIGH & A7 & 'As !D2 = !HIGH & A? & 'As & A5 & A4 & & A5 & A4 & & !A5 & A4 & 37 A3 A3 A3 & Az & Al & Az & Al & A2 & Al ( 2. 2) ( 2. 3) ( 2. 4)


!Dl = !HIGH & A7 & !As & As & A4 & A3 & Ai & Al ( 2 5 ) !K4 = !HIGH & A? & !As & As & A4 & !A3 & 2 & !Al ( 2 6 ) !K3 = !HIGH & A? & !As & A5 & A4 & A3 & !A2 & Al ( 2 7 ) !K2 = !HIGH & A? & !As & A5 & A4 & !A3 & A2 & !Al ( 2. 8) !Kl = !HIGH & A7 & !As & A5 & A4. & !A3 & A2 & Al ( 2. 9) (Chip A2 Formulae) Chip A3 is programmed to take !SA bus address lines A 1 -Ao ISA bus control lines !IO_READ and !IO_WRITE, and !HIGH from chip Al as inputs. It provides outputs !Key_Proc, !Data_Proc, and !BIT16. !Data_Proc is active when data processing control information is being passed from the motherboard to the DES board. !Key_Proc is active when key processing control information is being passed from the motherboard to the DES board. !BIT16 is active when 16 bit data transfers are taking place (i.e. !D4 -!Dl and !K4 -!Kl). This output is routed back to the !SA bus and is how an expansion board lets the bus controller know it is a sixteen bit capable address location being accessed. If this line was not active, the bus controller would only allow two eight bit transfers for sixteen bit transfers. !Data_Proc = HIGH & A? & A6 & A5 & A4 & A3 & A2 & A1 & !A0 (2.10) 38


!Key_Proc BIT16 = HIGH & A 7 &. A 6 & A 5 & A 4 & A 3 & Al & Ao = HIGH & A? & A6 & ( A5 + A4 ) & ( A5 !A3 & (!IO_WRITE + !IO_READ) (Chip A3 Formulae) !A & ( 22 11 ) + A ) & ( t 12) The outputs !K4 -!Kl are then passed to chip A4, a 74LS02 quad NOR chip. Each !Kn output is paired as a NOR input with the !SA bus signal !IO_WRITE. The output of the NOR chip is high when both the inputs are active (low). This output drives the high level triggers for the appropriate pair of 74LS373 key data in chips. Similar processing is performed by chip A5, another 74LS02, which has !D4 !D1 paired with !IO_WRITE to drive the appropriate pairs of 74LS373 encrypt/decrypt data in chips, The outputs !Data_Proc and !Key_Proc are passed to chip A6, another 74LS02 chip. These two signals are also paired with ISA bus signal !IO_WRITE. The output of these NOR operations are the triggers for the 74LS373 Data Processing Register and the 74LS373 Key Processing Register respectively. 39


The outputs !D4 !D1 are also passed to chip A7, a 74LS32 quad OR chip. Each !Dn output is paired as an OR input with the !SA bus signal !IO_READ. The output of the OR chip is low when both the inputs are active (low). This output drives the low level output enable triggers for. the appropriate pair of 7418373 encrypt/decrypt data out chips. 2.2.2 Hardware Key Generation The eight 74LS373 chips that hold the key data input from the motherboard have their output enable pins wired low so it is always driving data. This output data is then passed through a hardwired PC-1 permutation to the B input of fourteen 7418257 chips. The '257 takes two sets of four bit inputs (Input A and Input B) and based on a control line input from the Key Processing Register, will output one set of four bit inputs, As discussed in section 2.1, the sixty-four bit input to PC-1 come out as fifty-six bits. This allows fourteen four bit input chips to take all of the output of PC-1. The PC-1 permutation is handled by connecting the output of the 74LS373 to the correct input of the 74LS257 40


according to PC-1. The output of these fourteen '257 chips is passed to seven 7418374 chips. (The '374 chip is the same chip as the '373 except that the '374 is edge triggered for loading versus level triggered for the '373,) The edge triggered load command for the '374's come from the Key Processing Register. The output enable pins for the seven '374's are controlled by the Data Processing Register. The '374 output is back to the 7418257 chips into the input A portions of the chip. The left shift operations for the two twenty-eight bit words is hardwired in this transfer. When the data in the '374 is loaded from the '257 input A, the net effect is to perform a left shift on the two 28 bit words. The '374 output is also sent via a hardwired PC-2 permutation to the forty-eight cumulative I/0 lines of 6810 RAM chips. This allows the sixteen sub-keys to be stored for use in encryption/decryption. (As discussed earlier, the PC-2 permutation takes a fifty-six bit input and produces a forty-eight bit output.) 41


The 6810 is a eight bit by one hundred twenty-eight static RAM chip. It has seven address lines (of which three are wired directly to ground for this application), six chip enable lines (of which five are wired in the enabled state for this application), and a READ/!WRITE line. The remaining four address lines, one chip enable line and the READ/!WRITE line are controlled by the Key Processing Register for this application. The forty-eight I/0 lines from the 6810 chip also supply the sixteen sub-keys for the encryption/decryption portion of the DES board. See Appendix 2 for Key Processing details. 2.2.3 Data Encryption/Decryption The eight 74LS373's that contain the sixty-four bits of encrypt/decrypt data have their output enables active to continually drive data through the wired initial permutation (IP) to the B inputs of sixteen 74LS257 A/B switches. The A/B selector for the '257 chips is controlled by the Data Processing Register. The '257 outputs are sent to eight 74LS374's. The 374's have their edge triggered clocks driven by the Data Processing 42


Register and the output enables for the chips are enabled to drive data continually. The F function is provided to the right thirty-two bits of the '374 output by passing it through a thirtytwo bit input to forty-eight bit output wired permutation E. These forty-eight bits are Exclusive OR'ed with the forty-eight bit sub-keys from the key generation by twelve 74LS86 quad-input Exclusive OR chips. The outputs of the OR's are sent through the eight S-blocks. The S-block function is provided by four 2732 EPROMs. These EPROMs each have twelve address lines and eight output lines. These chips are programmed to combine two of the six to four conversions in one twelve to eight EPROM chip. The output enable and the chip select are wired to continuously send the thirty-two bits of data through the wired permutation P, supplying the final output of function F. The thirty-two bit output of function F is Exclusive OR'ed with the left thirty-two bits from the '374s. This is done by eight 74LS86 chips. The thirty-two bit output of these chips become the right thirty-two bits of the 43


input to the 74LS257 chips. The original right thirty-two bits of the '374 output then become the left thirty-two bits of the input to the 74LS257 chips. The right thirty-two bits of the '374 output are also wired as the left thirty-two bit input to the hardwired Inverse Initial Permutation (IP-1). The right thirty-two bits of this permutation are provided by the thirty-two bit output of the eight 7486 Exclusive OR output. This orientation takes care of the pre-output switch necessary before IP-1 The output of the wired IP-1 is input to the eight 74LS373 encrypt/decrypt data out buffer. These buffers have their level triggered inputs controlled by the Data Processing Register. The output enable lines of these chips are controlled by the 74LS32 or chips as discussed in the addressing scheme. See Appendix 2 for the Data Processing Register Diagram. 2.2.4 Execution of Key Data Generation To generate key data, the two control registers are initialized first. The Data Processing Register is set to the value OxOO to allow the key data transmission to 44


the RAM chip bus. The Key Processing Register is then loaded with Ox40 to load data from the input registers rather than through the left shift processing. (See Appendix 2 for diagrams of Key Processing Register and Data Processing Register.) The user's eight byte key is then written in four double byte writes to the eight key data inputs registers. The key data is then passed through the PC-1 permutation into the seven middle key data registers by writing OxCO then Ox40 to the Key Processing Register. (This toggles the edge sensitive trigger on the seven '374s, loading the data into the register.) The Key Processing Register is then loaded with OxOO to cause the middle key data registers to be loaded from the left shift operations rather than the input registers. The Key Processing Register is then loaded with Ox80 and OxOO in succession. (Again, this loads the seven '374s by toggling the triggers.) The data in the '374s is now the two 28 bit words previously held in the registers left shifted once (as called for by Appendix 1 ) 45


The Key Processing Register is then loaded with OxlO and OxOO in succession. This stores the data in the seven '374s through PC-2 into the six RAM chips in sub-key storage location number zero. The Key Processing Register is then loaded with Ox80, OxOO, Ox80, and OxOO in succession to left shift the data in the '374s two times (as called for in Appendix 1). The Key Processing Register is then loaded with Oxll and OxOO in succession. This stores the second sub-key data in the RAM chips at location number one. This process of left shifting the data and storing it in the RAM continues until all locations, from zero to fifteen, are filled. Then all sub-keys are generated and key processing is complete. 2.2.5 Execution of Data Encryption/Decryption Data encryption and decryption both start out the same. The Data Processing Register has Ox21 stored in it to keep key input data from passing to the key RAM bus and to set the middle data registers to load from the input registers. See Appendix 2 for diagrams of Key Processing Register and Data Processing Register. 46


The eight bytes of data to be encrypted/decrypted are loaded into the encrypt/decrypt input data registers two bytes at a time. The data is then loaded into the middle data registers (eight '374 chips) via permutation IP by loading the Data Processing Register with Ox61, and OxOl in succession. This loads the data in the mid-data registers and sets the mid-data registers to load from the internal processing, not the input registers. The processing is then run in a sixteen step (0 to 15 decimal, OxOO to OxOF hexadecimal) loop. The Key Processing Register is loaded with Ox3#. For encryption processing, the # equals the hexadecimal loop number. For decryption processing, the # equals OxOF minus the hexadecimal loop number. (This results in Ox30 through Ox3F being used for encryption and Ox3F through Ox30 for decryption.) The output registers are then loaded via IPl by placing Ox81 and OxOl in the Data Processing Register. At this point the encrypted/decrypted data is in the output registers and can be read from the board. 47


Chapter 3 Software Algorithm Design and Implementation The software element of this project serves two purposes. The first is to provide a software emulator for the hardware board. The other is to provide a common graphical user interface (GUI) to drive the hardware or software emulator for file operations. The software emulator will take eight bytes of data and eight bytes of key data and encrypt or decrypt the data. This emulator will be used to match the bitwise walk-throughs provided by several of the.sources. This is well suited for the purpose as it is possible to output the various data values at a given time and location. When the software emulator is working, it can be used as a test bed and truth data for the hardware board. (Data encrypted with the emulator should be decryptable by the hardware board and vice versa.) 48


The GUI driver allows the user to enter an existing filename, a new target filename, a process (i.e., encryption, decryption, copy, compress, or decompress), and an eight byte key. The GUI will check for file existence and presence of a key. It will also allow the user to select hardware or software encryption. 3.1 Software Emulator The software emulator is a 'C++' implementation of the algorithm described in chapter 2. The various permutations and S-block functions are performed by integer arrays that are initialized from a datafile at the beginning of encryption and decryption. The Exclusive OR functions and left shift operations are performed by 'C++' library functions. 3.2 Graphical User Interface This software provides the capability to encrypt and decrypt files by opening and closing file streams, processing the file eight bytes at a time, and giving a virtual representation of the encryption/decryption processing. 49


The interface allows the user to enter the data on the screen and then press execute to process the command. Before the encryption or decryption process begins, but after the executor is depressed, the program checks to make sure the two filenames are entered, the source file exists, the target file does not exist, and a key has been entered by the user. If one or more of the preceding items was not done, the user is given an error message for one of the conditions. This process continues until all conditions have been met. If the encryption chosen is software based, the permutation and S-block arrays loaded from the datafile. For both software and hardware encryption or decryption, the sixteen sub-keys are then generated. For hardware processing, this consists of writing the four two byte words to the hardware board and manipulating the control registers. For software processing, this is all done by the software emulator. The source file size is then-determined, and the byte size is divided by eight to determine the number of data words in the file and the size of the remainder (zero to seven bytes). A loop is set up for the number 50


of complete data words in the file. Eight bytes of data are read in from the file at a time, passed through the software emulator or passed to the hardware board (and processed by manipulating the control registers). The encrypted or decrypted data is then retrieved from the emulator or the hardware board and written to the target file. For encryption, the eight byte processing is continued until all complete data words have been processed. For remainder values of one to seven, the data is written into an eight byte word. The remaining byte values (eight -remainder) are filled with the remainder value. For remainder values of zero, an additional eight bytes of data, all equal to zero, is encrypted. The data is then written to the target file. This results in a file size increase from one to eight bytes for file encryption. For decryption, the eight byte processing is continued until the final eight bytes have been decrypted. The last byte in the final eight byte data word is an integer value from zero to seven that represents the number of bytes to write to the target 51


file. This will result in the decrypted file returning to the original file size before encryption. These size adjustments are non-standard and may cause problems if decrypting files from another DES system or encrypting files for decryption by other systems. This processing could easily be enabled and disabled by a switch on the GUI if needed. It has not been provided for this project however. Other actions may also be performed on files by this program, including file copying and a limited form of compression and decompression. These actions are all done by software and will not be discussed in detail in this report. 52


Chapter 4 System Performance and Improvements The system performs DES encryption either by software alone or a combination hardware/software process. The performance of the system along with possible improvements are issues that need to be addressed. 4.1 System Performance Three different measurements were obtained for both hardware and software encryption. These tests are key initialization, eight byte data encryption, and encryption of an 8,072 byte file. The timer routines were obtained from David Reid's article "Designing a High-Resolution Timer" [14 pp. 8-16]. These functions interface with the 8254 Programmable Interval Timer on all AT and later PC's delivering timing accuracies in greater than 1 micro-second. The tests were conducted on a 486DX2 33/66 53


Mhz Personal Computer with 8 MB of memory using MS-DOS 5 0 4.1.1 Key Initialization The interval timed for this test is from the function call for key initialization to the return from the function call. Upon return from the function the graphics mode is terminated, the difference from the start and stop time is computed, the value is printed, and the program terminates. Ten tests were executed for both the hardware and software key initialization methods. The ten software executions produced a mean time of 4,605.3 micro-seconds. The ten hardware executions produced a mean time of 269.2 micro-seconds, or 5.84% of the software execution time. 4.1.2 Eight Byte Encryption The interval timed for this test is from the function call to encrypt the single eight byte word to the return from that call. Upon return from the function the graphics mode is terminated, the difference from the start and stop time is computed, the value is printed, 54


and the program terminates. Note that this does not include key initialization. Ten tests were executed for both the hardware and software single word encryption methods. The ten software executions produced a mean time of 8,277.1 micro-seconds. The ten hardware executions produced a mean time of 195.7 micro-seconds, or 2.36% of the software execution time. 4.1.3 File Encryption The interval timed for this test is from the first read of data from the file to the closing of the files, flushing any buffered data. Upon the closing of the file, the graphics mode is terminated, the difference from the start and stop time is computed, the value is printed, and the program terminates. Note that this does not include key initialization. The file chosen for encryption is DATA.CPP, an ASCII source file 8,072 bytes long, Ten tests were executed for both the hardware and software file encryption methods. The ten software executions produced a mean time of 8,648.8 milli-seconds. 55


The ten hardware executions produced a mean time of 595.3 milli-seconds, or 6.88% of the software execution time. 4.1.4 Performance Overview The results from these tests are shown in Appendix 3. They are illustrative of the statement that "Hardware is always faster than software." For this application, hardware performance was always an order of magnitude faster than software. These results would be even more lopsided if the tests were conducted on a slower machine. The AT bus the hardware system uses functions at 8 Mhz whether on a 286 or a 486 class PC. There would be some drop off in the hardware system's performance due to file operations and software overhead, but it would by minor compared to the drop-off that the software only system would have on the 286. An interesting point is shown when comparing the eight byte encryption and the key initialization. For software performance, the encryption took almost twice as long as the key initialization. For hardware performance, the encryption was quicker than the key 56


initialization. This is due to relative volume of software to be executed and the number of operations needed for control register manipulation. The volume of code to be executed to encrypt the data is much greater than key initialization. For key initialization there are one permutation and one or two left shifts for each of the sixteen iterations along with one permutation for initialization. For data encryption there are many more permutations and many Exclusive OR's to be processed per iteration. For hardware key initialization, each of the sixteen iterations require two to four control register actions for one or two left shifts and two actions to store the data in the register. For hardware key encryption, each of the 16 iterations require one control register action for sub-key selection and two to process each iteration. This is why encryption is faster than key initialization for the hardware system. The complete file encryption shows the smallest differential between software and hardware performance. This is due to the common software overhead both algorithms employ for file I/0 and iteration control.-57


4.2 Possible Improvements This system has much room for improvement and optimization. Currently the hardware system consists of one !SA bus card connected by many wires to a secondary board. This is due to the high volume of chips contained on the boards. (Seventy-one on the primary board and thirty-seven on the secondary) This chip count could be reduced by using Very Large Scale Integration (VLSI) chips. This would reduce space requirements by reducing the number of chips necessary but may increase total part cost. Another method to increase speed is to implement the design using a 32 bit bus technology such as the VESA Local Bus (VLB) or the Peripheral Chip Interface (PC!). For instance, the VLB is an extension to the !SA bus allowing 32 bits of data to be transferred to the bus at the external microprocessor speed. (Generally does not exceed 33 Mhz). This would increase the bus throughput by roughly 800% (32 bits versus 16 bits, 33 Mhz versus 8 Mhz). This would increase all bus processing speed considerably. 58


Another method of increasing processing speed would be to use one of the new 32 bit operating systems for the PC such as OS/2, Windows NT, Solarus, or NEXT 486. These operating systems are designed for 386 class or higher PCs using flat memory models and multi-threading operations. This results in less overhead for segmented memory operations and the multi-threading keeps the processor in action a higher percentage of the time. 59


Chapter .5 Conclusion Now that a working implementation of the DES exists, it is necessary to examine the results and qualify the results. A series of criteria will be outlined and discussed in this chapter. 5.1 Criteria The criteria chosen for examination are performance, application, scalability, and economics. The DES board will be compared to each criterion. If found lacking in an area, possible changes to help the board meet the criterion will be discussed. 5.1.2 Performance Although no specific criterion for encryption speed was specified, it is for the board to process the data at a reasonable rate. The definition of 60


reasonable brings in all the other factors of application, scalability, and economics. However, one can compare rates of encrypting data stored in memory versus a high speed modem's transfer rate. The board can encrypt or decrypt over 40,000 bytes per second or over 320,000 bits per second. A high speed modem transfers data at 19,200 bits per second, which is an order of magnitude slower than the encryption/ decryption board presented here. A hard drive containing forty megabytes of data could be encrypted in about fifty minutes using the system configuration present in my tests. (This could be improved with disk caching and other performance enhancements.) 5.1.3 Application With its ability to encrypt at a high rate of speed, one of the possible applications of the encryption/ decryption board would be encryption of data as it passes over communication lines. Networking is another form of data communications that could use encryption. 61


Since all control of data is lost once it enters the phone lines, encryption is a strong defense against data compromise. As discussed earlier, the board could support high speed modems over standard phone lines easily, However, digital communication circuits could quickly reach or surpass the ability of the board to encrypt "on the fly." That could force communication to be slowed down to encryption speed, Networking is very similar to the modem situation discussed earlier. Some different questions arise pertaining to each individual situation. If the network is a LAN confined to one building where physical security and access control is present, there may not be a need for hardware encryption. For a wide area network (WAN) there may be long haul communication between servers. This brings back the circumstances discussed earlier about data across phone lines and other long haul circuits. For someone who encrypts large amount of data on a PC, the hardware based encryption would be a possibility. Although the approximate fifty minutes to encrypt a forty megabyte hard drive may have seemed excessive, to do the 62


same thing in software on a powerful desktop PC would take almost twelve hours. 5.1.4 Scalability If a person is using encryption for anything more than encrypting files on a disk, a board would be needed for each node in the communication network. Whether or not this would be feasible depends on cost, resources available, and need. For the system to be practical, it would have to fit on one expansion board. It would also have to use some other method of construction other than wire-wrapping for maintenance purposes. This points to using more VLSI technology and some sort of custom PCB expansion board. These options are only cost effective when larger quantities are being ordered. 5.1.5 Economics For this demonstration board, the total chip cost, if bought in quantity, would be under $70. The cost of the sockets was close to $200, the boards cost $40, and there was approximately $20 worth of wires, pins, and 63


other hardware. This totals around $330. It is tough to estimate what a wire wrap technician would charge to work on the board as I don't know what they charge and I have no idea how long it would take. Using VLSI and a custom board would increase costs. Some of this cost could be offset by the reduction in chip count, socket count, and wire wrap charges. This would have to be a product designed for high production to achieve the economies of scale necessary to offset these costs to make the board sell for under $500 a copy. 5.2 ConclusiQn The board met most of the criteria laid out with the possible exception of economics. It is difficult to foresee how much it would cost in mass quantities without redesigning the board incorporating the VLSI technology and the custom expansion board. Otherwise the board would be fine for encryption over long haul data lines. This would limit the number to be purchased, and provide a definite service in securing data links between network servers or for high value data between remote PC's and central computer 64


systems. Of course, along with the hardware, software for the specific application would be necessary. The hardware would have to be delivered with the necessary device drivers for the specific applications. Programming language support would open up a world of applications that would integrate the hardware encryption. The programming libraries could also support software encryption if the hardware is not present. The GUI supplied does something similar. The applicable source would either be provided as is or compiled into a library to preserve the source code. The board was a successful research and development tool. It showed the feasibility of hardware encryption on the PC. Current events are showing the increase in demand for such encryption support. A future evolution of this design may provide a low cost encryption capability for the personal computer. 65


0) 0) '""l K1 L I I cr I I on 1 ; 1 CPC-0 Kn GP C:> I cfo I I o(o 1 PC-2 J K16 Figure Al.l: Key Generation Diagram [6, p. 73] c til til > .... > 0 "' .., .... 5. tl' i .... M t:l .... c+ .... .... CD


PERMUTED INPUT Figure Al.2: INPUT I r-------L-------Kn J I '+ :.-----""\.!_T---L_ __J ... ----------OUTPUT Encryption Diagram [61 p. 65] 67


,.... (iJ OD t: co CD co -s < ... tiO < -r4 Q UJ c t-m 0 .... t:j ..., 0 c ::J 1:1111 (f) .... < Q) 1i) UJ ... t: t: ::J CD CD "' a. .... 1:1111 a: 68


PC-1 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 Table Al.l: Permuted Choice 1 Matrix Iteration Left Shifts 1 1 2 1 3 2 4 2 5 2 6 2 7 2 8 2 9 1 10 2 11 2 12 2 13 2 14 2 15 2 16 1 Table A1.2: Left Shift Table 69


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 Table A1.3: Permuted Choice 2 Matrix IP 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 Table A1.4: Initial Permutation Matrix 70


E 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 Table A1.5: E Bit Selection Matrix Sl Column Number Row No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 11 3 14 10 0 6 13 Table A1.6: 51 Block Permutation Table S2 Column Number Row No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 Table A1.7: S2 Block Permutation Table 71


83 Column Number Row No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 Table A1.8: 83 Block Permutation Table 84 Column Number Row No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 Table A1.9: 84 Block Permutation Table 85 Column Number Row No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 Table A1.10: 85 Block Permutation Table 72


S6 Column Number Row No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 Table A1.11: S6 Block Permutation Table S7 Column Number Row No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 Table Al.12: S7 Block Permutation Table S8 Column Number Row No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 Table A1.13: sa Block Permutation Table 73


E 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 Table A1 14.: p Bit Selection Matrix IP-l 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 Table A1.15: Inverse Initial Permutation Matrix 74


A1 Appendix 2 DES Implementation Details A15-A8 !High A7-A1 8f7 A2 GAL16V8 GAL16V8 I !High High A7-AO 8 A3 GAL16V8 4 IK4-!K1 !Data_Reg !Key_Reg !16 Xfer Figure A2.1: Addressing Logic 75 4 ID4-!D1


en !04-!01 or IK4-!K1 !10 Write I I 4 A4 or AS I 74LS02 4 I 4 DA4-DA 1 or KA4-KA 1 lKey_Reg !Data_ Reg !10 Write -2 AS 74LS02 DR KR 104-!01 !10 Read I 4 A7 I 74LS32 4 I -l0A4-!0A1 4 Figure A2.2: Addressing Logic Continued


015-00 I 16 KA 1-KA4 --+------+ 8x74LS373 A/!B I 14x74LS257 KLOAD 56 7x74LS374 KOUT 56 c or_, 1 4 ADDR I t48 6x6B10 R/!W I 48 cs I Key Data Out Figure A2.3: Key Generation Logic


-l Q:) -l I>AHIAI I A/!11 I M I)J.( li\1 )1----1 K.S. \74 \2 Ky llillil Out Fili!;ure A2.4: Ill M .12 p .\2 .\2 '2 10M'OAI-l OIJIAI> Itt 4K Encryption I Decryption Logic


CD D7rDO +8 Key Processing Register KR 74LS373 1 I I I KLOAD A/IB R/IW CS I I I RAM ADDR (4) 07-00 -+-8 Data Processing Register. DR ----4 74LS373 1 I I I I OLOAD DLOAD NIB I" 1 Figure A2.5: Control Register Logic KOUT


HW sw Key !nit 269.2 4,605.3 Appendix 3 Performance Results Eight Bytes 195.7 8,277.1 8,072 Byte File 595,300. 8,648,800. Table A3.1: Mean Encryption Time (micro-seconds) 80


Bibliography Alexander, Michael. "Data security plan bashed," ComputerWorld, July 1, 1991, pp. 1,80. Anthes, Gary H. "Fed officials pan ban of old encryption specs," ComputerWorld, June 7, 1993, p. 21. Cobb, Stephen. The Stephen Cobb Complete Book of PC and LAN Securtiy, Blue Ridge Summit, PA: Windcrest Books, 1992. Daly, "Hackers switch sides, offer security package," ComputerWorld, March 1, 1993, p. 6. I Daly, James. "PC package may tighten network security," ComputerWorld, February 22, 1993, p. 48. Davies, Donald W. Tutorial: The Security of Data in Networks, New York, NY: IEEE Computer Society Press, 1981. Faison, Ted. Graphical User Interfaces with Turbo C++, Carmel, IN: SAMS, 1991. Intel 486SL Microprocessor SuperSet System Design Guide, Mt. Prospect, IL: Intel Corporation, 1992. Katzan, Harry, Jr. The Standard Data Encryption Algorithm, New York, NY: Petrocelli Books, 1977. Mace, Scott, and Shawn Willett. "IS managers assail data encryption rule," InfoWorld, June 7, 1993, pp. 1,103. McNutt, Dinah. "Who are you?" Unix Review, November, p. 46-51. 1992, Messmer, Ellen. "NIST stumbles on proposal for public-key encryption," Network World, July 27, 1992, pp. 1,42,43,52. Messmer, Ellen. "NSA has public-key chip to complement Clipper Chip," Network World, April 26, 1993, pp. 5,8. Reid, David. "Designing a high-resolution timer," Inside Turbo C++, January/February 1993, pp. 8-16. 81


Rosch, Winn L. The Winn L. Rosch Hardware Bible, New York, NY: Brady Publishing, 1992. Scott, Karyl. "Encryption schemes put safety first," Data Communications, March 21, 1991, pp. 17-20. Seberry, Jennifer, and Josef Pieprzyk. CRYPTOGRAPHY: An Introduction to Computer Security, Sydney, Australia: Prentice-Hall, 1989. Slater, Michael. Microprocessor Based Design, Englewood Cliffs, NJ: Prentice-Hall, 1989. Stallings, William. COMPUTER COMMUNICATIONS: Architectures, Protocols, and Standards, Silver Spring, MD: IEEE Computer Society Press, 1985. Stephens, Mark. "Clinton team to review computer security policy," Infoworld, December 7, 1992, pp. 1,2. The TTL Data Book, Volume 2, Dallas, TX: Texas Instruments, 1985. Van Kirk, Doug. "Data encryption facilitates confidentialy," Infoworld, March 22, 1993, p. 62. 82