NATIONAL UNIVERSITY OF RWANDA
FACULTY OF APPLIED SCIENCES
DEPARTMENT OF COMPUTER SCIENCE

ACADEMIC YEAR 2011

Performance analysis of Encryption/Decryption algorithms using SimpleScalar

By: MANIRIHO Malachie and NIZEYIMANA Jean-Paul

Supervisor: Dr.-Ing. NIYONKURU Adronis

Huye, 2011
CHAPTER ONE: GENERAL INTRODUCTION

1.1. BACKGROUND TO THE STUDY

There are various security measures that can be imposed in order to secure the information stored. As more and more technologies evolve, an irresponsible person may try to find a way to excavate any loopholes within the system in order to penetrate into the heart of its weaknesses. This is due to the fact that human-made designs can also be broken by another human. Thus, over time security measures must constantly be reviewed and strengthened in order to combat hackers or culprits hot on the heels of system developers who are also using high technologies.

One of the means to secure the data is to apply a secret code of encryption. By having it encrypted, the sender can pass the data to the receiver and only the receiver or authorized personnel can have access to the data provided they have been given a key by the sender to decrypt it in order for them to view the information. Thus, without having the right key, nobody is able to read the encrypted data received or stored. Even if hackers or unauthorized person managed to intercept or steal the data, it would be futile because the text looks ridiculous to them.

It is widely recognized that data security will play a central role in the design of future IT systems. Many of those IT applications will be realized as embedded systems which rely heavily on security mechanisms. Examples include security for wireless phones, wireless computing, pay-TV, and copy protection schemes for audio/video consumer products and digital cinemas. In addition, a large share of those embedded applications will be wireless, which makes the communication channel especially vulnerable. All modern security protocols use encryption/decryption algorithms. This contribution surveys several important cryptographic concepts and their relevance to embedded system applications.

Many encryption algorithms are widely available and used in information security. They can be categorized into Symmetric (private) and Asymmetric (public) keys encryption.
The two main characteristics that identify and differentiate one encryption algorithm from another are its ability to secure the protected data against attacks and its speed and efficiency in doing so. This study provides a performance comparison between four of the most common encryption algorithms: DES, 3DES, Blowfish and AES (Rijndael) then find out an efficient and powerful cryptographic algorithm for embedded systems. The performance analysis for these algorithms will be carried out using SimpleScalar simulator.

SimpleScalar provides detailed performance information about program running on a variety of target platforms with a single host simulation platform. SimpleScalar is more widely used by architecture designers and researchers.

1.2. STATEMENT OF THE PROBLEM

Security is becoming increasingly important in wireless embedded systems, especially when the data being transmitted is life-critical and/or confidential via legal mandate. Miniaturization, mobility and networking are essential IT trends in recent years. For this reason security requirements have been increased correspondingly, so that common concepts are no longer sufficient (Schorcht 2010:3).

The networking of embedded systems constitutes an unsecured interaction or unsaved data exchange using various communication channels. Especially wireless communication is particularly endangered and provides a unique opportunity for active or passive attacks such as man-in-the-middle attack.

Encryption/decryption algorithms provide a secure communication between two parties and protect the information against unauthorized access. Due to limited resources in embedded systems, the practical implementation of usual cryptographic algorithms is not always possible. This leads to the following specification of central research question: Which cryptographic algorithm provides for data confidentiality, authentication, message integrity and anti-replay protection in spite of low processing speed, energy consumption and memory capacity of most embedded systems?
Performance analysis of different methods could answer such question. The main goal of this study is to evaluate the performance and efficiency encryption/decryption algorithms for embedded systems.

The main criteria of this analysis are processing computation, power needed, memory consumption, energy consumption, duration of encryption and decryption to perform the algorithm. For performance analysis, SimpleScalar tool set has been used. Each criterion achieved a different number of maximal obtainable points. A summary of the evaluation as well as the visualization of the results conclude the performance investigation and determine the high-performance algorithm for embedded systems.

1.3. OBJECTIVES OF THE STUDY

This study follows general and specific objectives as explained in the following paragraphs. 1.3.1. General objective

The general objective of this study is to analyse the performance of encryption/decryption algorithms using SimpleScalar tool set, and find out an efficient and powerful cryptographic algorithm for embedded systems. 1.3.2. Specific objectives

* To implement some encryption/decryption algorithms in C language * To analyse the performance of encryption/decryption algorithms and to compare those algorithms in the context of speed, memory consumption, complexity and to describe their functionality in data security. * To represent and interpret performance results from SimpleScalar using statistical tools.

1.4. RESEARCH QUESTIONS

The study aimed implementing cryptographic algorithms in C language and analyse their performance using SimpleScalar tool set then find out an efficient and powerful cryptographic algorithm for embedded systems. This research is guided by the following questions: * Which cryptographic algorithm provides for data confidentiality, authentication, message integrity and anti-replay protection in spite of low processing speed, energy consumption and memory capacity? * Which encryption/decryption algorithm is suitable for embedded system?

1.5. INTEREST OF THE STUDY

This research will help us to improve our knowledge in cryptography, performance analysis, embedded systems security and simulation (especially in SimpleScalar simulator). The study will show the cryptographic algorithm which suitable for embedded systems among the selected algorithms. Finally, this study will guide the interested future researchers in this domain. 1.6. SCOPE OF THE STUDY

This study is limited to the performance analysis of encryption/decryption algorithms. However, this study provides a performance comparison between four of the most common encryption algorithms: DES, RSA, Blowfish and AES (Rijndael). To implement those cryptographic algorithms, C programming language has been used and SimpleScalar has been used as compile and performance analysis tool.

1.7. METHODOLOGY

To carry out our research simulation method has been used. SimpleScalar simulator has been used to compile and run C programs and for performance analysis. SPSS and MS Excel have been used for results representation and interpretation. We used C language because SimpleScalar comes with a C compiler which compiles C programs targeting the SimpleScalar Simulator.
1.8. ORGANISATION OF THE STUDY

This study is divided into five chapters:
The first chapter deals with the general introduction of the study.
The second chapter deals with the review of literature.
The third chapter provides the research methodology.
The fourth chapter provides the implementation and performance analysis of cryptographic algorithms using SimpleScalar.
The last chapter is concerning the conclusion and recommendations.

CHAPTER TWO: LITERATURE REVIEW

2.1. INTRODUCTION

This chapter is made up by the conceptual framework and the overview on cryptography. In this chapter, several concepts are defined and various opinions, ideas of different authors pertaining to cryptography. In this chapter we will be presenting each encryption/decryption algorithm. First we will do a theoretical study of each one, followed by a security and analysis.

2.2. DEFINITION OF CONCEPTS

2.2.1. Performance analysis

According to Encyclopedia, in software engineering, performance analysis or program profiling, is the investigation of a program's behavior using information gathered as the program executes. The usual purpose of this analysis is to determine which sections of a program to optimize - to increase its overall speed, decrease its memory requirement or sometimes both.

2.2.1.1. Performance analysis techniques Three analysis techniques are used for performance analysis; these are analytical modeling, simulation, and measurement. To choose which one to use for the analysis of a system depends on certain considerations. The most important consideration is the stage in which the analysis is to be performed, measurement can’t be performed unless the system already exists or at least a similar system does, if the proposed design is a new idea then only analytical modeling or simulation techniques can be used. (Jain, Raj. 1991:23) 2.2.1.2. Performance metrics

Each performance study has different metrics that can be defined and used to evaluate that specific system under study, although these metrics are varied and different from one system to another, common metrics exist and are used in most general computer system evaluation.
These most common metrics are: System Efficiency, Throughput, Response time, Speedup, Redundancy, Utilization, Quality, Reliability, availability, Cost/performance ratio. (McKerrow, Phillip. 1988)

2.2.1.3. Algorithm Performance Analysis

The amount of time that it takes a computer to perform a task is primarily a function of the algorithm that is being performed. If an algorithm has many steps in it, this may cause the program to take a long time to execute. More commonly, however, an algorithm will take a long time to execute because of having to go through a loop a large number of times. Nesting one loop within another will increase the execution time considerably more.

The number of times that a program cycles through a loop is almost always related to the “size of the problem”. The size of the problem is usually given by one or two parameters, for example the number of elements that need to be sorted in a sort algorithm. We introduce here a notation, called the “Big-Oh” notation, which describes the asymptotic performance of an algorithm; that is, the performance as the size of the problem increases.

Let n be a non-negative integer parameter describing the size of the problem and let f(n) be a function describing the actual performance of the algorithm. The performance could be in terms of the amount of time it takes to perform the algorithm, or the number of steps that need to be executed multiplied by the number of times they must be re-executed. The relative time it takes to perform different types of operations (e.g. call a function, multiply two numbers) can also be considered using weighting functions.

Let g(n) be another function. If there is a real constant c > 0 and an integer constant n0 ≥ 1, such that f(n) ≤ cg(n) for every integer n ≥ n0, then g(n) is the “order or the complexity” of the algorithm. The order of the algorithm is then written in “Big-Oh” notation as O(g(n)). For example, if the time that it takes to execute an algorithm is given by f(n) = 7n – 2, then g(n) = n is a valid function for g(n) because, if c = 7 and n0 = 1, the criteria is satisfied. The order of the algorithm is therefore written in Big-Oh notation as O(n). Note: n could be the number of input data to be processed by the function f Example: - function: sort integer array n: how many elements to sort.

Note that, g(n) = n2 is also a valid function, however, since we always want to show our algorithms in the best light (show them to be as fast as possible), we always choose the smallest function possible. We also always use the simplest function possible, so we would use g(n) = n rather than g(n) = n - 2.

Most algorithms fall into one of the following types.

Logarithmic | O(log n) | Very good | Linear | O(n) | Good | Quadratic | O(n2) | Ok | Polynomial | O(nk) k ≥ 1 | Poor if k > 2 | Exponential | O(an) a > 1 | Awful |

In most cases the number of cycles is not only dependent on the size of the problem, but also on the data itself. In these cases, it is possible to use the same concepts to establish minimum, maximum or average performance for an algorithm, using the same techniques.

Creating algorithms with as fast as possible asymptotic behavior is important because the performance of a poor algorithm will not get much better, even if the hardware is improved. For example, consider an algorithm that is O(2n) and is able to process a problem of size m in 10 seconds. If the hardware speed is improved so that it is 256 times as fast, then only 8 more elements can be processed before it will take 10 seconds again (i.e. now a problem of size m + 8 will take 10 seconds). This is not a great improvement. Some problems have inherent limits in how quickly they can be solved, even if the best possible algorithm is used. This is referred to as the computational complexity of the problem. For example, some problems can be proved mathematically to be only solvable with algorithms that are exponential in the size of the problem.

2.2.2. SimpleScalar

The SimpleScalar is a simulator software used for program performance analysis, detailed microarchitectural modeling, and hardware-software co-verification. Using the SimpleScalar tools, users can run applications that simulate real programs running on a range of modern processors and systems.

The tool set includes sample simulators ranging from a fast functional simulator to a detailed, dynamically scheduled processor model that supports non-blocking caches, speculative execution, and state-of-the-art branch prediction. The SimpleScalar tool set includes performance visualization tools, statistical analysis resources, and debug and verification infrastructure. (www.simplescalar.com)

2.2.3. Embedded system
An embedded system is a computer system designed to do one or a few dedicated and/or specific functions often with real-time computing constraints. It is embedded as part of a complete device often including hardware and mechanical parts. By contrast, a general-purpose computer, such as a personal computer (PC), is designed to be flexible and to meet a wide range of end-user needs. Embedded systems control many devices in common use today (Michael Barr; Anthony J. Massa 2006).
Embedded systems are controlled by one or more main processing cores that are typically either microcontrollers or digital signal processors (DSP). The key characteristic, however, is being dedicated to handle a particular task. They may require very powerful processors and extensive communication, for example air traffic control systems may usefully be viewed as embedded, even though they involve mainframe computers and dedicated regional and national networks between airports and radar sites (each radar probably includes one or more embedded systems of its own). (Heath, Steve 2003).
Since the embedded system is dedicated to specific tasks, design engineers can optimize it to reduce the size and cost of the product and increase the reliability and performance. Some embedded systems are mass-produced, benefiting from economies of scale.
Physically, embedded systems range from portable devices such as digital watches and MP3 players, to large stationary installations like traffic lights, factory controllers, or the systems controlling nuclear power plants. Complexity varies from low, with a single microcontroller chip, to very high with multiple units, peripherals and networks mounted inside a large chassis or enclosure.

2.2.3.1. Embedded system security

The embedded or handheld devices are getting increasingly connected and are more and more involved in network communications. The users of these devices are now able to execute almost all the network/internet applications that run in a PC on these devices. These devices are also increasingly involved in transfer of secure data through public networks that needs protection from unauthorized access and thus the security requirements in embedded devices have become critical.

The secure data falls in different categories requiring different levels of security. According to whose interest the protection of the data is, the secure data can be classified as two: the users private data and the user restricted data. The users private data are those data which when its security is compromised impacts directly on the user.

A simple example of compromising such security is having access to a user’s internet banking password. But in case of user restricted data, it’s not the user but the content (data) provider who suffers direct loss on compromising the security of that data. The examples of such data are digital multimedia content such as copyrighted digital photos, audio and video contents.

The secure data not only requires protection during data transfer but also while handling the data at the end user devices. Vulnerability at the end user device, like easy access to the secret keys that are used to encrypt or decrypt the data, can easily turn down the entire security measures. The protocol involved for the secure transmission of either of the above mentioned contents through a public network uses more or less the same techniques but the handling of the user restricted data at the user’s end involves much more care as the content is protected from the user itself.
Thus an embedded device must implement methods or protocol for secure data transfer and also should implement security methods to defeat attempts of unauthorized access of secure data from the device. The security needs for an embedded device thus can be classified into two: * Security needs for data transfer and * Security needs within the device

a) Security needs for data transfer

The data in a public network passes through a number of untrusted intermediate points. Therefore the secure data must be scrambled in such a way that the data will be useless or unintelligible for anyone who is having unauthorized access to the secure data. This can be achieved with the help of cryptographic methods such as Encryption/Decryption, Key Agreement, Digital Signatures and Digital Certificates. (Anoop MS, 2007:3)

b) Security needs within the device

Whether it is the private-key of any public-key algorithm or it is any previously negotiated shared secret between the devices, the security of data transferred depends in the secrecy of these keys. To enforce additional security, some cryptographic algorithms may also specify a set of constant values that should not be disclosed from the device. (Anoop MS, 2007:4)

The secret keys are stored inside the device, some even for the lifetime of the device. Hardware and software security measures implemented in the device must defeat any attempts of unauthorized access to retrieve these secret keys. Also, there are data such as the Root CA Certificate in the device that can be disclosed but should be prevented form unauthorized modification. If Root CA certificate can be modified, then the attacker can make the device to accept any certificate by substituting a fake root CA certificate and thus defeating the purpose certificate and secured communication. It is therefore also important that the security in the device is such that the data such as Root CA Certificates in the device is not subjected to unauthorized modification. (Anoop MS, 2007:4)

2.2.4. Information security

In general, security denotes “the quality or state of being secure to be free from danger” (Whitman, 2007:9). Security is classified into different layers depending on the type of content intended to be secured:

Physical security: Defines the required issues that are needed to protect the physical data or objects from unauthorized intrusion. Personal security: It is defined as the security of the individuals who are officially authorized to access information about the company and its operations Operational security: It mainly relies on the protection of the information of a particular operation of the chain of activities.
Communication’s security: The communication’s security encompasses the security issues regarding the organisation’s communication media, technology and content.
Network security: The network security is responsible for safeguarding the information regarding the „networking components‟, „connections‟ and contents.

Information security:

Information security is the protection of information and the systems and hardware that use, store, and transmit that information. Information security can be defined as measures adopted to prevent the unauthorized use or modification of use of data or capabilities. The critical characteristics of information are: Availability, Accuracy, Authenticity, Confidentiality and Integrity.

Availability: prevention of unauthorised disclosure of information. It enables users who need access the information to do so without any interference or obstruction and to receive it in the required format. The availability of information requires the verification of the user as one with authorized access to information (Whitman, 2007).

In other words the availability can be defined as “Ensuring timely and reliable access to make use of information. A loss of availability is the disruption of access to or use of information or an information system” (Stallings, 2007:09).
Accuracy: The information is deemed accurate if it does not contain any mistakes / errors and possesses the value that end user expects. If the information holds a value different from that of the end user‟s expectations because of intentional or unintentional modifications of its content it becomes no longer accurate (Whitman, 2007).

Authenticity: Authenticity refers to the quality or state of being genuine or original. It should not be a reproduction or fabrication of any previously known data. The Information is considered authentic when it is originally created, placed, stored or transferred. In general, authenticity is ensuring that all the data remains in its original state by stopping any ways of the unauthorised modification of information (Whitman, 2007).

Confidentiality: “The confidentiality is the quality or state of preventing disclosure or exposure to unauthorized individuals or system”. Confidentiality is basically privacy and secrecy which means protection of personal data or that of data belonging to an organisation. Confidentiality of information ensures that only those with the rights and privileges access a particular set of information and prevent from unauthorized access (Whitman, 2007).

Integrity: It is the prevention of unauthenticated modification of data. “The quality or state of being whole, complete and uncorrupted is the integrity of information”. The integrity of any data is lost when it is subjected to corruption, damage (external / internal), destruction or other disruption of its authentic state by intended or unintended sources (Whitman, 2007).

2.3. OVERVIEW OF CRYPTOGRAPHY

2.3.1. Definition

The word cryptography is derived from two Greek words which mean “secret writing”. Cryptography is the process of scrambling the original text by rearranging and substituting the original text, arranging it in a seemingly unreadable format for others. Cryptography is an effective way to protect the information that is transmitting through the network communication paths (Bishop, 2005).

Cryptology is the science that deals about cryptography and cryptanalysis. Cryptography is the approach of sending the messages secretly and securely to the destination. Cryptanalysis is the method of obtaining the embedded messages into original texts (Whitman, 2007).

In general, cryptography is transferring data from source to destination by altering it through a secret code. The cryptosystems uses a plaintext as an input and generate a cipher text using encryption algorithm taking secret key as input.
The important elements in cryptosystems are:

Plain text: The plain text is an original piece of information that is needed to send information to the destination. Encryption algorithm: This is the main key to any cryptographic system. This encryption algorithm subjects the plain text to various substitutions and transformations.
Secret key: The secret key is given by the user which will act as an input to the encryption algorithm. Based on this key, various substitutions and transformations on the plain text will differ.
Cipher text: This is the output generated by the encryption algorithm. The cipher text is the jumbled text. The cipher text differs with each and every secret key that has given to the encryption algorithm.
Decryption algorithm: This is opposite to the “encryption algorithm‟. It will acquire cipher text and secret key as an input and produce plain text as an output.

Figure 1: General model of cryptographic system
2.3.2. Cryptographic algorithms

There are many different cryptographic algorithms. Many cryptographic algorithms rely on public mathematical techniques for strength while others purport strength through secrecy, however misguided this may be. All cryptographic algorithms can be divided into two groups: symmetric or asymmetric. In practice, asymmetric and symmetric ciphers are often used together.

2.3.2.1. Symmetric Encryption

Symmetric encryption is a single key encryption and also known as conventional encryption. It is also referred as “private key cryptography”. The symmetric encryption algorithm generally uses the same key for encryption and decryption. The security level for this type of encryption will depend on the length of the key.

Figure 2: Symmetric encryption

Symmetric ciphers can be divided into two types of ciphers: block and stream.

* Stream Ciphers are a type of symmetric encryption algorithm that can be designed to be very fast. Stream ciphers typically operate on small units, such as bits, of plaintext. Stream ciphers generate a keystream that is used as a key. Encryption is performed using the bitwise XOR operation of the keystream against the plaintext, one bit or one byte at a time (Stallings, 2003: 63). The security of stream ciphers is dependent on the robustness of the keystream generator; if the keystream generation is weak, the encryption may easily be broken (Schneier, 1994:170-171).

* Block ciphers are a type of symmetric-key encryption that transforms a fixed-length block of plaintext into a block of ciphertext. Typical block sizes are 64 and 128 bits while key sizes are generally 128 or 256 bits. The plaintext and resulting ciphertext are always the same size (Ferguson, 2003:43). If the plaintext is longer than the block length, a block cipher mode must be used to perform encryption. Block cipher modes of operation are discussed in the following sections.

One-time Pads

One-time pads, invented in 1917 by Major Joseph Mauborgne and Gilbert Vernam, have been called the “perfect encryption scheme” (Schneier, 1994:13). One-time pads, also called Vernam ciphers, use as a key a large set of nonrepeating data that is the same size as the data to be encrypted. Encryption is performed with each bit of the key XORed against each bit of the plaintext. One-time pads are considered perfectly secure, yet aren’t commonly used as it is impractical to generate and transmit a truly random key of the same size as the data.

a) Attack on symmetric encryption systems

There are two types of methods that will attack on symmetric encryption systems. The first one is Cryptanalysis. If the attacker gets to know some information about the plain text and cipher text, he analyses the characteristics of the algorithms used for encryption and tries to generate keys. The second type of attack is known as “brute force attack‟. In this type of attack, the defender attempts to know the cipher text and try every possible key for translation. To avoid this problem, the user should use the key that no longer can be estimated like 128 or 168 bit keys (Alfred J, M et al., 1996).

b) Different symmetric encryption algorithms

The different symmetric encryption algorithms are: * Data encryption standard * Advanced encryption standard

2.3.2.1.1. Data encryption standard (DES)

DES is the first standardized crypto algorithm. It was developed by IBM in the 1970s and published in the Official Gazette of the United States Patent and Trademark Office in 1975 and 1976. In 1977 DES became a Federal Information Processing Standard (FIPS). It fulfills the later defined Security Requirements for Cryptographic Modules which specify security requirements for protecting classified information within computer and telecommunication systems. The DES algorithm can be used in four different modes which are Electronic Codebook mode (ECB), Cipher Block Chaining mode (CBC), Cipher Feedback mode (CFB), and Output Feedback (OFB).

Design of the DES Algorithm

The DES algorithm basically consists of three parts which are initial permutation, 16 rounds of encryption and final (inverse initial) permutation. It operates on 64-bit chunks of data, hence any message which needs to be encrypted using DES has to be padded with appropriate filling data to the next 64-bit boundary. Also the key provided for en- or decryption needs to be 64-bit, however, every eighth bit is dropped during the key permutation resulting in an effective bit length of 56-bit. The remaining 8 bits can be used for parity checks but do not contribute to cryptographic strength.

Within each round, key generation and encryption take place. Key generation is fairly easy: The 56 bits of key data are split into halves; each half is fed into a 28-bit cyclic left-shift register which according to a round constant rotate the key halves up to two positions.

Figure 3: Data Encryption Standard Algorithm

The encryption process itself (see Figure 3) is slightly more complicated: The input data is split into two chunks of 32 bits each where only the right half is included into the encryption function. Through an expansion permutation these right 32 bits are expanded to 48 bits; similarly, the 56-bit key is compressed to 48 bits. Both values are then XORed, the result of this operation is fed into a lookup table implemented as 8 S-Boxes. These S-Boxes provide the main encryption (or decryption) function within the DES algorithm. All other permutations employed are used to evenly scatter the input data among a 64-bit chunk ensuring that no conclusions about message and key can be drawn by analyzing multiple chunks of encrypted data.

Functionally, each S-Box is a ROM with 32 memory locations: It translates a 5-bit input value into a corresponding unique 4-bit output value. No two S-Boxes are the same. The 48-bit result of the previously performed XOR operation between compressed round key and expanded right half of the input data is fed into the array of S-Boxes producing a 32-bit lookup value. This value undergoes another permutation, the P-Box permutation, before it is XORed with the left half of the input data.

Figure 4. DES Encryption Scheme
2.3.2.1.2. Triple DES

Triple DES is an extension to the DES algorithm. Triple DES uses the same approach for encryption as DES. 3DES takes three 64 bit keys which has a total length of 192 bits. We can give more than one key that is two or three keys for encryption as well as for decryption such that the security will be stronger. It is approximately 256 times stronger than the normal DES algorithm, so that this algorithm can avoid the brute force attack. The main drawback of using 3DES algorithm is that the number of calculations is high reducing the speed to a greater extent. And the second drawback is that both DES and 3DES use same 64 block size to avoid security issues. “Advanced Encryption Standard” algorithms are used to avoid these limitations.

2.3.2.1.3. Advanced Encryption Standards (AES)

Advanced Encryption Standards (AES) takes a block of size 128 bits as input and produces the output block of same size. AES supports different key sizes like 128, 192 and 256 bit keys. Each encryption key size will change the number of bits and also the complexity of cipher text.

The major limitation of AES is error propagation. The encryption operation and key generation both engage in number of non linear operations, so, for lengthy operations it is not suitable. A cryptanalyst may able to use the continuities in plain text to simplify the decryption (Whitman, 2007).

2.3.2.1.4. Blowfish

Blowfish is a 64-bit block cipher with a variable-length key. The algorithm consists of two parts: key expansion and data encryption. Key expansion converts a key of up to 448 bits into several subkey arrays totaling 4168 bytes.

Data encryption consists of a simple function iterated 16 times. Each round consists of a keydependent permutation, and a key- and data-dependent substitution. All operations are additions and XORs on 32-bit words. The only additional operations are four indexed array data lookups per round.
Blowfish uses a large number of subkeys. These keys must be precomputed before any data encryption or decryption.

The P-array consists of 18 32-bit subkeys: P1, P2,..., P18
Four 32-bit S-boxes have 256 entries each:
S1,0, S1,1,..., S1,255
S2,0, S2,1,..., S2,255
S3,0, S3,1,..., S3,255
S4,0, S4,1,..., S4,255

Figure 5: Blowfish
Security of Blowfish

Serge Vaudenay (1995) examined Blowfish with known S-boxes and r rounds; a differential attack can recover the P-array with 28r + 1 chosen plaintexts. For certain weak keys that generate bad S-boxes (the odds of getting them randomly are 1 in 214), the same attack requires only 24r + 1 chosen plaintexts to recover the P-array. With unknown S-boxes this attack can detect whether a weak key is being used, but cannot determine what it is (neither the S-boxes nor the P-array). This attack only works against reduced-round variants; it is completely ineffective against 16-round Blowfish.

The discovery of weak keys is significant, even though they seem impossible to exploit. A weak key is one in which two entries for a given S-box are identical. There is no way to check for weak keys before doing the key expansion. If you are worried, you have to do the key expansion and check for identical S-box entries. I don’t think this is necessary, though.

2.2.2 Asymmetric Encryption

Asymmetric encryption is also known as “Public key encryption‟. The AES works same as Symmetric encryption, the main difference between AES and Symmetric encryption is in using keys. In asymmetric encryption, the encryption and decryption will be done by two different keys. It will use plain text, encryption algorithm and decryption algorithm same as Symmetric encryption as discussed in above section.

Figure 6: Asymmetric Encryption

In Asymmetric encryption, only the data that is encrypted using public key can be decrypted using the same algorithm. And the message which is encrypted using private key can be decrypted using only the matching public key.

The main problem with Asymmetric algorithm is “cipher keys”. Whenever two different people want to exchange the data simultaneously using asymmetric encryption they need to have four different keys. It will be more confusing to resolve as the corresponding key is required for the particular file to open.
The most important public key encryption algorithm is RSA algorithm.

2.2.2.1. RSA algorithm

RSA was first developed in 1977. RSA functions depend upon the large prime numbers of public and private keys. The security is also based on the difficulty of prime numbers. The RSA algorithms are used in public key encryptions as well as in digital signatures. It allows the sender to encrypt the message using public key and decrypt the message using private key by receiver. So, the security will be high using RSA in public key encryption (Stallings, 2007).

Figure 7: RSA Algorithm

2.2.2.2. Security of Public-Key Algorithms

Since a cryptanalyst has access to the public key, he can always choose any message to encrypt. This means that a cryptanalyst, given C = EK(P), can guess the value of P and easily check his guess. This is a serious problem if the number of possible plaintext messages is small enough to allow exhaustive search, but can be solved by padding messages with a string of random bits. This makes identical plaintext messages encrypt to different ciphertext messages.

This is especially important if a public-key algorithm is used to encrypt a session key. Eve can generate a database of all possible session keys encrypted with Bob’s public key. Sure, this requires a large amount of time and memory, but for a 40-bit exportable key or a 56-bit DES key, it’s a whole lot less time and memory than breaking Bob’s public key. Once Eve has generated the database, she will have his key and can read his mail at will.
Public-key algorithms are designed to resist chosen-plaintext attacks; their security is based both on the difficulty of deducing the secret key from the public key and the difficulty of deducing the plaintext from the ciphertext. However, most public-key algorithms are particularly susceptible to a chosen-ciphertext attack.

In systems where the digital signature operation is the inverse of the encryption operation, this attack is impossible to prevent unless different keys are used for encryption and signatures.

CHAPTER THREE: RESEARCH METHODOLOGY

Methodology is a set of methods and principles that are used when studying a particular subject or doing a particular kind of work. It describes the ways in which data was collected, data collection instruments, and data processing and analysis. This chapter explains the methodology that was used in the study.

3.1. Documentation

Documentation is the process of collecting and extracting the documents which relevant research. This is a data gathering process based on visiting websites, reading books, texts and documents related to the topic.

3.2. Simulation

Simulation is the imitation of some real thing, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system.

A computer simulation (or "sim") is an attempt to model a real-life or hypothetical situation on a computer so that it can be studied to see how the system works. By changing variables, predictions may be made about the behaviour of the system. (SOKOLOWSKI, J.A., Banks, C.M. 2009:6).

In this study, to simulate SimpleScalar simulator has been used.

3.3. SimpleScalar

The SimpleScalar tool set is a simulator software used for program performance analysis, detailed microarchitectural modeling, and hardware-software co-verification. Using the SimpleScalar tools, users can run applications that simulate real programs running on a range of modern processors and systems.

3.3.1. History

SimpleScalar was written by Todd Austin for his PhD dissertation, First public release in July 1996 by Doug Burger. Current release 3.0

3.3.2. Overview of SimpleScalar

Figure 8: SimpleScalar overview * Compiler chain is GNU tools ported to SS ISA * Fortran codes are converted with AT&T f2c * GLIBC libraries ported to SimpleScalar

3.3.3. SimpleScalar Simulators The tool set itself consists of a collection of microarchitecture simulators that emulate the microprocessor at different levels of detail .The simulators in SimpleScalar are: * sim-safe : slightly slower instruction interpreter, as it checks for memory alignment and memory access permission on all memory operations. This simulator can be used if the simulated program causes sim-fast to crash without explanation.

* sim-fast : faster (and twisted) version of sim-safe. Fast instruction interpreter, optimized for speed. This simulator does not account for the behavior of pipelines, caches, or any other part of the microarchitecture. It performs only functional simulation using in-order execution of the instructions . * sim-profile : instruction interpreter and profiler. This simulator keeps track of and reports dynamic instruction counts, instruction class counts, usage of address modes, and profiles of the text and data segments.

* sim-cache: memory system simulator. This simulator can emulate a system with multiple levels of instruction and data caches, each of which can be configured for different sizes and organizations. This simulator is ideal for fast cache simulation if the effect of cache performance on execution time is not needed.

* sim-bpred : branch predictor simulator. This tool can simulate difference branch prediction schemes and reports results such as prediction hit and miss rates. Like sim-cache, this does not simulate accurately the effect of branch prediction on execution time.

* sim-outorder : detailed OoO issue performance simulator (with timing). This tool models in detail and out-of-order microprocessor with all of the bells and whistles, including branch prediction, caches, and external memory. This simulator is highly parameterized and can emulate machines of varying numbers of execution units.

3.3.3.1. Simulator Structure

Figure 9: Simulator Structure 3.3.4. Sample Commands * Running a simulator:
– sim-outorder [simulator opts] benchmark_name [bench opts] * Compiling a C program:
– ssbig-na-sstrix-gcc -g -O -o foo foo.c –lm * Compiling a Fortran program:
– ssbig-na-sstrix-f77 -g -O -o foo foo.f -lm * Compiling an SS assembly program:
– ssbig-na-sstrix-gcc -g -O -o foo.s -lm * Disassembling a program:
– ssbig-na-sstrix-objdump -x -d -l foo * Building a library: – ssbig-na-sstrix-{ar, ranlib} 3.3.5. Simulation Output (sim_outorder) Let’s compiling a new code and running it on top of SimpleScalar: create a new file, “hello.c”, that has the following code: #include<stdio.h> main() { printf("Hello World!\n"); } Compile it using the following command: $ $IDIR/bin/sslittle-na-sstrix-gcc –o hello hello.c That should generate a file “hello”, which we will run by: $ $IDIR/simplesim-3.0/sim-outorder hello In the output, we find the following:

3.3.6. Installation of SimpleScalar on Unix

The steps are as follows :

1) install Unix platform
2) update installation by ­$sudo apt­get update
3) get required applications using ­$ sudo apt­get install flex­old bison build-essentiel
4) start extraction by doing ­
$mkdir /tmp/simplescalar
$cd /tmp/simplescalar/
$wget http://csrl.unt.edu/downloads/simplescalar.tgz
$tar xvfz simplescalar.tgz
//NOTE ­ directories in /tmp in ubuntu are deleted once you restart your computer, so if you're using these steps, make sure u keep a backup of your files. Else once you're comfortable with the installation, change the path to some other directory. but even with this path, simplescalar and cross­compiler will work even after restarting ...

5) install gcc­3.4 ­
$sudo apt­get install gcc­3.4
$export CC="gcc­3.4";

6) setting up installation ­
$export HOST=i686­unknown­linux
$export TARGET=sslittle­na­sstrix
$export IDIR=/opt/simplescalar

//NOTE ­ if you're processor is old or if you're not sure of the architecture, do $uname ­a ... this will give the processor architecture as i686, i386 etc.

7) Simplescalar tools ­
$cd /tmp/simplescalar
$tar xvfz simpletools­2v0.tgz
$rm ­rf gcc­2.6.3
$sudo mkdir ­p /opt/simplescalar
$sudo mv f2c­1994.09.27/ glibc­1.09/ ssbig­na­sstrix/ sslittle­na­sstrix/ /opt/simplescalar/

8) Simplescalar utils ­
$cd /tmp/simplescalar
$tar xvfz simpleutils­990811.tar.gz
$cd /tmp/simplescalar/simpleutils­990811
$./configure ­­host=$HOST ­­target=$TARGET ­­with­gnu­as ­­with­gnu­ld ­­prefix=$IDIR
$sudo make CC=gcc­3.4
$sudo make install CC=gcc­3.4
9) Final Simplescalar installation step ­
$cd /tmp/simplescalar
$tar xvfz simplesim­3v0d.tgz
$cd simplesim­3.0
$sudo make config­pisa
$sudo make CC=gcc­3.4

//NOTE ­ if all steps go through, you should not get any errors and you will get a message at this point ­ "My work is done here"

10) Testing the installation ­$./sim­safe tests/bin.little/test­math

//NOTE ­ this should give some statistics like cache hits, misses etc.

11) cross­compiler installation ­
$cd /tmp/simplescalar
$sudo mv simplesim­3.0 /opt/simplescalar
$cd /tmp/simplescalar/
$tar xvfz gcc­2.7.2.3.ss.tar.gz
$cd /tmp/simplescalar/gcc­2.7.2.3
$export PATH=$PATH:$IDIR/sslittle­na­sstrix/bin
$./configure ­­host=$HOST ­­target=$TARGET ­­with­gnu­as ­­with­gnu­ld ­­prefix =$IDIR
$sudo make LANGUAGES="c c++" CFLAGS=­O3 CC=gcc­3.4

12) Copy some files ­ sudo cp patched/sys/cdefs.h /opt/simplescalar/sslittle­na­sstrix/include/sys/ sudo cp ../sslittle­na­sstrix/lib/libc.a ../lib/ sudo cp ../sslittle­na­sstrix/lib/crt0.o ../lib/

//NOTE ­ you might need to verify source and destination paths for the last 2 cp commands. once done, try again ­
$sudo make LANGUAGES="c c++" CFLAGS=­O3 CC=gcc­3.4
//NOTE ­ now you should not get any errors ...

13) make inquire ­ ???
$sudo make enquire CC=gcc­3.4
$sudo /opt/simplescalar/simplesim­3.0/sim­safe ./enquire ­f > float.h­cross

//NOTE ­ unsure what these commands do. always got a permission denied, but the installation should work even without it ... then do ­
$sudo make install LANGUAGES="c c++" CFLAGS=­O3 CC=gcc­3.4
PATH=$PATH:/opt/simplescalar/bin
//NOTE ­ this should go through without any errors ...

14) testing the installation ­
$cd /tmp/simplescalar
$/opt/simplescalar/bin/sslittle­na­sstrix­gcc hello.c

//NOTE ­ the above command compiles the c file made by the user and makes the a.out file. hello.c should be in the opt/simplescalar/bin folder ...
$/opt/simplescalar/simplesim­3.0/sim­safe a.out
//NOTE ­ the above command runs the a.out file ... "hello world" should be displayed in the terminal with simplescalar details like hits, misses etc.

3.4. Statistical method

This method helped us, as we quantified and encoded simulator results, and present them in form of tables and charts.