M.Sc.(CS)-IV Semester-PCSE402-Network Security.pdf

ANNAMALAI UNIVERSITY (Accredited with ‘A’ Grade by NAAC) FACULTY OF SCIENCE DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE M.Sc. (COMPUTER SCIENCE) II YEAR – IV SEMESTER PCSE402- NETWORK SECURITY ...

ANNAMALAI UNIVERSITY (Accredited with ‘A’ Grade by NAAC) FACULTY OF SCIENCE DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE M.Sc. (COMPUTER SCIENCE) II YEAR – IV SEMESTER PCSE402- NETWORK SECURITY  Elective - II Network Security Unit-I - Introduction - Attacks, Services, and Mechanisms – Security Attacks: Passive Attacks –Active Attacks – Security Services – Model for Internetwork Security – Internet Standards and RFCs: Internet Society – RFC Publication – Standardization Process – Non- Standardization Track Documents – Conventional Encryption and Message Confidentiality: Conventional Encryption Principles: Cryptography – Cryptanalysis – Feistel Cipher Structure – Conventional Encryption Algorithms – Cipher Blocks Models of Operation: Cipher Block Chaining Mode – Cipher Feedback Model – Location of Encryption Devices – Key distribution. Unit-II - Public Key Cryptography and Message Authentication - Approaches to Message Authentication: Authentication using Conventional Encryption – Message Authentication without Message Encryption – Message Authentication Code – One Way Hash Function – Secure Hash Function and HMAC: Hash Function Requirements – Simple Hash Functions the SHA–1 Secure Hash Function – Other Secure Hash Functions – HMAC Design Objectives – HMAC Algorithm – Public Key Cryptography Principles: Public Key Encryption Structure Application for Public Key Cryptosystems – Requirements for Public Key Cryptography – Public Key Cryptography Algorithms: RSA Public Key Encryption Algorithms – Diffie-Hellman Key Exchange – Other Public Key Cryptography Algorithms – Digital Signature – Key Management. Unit-III - Electronic Mail Security - Pretty Good Privacy (PGP): Notation – Operational Description – Cryptography Keys and Key Rings – Public Key Management – S/MIME: RFC 822 – Multipurpose Internet Mail Extensions – S/MIME Functionality – S/MIME Messages – S/MIME Certificate Processing – Enhanced Security Services – IP Security: IP Security Overview: Application of IPSec – Benefits of IPSec – Routing Applications – IP Security Architecture: IPSec Documents – IPSec Services – Security Associations – Transport and Tunnel Modes – Authentication Header – Encapsulating Security Payload – Combining Security Associations – Key Management: Oakley Key Determination Protocol – ISAKMP Unit-IV - Web security - Web security Requirements: Web security Threats – Web Traffic Security Approaches – Secure Socket Layer (SSL) and Transport Layer Security (TLS): SSL Architecture – SSL Record Protocol – Change Cipher Spec Protocol – Alert Protocol - Handshake Protocol – Cryptographic Computations – Transport Layer Security – Secure Electronics Transaction (SET): SET Overview – Dual Signature – Payment Processing – Network Management Security: Basic Concepts of SNMP: Network Management Architecture – Network Management Protocol Architecture – Proxies – snmpv2 – snmpv1 Community Facility – snmpv3: SNMP Architecture – Message Processing and the User Security Model – View Based Access Control. Unit-V - System Security - Intruders and Viruses: Intruders: Intrusion Techniques – Password Protection – Password Selection Strategies – Intrusions Detection – Viruses and Related Threats: Malicious Programs – The Nature of Viruses – Types of Viruses – Macro Viruses – Antiviruses Approaches – Advanced Antiviruses Techniques – Firewalls: Firewall Design Principles: Firewall Characteristics – Types of Firewalls – Firewall Configuration – Trusted Systems: Data Access Control – The Concept of Trusted Systems – Trojan Horse Defense. Text book: 1. William Stallings, Network Security Essentials, Prentice Hall, Third Edition, 2006. Reference Books: 1. Manish Tiwari, Handbook of Network Security and Anti Terrorism Laws, Neha Publishers and Distributors, 2012. 2. Adesh K. Pandey, Network Security and Administration, S.K. Kataria and Sons, 2010.  UNIT –I: INTRODUCTION Network Security is used to protect both equipment and information. Computer data often travels from one computer to another, leaving the safety of its protected physical surroundings. Once the data is out of hand, people with bad intention could modify or forge your data, either for amusement or for their own benefit. Cryptography can reformat and transform our data, making it safer on its trip between computers. The technology is based on the essentials of secret codes, augmented by modern mathematics that protects our data in powerful ways. Computer Security - generic name for the collection of tools designed to protect data and to thwart hackers. Network Security - measures to protect data during their transmission. Internet Security - measures to protect data during their transmission over a collection of interconnected networks. SECURITY ATTACKS There are four general categories of attack which are listed below. Interruption An asset of the system is destroyed or becomes unavailable or unusable. This is an attack on availability e.g., destruction of piece of hardware, cutting of a communication line or Disabling of file management system. Interception An unauthorized party gains access to an asset. This is an attack on confidentiality. Unauthorized party could be a person, a program or a computer. e.g., wire tapping to capture data in the network, illicit copying of files. Modification An unauthorized party not only gains access to but tampers with an asset. This is an attack on integrity. e.g., changing values in data file, altering a program, modifying the contents of messages being transmitted in a network. Fabrication An unauthorized party inserts counterfeit objects into the system. This is an attack on 1 authenticity. e.g., insertion of spurious message in a network or addition of records to a file. CRYPTOGRAPHIC ATTACKS Passive Attacks Passive attacks are in the nature of eavesdropping on, or monitoring of, transmissions. The goal of the opponent is to obtain Information that is being transmitted. Passive attacks are of two types:  Release of message contents: A telephone conversation, an e-mail message and a transferred file may contain sensitive or confidential information. We would like to prevent the opponent from learning the contents of these transmissions.  Traffic analysis: If we had encryption protection in place, an opponent might still be able to observe the pattern of the message. The opponent could determine the location and identity of communication hosts and could observe the frequency and length of messages being exchanged. Passive attacks are very difficult to detect because they do not involve any alteration of data. However, it is feasible to prevent the success of these attacks. Active Attacks These attacks involve some modification of the data stream or the creation of a false stream. These attacks can be classified in to four categories:  Masquerade – One entity pretends to be a different entity.  Replay – involves passive capture of a data unit and its subsequent transmission to produce an unauthorized effect.  Modification of messages – Some portion of message is altered or the messages are delayed or recorded, to produce an unauthorized effect.  Denial of service – Prevents or inhibits the normal use or management of communication  Facilities- Another form of service denial is the disruption of an entire network, either by disabling the network or overloading it with messages so as to degrade performance. It is quite difficult to prevent active attacks absolutely, because to do so would require 2 physical protection of all communication facilities and paths at all times. Instead, the goal is to detect them and to recover from any disruption or delays caused by them. SECURITY SERVICES  The classification of security services are as follows:  Confidentiality: Ensures that the information in a computer system a n d transmitted information are accessible only for reading by authorized parties. E.g. Printing, displaying and other forms of disclosure.  Authentication: Ensures that the origin of a message or electronic document is correctly identified, with an assurance that the identity is not false.  Integrity: Ensures that only authorized parties are able to modify computer system assets and transmitted information. Modification includes writing, changing status, deleting, creating and delaying or replaying of transmitted messages.  Non repudiation: Requires that neither the sender nor the receiver of a message be able to deny the transmission.  Access control: Requires that access to information resources may be controlled by or the target system.  Availability: Requires that computer system assets be available to authorized parties when needed. 3 MODEL FOR NETWORK SECURITY 1. Design an algorithm for performing the security-related transformation. The algorithm should be such that an opponent cannot defeat its purpose. 2. Generate the secret information to be used with the algorithm. 3. Develop methods for the distribution and sharing of the secret information. 4. Specify a protocol to be used by the two principals that makes use of the security algorithm and the secret information to achieve a particular security service. Symmetric cipher model consists of five components 1. Plain text: An Original message is known as plaintext. That is feed into the algorithm as input. 2. Encryption Algorithm: The encryption algorithm perform various transposition and substitution techniques. 3. Secret Key: The secret key is also input to the encryption algorithm. The value is independent of the plain text and encryption algorithm. 4. Cipher text: This is the scrambled message produced as output. It depends on the plaintext and secret key. 5. Decryption Algorithm: The encryption algorithm run in the reverse. It take the cipher text and the secret key and produce the original message. The symmetric encryption is also known as Conventional encryption or single key encryption. 4 CRYPTOGRAPHY Cryptographic systems are generally classified along three independent dimensions: Type of operations used for transforming plain text to cipher text All the encryption algorithms are based on two general principles: substitution, in which each element in the plaintext is mapped into another element, and transposition, in which elements in the plaintext are rearranged. The number of keys used If the sender and receiver uses same key then it is said to be symmetric key (or) single key (or) conventional encryption. If the sender and receiver use different keys then it is said to be public key encryption. The way in which the plain text is processed A block cipher processes the input and block of elements at a time, producing output block for each input block. A stream cipher processes the input elements continuously, producing output element one at a time, as it goes along. Types of Cryptosystems Fundamentally, there are two types of cryptosystems based on the manner in which encryption-decryption is carried out in the system − Symmetric Key Encryption Asymmetric Key Encryption The main difference between these cryptosystems is the relationship between the encryption and the decryption key. Logically, in any cryptosystem, both the keys are closely associated. It is practically impossible to decrypt the ciphertext with the key that is unrelated to the encryption key. Symmetric Key Encryption The encryption process where same keys are used for encrypting and decrypting the information is known as Symmetric Key Encryption. The study of symmetric cryptosystems is referred to as symmetric cryptography. 5 Symmetric cryptosystems are also sometimes referred to as secret key cryptosystems. A few well-known examples of symmetric key encryption methods are − Digital Encryption Standard (DES), Triple-DES (3DES), IDEA, and BLOWFISH. Prior to 1970, all cryptosystems employed symmetric key encryption. Even today, its relevance is very high and it is being used extensively in many cryptosystems. It is very unlikely that this encryption will fade away, as it has certain advantages over asymmetric key encryption. The salient features of cryptosystem based on symmetric key encryption are − Persons using symmetric key encryption must share a common key prior to exchange of information. Keys are recommended to be changed regularly to prevent any attack on the system. A robust mechanism needs to exist to exchange the key between the communicating parties. As keys are required to be changed regularly, this mechanism becomes expensive and cumbersome. In a group of n people, to enable two-party communication between any two persons, the number of keys required for group is n × (n – 1)/2. Length of Key (number of bits) in this encryption is smaller and hence, process of encryption-decryption is faster than asymmetric key encryption. Processing power of computer system required to run symmetric algorithm is less. 6 Asymmetric Key Encryption The encryption process where different keys are used for encrypting and decrypting the information is known as Asymmetric Key Encryption. Though the keys are different, they are mathematically related and hence, retrieving the plaintext by decrypting ciphertext is feasible. The process is depicted in the following illustration − Asymmetric Key Encryption was invented in the 20th century to come over the necessity of pre- shared secret key between communicating persons. The salient features of this encryption scheme are as follows − Every user in this system needs to have a pair of dissimilar keys, private key and public key. These keys are mathematically related − when one key is used for encryption, the other can decrypt the ciphertext back to the original plaintext. It requires to put the public key in public repository and the private key as a well- guarded secret. Hence, this scheme of encryption is also called Public Key Encryption. Though public and private keys of the user are related, it is computationally not feasible to find one from another. This is a strength of this scheme. When Host1 needs to send data to Host2, he obtains the public key of Host2 from repository, encrypts the data, and transmits. Host2 uses his private key to extract the plaintext. Length of Keys (number of bits) in this encryption is large and hence, the process of encryption-decryption is slower than symmetric key encryption. Processing power of computer system required to run asymmetric algorithm is higher. 7 Cryptanalysis The process of attempting to discover X or K or both is known as cryptanalysis. The strategy used by the cryptanalysis depends on the nature of the encryption scheme and the information available to the cryptanalyst. There are various types of cryptanalytic attacks based on the amount of information known to the cryptanalyst. Ciphertext Only Attacks (COA) − In this method, the attacker has access to a set of ciphertext(s). He does not have access to corresponding plaintext. COA is said to be successful when the corresponding plaintext can be determined from a given set of ciphertext. Occasionally, the encryption key can be determined from this attack. Modern cryptosystems are guarded against ciphertext-only attacks. Known Plaintext Attack (KPA) − In this method, the attacker knows the plaintext for some parts of the ciphertext. The task is to decrypt the rest of the ciphertext using this information. This may be done by determining the key or via some other method. The best example of this attack is linear cryptanalysis against block ciphers. Chosen Plaintext Attack (CPA) − In this method, the attacker has the text of his choice encrypted. So he has the ciphertext-plaintext pair of his choice. This simplifies his task of determining the encryption key. An example of this attack is differential cryptanalysis applied against block ciphers as well as hash functions. A popular public key cryptosystem, RSA is also vulnerable to chosen-plaintext attacks. Dictionary Attack − This attack has many variants, all of which involve compiling a ‘dictionary’. In simplest method of this attack, attacker builds a dictionary of ciphertexts and corresponding plaintexts that he has learnt over a period of time. In future, when an attacker gets the ciphertext, he refers the dictionary to find the corresponding plaintext. Brute Force Attack (BFA) − In this method, the attacker tries to determine the key by attempting all possible keys. If the key is 8 bits long, then the number of possible keys is 28 = 256. The attacker knows the ciphertext and the algorithm, now he attempts all the 256 keys one by one for decryption. The time to complete the attack would be very high if the key is long. 8 Birthday Attack − This attack is a variant of brute-force technique. It is used against the cryptographic hash function. When students in a class are asked about their birthdays, the answer is one of the possible 365 dates. Let us assume the first student's birthdate is 3rd Aug. Then to find the next student whose birthdate is 3rd Aug, we need to enquire 1.25* √365 ≈ 25 students. Similarly, if the hash function produces 64 bit hash values, the possible hash values are 1.8x1019. By repeatedly evaluating the function for different inputs, the same output is expected to be obtained after about 5.1x109 random inputs. If the attacker is able to find two different inputs that give the same hash value, it is a collision and that hash function is said to be broken. Man in Middle Attack (MIM) − The targets of this attack are mostly public key cryptosystems where key exchange is involved before communication takes place. o Host A wants to communicate to host B, hence requests public key of B. o An attacker intercepts this request and sends his public key instead. o Thus, whatever host A sends to host B, the attacker is able to read. o In order to maintain communication, the attacker re-encrypts the data after reading with his public key and sends to B. o The attacker sends his public key as A’s public key so that B takes it as if it is taking it from A. Side Channel Attack (SCA) − This type of attack is not against any particular type of cryptosystem or algorithm. Instead, it is launched to exploit the weakness in physical implementation of the cryptosystem. Timing Attacks − They exploit the fact that different computations take different times to compute on processor. By measuring such timings, it is be possible to know about a particular computation the processor is carrying out. For example, if the encryption takes a longer time, it indicates that the secret key is long. Power Analysis Attacks − These attacks are similar to timing attacks except that the amount of power consumption is used to obtain information about the nature of the underlying computations. 9  Fault analysis Attacks − In these attacks, errors are induced in the cryptosystem and the attacker studies the resulting output for useful information. FEISTEL CIPHER STRUCTURE The input to the encryption algorithm are a plaintext block of length 2w bits and a key K.The plaintext block is divided into two halves L0 and R0. The two halves of the data pass through „n‟ rounds of processing and then combine to produce the ciphertext block. Each round „i‟ has inputs Li-1 and Ri-1, derived from the previous round, as well as the subkey Ki, derived from the overall key K. in general, the subkeys Ki are different from K and from each other. Classical Feistel Network All rounds have the same structure. A substitution is performed on the left half of the data (as similar to S-DES). This is done by applying a round function F to the right half of the data and then taking the XOR of the output of that function and the left half of the data. The round function has the same general structure for each round but is parameterized by the round sub key ki. Following this substitution, a permutation is performed that consists of the interchange of the two halves of the data. This structure is a particular form of the substitution- permutation network. The exact realization of a Feistel network depends on the choice of the following parameters and design features: 10  Block size - Increasing size improves security, but slows cipher Key size - Increasing size improves security, makes exhaustive key searching harder, but may slow cipher Number of rounds - Increasing number improves security, but slows cipher Subkey generation - Greater complexity can make analysis harder, but slows cipher Round function - Greater complexity can make analysis harder, but slows cipher Fast software en/decryption & ease of analysis - are more recent concerns for practical use and testing. Feistel encryption and decryption The process of decryption is essentially the same as the encryption process. The rule is as follows: use the cipher text as input to the algorithm, but use the subkey ki in reverse order. i.e., kn in the first round, kn-1 in second round and so on. For clarity, we use the notation LEi and REi for data traveling through the decryption algorithm. The diagram below indicates that, 11 at each round, the intermediate value of the decryption process is same (equal) to the corresponding value of the encryption process with two halves of the value swapped. i.e., REi || LEi (or) equivalently RD16-i || LD16-i After the last iteration of the encryption process, the two halves of the output are swapped, so that the cipher text is RE16 || LE16. The output of that round is the cipher text. Now take the cipher text and use it as input to the same algorithm. The input to the first round is RE16 || LE16, which is equal to the 32-bit swap of the output of the sixteenth round of the encryption process. CLASSICAL ENCRYPTION TECHNIQUES There are two basic building blocks of all encryption techniques: substitution and transposition. SUBSTITUTION TECHNIQUES A substitution technique is one in which the letters of plaintext are replaced by other letters or by numbers or symbols. If the plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with cipher text bit patterns. Caesar cipher (or) shift cipher The earliest known use of a substitution cipher and the simplest was by Julius Caesar. The Caesar cipher involves replacing each letter of the alphabet with the letter standing 3 places further down the alphabet. e.g., plain text : pay more money Cipher text: SDB PRUH PRQHB Note that the alphabet is wrapped around, so that letter following „z‟ is „a‟. For each plaintext letter p, substitute the cipher text letter c such that C = E(p) = (p+3) mod 26 A shift may be any amount, so that general Caesar algorithm is C = E (p) = (p+k) mod 26 Where k takes on a value in the range 1 to 25. The decryption algorithm is simply P = D(C) = (C-k) mod 26 12 Monoalphabetic Ciphers With only 25 possible keys, the Caesar cipher is far from secure. A dramatic increase in the key space can be achieved by allowing an arbitrary substitution. Recall the assignment for the Caesar cipher: plain: a b c d e f g h i j k l m n o p q r s t u v w x y z cipher: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C If, instead, the "cipher" line can be any permutation of the 26 alphabetic characters, then there are 26! or greater than 4 x 1026 possible keys. This is 10 orders of magnitude greater than the key space for DES and would seem to eliminate brute-force techniques for cryptanalysis. Such an approach is referred to as a monoalphabetic substitution cipher. Playfair cipher The best known multiple letter encryption cipher is the playfair, which treats diagrams in the plaintext as single units and translates these units into cipher text diagrams. The playfair algorithm is based on the use of 5x5 matrix of letters constructed using a keyword. Let the keyword be „monarchy‟. The matrix is constructed by filling in the letters of the keyword (minus duplicates) from left to right and from top to bottom, and then filling in the remainder of the matrix with the remaining letters in alphabetical order. The letter „i‟ and „j‟ count as one letter. Plaintext is encrypted two letters at a time. According to the following rules: Repeating plaintext letters that would fall in the same pair are separated with a Filler letter such as „x‟. Plaintext letters that fall in the same row of the matrix are each replaced by the letter to the right, with the first element of the row following the last. Plaintext letters that fall in the same column are replaced by the letter beneath, with the top element of the column following the last. Otherwise, each plaintext letter is replaced by the letter that lies in its own row and the column occupied by the other plaintext letter. 13  M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z Plaintext : meet me at the school house Splitting two letters as a unit => me et me at th es ch o x ol ho us ex Corresponding cipher text => CL KL CL RS PD IL HY AV MP HF XL IU Polyalphabetic ciphers Another way to improve on the simple monoalphabetic technique is to use different monoalphabetic substitutions as one proceeds through the plaintext message. The general name for this approach is polyalphabetic cipher. All the techniques have the following features in common. A set of related monoalphabetic substitution rules are used A key determines which particular rule is chosen for a given transformation. Vigenere cipher In this scheme, the set of related monoalphabetic substitution rules consisting of 26 caesar ciphers with shifts of 0 through 25. Each cipher is denoted by a key letter. e.g., Caesar cipher with a shift of 3 is denoted by the key value 'd‟ (since a=0, b=1, c=2 and so on). To aid in understanding the scheme, a matrix known as vigenere tableau is Constructed Each of the 26 ciphers is laid out horizontally, with the key letter for each cipher to its left. A normal alphabet for the plaintext runs across the top. The process ofEEncryption is simple: Given a key letter X and a plaintext letter y, the cipher text is at the intersection of the row labeled x and the column labeled y; in this case, the ciphertext is V. To encrypt a message, a key is needed that is as long as the message. Usually, the key is a repeating keyword. e.g., key = d e c e p t i v e d e c e p t i v e d e c e p t i v e PT = w e a r e d i s c o v e r e d s a v e yo u r s elf CT = ZICVTWQNGRZGVTWAVZHCQYGLMGJ 14  Decryption is equally simple. The key letter again identifies the row. The position of the cipher text letter in that row determines the column, and the plaintext letter is at the top of that column. Strength of Vigenere cipher o There are multiple cipher text letters for each plaintext letter. o Letter frequency information is obscured. TRANSPOSITION TECHNIQUES All the techniques examined so far involve the substitution of a cipher text symbol for a plaintext symbol. A very different kind of mapping is achieved by performing some sort of permutation on the plaintext letters. This technique is referred to as a transposition cipher. Rail fence is simplest of such cipher, in which the plaintext is written down as a sequence of diagonals and then read off as a sequence of rows. Plaintext = meet at the school house To encipher this message with a rail fence of depth 2, we write the message as follows: meatecolosetthshohue The encrypted message is MEATECOLOSETTHSHOHUE Row Transposition Ciphers- A more complex scheme is to write the message in a rectangle, row by row, and read the message off, column by column, but permute the order of the columns. The order of columns then becomes the key of the algorithm. e.g., plaintext = meet at the school house Key = 4 3 1 2 5 6 7 PT = m e e t a t t h e s c h o o l h o u s e CT = ESOTCUEEHMHLAHSTOETO A pure transposition cipher is easily recognized because it has the same letter frequencies as the original plaintext. The transposition cipher can be made significantly more secure by performing more than one stage of transposition. The result is more complex permutation that is not easily reconstructed. 15 DATA ENCRYPTION STANDARD (DES) The Data Encryption Standard (DES) is a symmetric-key block cipher published by the National Institute of Standards and Technology (NIST). DES is an implementation of a Feistel Cipher. It uses 16 round Feistel structure. The block size is 64-bit. Though, key length is 64-bit, DES has an effective key length of 56 bits, since 8 of the 64 bits of the key are not used by the encryption algorithm (function as check bits only). General Structure of DES is depicted in the following illustration Since DES is based on the Feistel Cipher, all that is required to specify DES is − Round function Key schedule Any additional processing − Initial and final permutation Initial and Final Permutation The initial and final permutations are straight Permutation boxes (P-boxes) that are inverses of each other. They have no cryptography significance in DES. The initial and final permutations are shown as follows − 16 Round Function The heart of this cipher is the DES function, f. The DES function applies a 48-bit key to the rightmost 32 bits to produce a 32-bit output. Expansion Permutation Box − Since right input is 32-bit and round key is a 48-bit, we first need to expand right input to 48 bits. Permutation logic is graphically depicted in the following illustration − 17 The graphically depicted permutation logic is generally described as table in DES specification illustrated as shown − XOR (Whitener). − After the expansion permutation, DES does XOR operation on the expanded right section and the round key. The round key is used only in this operation. Substitution Boxes. − The S-boxes carry out the real mixing (confusion). DES uses 8 S- boxes, each with a 6-bit input and a 4-bit output. Refer the following illustration − The S-box rule is illustrated below − 18  There are a total of eight S-box tables. The output of all eight s-boxes is then combined in to 32 bit section. Straight Permutation − The 32 bit output of S-boxes is then subjected to the straight permutation with rule shown in the following illustration: Key Generation The round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key. The process of key generation is depicted in the following illustration – 19  The logic for Parity drop, shifting, and Compression P-box is given in the DES description. DES Analysis The DES satisfies both the desired properties of block cipher. These two properties make cipher very strong. Avalanche effect − A small change in plaintext results in the very great change in the ciphertext. Completeness − Each bit of ciphertext depends on many bits of plaintext. TRIPLE DES The speed of exhaustive key searches against DES after 1990 began to cause discomfort amongst users of DES. However, users did not want to replace DES as it takes an enormous amount of time and money to change encryption algorithms that are widely adopted and embedded in large security architectures. 20  The pragmatic approach was not to abandon the DES completely, but to change the manner in which DES is used. This led to the modified schemes of Triple DES (sometimes known as 3DES). Incidentally, there are two variants of Triple DES known as 3-key Triple DES (3TDES) and 2- key Triple DES (2TDES). 3- KEY Triple DES Before using 3TDES, user first generate and distribute a 3TDES key K, which consists of three different DES keys K1, K2 and K3. This means that the actual 3TDES key has length 3×56= 168 bits. The encryption scheme is illustrated as follows − The encryption-decryption process is as follows −  Encrypt the plaintext blocks using single DES with key K1.  Now decrypt the output of step 1 using single DES with key K2.  Finally, encrypt the output of step 2 using single DES with key K3.  The output of step 3 is the ciphertext. 21   Decryption of a ciphertext is a reverse process. User first decrypt using K3, then encrypt with K2, and finally decrypt with K1. Due to this design of Triple DES as an encrypt–decrypt–encrypt process, it is possible to use a 3TDES (hardware) implementation for single DES by setting K1, K2, and K3 to be the same value. This provides backwards compatibility with DES. Second variant of Triple DES (2TDES) is identical to 3TDES except that K3is replaced by K1. In other words, user encrypt plaintext blocks with key K1, then decrypt with key K2, and finally encrypt with K1 again. Therefore, 2TDES has a key length of 112 bits. Triple DES systems are significantly more secure than single DES, but these are clearly a much slower process than encryption using single DES. ADVANCED ENCRYPTION STANDARD The more popular and widely adopted symmetric encryption algorithm likely to be encountered nowadays is the Advanced Encryption Standard (AES). It is found at least six time faster than triple DES. A replacement for DES was needed as its key size was too small. With increasing computing power, it was considered vulnerable against exhaustive key search attack. Triple DES was designed to overcome this drawback but it was found slow. The features of AES are as follows −  Symmetric key symmetric block cipher  128-bit data, 128/192/256-bit keys  Stronger and faster than Triple-DES  Provide full specification and design details  Software implementable in C and Java Operation of AES AES is an iterative rather than Feistel cipher. It is based on ‘substitution–permutation network’. It comprises of a series of linked operations, some of which involve replacing inputs by specific outputs (substitutions) and others involve shuffling bits around (permutations). 22  Interestingly, AES performs all its computations on bytes rather than bits. Hence, AES treats the 128 bits of a plaintext block as 16 bytes. These 16 bytes are arranged in four columns and four rows for processing as a matrix − Unlike DES, the number of rounds in AES is variable and depends on the length of the key. AES uses 10 rounds for 128-bit keys, 12 rounds for 192-bit keys and 14 rounds for 256- bit keys. Each of these rounds uses a different 128-bit round key, which is calculated from the original AES key. The schematic of AES structure is given in the following illustration − Encryption Process Here, we restrict to description of a typical round of AES encryption. Each round comprise of four sub-processes. The first round process is depicted below − 23 Byte Substitution (SubBytes) The 16 input bytes are substituted by looking up a fixed table (S-box) given in design. The result is in a matrix of four rows and four columns. Shiftrows Each of the four rows of the matrix is shifted to the left. Any entries that ‘fall off’ are re- inserted on the right side of row. Shift is carried out as follows −  First row is not shifted.  Second row is shifted one (byte) position to the left.  Third row is shifted two positions to the left.  Fourth row is shifted three positions to the left.  The result is a new matrix consisting of the same 16 bytes but shifted with respect to each other. MixColumns Each column of four bytes is now transformed using a special mathematical function. This function takes as input the four bytes of one column and outputs four completely new bytes, which replace the original column. The result is another new matrix consisting of 16 new bytes. It should be noted that this step is not performed in the last round. Addroundkey The 16 bytes of the matrix are now considered as 128 bits and are XORed to the 128 bits of the round key. If this is the last round then the output is the ciphertext. Otherwise, the resulting 128 bits are interpreted as 16 bytes and we begin another similar round. Decryption Process The process of decryption of an AES ciphertext is similar to the encryption process in the reverse order. Each round consists of the four processes conducted in the reverse order −  Add round key  Mix columns 24   Shift rows  Byte substitution Since sub-processes in each round are in reverse manner, unlike for a Feistel Cipher, the encryption and decryption algorithms needs to be separately implemented, although they are very closely related. AES Analysis In present day cryptography, AES is widely adopted and supported in both hardware and software. Till date, no practical cryptanalytic attacks against AES has been discovered. Additionally, AES has built-in flexibility of key length, which allows a degree of ‘future- proofing’ against progress in the ability to perform exhaustive key searches. However, just as for DES, the AES security is assured only if it is correctly implemented and good key management is employed. BLOCK CIPHER PRINCIPLES Virtually, all symmetric block encryption algorithms in current use are based on a structure referred to as Fiestel block cipher. For that reason, it is important to examine the design principles of the Fiestel cipher. We begin with a comparison of stream cipher with block cipher. A stream cipher is one that encrypts a digital data stream one bit or one byte at a time. E.g, vigenere cipher. A block cipher is one in which a block of plaintext is treated as a whole and used to produce a cipher text block of equal length. Typically a block size of 64 or 128 bits is used. Block cipher principles Most symmetric block ciphers are based on a Feistel Cipher Structure needed since must be able to decrypt ciphertext to recover messages efficiently. block ciphers look like an extremely large substitution Would need table of 264 entries for a 64-bit block Instead create from smaller building blocks Using idea of a product cipher in 1949 Claude Shannon introduced idea of substitution- 25  permutation (S-P) networks called modern substitution-transposition product cipher these form the basis of modern block ciphers S-P networks are based on the two primitive cryptographic operations we have seen before: substitution (S-box) permutation (P-box) provide confusion and diffusion of message diffusion – dissipates statistical structure of plaintext over bulk of ciphertext. confusion – makes relationship between ciphertext and key as complex as possible. BLOCK CIPHER MODES OF OPERATION. i. Cipher Block Chaining(CBC) ii. Cipher Feedback(CFB) A block cipher processes the data blocks of fixed size. Usually, the size of a message is larger than the block size. Hence, the long message is divided into a series of sequential message blocks, and the cipher operates on these blocks one at a time. Cipher Block Chaining (CBC) Mode CBC mode of operation provides message dependence for generating ciphertext and makes the system non-deterministic Operation. The operation of CBC mode is depicted in the following illustration. The steps are as follows: Load the n-bit Initialization Vector (IV) in the top register. XOR the n-bit plaintext block with data value in top register. Encrypt the result of XOR operation with underlying block cipher with key K. Feed ciphertext block into top register and continue the operation till all plaintext blocks are processed. For decryption, IV data is XORed with first ciphertext block decrypted. The first ciphertext block is also fed into to register replacing IV for decrypting next ciphertext block. 26 Analysis of CBC Mode In CBC mode, the current plaintext block is added to the previous ciphertext block, and then the result is encrypted with the key. Decryption is thus the reverse process, which involves decrypting the current ciphertext and then adding the previous ciphertext block to the result. Advantage of CBC over ECB is that changing IV results in different ciphertext for identical message. On the drawback side, the error in transmission gets propagated to few further block during decryption due to chaining effect. It is worth mentioning that CBC mode forms the basis for a well-known data origin authentication mechanism. Thus, it has an advantage for those applications that require both symmetric encryption and data origin authentication. Cipher Feedback (CFB) Mode In this mode, each ciphertext block gets ‘fed back’ into the encryption process in order to encrypt the next plaintext block. Operation The operation of CFB mode is depicted in the following illustration. For example, in the present system, a message block has a size ‘s’ bits where 1 < s < n. The CFB mode requires an initialization vector (IV) as the initial random n-bit input block. The IV need not be secret. Steps of operation are − 27  Load the IV in the top register. Encrypt the data value in top register with underlying block cipher with key K. Take only ‘s’ number of most significant bits (left bits) of output of encryption process and XOR them with ‘s’ bit plaintext message block to generate ciphertext block. Feed ciphertext block into top register by shifting already present data to the left and continue the operation till all plaintext blocks are processed. Essentially, the previous ciphertext block is encrypted with the key, and then the result is XORed to the current plaintext block. Similar steps are followed for decryption. Pre-decided IV is initially loaded at the start of decryption. Analysis of CFB Mode CFB mode differs significantly from ECB mode, the ciphertext corresponding to a given plaintext block depends not just on that plaintext block and the key, but also on the previous ciphertext block. In other words, the ciphertext block is dependent of message. CFB has a very strange feature. In this mode, user decrypts the ciphertext using only the encryption process of the block cipher. The decryption algorithm of the underlying block cipher is never used. Apparently, CFB mode is converting a block cipher into a type of stream cipher. The encryption algorithm is used as a key-stream generator to produce key-stream that is placed in the bottom register. This key stream is then XORed with the plaintext as in case of stream cipher. By converting a block cipher into a stream cipher, CFB mode provides some of the advantageous properties of a stream cipher while retaining the advantageous properties of a block cipher.On the flip side, the error of transmission gets propagated due to changing of blocks. 28 LOCATION OF ENCRYPTION DEVICES Two approaches are 1. Link encryption 2. End to end encryption Link versus End-to-End Encryption With link encryption, each vulnerable communications link is equipped on both ends with an encryption device. Thus, all traffic over all communications links is secured. Although this recourse requires a lot of encryption devices in a large network, its value is clear. One of its disadvantages is that the message must be decrypted each time it enters a switch (such as a frame relay switch) because the switch must read the address (logical connection number) in the packet header in order to route the frame. Thus, the message is vulnerable at each switch. If working with a public network, the user has no control over the security of the nodes. Several implications of link encryption should be noted. For this strategy to be effective, all the potential links in a path from source to destination must use link encryption. Each pair of nodes that share a link should share a unique key, with a different key used on each link. Thus, many keys must be provided. With end-to-end encryption, the encryption process is carried out at the two end systems. The source host or terminal encrypts the data. The data in encrypted form are then transmitted unaltered across the network to the destination terminal or host. The destination shares a key with the source and so is able to decrypt the data. This plan seems to secure the 29 transmission against attacks on the network links or switches. Thus, end-to-end encryption relieves the end user of concerns about the degree of security of networks and links that support the communication. There is, however, still a weak spot. Consider the following situation. A host connects to a frame relay or ATM network, sets up a logical connection to another host, and is prepared to transfer data to that other host by using end-to-end encryption. Data are transmitted over such a network in the form of packets that consist of a header and some user data. What part of each packet will the host encrypt? Suppose that the host encrypts the entire packet, including the header. This will not work because, remember, only the other host can perform the decryption. The frame relay or ATM switch will receive an encrypted packet and be unable to read the header. Therefore, it will not be able to route the packet. It follows that the host may encrypt only the user data portion of the packet and must leave the header in the clear. Thus, with end-to-end encryption, the user data are secure. However, the traffic pattern is not, because packet headers are transmitted in the clear. On the other hand, end-to-end encryption does provide a degree of authentication. If two end systems share an encryption key, then a recipient is assured that any message that it receives comes from the alleged sender, because only that sender shares the relevant key. Such authentication is not inherent in a link encryption scheme. To achieve greater security, both link and end-to-end encryption are needed, When both forms of encryption are employed, the host encrypts the user data portion of a packet using an end-to-end encryption key. The entire packet is then encrypted using a link encryption key. As the packet traverses the network, each switch decrypts the packet, using a link encryption key to read the header, and then encrypts the entire packet again for sending it out on the next link. Now the entire packet is secure except for the time that the packet is actually in the memory of a packet switch, at which time the packet header is in the clear. Link Encryption Link Encryption Security within End Systems and Intermediate Systems Message exposed in sending host Message encrypted in sending host Message exposed in intermediate nodes Message encrypted in intermediate nodes Role of User 30  Applied by sending host Applied by sending process Transparent to user User applies encryption Host maintains encryption facility User must determine algorithm One facility for all users Users selects encryption scheme Can be done in hardware Software implementation All or no messages encrypted User chooses to encrypt, or not, for each message Implementation Concerns Requires one key per (host-intermediate node) Requires one key per user pair pair and (intermediate node-intermediate node) pair Provides host authentication Provides user authentication Key Distribution For symmetrical encryption systems to work, the two parties must have the same key, and that key must be protected from access by others. Furthermore, frequent key changes are usually desirable to limit the amount of data compromised if an opponent, Oscar, leaves the key. Therefore, the strength of any cryptographic system rests with the key distribution technique. That is, the means of delivering a key to two parties that wish to exchange data securely. Key distribution can be achieved in a number of ways. For two parties, Alice and Bob:  A key could be selected by Alice and physically delivered to Bob:  A 3rd party could select the key and physically deliver it to Alice and Bob.  If Alice and Bob have previously and recently used a key, one party could transmit the new key to the other, encrypted using the old key.  If Alice and Bob each have an encrypted connection to a trusted 3 rd party, named Casey, he could deliver a key on the encrypted links to Alice and Bob. Note 1 – Option 1 and 2 call for manual delivery of a key. This is seasonal for link encryption. However, for end-to-end encryption, manual delivery is awkward. In a distributed system, any given host on terminal may need to engage in exchange with many other hosts and terminal over time. Thus each device needs a number of keys, supplied dynamically. The problem becomes quite difficult is a wide area distributed system. Note 2 – Option 3 is a possibility for either link encryption on end-to-end encryption, but it an opponent, Oscar, ever succeeds in gaining access to one key, then all subsequent keys are revealed. Note 3 – To provide keys for end-to-end encryption, option 4 is preferable. 31  UNIT –II: PUBLIC KEY CRYPTOGRAPHY AND MESSAGE AUTHENTICATION MESSAGE AUTHENTICATION AND HASH FUNCTIONS Authentication Requirements In the context of communications across a network, the following attacks can be identified: 1. Disclosure: Release of message contents to any person or process not possessing the appropriate cryptographic key. 2. Traffic analysis: Discovery of the pattern of traffic between parties. In a connection- oriented application, the frequency and duration of connections could be determined. In either a connection-oriented or connectionless environment, the number and length of messages between parties could be determined. 3. Masquerade: Insertion of messages into the network from a fraudulent source. This includes the creation of messages by an opponent that are purported to come from an authorized entity. Also included are fraudulent acknowledgments of message receipt or non receipt by someone other than the message recipient. 4. Content modification: Changes to the contents of a message, including insertion, deletion, transposition, and modification. 5. Sequence modification: Any modification to a sequence of messages between parties, including insertion, deletion, and reordering. 6. Timing modification: Delay or replay of messages. In a connection-oriented application, an entire session or sequence of messages could be a replay of some previous valid session, or individual messages in the sequence could be delayed or replayed. In a connectionless application, an individual message (e.g., datagram) could be delayed or replayed. 7. Source repudiation: Denial of transmission of message by source. 8. Destination repudiation: Denial of receipt of message by destination. AUTHENTICATION FUNCTIONS  Message encryption: The ciphertext of the entire message serves as its authenticator  Message authentication code (MAC): A function of the message and a secret key that produces a fixed-length value that serves as the authenticator  Hash function: A function that maps a message of any length into a fixed-length hash value, which serves as the authenticator.  Message Encryption Message encryption by itself can provide a measure of authentication. The analysis differs for symmetric and public-key encryption schemes. 32 Symmetric Encryption Consider the straightforward use of symmetric encryption in the below figure. A message M transmitted from source A to destination B is encrypted using a secret key K shared by A and B. If no other party knows the key, then confidentiality is provided: No other party can recover the plaintext of the message. MESSAGE AUTHENTICATION CODE An alternative authentication technique involves the use of a secret key to generate a small fixed-size block of data, known as a cryptographic checksum or MAC that is appended to the message. This technique assumes that two communicating parties, say A and B, share a common secret key K. When A has a message to send to B, it calculates the MAC as a function of the message and the key: 33  MAC = C(K, M), where M = input message C = MAC function K = shared secret key MAC = message authentication code The message plus MAC are transmitted to the intended recipient. The recipient performs the same calculation on the received message, using the same secret key, to generate a new MAC. The received MAC is compared to the calculated MAC. If we assume that only the receiver and the sender know the identity of the secret key, and if the received MAC matches the calculated MAC, then  The receiver is assured that the message has not been altered. If an attacker alters the message but does not alter the MAC, then the receiver's calculation of the MAC will differ from the received MAC. Because the attacker is assumed not to know the secret key, the attacker cannot alter the MAC to correspond to the alterations in the message.  The receiver is assured that the message is from the alleged sender. Because no one else knows the secret key, no one else could prepare a message with a proper MAC.  If the message includes a sequence number (such as is used with HDLC, X.25, and TCP), then the receiver can be assured of the proper sequence because an attacker cannot successfully alter the sequence number. HASH FUNCTION A variation on the message authentication code is the one-way hash function. As with the message authentication code, a hash function accepts a variable-size message M as input and produces a fixed size output, referred to as a hash code H(M). Unlike a MAC, a hash code 34 does not use a key but is a function only of the input message. The hash code is also referred to as a message digest or hash value. The hash code is a function of all the bits of the message and provides an error-detection capability. A change to any bit or bits in the message results in a change to the hash code. Basic Uses of Hash Function  The message plus concatenated hash code is encrypted using symmetric encryption. A and B share the secret key, the message must have come from A and has not been altered. The hash code provides the structure or redundancy required to achieve authentication. Because encryption is applied to the entire message plus hash code, confidentiality is also provided. 35   Only the hash code is encrypted, using symmetric encryption. This reduces the processing burden for those applications that do not require confidentiality.  Only the hash code is encrypted, using public-key encryption and using the sender's private key. As with (b), this provides authentication. It also provides a digital signature, because only the sender could have produced the encrypted hash code. In fact, this is the essence of the digital signature technique.  If confidentiality as well as a digital signature is desired, then the message plus the private-key encrypted hash code can be encrypted using a symmetric secret key. This is a common technique.  It is possible to use a hash function but no encryption for message authentication. The technique assumes that the two communicating parties share a common secret value S. A computes the hash value over the concatenation of M and S and appends the resulting hash value to M. Because B possesses S, it can re-compute the hash value to verify. Because the secret value itself is not sent, an opponent cannot modify an intercepted message and cannot generate a false message.  Confidentiality can be added to the approach of (e) by encrypting the entire message plus the hash code. Hash functions are extremely useful and appear in almost all information security applications. A hash function is a mathematical function that converts a numerical input value into another compressed numerical value. The input to the hash function is of arbitrary length but output is always of fixed length. Values returned by a hash function are called message digest or simply hash values. The following picture illustrated hash function. Features of Hash Functions 36 The typical features of hash functions are  Fixed Length Output (Hash Value) o Hash function coverts data of arbitrary length to a fixed length. This process is often referred to as hashing the data. o In general, the hash is much smaller than the input data, hence hash functions are sometimes called compression functions. o Since a hash is a smaller representation of a larger data, it is also referred to as a digest. o Hash function with n bit output is referred to as an n-bit hash function. Popular hash functions generate values between 160 and 512 bits.  Efficiency of Operation o Generally for any hash function h with input x, computation of h(x) is a fast operation. o Computationally hash functions are much faster than a symmetric encryption. Design of Hashing Algorithms At the heart of a hashing is a mathematical function that operates on two fixed-size blocks of data to create a hash code. This hash function forms the part of the hashing algorithm. The size of each data block varies depending on the algorithm. Typically the block sizes are from 128 bits to 512 bits. The following illustration demonstrates hash function − Hashing algorithm involves rounds of above hash function like a block cipher. Each round takes an input of a fixed size, typically a combination of the most recent message block and the output of the last round. This process is repeated for as many rounds as are required to hash the entire message. Schematic of hashing algorithm is depicted in the following illustration − 37  Since, the hash value of first message block becomes an input to the second hash operation, output of which alters the result of the third operation, and so on. This effect, known as an avalanche effect of hashing. Avalanche effect results in substantially different hash values for two messages that differ by even a single bit of data. Understand the difference between hash function and algorithm correctly. The hash function generates a hash code by operating on two blocks of fixed-length binary data. Hashing algorithm is a process for using the hash function, specifying how the message will be broken up and how the results from previous message blocks are chained together. Secure Hash Function (SHA) Family of SHA comprise of four SHA algorithms; SHA-0, SHA-1, SHA-2, and SHA-3. Though from same family, there are structurally different.  The original version is SHA-0, a 160-bit hash function, was published by the National Institute of Standards and Technology (NIST) in 1993. It had few weaknesses and did not become very popular. Later in 1995, SHA-1 was designed to correct alleged weaknesses of SHA-0.  SHA-1 is the most widely used of the existing SHA hash functions. It is employed in several widely used applications and protocols including Secure Socket Layer (SSL) security.  In 2005, a method was found for uncovering collisions for SHA-1 within practical time frame making long-term employability of SHA-1 doubtful.  SHA-2 family has four further SHA variants, SHA-224, SHA-256, SHA-384, and SHA- 512 depending up on number of bits in their hash value. No successful attacks have yet been reported on SHA-2 hash function.  Though SHA-2 is a strong hash function. Though significantly different, its basic design is still follows design of SHA-1. Hence, NIST called for new competitive hash function designs.  In October 2012, the NIST chose the Keccak algorithm as the new SHA-3 standard. Keccak offers many benefits, such as efficient performance and good resistance for attacks. 38 Message Authentication Code (MAC) MAC algorithm is a symmetric key cryptographic technique to provide message authentication. For establishing MAC process, the sender and receiver share a symmetric key K. Essentially, a MAC is an encrypted checksum generated on the underlying message that is sent along with a message to ensure message authentication. The process of using MAC for authentication is depicted in the following illustration − Let us now try to understand the entire process in detail −  The sender uses some publicly known MAC algorithm, inputs the message and the secret key K and produces a MAC value.  Similar to hash, MAC function also compresses an arbitrary long input into a fixed length output. The major difference between hash and MAC is that MAC uses secret key during the compression.  The sender forwards the message along with the MAC. Here, we assume that the message is sent in the clear, as we are concerned of providing message origin authentication, not confidentiality. If confidentiality is required then the message needs encryption.  On receipt of the message and the MAC, the receiver feeds the received message and the shared secret key K into the MAC algorithm and re-computes the MAC value.  The receiver now checks equality of freshly computed MAC with the MAC received from the sender. If they match, then the receiver accepts the message and assures himself that the message has been sent by the intended sender.  If the computed MAC does not match the MAC sent by the sender, the receiver cannot determine whether it is the message that has been altered or it is the origin that has been falsified. As a bottom-line, a receiver safely assumes that the message is not the genuine. 39 Limitations of MAC There are two major limitations of MAC, both due to its symmetric nature of operation −  Establishment of Shared Secret. o It can provide message authentication among pre-decided legitimate users who have shared key. o This requires establishment of shared secret prior to use of MAC.  Inability to Provide Non-Repudiation o Non-repudiation is the assurance that a message originator cannot deny any previously sent messages and commitments or actions. o MAC technique does not provide a non-repudiation service. If the sender and receiver get involved in a dispute over message origination, MACs cannot provide a proof that a message was indeed sent by the sender. o Though no third party can compute the MAC, still sender could deny having sent the message and claim that the receiver forged it, as it is impossible to determine which of the two parties computed the MAC. HMAC Algorithm Notations H = embedded hash function (e.g., MD5, SHA-1, RIPEMD-160) IV = initial value input to hash function M = message input to HMAC(including the padding specified in the embedded hash function) Yi = ith block of M, 0 i (L - 1) L = number of blocks in M b = number of bits in a block n = length of hash code produced by embedded hash function K= secret key recommended length is n; if key length is greater than b; the key is input to the hash function to produce an n-bit key K+ = K padded with zeros on the left so that the result is b bits in length ipad = 00110110 (36 in hexadecimal) repeated b/8 times opad = 01011100 (5C in hexadecimal) repeated b/8 times Then HMAC can be expressed as follows: HMAC(K,M) = H[(K+opad)||H[(K+ ipad)||M]] In words, 1. Append zeros to the left end of K to create a b-bit string K+(e.g., if K is of length 160 bits and b= 512 then K will be appended with 44 zero bytes 0 x 00). 40 2. XOR (bitwise exclusive-OR) K+ with ipad to produce the b-bit block Si. 3. Append M to Si. 4. Apply H to the stream generated in step 3. 5. 5.XOR K+ with opad to produce the b-bit block So 6. 6.Append the hash result from step 4 to So 7. Apply H to the stream generated in step 6 and output the result. Authentication Protocols An important application area is that of mutual authentication protocols. Such protocols enable communicating parties to satisfy themselves mutually about each other's identity and to exchange session keys.  Authentication Protocols(ap1.o) - Simple authentication Protocol.  Authentication Protocols(ap2.o) - Network address(IP address)  Authentication Protocols(ap3.o) - Secret password  Authentication Protocols(ap3.1) - Encrypted Secret password  Authentication Protocols(ap4..o) – Nonce(Different password each time)  Authentication Protocols(ap5.o) – Nonce(Asymmetric key encryption. 41 Public Key Cryptography Principles Unlike symmetric key cryptography, we do not find historical use of public-key cryptography. It is a relatively new concept. Symmetric cryptography was well suited for organizations such as governments, military, and big financial corporations were involved in the classified communication. With the spread of more unsecure computer networks in last few decades, a genuine need was felt to use cryptography at larger scale. The symmetric key was found to be non-practical due to challenges it faced for key management. This gave rise to the public key cryptosystems. The process of encryption and decryption is depicted in the following illustration − The most important properties of public key encryption scheme are −  Different keys are used for encryption and decryption. This is a property which set this scheme different than symmetric encryption scheme.  Each receiver possesses a unique decryption key, generally referred to as his private key.  Receiver needs to publish an encryption key, referred to as his public key.  Some assurance of the authenticity of a public key is needed in this scheme to avoid spoofing by adversary as the receiver. Generally, this type of cryptosystem involves trusted third party which certifies that a particular public key belongs to a specific person or entity only.  Encryption algorithm is complex enough to prohibit attacker from deducing the plaintext from the ciphertext and the encryption (public) key. Though private and public keys are related mathematically, it is not be feasible to calculate the private key from the public key. In fact, intelligent part of any public-key cryptosystem is in designing a relationship between two keys. 42 A public-key encryption scheme has six ingredients Plaintext: This is the readable message or data that is fed into the algorithm as input. Encryption algorithm: The encryption algorithm performs various transformations on the plaintext. Public and private keys: This is a pair of keys that have been selected so that if one is used for encryption, the other is used for decryption. The exact transformations performed by the algorithm depend on the public or private key that is provided as input. Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertexts. Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext. RSA Algorithm This cryptosystem is one the initial system. It remains most employed cryptosystem even today. The system was invented by three scholars Ron Rivest, Adi Shamir, and Len Adleman and hence, it is termed as RSA cryptosystem. 43  We will see two aspects of the RSA cryptosystem, firstly generation of key pair and secondly encryption-decryption algorithms. Generation of RSA Key Pair Each person or a party who desires to participate in communication using encryption needs to generate a pair of keys, namely public key and private key. The process followed in the generation of keys is described below –  Generate the RSA modulus (n) o Select two large primes, p and q. o Calculate n=p*q. For strong unbreakable encryption, let n be a large number, typically a minimum of 512 bits.  Find Derived Number (e) o Number e must be greater than 1 and less than (p − 1)(q − 1). o There must be no common factor for e and (p − 1)(q − 1) except for 1. In other words two numbers e and (p – 1)(q – 1) are co prime.  Form the public key o The pair of numbers (n, e) form the RSA public key and is made public. o Interestingly, though n is part of the public key, difficulty in factorizing a large prime number ensures that attacker cannot find in finite time the two primes (p & q) used to obtain n. This is strength of RSA.  Generate the private key o Private Key d is calculated from p, q, and e. For given n and e, there is unique number d. o Number d is the inverse of e modulo (p - 1)(q – 1). This means that d is the number less than (p - 1)(q - 1) such that when multiplied by e, it is equal to 1 modulo (p - 1)(q - 1). o This relationship is written mathematically as follows − ed = 1 mod (p − 1)(q − 1) The Extended Euclidean Algorithm takes p, q, and e as input and gives d as output. Example An example of generating RSA Key pair is given below. (For ease of understanding, the primes p & q taken here are small values. Practically, these values are very high).  Let two primes be p = 7 and q = 13. Thus, modulus n = pq = 7 x 13 = 91.  Select e = 5, which is a valid choice since there is no number that is common factor of 5 and (p − 1)(q − 1) = 6 × 12 = 72, except for 1. 44   The pair of numbers (n, e) = (91, 5) forms the public key and can be made available to anyone whom we wish to be able to send us encrypted messages.  Input p = 7, q = 13, and e = 5 to the Extended Euclidean Algorithm. The output will be d = 29.  Check that the d calculated is correct by computing − de = 29 × 5 = 145 = 1 mod 72  Hence, public key is (91, 5) and private keys is (91, 29). Encryption and Decryption Once the key pair has been generated, the process of encryption and decryption are relatively straightforward and computationally easy. Interestingly, RSA does not directly operate on strings of bits as in case of symmetric key encryption. It operates on numbers modulo n. Hence, it is necessary to represent the plaintext as a series of numbers less than n. RSA Encryption  Suppose the sender wish to send some text message to someone whose public key is (n, e).  The sender then represents the plaintext as a series of numbers less than n.  To encrypt the first plaintext P, which is a number modulo n. The encryption process is simple mathematical step as C = Pe mod n  In other words, the ciphertext C is equal to the plaintext P multiplied by itself e times and then reduced modulo n. This means that C is also a number less than n.  Returning to our Key Generation example with plaintext P = 10, we get ciphertext C  C = 105 mod 91  RSA Decryption  The decryption process for RSA is also very straightforward. Suppose that the receiver of public-key pair (n, e) has received a ciphertext C.  Receiver raises C to the power of his private key d. The result modulo n will be the plaintext P. Plaintext = Cd mod n  Returning again to our numerical example, the ciphertext C = 82 would get decrypted to number 10 using private key 29, Plaintext = 8229 mod 91 = 10 45 RSA Analysis The security of RSA depends on the strengths of two separate functions. The RSA cryptosystem is most popular public-key cryptosystem strength of which is based on the practical difficulty of factoring the very large numbers.  Encryption Function − It is considered as a one-way function of converting plaintext into ciphertext and it can be reversed only with the knowledge of private key d.  Key Generation − The difficulty of determining a private key from an RSA public key is equivalent to factoring the modulus n. An attacker thus cannot use knowledge of an RSA public key to determine an RSA private key unless he can factor n. It is also a one way function, going from p & q values to modulus n is easy but reverse is not possible. The strength of RSA encryption drastically goes down against attacks if the number p and q are not large primes and/ or chosen public key e is a small number. 46 KEY MANAGEMENT One of the major roles of public-key encryption has been to address the problem of key distribution. There are actually two distinct aspects to the use of public-key cryptography in this regard: The distribution of public keys The use of public-key encryption to distribute secret keys Distribution of Public Keys Several techniques have been proposed for the distribution of public keys. Virtually all these proposals can be grouped into the following general schemes: Public announcement Publicly available directory Public-key authority Public-key certificates Public Announcement of Public Keys On the face of it, the point of public-key encryption is that the public key is public. Thus, if there is some broadly accepted public-key algorithm, such as RSA, any participant can send his or her public key to any other participant or broadcast the key to the community at large. Although this approach is convenient, it has a major weakness. Anyone can forge such a public announcement. That is, some user could pretend to be user A and send a public key to another participant or broadcast such a public key. Until such time as user A discovers the forgery and alerts other participants, the forger is able to read all encrypted messages intended for A and can use the forged keys for authentication. Publicly Available Directory A greater degree of security can be achieved by maintaining a publicly available dynamic directory of public keys. Maintenance and distribution of the public directory would have to be the responsibility of some trusted entity or organization. Such a scheme would include the following elements: 47   The authority maintains a directory with a {name, public key} entry for each participant.  Each participant registers a public key with the directory authority. R  A participant may replace the existing key with a new one at any time, either because of the desire to replace a public key that has already been used for a large amount of data, or because the corresponding private key has been compromised in some way.  Participants could also access the directory electronically. For this purpose, secure, authenticated communication from the authority to the participant is mandatory. This scheme is clearly more secure than individual public announcements but still has vulnerabilities. If an adversary succeeds in obtaining or computing the private key of the directory authority, the adversary could authoritatively pass out counterfeit public keys and subsequently impersonate any participant and eavesdrop on messages sent to any participant. Another way to achieve the same end is for the adversary to tamper with the records kept by the authority. Public-Key Authority Stronger security for public-key distribution can be achieved by providing tighter control over the distribution of public keys from the directory. The scenario assumes that a central authority maintains a dynamic directory of public keys of all participants. In addition, each participant reliably knows a public key for the authority, with only the authority knowing the corresponding private key. The following steps 1. A sends a time stamped message to the public-key authority containing a request for the current public key of B. 2. The authority responds with a message that is encrypted using the authority's private key, PRauth Thus, A is able to decrypt the message using the authority's public key. Therefore, A is assured that the message originated with the authority. The message includes the following: B's public key, PUb which A can use to encrypt messages destined for B The original request, to enable A to match this response with the corresponding earlier request and to verify that the original request was not altered before reception by 48  the authority. The original timestamp, so A can determine that this is not an old message from the authority containing a key other than B's current public key. 3. A stores B's public key and also uses it to encrypt a message to B containing an identifier of A (IDA) and a nonce (N1), which is used to identify this transaction uniquely. 4. B retrieves A's public key from the authority in the same manner as A retrieved B's public key. 5. At this point, public keys have been securely delivered to A and B, and they may begin their protected exchange. However, two additional steps are desirable: 6. B sends a message to A encrypted with PUa and containing A's nonce (N1) as well as a new nonce generated by B (N2) Because only B could have decrypted message (3), the presence of N1 in message (6) assures A that the correspondent is B. 7. A returns N2, encrypted using B's public key, to assure B that its correspondent is A. Thus, a total of seven messages are required. However, the initial four messages need be used only infrequently because both A and B can save the other's public key for future use, a technique known as caching. Periodically, a user should request fresh copies of the public keys of its correspondents to ensure currency. Public-Key Certificates The scenario of Figure 10.3 is attractive, yet it has some drawbacks. The public-key authority could be somewhat of a bottleneck in the system, for a user must appeal to the authority for a public key for every other user that it wishes to contact. As before, the directory of names and public keys maintained by the authority is vulnerable to tampering. An alternative approach, to use certificates that can be used by participants to exchange keys without contacting a public-key authority, in a way that is as reliable as if the 49 keys were obtained directly from a public-key authority. In essence, a certificate consists of a public key plus an identifier of the key owner, with the whole block signed by a trusted third party. Typically, the third party is a certificate authority, such as a government agency or a financial institution, that is trusted by the user community. A user can present his or her public key to the authority in a secure manner, and obtain a certificate. The user can then publish the certificate. Anyone needed this user's public key can obtain the certificate and verify that it is valid by way of the attached trusted signature. A participant can also convey its key information to another by transmitting its certificate. Other participants can verify that the certificate was created by the authority. We can place the following requirements on this scheme: 1. Any participant can read a certificate to determine the name and public key of the certificate's owner. 2. Any participant can verify that the certificate originated from the certificate authority and is not counterfeit. 3. Only the certificate authority can create and update certificates 4. Any participant can verify the currency of the certificate. A certificate scheme is illustrated in Figure. Each participant applies to the certificate authority, supplying a public key and requesting a certificate. Application must be in person or by some form of secure authenticated communication. For participant A, the authority provides a certificate of the form CA = E(PRauth, [T||IDA||PUa]) where PRauth is the private key used by the authority and T is a timestamp. A may then pass this certificate on to any other participant, who reads and verifies the certificate as follows: D(PUauth, CA) = D(PUauth, E(PRauth, [T||IDA||PUa])) = (T||IDA||PUa) The recipient uses the authority's public key, PUauth to decrypt the certificate. Because the certificate is readable only using the authority's public key, this verifies that the certificate came from the certificate authority. The elements IDA and PUa provide the recipient with the 50 name and public key of the certificate's holder. The timestamp T validates the currency of the certificate. The timestamp counters the following scenario. A's private key is learned by an adversary. A generates a new private/public key pair and applies to the certificate authority for a new certificate. Meanwhile, the adversary replays the old certificate to B. If B then encrypts messages using the compromised old public key, the adversary can read those messages. DIFFIE- HELLMAN KEY EXCHANGE The first published public-key algorithm appeared in the seminal paper by Diffie and Hellman that defined public-key cryptography and is generally referred to as Diffie-Hellman key exchange. The purpose of the algorithm is to enable two users to securely exchange a key that can then be used for subsequent encryption of messages. The algorithm itself is limited to the exchange of secret values.  It is not an encryption algorithm  It Exchange Secret/Symmetric key between end users  It use Asymmetric encryption 51  i. Assume XA (Private Key of user A) XA= q ii. Calculate YA(Public key of user A) YA = α XA mod q iii. Assume XB (Private Key of user A) XB= q iv. Calculate YB (Public key of user A) YB = α XB mod q v. K= (YB) XA mod q for User A vi. K= (YA) XB mod q for User B Example i. q=11 , α = 2 ii. α is a primitive root of p, that is α mod p, α2mod p,… αp- 1 mod p is 1,2,3…p-1. iii. Select XA = 8 YA = α XA mod q YA = 2 8 mod 11 YA = 3 iv. Select XB = 4 YB = α XB mod q YB = 2 4 mod 11 YB = 5 v. For User A K = (YB) XA mod q K = (5) 8mod 11 K=4 vi. For User B K = (YA) XB mod q K = (3) 4mod 11 K=4 User A and B have a same Key values. ElGamal Cryptosystem Along with RSA, there are other public-key cryptosystems proposed. Many of them are based on different versions of the Discrete Logarithm Problem. 52  ElGamal cryptosystem, called Elliptic Curve Variant, is based on the Discrete Logarithm Problem. It derives the strength from the assumption that the discrete logarithms cannot be found in practical time frame for a given number, while the inverse operation of the power can be computed efficiently. Let us go through a simple version of ElGamal that works with numbers modulo p. In the case of elliptic curve variants, it is based on quite different number systems. Generation of ElGamal Key Pair Each user of ElGamal cryptosystem generates the key pair through as follows −  Choosing a large prime p. Generally a prime number of 1024 to 2048 bits length is chosen.  Choosing a generator element g. o This number must be between 1 and p − 1, but cannot be any number. o It is a generator of the multiplicative group of integers modulo p. This means for every integer m co-prime to p, there is an integer k such that gk=a mod n. For example, 3 is generator of group 5 (Z5 = {1, 2, 3, 4}). N 3n 3n mod 5 1 3 3 2 9 4 3 27 2 4 81 1  Choosing the private key. The private key x is any number bigger than 1 and smaller than p−1.  Computing part of the public key. The value y is computed from the parameters p, g and the private key x as follows – y = gx mod p  Obtaining Public key. The ElGamal public key consists of the three parameters (p, g, y). For example, suppose that p = 17 and that g = 6 (It can be confirmed that 6 is a generator of group Z17). The private key x can be any number bigger than 1 and smaller than 71, so we choose x = 5. The value y is then computed as follows − y = 65 mod 17 = 7  Thus the private key is 62 and the public key is (17, 6, 7). 53  Encryption and Decryption The generation of an ElGamal key pair is comparatively simpler than the equivalent process for RSA. But the encryption and decryption are slightly more complex than RSA. ElGamal Encryption Suppose sender wishes to send a plaintext to someone whose ElGamal public key is (p, g, y), then −  Sender represents the plaintext as a series of numbers modulo p.  To encrypt the first plaintext P, which is represented as a number modulo p. The encryption process to obtain the ciphertext C is as follows − o Randomly generate a number k; o Compute two values C1 and C2, where − k C1 = g mod p C2 = (P*yk) mod p  Send the ciphertext C, consisting of the two separate values (C1, C2), sent together.  Referring to our ElGamal key generation example given above, the plaintext P = 13 is encrypted as follows − o Randomly generate a number, say k = 10 o Compute the two values C1 and C2, where − C1 = 610 mod 17 C2 = (13*710) mod 17 = 9  Send the ciphertext C = (C1, C2) = (15, 9). ElGamal Decryption  To decrypt the ciphertext (C1, C2) using private key x, the following two steps are taken − o Compute the modular inverse of (C1)x modulo p, which is (C1)-x , generally referred to as decryption factor. o Obtain the plaintext by using the following formula − C2 × (C1)-x mod p = Plaintext  In our example, to decrypt the ciphertext C = (C1, C2) = (15, 9) using private key x = 5, the decryption factor is 54 15-5 mod 17 = 9  Extract plaintext P = (9 × 9) mod 17 = 13. ElGamal Analysis In ElGamal system, each user has a private key x. and has three components of public key − prime modulus p, generator g, and public Y = g x mod p. The strength of the ElGamal is based on the difficulty of discrete logarithm problem. The secure key size is generally > 1024 bits. Today even 2048 bits long key are used. On the processing speed front, Elgamal is quite slow, it is used mainly for key authentication protocols. Due to higher processing efficiency, Elliptic Curve variants of ElGamal are becoming increasingly popular. DIGITAL SIGNATURE The digital signature scheme is based on public key cryptography. The model of digital signature scheme is depicted in the following illustration − The following points explain the entire process in detail −  Each person adopting this scheme has a public-private key pair.  Generally, the key pairs used for encryption/decryption and signing/verifying are different. The private key used for signing is referred to as the signature key and the public key as the verification key.  Signer feeds data to the hash function and generates hash of data.  Hash value and signature key are then fed to the signature algorithm which produces the digital signature on given hash. Signature is appended to the data and then both are sent to the verifier.  Verifier feeds the digital signature and the verification key into the verification 55  algorithm. The verification algorithm gives some value as output.  Verifier also runs same hash function on received data to generate hash value.  For verification, this hash value and output of verification algorithm are compared. Based on the comparison result, verifier decides whether the digital signature is valid.  Since digital signature is created by ‘private’ key of signer and no one else can have this key; the signer cannot repudiate signing the data in future. It should be noticed that instead of signing data directly by signing algorithm, usually a hash of data is created. Since the hash of data is a unique representation of data, it is sufficient to sign the hash in place of data. The most important reason of using hash instead of data directly for signing is efficiency of the scheme. Let us assume RSA is used as the signing algorithm. As discussed in public key encryption chapter, the encryption/signing process using RSA involves modular exponentiation. Signing large data through modular exponentiation is computationally expensive and time consuming. The hash of the data is a relatively small digest of the data, hence signing a hash is more efficient than signing the entire data. Importance of Digital Signature Out of all cryptographic primitives, the digital signature using public key cryptography is considered as very important and useful tool to achieve information security. Apart from ability to provide non-repudiation of message, the digital signature also provides message authentication and data integrity. Let us briefly see how this is achieved by the digital signature  Message authentication − When the verifier validates the digital signature using public key of a sender, he is assured that signature has been created only by sender who possess the corresponding secret private key and no one else.  Data Integrity − In case an attacker has access to the data and modifies it, the digital signature verification at receiver end fails. The hash of modified data and the output provided by the verification algorithm will not match. Hence, receiver can safely deny the message assuming that data integrity has been breached.  Non-repudiation − Since it is assumed that only the signer has the knowledge of the signature key, he can only create unique signature on a given data. Thus the receiver can present data and the digital signature to a third party as evidence if any dispute arises in the future. Key Management Key management refers to the distribution of cryptographic keys; the mechanisms used to bind an identity to a key; and the generation, maintenance, and revoking of such keys. The notation that we will use is X → Y: { Z } k 56  means that entity X sends to entity Y a message Z encrypted with the key k e.g. Alice → Bob: { “Hello World” } k means that Alice send Bob the message “Hello World” using key k. k represents the secret key for the classical (symmetrical) key encryption system. e and d represent the public and private key, respectively, for a public key (asymmetrical) encryption system. Session and Interchange Keys Def: An interchange key is a cryptographic key associated with a principal to a communication. Def: A session key is a cryptographic key associated with the communications itself talk about way to communicate different key for each communications A session key prevents forward searches.Forward Search Attack small number of plain text messages encrypt with a public key compare to sent messages know plain text message. e.g. Suppose that Alice is a client of Bob’s stock brokerage firm. Alice need to send Bob one of two messages: BUY or SELL. Cathy, the attacker, enciphers both messages with Bob’s public key. When Alice sends her message, Cathy compares it with her enciphered