Implementation and Evaluation of Secure Industrial Ethernet Communication Master of Science Thesis, Communication Engineering KAN YU Department of Signals and Systems CHALMERS UNIVERSITY OF TECHNOLOGY Göteborg, Sweden, August 2010 Page 2/88 Abstract Automation network security becomes increasingly important due to the introduction of Ethernet- based fieldbus protocols and cryptographic algorithms play a vital important role in these protocols. Choosing the most suitable cryptographic algorithms under consideration of security and performance according to different application cases is essential. In this thesis, we first present a comprehensive survey of most commonly used cryptographic algorithms which can be applied in automation networks and then identify our candidates based on existing literature and related works for further evaluation in ARM platform for industrial purpose. Finally, according to our evaluation results, we choose suitable algorithms for different applications: for symmetric algorithms, Twofish is recommended for best performance and eXtended Tiny Encryption Algorithm (XTEA) and Corrected Block Tiny Encryption Algorithm (XXTEA) are recommended for the least footprint; for Message Authentication Code (MAC) algorithms, UMAC is strongly recommended for excellent speed; for asymmetric algorithms, Elliptic Curve Cryptography (ECC) has much better performance than RSA at the same security level in our platform. Page 3/88 TABLE OF CONTENTS 1 INTRODUCTION ................................................................................................................................... 5 1.1 AUTOMATION NETWORK SECURITY ..................................................................................................... 5 1.2 RESEARCH PROBLEM ........................................................................................................................ 6 1.3 RESEARCH APPROACH ...................................................................................................................... 6 1.4 THESIS CONTRIBUTIONS .................................................................................................................... 7 1.5 THESIS OUTLINE ............................................................................................................................... 7 2 SECURITY AND NETWORK SECURITY .............................................................................................. 9 2.1 SECURITY......................................................................................................................................... 9 2.2 OBJECTIVES ..................................................................................................................................... 9 2.3 SECURITY ATTACK .......................................................................................................................... 10 2.4 CRYPTOGRAPHY ............................................................................................................................. 12 2.4.1 Basic Concept ........................................................................................................................ 13 2.4.2 Symmetric Encryption ............................................................................................................ 15 2.4.3 Asymmetric Encryption ........................................................................................................... 16 2.4.4 Hash and MAC Algorithms ..................................................................................................... 18 2.4.5 Cryptanalytic attacks .............................................................................................................. 19 2.5 COMMUNICATION AND NETWORK SECURITY ....................................................................................... 20 2.5.1 Kerberos ................................................................................................................................ 20 2.5.2 SSL/TLS ................................................................................................................................ 21 2.5.3 IPSec ..................................................................................................................................... 22 2.5.4 Virtual Private Networks ......................................................................................................... 23 3 SURVEY OF CRYPTOGRAPHIC ALGORITHMS ................................................................................ 24 3.1 SYMMETRIC ALGORITHMS ................................................................................................................ 24 3.1.1 Introduction ............................................................................................................................ 24 3.1.2 Security and Performance Analysis ........................................................................................ 27 3.1.3 Candidates ............................................................................................................................ 33 3.2 MAC ALGORITHMS .......................................................................................................................... 34 3.2.1 Introduction ............................................................................................................................ 34 3.2.2 Security and Performance Analysis ........................................................................................ 38 3.2.3 Candidates ............................................................................................................................ 44 3.3 ASYMMETRIC ALGORITHMS .............................................................................................................. 45 3.3.1 Introduction ............................................................................................................................ 45 3.3.2 Security and Performance Analysis ........................................................................................ 47 3.3.3 Candidates ............................................................................................................................ 52 4 BENCHMARKING ON ARM PLATFORM ............................................................................................ 53 4.1 INTRODUCTION TO ARM PLATFORM .................................................................................................. 53 4.2 METHODOLOGY AND CONSIDERATION ............................................................................................... 54 4.2.1 Implementation Tools and Settings ......................................................................................... 54 4.2.2 Implementation Sources ......................................................................................................... 54 4.2.3 Cipher Parameters ................................................................................................................. 56 4.2.4 Methods for Measurement...................................................................................................... 57 5 RESULTS AND ANALYSIS ................................................................................................................. 60 5.1 SYMMETRIC ALGORITHMS ................................................................................................................ 60 5.1.1 Memory.................................................................................................................................. 60 Page 4/88 5.1.2 Performance .......................................................................................................................... 61 5.1.3 Analysis and Conclusion ........................................................................................................ 66 5.2 MAC ALGORITHMS .......................................................................................................................... 68 5.2.1 Memory.................................................................................................................................. 68 5.2.2 Performance .......................................................................................................................... 70 5.2.3 Analysis and Conclusion ........................................................................................................ 72 5.3 ASYMMETRIC ALGORITHMS .............................................................................................................. 73 5.3.1 Memory.................................................................................................................................. 73 5.3.2 Performance .......................................................................................................................... 74 5.3.3 Analysis and Conclusion ........................................................................................................ 76 6 CONCLUSION AND FUTURE WORK ................................................................................................. 78 6.1 SUMMARY AND CONCLUSION ............................................................................................................ 78 6.2 FUTURE WORK ............................................................................................................................... 79 7 REFERENCES .................................................................................................................................... 80 Page 5/88 1 INTRODUCTION 1.1 Automation Network Security Automation technology is a synthesized technology involving control theory, information theory, system engineering, computer technology, etc. Industrial automation, which may refer to process automation or factory automation, is the most important part of automation applications. Industrial automation network is built into a hierarchical structure. It consists of a number of different components at different hierarchy levels. For instance, it may include application specific devices, such as sensors, at the bottom, and plant LANs at the top [51]. Figure 1.1 illustrates network architecture of a process automation system. Different from other architectures, the process automation system in Figure 1.1 is isolated from the outside due to the security consideration. Since there is no connection to the outside, no security attack from outside can threaten the automation system. It shows that security is a vital important issue in designing an automation network [50]. Figure 1.1 Example of Network Architecture for a Process Automation System [50] However, not all automation systems are designed to be a closed network. There may be requirements for an automation system to communicate with the outside, such as remote control service. Thus, the inside automation network is exposed to adversaries from the outside who are able to launch different security attacks against the inside network Page 6/88 according to different automation systems. The common method to protect the entrance is to setup a security zone between inside and outside networks, such as a firewall, to filter the incoming and outgoing data. Automation network security issues are not only provided by network architecture, but also from communication protocols. A number of different network protocols are used at different hierarchy levels. Common used protocols at the higher level of automation networks are Object Linking and Embedding for Process Control (OPC), Manufacturing Message Specification (MMS), IEC 61850 and Inter Control Centre Protocol (ICCP) [51]. This thesis focuses more on the security at lower level. At lower field network level, different protocols are designed according to different physical linking methods. Field buses are employed in traditional field networks, which offer no security features against any security attack. Ethernet and TCP/IP protocols are used in the newly generated Ethernet-based field buses. A number of protocols are specified in IEC standards series, for more details see [50] [51]. Compared with traditional field networks, such networks are more vulnerable to security attacks, so security services should be provided. Nowadays, wireless systems are commonly used at device level. Due to the radio connection, automation systems are even more vulnerable to security attacks than the former one. Security is greatly considered and well addressed in the wireless sensor network protocols, such as WirelessHART [117] and ISA 100 [118]. Power line is another method to construct field networks. A number of standards specify the way to transmit data on power lines. For more details see [51]. 1.2 Research Problem Nowadays, since Ethernet-based field buses are increasingly used in automation systems, more and more attentions are paid to the security of Ethernet-based fieldbus protocols. However, most protocols were designed before with fewer concerns about security. For instance, PROFINET IO, one of the Ethernet-based fieldbus protocols, has no explicit security countermeasures in the protocol, so a number of possible attacks can be launched against PROFINET IO nodes to get unauthorized access. [50] has shown the concept of security modules to provide security in PROFINET IO without violating the standards, but cryptographic algorithms to provide confidentiality or message authentication are still not specified. Another problem is that at the lower field bus level, application specific devices are most embedded devices has less CPU processing power and memory than desktop computers. Therefore, cryptographic algorithms should be carefully chosen with these considerations. 1.3 Research Approach In order to choose the most appropriate cryptographic algorithms for automation fieldbus networks balanced both in security and performance, a survey of cryptographic algorithms Page 7/88 based on existing literature and authoritative recommendations is necessary. This survey involves most widely used cryptographic algorithms including symmetric algorithms, asymmetric algorithms and MAC algorithms. Then several candidates from each catalog will be chosen for further evaluating and assessing based on the comparison of security and performance between each other. The software implementations of all candidates are written in pure C language based on existing open source projects or cryptographic libraries. Finally, existing automation equipment is used as benchmarking platform to evaluate the performance of all candidates and followed by our analysis. The goal of this thesis is to propose suggestions of cryptographic algorithms suitable for automation field networks. 1.4 Thesis Contributions The main contributions of this thesis are: 1. A comprehensive survey of most commonly used cryptographic algorithms including symmetric algorithms, asymmetric algorithms and MAC algorithms with security and performance analysis. 2. Evaluation of candidate algorithms using software implementation and a comparison with the performance of all candidates. 3. Propose suggestions of suitable cryptographic algorithms in our specific platform according to different applications: for symmetric encryption, Twofish is recommended for the best performance and XTEA or XXTEA for the least footprint; for MAC algorithms, UMAC is recommended for the best performance, CMAC for applications with AES already implemented; for asymmetric algorithms, ECC is recommended compared to RSA. 1.5 Thesis Outline This report has the following structure. Chapter 1 Introduction describes the purpose and scope for this thesis. Chapter 2 This chapter introduces the basic concept of security, security attacks, cryptography and network security. It gives a brief understanding to readers who are not familiar with this domain. Chapter 3 In this chapter, a comprehensive survey of cryptographic algorithms including symmetric algorithms, asymmetric algorithms and MAC algorithms is presented. The candidates are selected based on the security and performance analysis. Chapter 4 This chapter introduces our benchmarking platform, the source of software implementation of all algorithms, the cipher parameters we chose in our evaluations and the methods we use to measure the performance. Page 8/88 Chapter 5 This chapter presents the evaluation results of all algorithms. Analysis and suggestions are given according to the comparison of performance. Chapter 6 This chapter presents the conclusions and future works after this thesis. Page 9/88 2 SECURITY AND NETWORK SECURITY 2.1 Security In ancient wars, keeping information unknown from enemies is one of the essential parts to the victory. As rapid development of communication and network technology, what we said, we wrote and we behaved are always under the threat of being monitored, eavesdropped, modified and analyzed by any adversary1. From [3], several types of adversaries and their goals are listed in Table 2.1. Therefore, the security of information is considered to be more and more important. Table 2.1 Examples of people who cause security problems and why [3] Adversary Goals Student To have fun snooping on people’s e-mail Cracker To test out someone’s security system; steal data Sales rep To claim to represent all of Europe, not just Andorra Businessman To discover a competitor’s strategic marketing plan Ex-employee To get revenge for being fired Accountant To embezzle money from a company Stockbroker To deny a promise made to a customer by e-mail Con man To steal credit card numbers for sale Spy To learn an enemy’s military or industrial secrets Terrorist To steal germ warfare secrets Security mainly concerns confidentiality, integrity and availability [2].To understand security in communication and networking, knowledge of related issues, such as cryptography and network security is necessary. This part, we introduce several important issues related to information security as the preliminary knowledge of the thesis. 2.2 Objectives Not only keeping information unknown from adversary is required, the objective of security also refers to other issues. A summary of some information security objectives, shown in Table 2.2, is given in [60]. During a transaction, all parties involved should make sure that certain security objectives have been achieved. 1 An adversary in this thesis means a person or orgnization who intends to obtain crucial or sensitive information from a system or make the system out of working via illegal ways, such as eavesdroping, hijacking, denial of service atacks ect. Page 10/88 Table 2.2: Some information security objectives. [60] Security Objectives Explanations Privacy or confidentiality Keeping information secret from all but those who are authorized to see it. Data integrity Ensuring information has not been altered by unauthorized or unknown means. Entity authentication or identification Corroboration of the identity of an entity (e.g., a person, a computer terminal, a credit card, etc.). Message authentication Corroborating the source of information; also known as data origin authentication. Signature A means to bind information to an entity Authorization Conveyance, to another entity, of official sanction to do or be something. Validation A means to provide timeliness of authorization to use or manipulate information or resources. Access control Restricting access to resources to privileged entities. Certification Endorsement of information by a trusted entity. Timestamping Recording the time of creation or existence of information. Witnessing Verifying the creation or existence of information by an entity other than the creator. Receipt Acknowledgement that information has been received. Confirmation Acknowledgement that services has been provided. Ownership A means to provide an entity with the legal right to use or transfer a resource to others. Anonymity Concealing the identity of an entity involved in some process. Non-repudiation Preventing the denial of previous commitments or actions. Revocation Retraction of certification or authorization. 2.3 Security Attack At present, the main factors causing insecure problems are due to the flaws in the design of algorithms, protocols, systems and database. An adversary is able to take advantage of any flaw to launch different types of attack. In [105], security attacks can be classified into passive attacks and active attacks. An "active attack" means an adversary trying to affect Page 11/88 their operations or alter system resources. A "passive attack" means an adversary trying to spy information from the system but does not affect system resources. 2.3.1.1 Active attack An active attack can be launched to modify a data stream or create a fake data stream. It can be categorized into four types: replay, masquerade, modification of messages and denial of service. [4] A masquerade takes place when one entry pretends to be another authorized or legitimate entry in order to get access to restricted resource or infiltrate the system. It is also known as a spoofing attack. A reply attack means that an adversary captures a data unit and retransmits it to produce an unauthorized effect. Modification of messages usually involves altering, delaying or recording a legitimate message to produce an unauthorized effect. The denial of service attacks come in a variety of forms. There are three main forms of denial of service attack: consumption of scare resource, alteration of configuration information and physical destruction of network components. It aims to decrease the availability of the system. Attacks are actually quite difficult to be prevented, since there are a lot of potential vulnerabilities in the design of software and network. Fortunately, according to the properties of active attacks, it is possible to detect them and recover information from any disruption or delays caused by them. 2.3.1.2 Passive attack Passive attack takes place when an adversary eavesdrops, monitors the transmissions between two communication entries to obtain useful information. There are two types of passive attacks: release of message contents and traffic analysis [4]. The release of message contents is referred that an adversary can learn the contents of information between two entries when they are communicating, such as a telephone conversation or an electronic mail message. Traffic analysis is much more difficult than the release of message contents. In order to prevent any adversary from knowing the information, two entries may mask the contents of messages or other information traffic. Therefore, if an adversary captures a message from then, he has no idea what the message means without knowing the way to extract the message. However, a smart adversary might still be able to observe the pattern of the message. For instance, an adversary could still observe the frequency and the length of messages being exchanged. This leaked information might be helpful for the adversary to guess the nature of the communication which was taking place [4]. Page 12/88 Passive attacks present the opposite characteristics of active attacks. Since passive attacks do not affect system resources at all, it is very difficult to detect them. One of the most effective way to prevent passive attacks is to encrypt messages. However, it will obviously increase the complexity of communications to some extent. 2.4 Cryptography As mentioned above, one way to prevent passive attacks is to use encryption scheme to protect information. Encryption/decryption scheme is related to cryptographic algorithms. The definition of cryptography is given in the book [60]: “Cryptography is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication.” Cryptography has a very long history. It can be traced to 4000 years ago from its initial and limited use by the Egyptians. Kings and generals communicated with their armies using some simple and basic masking methods to prevent the enemy from knowing sensitive military information. One of the earliest cryptosystems is called shift ciphers, often attributed to Julius Caesar. Encryption is simply shifting each letter in the text by certain places in the alphabet. Decryption is accomplished by shifting letters back. This cryptosystem had been used for centuries. Even as late as 1915, the Caesar cipher was still in use [5]. Later in the sixteenth century, a variation of the shift cipher, named Vigenère cipher, was invented. Even into the twentieth century, this cryptosystem was widely considered to be secure. However, in the 1920s, Friedmen finally developed additional methods to break Vigenère and its related cipher. Although those classical cryptosystems are too weak to be broken by computers today, they give very good illustrations of several of the important ideas of cryptology. Modern cryptography today draws heavily upon mathematics, computer science and cleverness, but it still uses many same basic principles as classical cryptosystems, such as transposition, substitution, padding or block division. The huge difference is that the proliferation of computers in the mid 20th century called for the demand to protect information in digital form. Also with the help of super computers, modern cryptographic algorithms should be design as complex as possible against all kinds of cryptanalytic attacks. In modern cryptosystems, there are a number of a number of basic cryptographic primitives used to provide information security. These can mainly be divided into three catalogs: symmetric-key primitives, public-key primitives and unkeyed primitives. Figure 2.1 provides a schematic listing of the primitives considered and how they relate [60]. More details are discussed as follows. Page 13/88 Figure 2.1: A taxonomy of cryptographic primitives. [60] 2.4.1 Basic Concept Before introducing more details of cryptographic algorithms, some basic terminology and concepts are necessary. 1) Encryption domains A denotes a finite set named the alphabet of definition. For instance, A = {0, 1}, the binary alphabet, is a frequently used alphabet of definition. Page 14/88 M denotes a set named the message space. M consists of strings of symbols from an alphabet of definition. Elements in M are called plaintext. C denotes a set named the ciphertext space. C also consists of strings of symbols from an alphabet of definition. Elements in C are called ciphertext. 2) Encryption and decryption transformations K denotes a set named the key space. Each element e ∈ K is called a key. Each e uniquely determines a bijection from M to C, defined as an encryption function Ee. Conversely, an element d ∈ K also uniquely determines a bijection from C to M, defined as a decryption function. The keys e and d, sometimes denoted by (e; d), are referred to as a key pair. Note that e and d could be the same. An encryption scheme is constructed with a message space M, a ciphertext space C, a key space K, a set of encryption transformations {Ee: e ∈ K}, and a corresponding set of decryption transformations {Dd: d ∈ K}. [60] 3) Communication participants An entry is referred to a party who sends, receives or manipulates information. A sender is a legitimate entry who transmits information. A receiver is an entry to whom the corresponding sender intends to transmit information. An adversary is an entry who tries to defeat security strategy and obtain the information transmitted between a sender and a receiver. 4) Achieving confidentiality In order to achieve confidentiality, an encryption scheme should be used as follows. As described in the book [60], the sender and the receiver should firstly choose or exchange a key pair (e, d) in a secure way. If the sender wishes to send a message m ∈ M, he computes c = Ee(m) and transmits it to the receiver. When receiving c, the receiver computes m = Dd(c). Finally, the original message m is recovered, since for each e ∈ K, there is a unique d ∈ K such that Dd = Ee-1; that is Dd (Ee (m)) = m for all m ∈ M. 5) Cryptology and cryptanalysis The three names, cryptography, cryptology and cryptanalysis, are often used interchangeably. Cryptology is the all-inclusive term for the study of communication over nonsecure channels [1]. The process of designing systems to do this is called cryptography. Page 15/88 Cryptanalysis deals with breaking cryptographic techniques or information security services. Another word cryptosystem is referred to a set of cryptographic primitives used to provide information security services [60]. 2.4.2 Symmetric Encryption Symmetric cryptography uses one private key for both encryption and decryption. That is for the sets of encryption and decryption transformations {Ee: e ∈ K} and {Dd: d ∈ K}, e = d. Other terms used in the literature are single-key, one-key, private key, and conventional encryption [60]. All of the classical (pre - 1970) cryptosystems are symmetric. A further division of symmetric cryptosystems is block ciphers and stream ciphers. To use block cipher, the plaintext should be divided into an identical fixed length. Then each block of the plaintext is encrypted respectively. Different from block ciphers, stream ciphers work on individual plaintext digits with a time-varying transformation. To apply a block cipher to encrypt a plaintext with an arbitrary length, there are several different of modes of operation. A mode of operation is a technique to enhance the effect of a cryptographic algorithm or to adapt the algorithm for an application, such as applying a block cipher to a sequence of data blocks or a data stream [4]. Five commonly used modes of operation are defined by NIST, which are listed in the Table 2.3. Table 2.3: Block Cipher Modes of Operation [4] Mode Description Typical Application Electronic Codebook (ECB) Each block of 64 plaintext bits is encoded independently using the same key. • Secure transmission of single values (e.g., an encryption key) Cipher Block Chaining (CBC) The input to the encryption algorithm is the XOR of the next 64 bits of plaintext and the preceding 64 bits of ciphertext. • General-purpose block- oriented transmission • Authentication Cipher Feedback (CFB) Input is processed j bits at a time. Preceding ciphertext is used as input to the encryption algorithm to produce pseudorandom output, which is XORed with plaintext to produce next unit of ciphertext. • General-purpose stream- oriented transmission • Authentication Output Feedback Similar to CFB, except that the input to the encryption algorithm is the preceding DES • Stream-oriented transmission over noisy channel (e.g., Page 16/88 (OFB) output. satellite communication) Counter (CTR) Each block of plaintext is XORed with an encrypted counter. The counter is incremented for each subsequent block. • General-purpose block- oriented transmission • Useful for high-speed requirements Symmetric cryptography algorithms are typically fast and suitable for processing large amount of data. The main disadvantage of symmetric algorithms is that sender and receiver have to agree on a same private key in a secure manner prior to their communications. Symmetric cryptography can provide not only confidentiality, but also a degree of authentication, since data encrypted with one private key cipher cannot be decrypted with any other keys. Therefore, as long as the symmetric key cipher is kept secret by the two parties using it to encrypt communications, each party can be sure that is communicating with the other as long as the decrypted messages continue to make sense. 2.4.3 Asymmetric Encryption Asymmetric cryptography is also referred to public-key cryptography. Different from symmetric encryption, a pair of keys is required during asymmetric encryption, public key and private key. That is for the sets of encryption and decryption transformations {Ee: e ∈ K} and {Dd: d ∈ K}, e ≠ d. The asymmetric encryption and decryption are described as follows. An entry Alice has a pair of keys, e and d. Assume that e is Alice’s public key and d is Alice’s private key. In a secure system, it is a computationally infeasible task of computing d given e. We define an encryption transformation Ee using public key e and a decryption transformation Dd using private key d. Another entry Bob wants to send a message m to Alice. First, Bob should obtain an authentic copy of Alice’s public key. Then he encrypts the message m applying the encryption transformation Ee to obtain the ciphertext c = Ee(m) and send c to Alice. For decryption, Alice uses the decryption transformation Dd to recover the original message: m = Dd(c). As the definition of public-key encryption, the public key need not be kept secret. Therefore, any entry can obtain a copy of Alice’s public key. Any ciphertext encrypted using Alice’s public key can only be decrypted by Alice. The reason why Bob should get an authentic copy of Alice’s public key is that if the public key is not authentic, but transmitted through an unsecure channel, this public key may be manipulated by an adversary. Then Alice will be Page 17/88 able to decrypt the cipher to obtain the original message. One way to obtain an authentic copy of public keys is through Certification Authority (CA). Each wide used asymmetric cryptography algorithm is based on one of the intractability of certain mathematical problems. There are several famous intractable mathematical problems, such as integer factorization problem and discrete logarithm problem. Each of them has one or several typical and widely used cryptography algorithms or standards. For instance, the most famous public-key algorithm RSA is based on integer factorization and one of the most widely used public-key algorithms ECC is based on discrete logarithm problem. One of the most widely used applications of public-key algorithms is key exchange or key negotiation for symmetric encryptions. Since for symmetric cryptosystems, a sender and a receiver may be hundreds of kilometers apart and have not agreed on a same secure key to use. With public-key algorithms, this problem can be solved amazingly. Another application of public-key algorithms is to achieve authentication. As mentioned above, any message encrypted with Alice’s public key, only Alice with her private key can decrypt this ciphertext, which can guarantee Alice’s identity. When comparing symmetric encryption with asymmetric encryption, one of the most distinguished differences is the complexity. Since big number operation is involved in the calculation of public-key encryption and extremely long key is required to achieve a certain level of security, all public-key algorithms are much slower by an order of magnitude than symmetric-key algorithms. Other differences are listed in [60], shown in the Table 2.4. Table 2.4: Differences between symmetric and asymmetric encryption [60] Differences Symmetric Encryption Asymmetric Encryption An extensive history Long Short Data throughput Fast Slow Key length Relatively short Long Generating pseudorandom number Yes No Key management Poor Strong Digital signature Inefficient Efficient Page 18/88 2.4.4 Hash and MAC Algorithms One of the basic components of many cryptographic algorithms is hash function, often informally called a one-way hash function. The definition of hash function is described in the book [60]: “A hash function is a computationally efficient function mapping binary strings of arbitrary length to binary strings of some fixed length, called hash-values.” More properties of hash function which should be satisfied are: � Consider h as a hash function. Given a message m, then the message digest h (m) can be computed efficient and fast. � Hash function h must be a one-way function. That is, Given another message digest y, it is computationally infeasible to find an m’ with h(m’) = y. � Hash function h must be collision-free. That is, it is computationally infeasible to find two messages m1 and m2 with h (m1) = h (m2). As the definition, hash function implies an unkeyed hash function. At the highest level, hash functions may be divided into two catalogs: unkeyed hash functions and keyed hash functions. In [60], it gives a simplified classification, illustrated in Figure 2.2. Figure 2.2: Simplified classification of cryptographic hash functions and applications. [60] In the Figure2.2, MDCs represent modification detection codes. It is a subclass of unkeyed hash functions. It can provide data integrity assurances, since even 1 bit in the input Page 19/88 message changes; the whole output will be totally different. Therefore, to verify the integrity of an input message, the receiver can compute the message digest using the same hash function as the sender and compare it with the original message digest provided by the sender. If they are equal, it is confident that the message is not altered during the transmission. MACs represent message authentication codes. Different from MDCs, MACs have two different parameters, a message input and a secret key. The secret key is only shared by the sender and the receiver. Therefore, MACs cannot only provide message integrity, but also authentication, assuring the source of the message. Another application of hash function is digital signature. Since the length of a digital signature is at least as long as the document being signed, it is much more efficient to sign the hash value of the document rather than the whole document [1]. Through this way, both time and space are saved. However, one important thing should be mentioned that the hash function for the digital signature must be carefully design, especially strong collision-free. Otherwise two messages m1 and m2 will have the same hash value, which leads to the same digital signature value. 2.4.5 Cryptanalytic attacks Previously, we have mentioned several methods of security attacks. However, there are several types of attacks aiming to break encryption schemes, in order to recover plaintext from ciphertext, or even more drastically, named cryptanalytic attacks. There are four basic types of cryptanalytic attacks that an adversary might be able to use. The differences between these attacks are the amounts of information the adversary can obtain when trying to determine the key. � Ciphertext only: The adversary only has a copy of a ciphertext. This is the most unsatisfactory case for the adversary to deduce the key of a cryptosystem. � Known plaintext: The adversary has a copy of a ciphertext and its corresponding plaintext. � Chosen plaintext: The adversary is able to choose any plaintext and obtain the corresponding ciphertext and trying to use the resulting ciphertext to deduce the secret key of the cryptosystem. � Chosen ciphertext: The adversary is able to choose any ciphertext and obtain the corresponding plaintext and trying to use the result to deduce the secret key of the cryptosystem. Most of these types of cryptanalytic attacks also apply to digital signature schemes and message authentication codes. Page 20/88 One of the most famous assumptions in modern cryptography is Kerckhoffs’s principle [1]. This important principle refers that the security of a cryptosystem should not be based on the obscurity of the algorithms used, but only based on the secret key. It means that the adversary may have knowledge of the algorithms, but if he has not any idea of the secret key, the whole cryptosystem is still considered to be secure enough. 2.5 Communication and Network Security Previously, we have introduced many basic cryptographic tools, from symmetric algorithms to hash functions. However, only with these tools, we are far from making our communication secure enough. Cryptographic algorithms should be applied based on a certain security protocol or mechanism. A faulty designed security protocol or mechanism with serious flaws, even with the most secure cryptographic algorithm, can be easily broken by an adversary without any cryptanalytic attack. For instance, for a poor design secure protocol, an adversary may simply parse a data packet and apply a reply attack to obtain the important information without knowing the secret key. Therefore, a well designed security protocol or mechanism is vital important. This part we will introduce several important and widely-used security protocols and mechanism to carry out secure transactions over unsecure channels. 2.5.1 Kerberos Originally, Kerberos in the Greek and Roman mythology is a many-headed dog guarding the entrance of Hades. Now Kerberos is referred to a trusted third party used for authentication and authorization originally as a part of Project Athena at MIT in early 80s last century. One of the significant features and design objectives of Kerberos is Single Sign On (SSO), which means that a user only needs to sign in once for credentials and then obtain a Kerberos ticket-granting ticket (TGT) and with TGT the user gains access to all systems. Other design objectives of Kerberos are: i) secure: An eavesdropper should not be able to impersonate a user; ii) Modular and distributed architecture: servers can back up each other for reliable and the system is able to support a large number of clients and servers for scalable [4]. Kerberos is very is suited for large environments, two reasons are: i) No individual computers have to do authentication; ii) Application servers only have to share a secret with the Kerberos server. Page 21/88 Kerberos performs both authentication and authorization. An entire authentication or authorization progress of a Kerberos system is quite complicated. For more details of authentication see the book [4]. There are two versions of Kerberos in common use. Version 4 implementations still exist, using symmetric algorithm DES for encryption. Version 5 corrects some of the security deficiencies of version 4 and has been issued as a proposed Internet Standard [106]. In version 5, new symmetric algorithm AES is supported. 2.5.2 SSL/TLS Secure Sockets Layer (SSL) was developed by Netscape in order to perform http communications securely. The version 3 was released in 1995 and is the preferred version today. Transport Layer Security (TLS) is a slight modification of SSL version 3 and was released by IETF in 1999. The latest version as of today is TLS 1.2. [1] SSL is designed to make use of TCP to provide a secure and reliable end-to-end service. Therefore, SSL can be used to secure all TCP connections. SSL is two layers of protocols, rather than a single security protocol. It is illustrated in Figure 2.3. Figure 2.3: SSL Protocol Stack [4] From the figure, SSL consists of two main components. The first component is SSL Record Protocol, which is responsible for compressing and encrypting data and serves for various higher-layer protocols. It provides both confidentiality and message integrity. A collection of three higher-layer protocols, SSL Handshake Protocol, SSL Change Cipher Spec Protocol, and SSL Alert Protocol, is the second component of SSL. This component is responsible for setting up and maintaining the parameters used by SSL record protocol [1]. Among these protocols, SSL Handshake Protocol is the most complex one. It is not only used for authentication between a server and client, but also for negotiation of encryption and MAC algorithms and secret keys to be used to protect data sent in an SSL record. The Handshake Protocol is used before any application data is transmitted [4]. For more details of SSL/TLS see [1] [4]. Page 22/88 2.5.3 IPSec Different from SSL/TLS, IPSec can encrypt and/or authenticate all traffic at IP level, not TCP level. Therefore, all distributed applications, including remote logon, client/server, e-mail, file transfer, web access, and so on, can be secured. The IPSec specification is quite complicated, consisting of a number of documents. Among all these documents, the most important ones are [107], [108], [109] and [110], which are issued in November of 1998. Two protocols with different headers in IPSec can be used to provide security. One is an authentication protocol with Authentication Header (AH), the other is a combined encryption/authentication protocol with Encapsulating Security Payload (ESP). For ESP, there are two cases: with and without the authentication option. These two protocols can provide different services, which is illustrated in Table 2.5. Table 2.5: IPSec Services [4] IPSec also has two modes: Transport Mode and Tunnel Mode. Transport mode provides protection for upper-layer protocols. Tunnel mode provides protection to the entire IP packet. With tunnel mode, a number of hosts on networks behind firewalls may engage in secure communications without implementing IPSec [4]. According to the properties of IPSec, there are several outstanding benefits of IPSec: i) Since IPSec is applied at IP level, it is totally transparent to all above applications. All upper layer software on a user or server system will not be affected. ii) IPSec can be transparent to end users. iii) IPSec can provide security for individual users if needed. [4] Page 23/88 2.5.4 Virtual Private Networks If an international company has many branches locating in different places in the world, for information security, it is necessary to connect every computer through an underlying local or wide-area network to setup a network which is isolated from other networks. Traffic separation can be obtained in several ways: a) Physical separation using different hardware; b) Temporal separation (separation in time); c) Logical separation, for example, by software as with VLAN; d) Cryptographic separation. The most secure and reliable way is the last one and the solution is Virtual Private Networks (VPN). Two basic technologies make VPN possible: encryption and tunneling. For confidentiality, VPN encrypts output data and encapsulating it into another packet, such as IP-in-IP encapsulation, for transmission. When this encrypted packet reaches the end of the tunnel, the router responsible for receiving will parse the packet, decrypts the data and forward the inner data packet. There are three basic types of VPN systems: Host-to-Host VPN, Remote Access VPN and Site-to-Site VPN. For Remote Access VPN, a user needs to connect to a VPN gateway, which authenticates and gives access to authorized resources in the site. For Site-to-Site VPN, a VPN gateway is also involved. The sending VPN gateway will encrypt all outgoing messages and the receiving VPN gateway will do the decryption. Since tunneling technology is used, it is totally transparent to all users, which is a main advantage of VPN. Page 24/88 3 SURVEY OF CRYPTOGRAPHIC ALGORITHMS This chapter is a survey that covers most of the wide-used cryptographic algorithms, including symmetric ciphers, asymmetric ciphers and MAC algorithms. For each kind of algorithm, we first give a brief introduction about its basic information and then analyze its security and performance. All the analysis is based on related works that have been done before by other researchers. In order to make our survey more convincing and help us to find the most suitable algorithms, we studied as many algorithms as we are able to. For performance analysis, the best method is to implement them in target devices and evaluate the results. However, due to the limitation of time, we cannot implement all studied cryptographic algorithms. Therefore, based on related works, we pick up candidates within much smaller subset for further implementation in our target devices. At this end, according to the analysis, we choose three candidates from symmetric algorithms and MAC algorithms, two candidates from asymmetric algorithms, for the software implementation in ARM platform. 3.1 Symmetric Algorithms We have previously introduced that symmetric algorithms use only one secret key for both encryption and decryption. Symmetric algorithms are typically fast and suitable for processing large amount of data. There are a number of widely used symmetric algorithms, which is listed and briefly described and analyzed as follows. 3.1.1 Introduction 3.1.1.1 Data Encryption Standard (DES) / 3DES / DES-X/ DESL: DES is a block cipher, one form of symmetric cryptography algorithms, which was designed by IBM and selected by the National Bureau of Standards (NBS) in the early 70’ies. It has been the standard encryption algorithm for civilian applications for more than 25 years. It has been considered completely insecure due to the short key length. Since the key length of DES is too short, an improvement to enhance security is to encrypt data using DES more than once. However, double DES encryption (2DES) is also considered insecure due to the meet-in-the-middle attack. Triple DES (3DES) is considered to be temporarily secure enough and still widely used recently. DES-X is another variant on the DES block cipher intended to increase the complexity of a brute force attack using a technique called key whitening. Another reason for DES-X is that Page 25/88 the speed of 3DES is unacceptable in many situations. Therefore, there is a need for an efficient way to strengthen DES. DESL (DES Lightweight extension) is a new extension to DES and was suggested by A. Poschmann et al. in 2006 as a new alternative for ultra-low-cost encryption. To decrease chip size requirements it uses only one S-Box repeated eight times. It therefore requires 38% fewer transistors than the smallest DES implementation [99]. 3.1.1.2 Blowfish / Twofish: Blowfish was designed by Bruce Schneier in 1993 [103]. Blowfish is still considered to be secure, since there is no effective cryptanalysis found. It also provides a decent encryption performance in software implementation. However, Bruce Schneier himself recommended using the more advanced version - Twofish instead. Twofish is another block cipher published in 1998 by Counterpane Labs. It was one of the five Advanced Encryption Standard (AES) finalists. However, it was not selected by NIST as AES, since the winner of AES (Rijndael) is considered to have better performance than other finalists in both hardware and software in average. Twofish allows a wide range of tradeoffs between size and speed. It is also designed to be efficient on a wide range of platforms. Although it was not selected as AES, it may still be the suitable choice in our case due to the different platform. 3.1.1.3 Tiny Encryption Algorithm (TEA)/ XTEA / XXTEA The TEA is a block cipher presented in 1994 [104]. The aim of TEA is to minimize memory footprint and maximize speed. It is a Feistel type cipher that uses operations from mixed (orthogonal) algebraic groups. There are two variants of TEA - extended TEA (XTEA) and Corrected Block TEA (XXTEA), which were designed to correct weaknesses in the original TEA. 3.1.1.4 Rijndael Algorithm (AES): Rijndael was selected the winner of AES by NIST in 2000 [1]. It is based on a design principle known as a Substitution permutation network. It is fast in both software and hardware. Unlike its predecessor DES, Rijndael does not use a Feistel network. 3.1.1.5 Skipjack Algorithm: Page 26/88 Skipjack was developed by the U.S. National Security Agency (NSA). It is one of the simplest and fastest block cipher algorithms, which is very important for embedded systems. Skipjack or a variant of Skipjack is now used in TinySec , SenSec and MiniSec in Wireless Sensor Networks [45] [44] [46]. 3.1.1.6 Scalable Encryption Algorithm (SEA): The Scalable Encryption Algorithm was proposed by Franccois-Xavier Standaert et al. and is designed for processors with a limited instruction set. The proposed design is parametric in the text, key and processor size, provably secure against linear/differential cryptanalysis, allows efficient combination of encryption/decryption and “on-the-fly" key derivation. Target applications for such routines include any context requiring low-cost encryption and/or authentication [101]. 3.1.1.7 HIGHT Algorithm: HIGHT is another block cipher proposed by Deukjo Hong et al. and provides low-resource hardware implementation, which is proper to ubiquitous computing device such as a sensor in Wireless Sensor Network (WSN) or a RFID tag. HIGHT does not only consist of simple operations to be ultra-light but also has enough security as a good encryption algorithm [100]. 3.1.1.8 Other Symmetric Cryptographic Algorithms: Besides the algorithms mentioned above, there are still a number of other symmetric algorithms. However, we cannot include all symmetric algorithms in our survey due to the time limitation. We will skip the rest and the reasons will be given as follows: FEAL is no longer considered in our survey, since the inventor of FEAL, Akihiro Shimizu and Shoji Miyaguchi from NTT, noticed that Camellia is strongly recommended to replace FEAL in new applications in the future for efficiency and security. SAFER++128 is not included, since according to [6] there some concerns about certain structural properties of SAFER++128 and the low security margin of SAFER++128. MARS is not included. The reason is its high algorithmic complexity, which results in high RAM and ROM usage [7]. Page 27/88 Serpent is not included, since it consistently performs poorly in software encryption and decryption due to its large security margins [7]. Therefore, in the competition of AES, supporter of Serpent prioritized security over performance. SHACAL-2 is a new 256-bit hash function-based block cipher recommended by NESSIE, but has not been studied by NIST or CRYPTREC. Also 256-bit is a little too long as a symmetric algorithm for embedded applications. Although IDEA, RC5, RC6, MISTY1, KASUMI and Camellia are also considered to be fast, efficient and secure algorithms, as their authors announced, they are all patented. And IDEA has very unbalanced performance of encryption and decryption. For more details see [102]. If these algorithms are used for commercial purpose, some extra fee needs to be paid to authors or certain organizations. Some of them are only free to use in certain projects, such as OpenSSL. From the related work [96], these algorithms cannot provide outstanding and better performance than unpatented algorithms and the cost is always a vital and important issue. Therefore, they are not considered in our study. Remaining symmetric algorithms are not included due to the time limitation. 3.1.2 Security and Performance Analysis 3.1.2.1 Security Analysis Security of cryptographic algorithms should be considered with high priority. However, the security of cryptographic algorithms is very difficult to measure. Some basic information related to security, such as key length and number of rounds, is shown in Table 3.1. Table 3.1: Details of Symmetric Cryptographic Algorithms Algorithm Name Key Size (bit) Block Size (bit) Structure Round DES 56 64 Balanced Feistel network 16 3DES 168, 112 or 56 64 Feistel network 48 DES-quivalent rounds DES-X 184 64 Feistel network 16 Blowfish 32–448 bits in steps of 8 bits; default 128 bits 64 Feistel network 16 Page 28/88 Twofish 128, 192 or 256 bits 128 Feistel network 16 TEA, XTEA 128 64 Feistel network variable; recommended 64 Feistel rounds (32 cycles) XXTEA 128 arbitrary, at least two words (64) Unbalanced Feistel Network depends on the block size; ~52+6*words (6- 32 full cycles) AES (Rijndael) 128, 192 or 256 128 Substitution- permutation network 10, 12 or 14 (depending on key size) Skipjack 80 bits 64 unbalanced Feistel network 32 HIGHT 128 64 Feistel Network 32 Note: DESL has several modes, values change depending on working mode SEA has various key size, round depending on parameters The security of a cryptographic algorithm is related to how difficult it is for adversary to find out the secret key. The most naïve and the simplest way to determine the secret key is a brute force attack. Therefore, the key length is related to how much time an adversary will spend on searching the entire keyspace. However, longer keys cannot guarantee more difficulty for an adversary to determine the key, since the design of the algorithm also plays a critical role in security. Key length is a reference to analysis security of an algorithm, but it is far from enough. Respective security analysis is discussed as follows. 1) DES/3DES/DES-X/DESL: DES is considered entirely insecure since the key length is too short. The key size is only 56 bits, so the key space size = 256 ≈ 7 * 1016. In January 2000, distributed.net organized idle CPU time of 100,000 computers to search 250G [key/sec]. DES is cracked in 22 hours with a brute force attack. 3DES is considered much more secure than DES due to the longer key size. However, according to [54], the meet-in-the-middle attack on 3DES can reduce its “efficient” key length to 112. Page 29/88 The key size of DESX is increased to 56 + 2×64 = 184 bits. However, the efficient key size is only increased to 56 + 64 – 1 – lb(M) = 119 – lb(M) ≈ 119 bits, where M is the number of known plaintext/ciphertext pairs the adversary can obtain, and lb denotes the binary logarithm. According to the research done by Kaliski and Robshaw, DESX actually improves security against differential and linear cryptanalysis, increasing the required number of known or chosen plaintext s to be in excess of 260 [55]. Also it has been proven, in a strong sense, to add much strength against exhaustive key search. DESL can be used in simple mode, with only 56 bit key size. This implementation is only relevant for the application where short-term security is needed, or where the values protected are relatively low [99]. If a higher security level is needed, the key-whitening can be used. In [99], designer declares that DESL can be resistant to Differential Cryptanalysis and Davis Murphy Attack, Linear Cryptanalysis, and if key whitening is used, then against brute force attack. However, since it is new, no current attack is found on DESL. 2) Blowfish/Twofish: There is no effective cryptanalysis on the full-round version of Blowfish known publicly as of 2009. In 1996, Serge Vaudenay found a known-plaintext attack requiring 28r+1 known plaintexts to break, where r is the number of rounds. Moreover, he also found a class of weak keys that can be detected and broken by the same attack with only 24r+1 known plaintexts. This attack cannot be used against the regular Blowfish; it assumes knowledge of the key-dependent S-boxes. Vincent Rijmen, in his Ph.D. thesis, introduced a second-order differential attack that can break four rounds and no more. There is no known way to break the full 16 rounds, apart from a brute-force search [59]. Up to now, Twofish is still considered to be secure enough. One famous cryptanalysis on Twofish block cipher published by Shiho Moriai and Yiqun Lisa Yin in 2000 is a truncated differential cryptanalysis of 12- and 16-round version [97]. The paper claimed that a 16- round truncated differential with probability of about 2-57.3 is discovered. They claimed a good pair of truncated differentials can be found only with roughly 251 chosen plaintexts. However, Twofish is still far from being broken. 3) Tiny Encryption Algorithm (TEA)/ XTEA / XXTEA: There are several weaknesses in TEA. However, most notably it suffers from equivalent keys—each key is equivalent to three others, which means the effective key size is only 126 bits. [63] Therefore, TEA is a definitely not a smart choice as a cryptographic hash function. Page 30/88 Revisions of TEA, XTEA and XXTEA are designed due to this problem. As of 2004, the best attack reported on XTEA is a related-key differential attack on 27 out of 64 rounds of XTEA, requiring 220.5 chosen plaintexts and a time complexity of 2115.15. XXTEA is considered to be secure enough. However, recently on May 4, 2010, a chosen plaintext attack for XXTEA using about 259 queries and negligible work was announced in [8]. 4) AES (Rijndael): Unlike most other block ciphers, AES has a very neat algebraic description [56]. In 2002, a theoretical attack, termed the "XSL attack", was announced by Nicolas Courtois and Josef Pieprzyk, purporting to show a weakness in the AES algorithm due to its simple description [57]. Since then, other papers have shown that the attack as originally presented is unworkable. On July 1, 2009, Bruce Schneier presented a related-key attack on the 192-bit and 256-bit versions of AES discovered by Alex Biryukov and Dmitry Khovratovich; the related key attack on the 256-bit version of AES exploits AES' somewhat simple key schedule and has a complexity of 2119 [52]. This is a follow-up to an attack discovered earlier in 2009 by Alex Biryukov, Dmitry Khovratovich, and Ivica Nikolic, with a complexity of 296 for one out of every 235 keys. The first attack against a reduced 8-round version of AES-128 was published in November 2009. This known-key distinguishing attack is an improvement of the rebound or the start- from-the-middle attacks for AES-like permutations, which view two consecutive rounds of permutation as the application of a so-called Super-Box. It works on the 8-round version of AES-128, with a computation complexity of 248, and a memory complexity of 232 [53]. Although, many attack methods on AES appear these years, AES is still considered to be a very secure algorithm, and in June 2003, the US Government announced that AES may be used to protect classified information. 5) Skipjack Algorithm: The best and most efficient cryptanalysis of Skipjack is announced by Biham, Shamir and Biryukov's attack. They used a new cryptanalytic technique, based on impossible differentials to show that Skipjack reduced from 32 to 31 rounds can be broken by an attack which is faster than exhaustive search. Truncated differentials and later a complementation slide attack were published against all 32 rounds of Skipjack cipher. However, Reichardt and Wagner showed that there are no meaningful truncated differentials for Skipjack with full 32 rounds, providing heuristic evidence that Skipjack may be secure against truncated Page 31/88 differential distinguishing attacks [9]. In [96], author concluded that Skipjack with full 32 rounds is secure enough as of today, with a security margin of 2013. 6) SEA Algorithm: SEA is designed to be resistant to known attacks: Linear and differential cryptanalysis, extensions of linear and differential cryptanalysis, a dedicated attack against a modified version, square attacks, truncated and impossible differentials, interpolation attacks, slide attacks, related-key attacks, and algebraic attacks [101]. Since it is a new algorithm, no practical attack is found on SEA currently. 7) HIGHT Algorithm: In [100], the authors claim that HIGHT is secure enough for cryptographic applications. It can be resistant to a number of different cryptanalytic attacks, such as differential cryptanalysis, linear cryptanalysis, truncated differential cryptanalysis, impossible differential cryptanalysis, saturation attack, boomerang attack, interpolation, higher order differential attack, slide attacks, related-key attacks, and algebraic attacks [100]. However, in [10], authors analyzed the resistance of HIGHT against impossible differential attacks by mounting new 26-round impossible differential and 31-round related-key impossible differential attacks where the former requires time complexity of 2119.53 reduced round HIGHT evaluations and proved it is slightly better than exhaustive search. 3.1.2.2 Performance Analysis As we mentioned before, performance analysis in this part is based on related work. It gives us basic information how these algorithms perform. In the end, it helps us to reduce our candidates to a smaller subset. 1) Performance Comparison of DES, 3DES, Blowfish and AES. Although, as we introduced previously that DES is considered to be entirely insecure and Blowfish is the previous version of Twofish, it is still necessary for us to know how well these algorithms perform. [64] has given more prospective about the performance of these compared algorithms. They conducted it on two different machines: P-II 266 MHz and P-4 2.4 GHz and implemented them in Java. The final results showed that Blowfish has a very good performance compared to other algorithms. Also it showed that AES has a better performance than 3DES and DES. Amazingly it shows also that 3DES has almost 1/3 throughput of DES, or in other words it needs 3 times more time than DES to process the same amount of data. For more details see [64]. Page 32/88 2) Performance Comparison of Skipjack, AES, Twofish, RC5, RC6, MISTY1, KASUMI, Camellia [96]. Although, RC5, RC6, MISTY1, KASUMI, Camellia are not in our list, it is still helpful to have brief idea of their performance. In [96], the authors gave a comprehensive comparison of all these block cipher based on WSN. For more details see [96]. They presented a ranking of these ciphers based on code size, data memory, en/decryption efficiency and key setup efficiency. According to their evaluation result, Skipjack, either size-optimized or speed-optimized, is on the top in every test issue. Rijndael has median performance among all competitors. Compared with Rijndael, Twofish is better with respect to footprint. All the rest, RC5, RC6, MISTY1, KASUMI and Camellia did not provide more attractive and overwhelming performance than Rijndael, Skipjack and Twofish. Since these algorithms are patented, we will not consider them in our study. 3) Performance Comparison of DES, AES, DES-X, DESL, HIGHT, TEA, XTEA [98]. In [98], authors implemented these algorithms for the 8-bit AVR architecture, which is a modified Harvard architecture. They took MICA Motes, which is a platform for testing query processing techniques over ad-hoc sensor networks, as an adequate target platform and used an ATmega128 or ATmega128L microcontroller as CPU. The ATmega128 (L) is equipped with 128 kbytes of Flash memory and 4 kbytes of SRAM. They implemented them in AVR-Assembly language by themselves, except for the AES, which is an implementation of the Chair for Communication Security at the Ruhr University of Bochum, and SEA, which is an existing implementation in assembly language available. For more details see [98]. Finally, they came to a conclusion of throughput of encryption and decryption of these algorithms, which is shown in Figure 3.1. Figure 3.1: Throughput of encryption and decryption of algorithms [98] From these results, it is obvious that AES has the highest throughput of encryption and decryption. The total throughputs of TEA, XTEA, SEA, DESL, DES and DES-X are very close to each other. Page 33/88 3.1.3 Candidates As described above, our survey list of symmetric algorithms includes: DES, 3DES, DES-X, DES-L, Blowfish/Twofish, TEA/XTEA/XXTEA, Rijndael, Skipjack, SEA, and HIGHT. Finally, we select Rijndael, Skipjack, XTEA, XXTEA and Twofish as our candidates for further software implementation. The reasons of algorithm selected are given as follows. Rijndael is selected as our candidate, since it is the Advanced Encryption Standard selected by NIST after extensive security and performance evaluation and adopted as a U.S. Federal Information Processing Standard. It is also recommended by NESSIE as one of the 128 bits block ciphers [6]. Skipjack is selected as our candidate, since it is used as a default block cipher in TinySec [44] and MiniSec [46]. TinySec is an optional part of TinyOS, which is the de facto operating system for Wireless Sensor Networks, while MiniSec is a secure network layer protocol for Wireless Sensor Networks. SenSec, another cryptographic layer for Wireless Sensor Networks, [45] uses a variant of Skipjack, named Skipjack-X. Skipjack-X enhances the key length of original Skipjack to be resistant to brute force attacks. All these imply that Skipjack may be a good choice for embedded applications. XTEA and XXTEA are selected as our candidates. The most attractive property of XTEA and XXTEA is their extremely simple implementation in software. As described above, XTEA also has decent performance. We add XXTEA as a candidate since it provides more security than XTEA, although the latest attack on XXTEA shows it does not provide intensive entire 128 bits security. We still would like to evaluate the performance on our platform. Twofish is also selected as one of our candidates. Although Twofish did not win the competition of AES, it is still considered to be efficient on a wide range of platforms. Sano et al. in [47] implemented five AES finalists in a Z80 core with Toshiba’s arithmetic coprocessor. According to their results, Twofish is in the second place of performance, very closed to Rijndael, which is the first. Rijndael can provide good performance in average, but it is proven that Rijndael can perform better than Twofish in every platform. We would like to evaluate the difference between them in our platform. All the rest are not selected as our candidates. The reason is briefly shown as follows. DES is not a good candidate, since its key length is too short to be resistant to brute force attack. Although it is efficient in both software and hardware implementation, it cannot prove Page 34/88 convincing security. 3DES is not selected as a candidate, since its performance is unacceptable. As analysis above, 3DES has only 1/3 throughput of DES, which cannot satisfy the performance requirement. DES-X is not selected. DES-X is DES compatible. The main motivation for DES-X is to improve on the resistance of DES to exhaustive key search attacks. It is a good choice for old platforms which already have DES in use. For new applications, it is better to use other block ciphers. DES-L, SEA and HIGHT are not selected as our final candidates, since they are brand new. They are not recently widely studied by researchers to show they are secure enough. Therefore, very rare applications use these algorithms as their block cipher schemes. For our practical application in industrial networks, it is recommended to apply well studied and widely used block ciphers. 3.2 MAC Algorithms Protecting the integrity of data is of utmost importance for industrial automation networks. In many cases not the confidentiality of the data, but its authenticity and integrity are vital important. Therefore, we need to study hash algorithms to guarantee the data integrity. Previously we have mentioned that hash functions can be catalogued into two types: unkeyed hash functions and keyed hash functions. Of the numerous categories in such a functional classification, two types of hash functions are considered: modification detection codes (MDCs) and message authentication codes (MACs). For industrial automation networks, not only integrity, but also authentication is another important issue. As we introduced before, MAC has two parameters, a message input and a secret key, shared by the sender and the receiver. According to this property, MAC cannot only provide message integrity, but also authentication. Therefore, MAC is more suitable for our case rather than MDC. Normally, MAC can be constructed in several different ways. There are two basic and widely used methods. One is MAC based on block cipher. The simplest way is CBC-MAC; the other is based on cryptographic hash functions. The later one can also be classified into two types. One is using traditional hash function to build MAC, such as HMAC-MD5 or HMAC- SHA1. The other is more advanced method, which is using universal hash function to construct MAC, such as UMAC. We will discuss them in details below. 3.2.1 Introduction 3.2.1.1 Block cipher based MAC There are several MAC algorithms based on block cipher. The details are listed below: 1) CBC-MAC Page 35/88 The most commonly used MAC algorithm based on a block cipher makes use of cipher- block-chaining. A common way to create a MAC is CBC-MAC to encrypt the (padded) message with a block cipher in CBC mode using a fixed IV (e.g. 0). The last ciphertext block is the MAC. (All intermediate blocks discarded.) There are several variations of CBC- MAC: � Prepend message with the length of message in bytes before MAC computation; � Truncate the computed MAC if block size is larger than desired MAC size. 2) OMAC/CMAC and several variant of CBC-MAC There are several variants of CBC-MAC and OMAC is one of them. OMAC is short for one- key MAC. OMAC allows and is secure for messages of any bit length (while the CBC MAC is only secure on messages of one fixed length, and the length must be a multiple of the block length). Officially there are two OMAC algorithms (OMAC1 and OMAC2). OMAC1 is equivalent to CMAC. NIST Special Publication 800-38B Recommendation for Block Cipher Modes of Operation: the CMAC Mode for Authentication has been finalized on May 18, 2005 [87]. Other variants of CBC-MAC are: a) EMAC: The Encrypted MAC (EMAC), also known as double MAC (DMAC), is a popular variant of the CBC-MAC developed by the RACE project. It is derived from the CBC function by additionally encrypting the output with an independent permutation and secure without any restriction on the message space [12]. The EMAC is also is one of the message authentication codes recommended by NESSIE [6]. b) XCBC: The XCBC scheme was originally proposed by Black and Rogaway in 2000, with the objective of providing a provably secure CBC-MAC scheme which minimizes the number of block cipher encryptions and decryptions [14]. c) RMAC: It was proposed by Jaulmes, Joux and Valette, which is an extension of EMAC. The block cipher algorithms currently approved to be used in RMAC are the AES and triple- DES. d) TMAC: stands for two-key MAC. It is a refinement of XCBC shown by Black and Rogaway. It was proposed by Kurosawa and Iwata with the goal of reducing the number of required keys from three to two [90]. Page 36/88 e) PMAC: PMAC stands for Parallelizable MAC. It was created by Phillip Rogaway in 2002. PMAC is a simple and fully parallelizable block-cipher mode of operation for message authentication. It is deterministic, resembles a standard mode of operation (and not a Carter-Wegman MAC), works for strings of any bit length, and employs a single block-cipher key [85]. 3.2.1.2 Hash function based MAC MAC can be constructed with traditional iterative hash functions (different from new universal hash function). Two famous MAC algorithms are constructed based on hash functions, HMAC and TTMAC. TTMAC, also known as Two-Track-MAC, was proposed by K.U.Leuven, Belgium and debis AG. It is based on a slightly modified version of the HASH function RIPEMD-160 taking advantage of the two trails used in its compression function [6]. It is in comparison with the MDx-MAC based on RIPEMD-160, much more efficient on short messages and percentage- wise slightly more efficient on long messages [18]. NESSIE recommended it as one of the secure and efficient MAC algorithms. HMAC is one of the most successful constructions of MAC. It was first published in 1996 by Mihir Bellare, Ran Canetti, and Hugo Krawczyk. HMAC is a variant of NMAC, though NMAC is rarely used today. It does not require the direct loading of the key into the chaining variable of the compression function, but only calls to a hash function. Actually, it is a practical advantage to build MAC through this mechanism, due to the wide availability of free library code for hash functions. Since any iterative hash function can be used in the calculation of HMAC and the security and performance of HMAC is closely related to the inbuilt hash function, it is necessary for us to study traditional hash functions. Here we only list several widely used hash function families. 1) MD5 Message-Digest algorithm 5 (MD5) is a widely used cryptographic hash function with a 128- bit hash value and specified in [111]. MD5 was designed by Ron Rivest in 1991, improved for its previous version MD4. Although MD5 is slightly slower than MD4, it is proven to be more secure. However, MD5 is found not to be collision resistant [19]. 2) SHA-1 / SHA -2 The Secure Hash Algorithm (SHA-1), based on MD4, was proposed by the U.S. National Institute for Standards and Technology (NIST) for certain U.S. federal government Page 37/88 applications. SHA-1 is also one of the most widely used of hash functions, and is used in several widely-used security applications and protocols, such as Digital Signature Stand (DSS). The SHA–2 family includes 224, 256, 384 and 512-bit variants. For more details of SHA-2 see [93]. SHA-256 is used to authenticate Debian Linux software packages and in the DKIM message signing standard; SHA-512 is part of a system to authenticate archival video from the International Criminal Tribunal of the Rwandan genocide. SHA-256 and SHA-512 are proposed for use in DNSSEC. 3) HAVAL HAVAL was proposed by Yuliang Zheng, Josef Pieprzyk, and Jennifer Seberry in 1992. It compresses a message of arbitrary length into a digest of 128, 160, 192, 224 or 256 bits. In addition, HAVAL has a parameter that controls the numbers of passes a message block (of 1024 bits) is processed. 4) RIPEMD - 160 RIPEMD-160 is a hash function based on MD4, taking into account knowledge gained in the analysis of MD4, MD5, and RIPEMD. The overall RIPEMD-160 compression function maps 21-word input to5-word output. Each input block is processed in parallel by distinct versions of the compression function. The 160-bit outputs of the separate lines are combined to give a single160-bit output. For more details see [95]. There also exist 128, 256 and 320-bit versions of this algorithm, called RIPEMD-128, RIPEMD-256, and RIPEMD-320. 5) WHIRLPOOL WHIRLPOOL is a cryptographic hash function, which is designed by Vincent Rijmen and Paulo S. L. M. Barreto. It operates on messages with the length less than 2256 bits, and produces a 512-bit long message digest. There are three versions of WHIRLPOOL. The final version was adopted by the International Organization for Standardization (ISO) in the ISO/IEC 10118-3:2004 standard [20]. 6) SHA -3 The competition of SHA3 is still ongoing. Now it is on Round 2 and there are 14 candidates. Final result will be present in 2012. For more details see the web page of SHA3 competition at NIST. Page 38/88 3.2.1.3 Carter-Wegman MAC Both block cipher based MAC and hash function based MAC are widely used, but nowadays it is widely considered that the state-of-the-art MAC algorithms are based on universal hash function. Universal hash functions, first introduced by Carter and Wegman, provide a unique solution to the aforementioned security problems. Roughly speaking, universal hash functions are collections of hash functions that map messages into short output strings such that the collision probability of any given pair of messages is small. A universal hash function family can be used to build an unconditionally secure MAC [81]. Recently there are two famous MAC algorithms based on strongly universal hash function and AES, named Poly1305-AES and UMAC. 1) Poly1305 - AES Poly1305-AES is one of the state-of-the-art message-authentication codes suitable for a wide variety of applications. Poly1305-AES computes a 16-byte authenticator of a variable- length message, using a 16-byte AES key, a 16-byte additional key, and a 16-byte nonce. The security of Poly1305-AES is very close to the security of AES. There are several useful features of Poly1305-AES, such as extremely high speed, cipher replaceability and etc [91]. 2) UMAC Black et. al. describe a new provably secure message authentication code, called UMAC. UMAC is the fastest message authentication code that has been reported on in the cryptographic literature. First described in 1999, UMAC has undergone significant revisions since its introduction. Large algorithmic changes were made in 2000 to make UMAC faster on short messages. Small algorithmic changes were made in 2004 and a number of UMAC options were eliminated for simplicity [81] [83]. 3.2.2 Security and Performance Analysis 3.2.2.1 Block Cipher Based MAC 1) CBC-MAC In [21], Bellare, Kilian, and Rogaway have already proven that CBC-MAC construction is secure if the underlying block cipher is secure. However, in the end of [21], they emphasized a restriction of the use of CBC-MAC. The restriction is CBC-MAC does not handle variable-length inputs. If an adversary knows two legitimate message-tag pairs, it is extremely easy for him to generate a new legitimate message-tag. Other disadvantages are mandatory serial evaluation and no added resistance to key-search attacks [84]. Page 39/88 However, there are still several advantages of CBC – MAC, which are arbitrary message lengths, efficiency, simplicity and familiarity, no re-keying and proven security. CBC-MAC is very efficient in some cases if block cipher is already used, since it is not necessary to build additional hash functions. However, it is considered that the speed of CBC-MAC is slower than HMAC in most cases. 2) Variants of CBC-MAC: � EMAC: In [12], Erez Petrank and Charles Rackoff have proven that EMAC is secure. They mentioned that if there is an attack against it, then an attack with comparable parameters can also be set on the underlying block cipher. It means that the security of EMAC is proven on the assumption that the underlying block cipher is pseudo-random. For performance, Erez Petrank and Charles Rackoff also proved that there is almost no additional cost for EMAC on that of using CBC MAC to provide a secure solution for authenticating variable-length messages. Also in [6], NESSIE analyzed that the performance and key-agility of EMAC are reasonable. They mentioned that since the block length is smaller compared to the schemes based on a hash function, then EMAC is preferable for short messages. � XCBC: XCBC is initiated by the important lemma in the literature. With this lemma, we can generate two computationally different pseudorandom permutations out of one secret pseudorandom permutation and we can prove the proposed construction is secure. However, in [24] the author introduced forgery attacks and key recovery attacks on XCBC. Another disadvantage of XCBC is that three keys are involved in the calculation of XCBC. � RMAC: In [16] [22], researchers have analyzed the security of RMAC. In [22], NESSIE mentioned that the main advantage of the randomised variant RMAC is that it offers improved resistance against attacks that are based on internal collisions. On the other hand RMAC needs stronger assumptions for its security proof; for instance, the underlying block cipher must be secure against related-key attacks. As the same meaning, in [16], authors present a serious attack against RMAC using 3DES. They also present generic attacks against RMAC using any block cipher but with certain parameters. This attack is able to find one of the two keys in the system faster than by an exhaustive search. Also in [23], the author introduced trivial key recovery attack on the RMAC with about 2n computations. � TMAC: TMAC is a refinement of XCBC. In XCBC, three keys with total length (k + 2n) bits are used, where k is the key length of the underlying block cipher and n is its block length. In TMAC, total key length reduces to (k + n ) bits, since TMAC just changes the Page 40/88 third key K3 in XCBC with K2×x. The proposers of TMAC proved that it is a variable length pseudorandom function with fixed length by assuming that the underlying block cipher is a pseudorandom permutation. However, in [23] [24] [25], all authors present key recover attacks against TMAC, they also gave the suggestion to improve the security of TMAC. For performance, inventor of TMAC declared several advantages of TMAC, such as efficiency, since TMAC uses max block cipher calls, no re-keying, backwards compatibility and simplicity. � PMAC: The inventor of PMAC announced in [85] that PMAC is proven to be secure, as long as the underlying block ciphers meet a standard cryptographic assumption. However, in [25], authors present forgery and Key Recovery Attacks on PMAC and mentioned that PMAC have no significant advantage in comparison with other well- established MAC schemes. For performance, the inventor introduced in [85] that key setup of PMAC is very cheap: one block-cipher call and, if desired, a few XORs and conditional (128-bit) shifts; PMAC has a small footprint, even a memory-minimal implementation doesn't give up much speed. The biggest advantage of PMAC is the high efficiency in parallel environment. However, in a serial environment, PMAC is about as efficient as CBC MAC. In [86], the author shows that PMAC-AES128 is even 8% slower than CBCMAC-AES128 in a serial environment. � CMAC: CMAC is one of the versions of OMAC. Different from XCBC and TMAC, only one key is needed in CMAC. The saving of the key length makes the security proof of CMAC substantially harder than those of XCBC and TMAC [89]. Proposer of CMAC proved that OMAC is secure, where the security analysis is in the concrete-security paradigm. In [24], Mitchell presents a key recover attack against CMAC. However, just soon after that, the proposer of CMAC immediately announced that Mitchell’s result was incorrect [26]. After analysis of [24], they announced that Mitchell’s claims do not give any information except for trivial and expected attacks, do not break the security bound of CMAC and do not find any “significant weakness” in CMAC. Therefore, CMAC is still secure until now. � Comparison of RMAC, EMAC, XCBC, TMAC and CMAC [88]: In [88], Tetsu Iwata presented an entire comparison of these MAC algorithms. He showed that for security, EMAC, XCBC, TMAC and CMAC are better than RMAC. There is no significant difference among EMAC, XCBC, TMAC and CMAC in security. For key length, he showed CMAC gives the best performance, since CMAC is still as secure as EMAC, XCBC, and TMAC despite its optimal key length. After comparison in number of key schedulings, number of block cipher invocations and number of block cipher invocations during the pre-processing time, he made conclusion that CMAC gives the best performance and trade of in efficiency. Page 41/88 3.2.2.2 Hash Function Based MAC 1) MAC Algorithms: � TTMAC: TTMAC stands for Two-Traces MAC algorithm. TTMAC is one of the recommended MAC algorithms by NESSIE. For security, since TTMAC is based on RIPEND-160, it takes advantage of the structure of RIPEND, which consists of two parallel trails. Since two trails are used, the proposer of TTMAC showed that there is impossible for an adversary to do a bijective operation, where he can choose the bijective. Another technology they used to guarantee the transformation of TTMAC to be a one-way function is that a feedback is used to counter a straightforward inverse operation. They also proved that TTMAC is resistant to general attacks, such as key searching, guessing the MAC and internal collision. NESSIE also analyzed the security of TTMAC. NESSIE declared that TTMAC has the highest security level of the MAC primitives considered by NESSIE [6]. They also mentioned that the security can be proven on the assumption that the underlying compression function is pseudo-random. However, the decision made by NESSIE was published in 2003. In 2004, the researcher Wang Xiaoyun had found the collision in RIPEND [94]. Although there are still no attacks published against TTMAC, we still suspect the security of TTMAC. For performance, NESSIE listed two advantages of TTMAC: especially efficient in the case of short messages and having optimal key-agility [6]. � HMAC: In [17], Bellare et al. gave a theoretical support for the security of HMAC. HMAC can be considered to be a particular case of NMAC, so the security of HMAC is closely related to the security of NMAC. According to the analysis of NMAC and the difference between NMAC and HMAC, he proved that the security of HMAC is based on the security of “built-in” compressing function. He also mentioned that two particular parameters, opad and ipad, are very important, since they provide computational independence between the two derived keys [17]. To the end, he proved that only one key used in HMAC does not provide less security than using two independent keys against exhaustive key searching attacks. NESSIE also proved the security of HMAC in [22]. In [34], authors presented distinguishing and forgery attacks against HMAC when HMAC employs hash functions that have slow difference propagations. For performance, how fast HMAC can achieve is essentially related to the performance of the underlying hash function [17]. However, one disadvantage of HMAC is that it is not very efficient short messages. For instance, when the length of an original message is less than one block length, HMAC still calls the built-in hash function for twice, which is significant inefficient. 2) Hash Functions: Page 42/88 Since the security and performance of HMAC are closely related to hash functions in use, we evaluate several commonly used hash functions. � MD5: In 2004, collisions are found by researcher Wang Xiaoyun which makes MD5 no longer secure [19]. Years after that more and more attacks on MD5 were proposedd. MD5 now is weaker than weak. The recommendation of NIST is not to use HMAC-MD5 as MAC any more. � SHA-1 / SHA-2: The hash-value of SHA-1 is 160 bits and five 32-bit chaining variables are used. SHA-1 was considered robust enough against brute-force attacks. However, in 2005, Chinese cryptographer Xiaoyun Wang found collision-finding attacks that require only 263 operations, rather than the 280 operations of the birthday attack. Such an attack is feasible for a very well-funded adversary. Therefore, in March 2006, the Policy on hash functions was published: “Federal agencies should stop using SHA-1 for digital signatures, digital time stamping and other applications that require collision resistance as soon as practical, and must use the SHA-2 family of hash functions for these applications after 2010.” However, we should notice that this attack on SHA-1 is more harmful to digital signature, but for MAC, this attack may make less sense. However, in [35], the authors presented distinguishing, forgery, and partial key recovery attacks on HMAC using collisions a reduced version of SHA-1. Therefore, for security consideration, new applications based on HMAC concerning security more than performance, HMAC-SHA2 should be considered instead of HMAC-SHA1. Although collisions were found in SHA-1, SHA-2 family is not affected. Until now, no efficient attacks on full SHA-2 family are proposed, but still several security analysis on SHA-2 were published. Yoshida and Biryukov showed at SAC 2005 a pseudo-collision for a simplified variant of SHA-256 (up to 34 steps). In [27], Somitra and Palash proposed improved attacks against 22, 23 and 24-step SHA-2 family using a local collision given by Sanadhya and Sarkar (SS) at ACISP ’08. However, these attacks do not affect full SHA-2 family. Therefore, SHA-2 is still considered to be secure. For performance, in [6], NESSIE wrote that the performance of SHA-2 family is acceptable, SHA-512 and SHA-384 being a big faster than Whirlpool on most platforms. SHA-256 is about twice faster on most platforms. � HAVAL: Collisions were found in HAVAL in [19]. In 2006, cryptographer Wang Xiaoyun again gave the full key-recovery attacks on the HMAC/NMAC instantiated with 3 and 4- Pass HAVAL [28], which made HMAC-HAVAL totally insecure and it should not be used any longer. � RIPEND-160: In 2004, collisions were found in RIPEND by cryptographer Wang Xiaoyun [19]. And in 2007, in [28], the authors showed the first cryptanalytic attacks on Page 43/88 the last three rounds of RIPEMD-128. Since RIPEND-160 is an improved version of RIPEND and RIPEND-128, to our knowledge, there is no efficient attack against RIPEND-160 until now. For performance, in [95], it is shown that RIPEND-160 implemented both in 80x86 assembly language and C language and optimized for the Pentium processor is still slower than SHA-1. � WHIRLPOOL: The proposer of WHIRLPOOL declared it is secure. He claimed WHIRLPOOL is resistant to differential attacks and attacks against the internal block cipher [31]. NESSIE also claimed WHIRLPOOL is a collision-resistant hash function. They claimed that the best known attack on WHIRLPOOL finds non-random properties when the compression function is reduced to six rounds or less (out of ten) [6]. However, in [32], authors presented a distinguishing attack on the full compression function of Whirlpool by improving the rebound attack on reduced Whirlpool with two techniques. For performance, WHIRLPOOL is not that fast. NESSIE also claimed that on most platforms it is a bit slower than SHA-512. 3.2.2.3 Cater – Wegman MAC 1) Poly1305-AES: In [91], the proposer of Poly1305-AES proved the security of it. He claimed that the security of Poly1305-AES is very close to the security of AES. He proved that it can guarantee that the only way to break Poly1305-AES is to break AES, which is very secure. Even if an adversary is able to get all the authenticated messages, to check whether or not the receiver accepts a forgery and to affect the sender’s choice of messages, Poly1305-AES is still very secure. However, the user of Poly1305-AES should be responsible to keep the secret key unpredictable and never use the same nonce for two different messages. Otherwise, Poly1305-AES cannot guarantee its security any longer. For performance, the proposer declared in [91] that Poly1305-AES can achieve an extremely high speed, for example, fewer than 3.1L + 780 Athlon cycles for an L-byte message and 1000 keys can be handled simultaneously without cache misses. There is a comparison of Poly127-AES, which is a former version of Poly1305-AES, and SHA1, shown in the next part. 2) UMAC: The security of UMAC is based on the security of its underlying cryptographic functions: the key-derivation function (KDF) and the pad-derivation function (PDF). These functions use a block cipher. The default block cipher is AES, which is considered to be secure. Another important property of UMAC is using UHASH function as the core technology. The UHASH Page 44/88 function does not depend on cryptographic assumption, which means the strength of UHASH is guaranteed regardless of advances in cryptanalysis [33]. The analysis in [33] also shows that UMAC is very secure, resistant against several types of cryptographic attacks, such as reply attacks or side-channel attacks. For performance, in [92], a comparison of UMAC performance and Poly127 and SHA1 is given. The performances were measured on 2.7GHz Pentium 4 running Red Hat Linux. The SHA-1 speeds were acquired by using the command "openssl speed sha1". Since theoretically the speed of HMAC-SHA1 should never be faster than SHA-1, SHA-1 can be used as a reference. The result shows that UMAC32, UMAC64 and UMAC96 are all much faster than HMAC-SHA1. Hash127-AES, also called Poly127-AES, a former version of Poly1305-AES, has a similar performance of UMAC, since they are both based on strong universal hash functions. In [36], the performance of UMAC is also measured by NESSIE. They claimed that for message authentication, UMAC is very fast on the PCs, slow on the Sun. However, for key setup stage, UMAC is exceedingly slow. 3.2.3 Candidates As described above, there are three types of MAC algorithms in our survey list. For block cipher based MAC, there are original CBC-MAC, EMAC, XCBC, RMAC, TMAC, PMAC, CMAC (OMAC); for hash function based MAC, there are TTMAC and HMAC; for Carter- Wegman MAC, there are Poly1305-AES and UMAC. Since HMAC can adopt any hash functions, we have studied several hash functions, they are MD5, SHA-1, SHA-256, HAVAL, RIPEND-160, WHIRLPOOL. It is necessary to evaluate all these three types of MAC algorithms. We choose CMAC from block cipher based MAC algorithms, HMAC- SHA1 and HMAC-SHA2 from hash function based MAC algorithms and UMAC from Carter-Wegman MAC algorithms. The reasons of our choice are given as follows. We select CMAC as a candidate, since it is NIST Special Publication 800-38B Recommendation for Block Cipher Modes of Operation in 2005. As we pointed out, the comparison between CMAC, EMAC, XCBC, RMAC and TMAC done by Tetsu Iwata in [88] shows that CMAC is the most efficient block cipher based MAC among them. Therefore, we select CMAC as our candidate from block cipher based MAC instead of EMAC. Another PMAC is proven to be very efficient in parallel environment, but in our case we cannot obtain any advantage from it. We select HMAC-SHA1 and HMAC-SHA256 as