Public Key Cryptography

Public Key Cryptography,Rivest, Shamir & Adleman ,Diffe-Hellman Key Exchange Algorithm,Digital Signature Standard,Euclid Algorithm,Euler Theorem,Euler Totient Function

1. Mr. Gopal Sakarkar Security Concept Part-2 Mr.Gopal Sakarkar

2. Mr. Gopal Sakarkar Public Key Cryptography It is used two keys for encryption and for decryption. a public-key, which may be known by anybody, and can be used to encrypt messages a private-key, known only to the recipient, used to decrypt messages It has six ingredient 1 Plain text 2 Encryption algorithm 3 Public and private keys 4 Ciphertext 5 Decryption algorithm

3. Mr. Gopal Sakarkar

4. Mr. Gopal Sakarkar Public-Key Characteristics Public-Key algorithms rely on two keys where: it is computationally infeasible to find decryption key knowing only algorithm & encryption key it is computationally easy to en/decrypt messages when the relevant (en/decrypt) key is known either of the two related keys can be used for encryption, with the other used for decryption (for some algorithms)

5. Mr. Gopal Sakarkar Public key Cryptosystem : Authentication and secrecy

6. Mr. Gopal Sakarkar Requirement of Public key Cryptography It is easy for party B to generate a pair of keys (public key PU b , Private key PR b). It is easy for a sender A , knowing the public key and message to be encrypt . C=E(PU b , M) It is easy for receiver B to decrypt the resulting ciphertext using the private key . M=D(PR b ,C)=D[PR b ,E(PU b ,M)] It is infeasible for an any person , to know the public key PU b to determine the private key PR b. It is infeasible for any person to know the public key PUb and a ciphertext C to recover the original message M. Two keys can be applied in either order M=DP[PU b , E(PR b ,M)] = D[PR b ,E(PU b , M)]

7. Mr. Gopal Sakarkar Exercise Explain the difference between conventional and public key encryption. What are the different requirements for public key cryptography .

8. Mr. Gopal Sakarkar Related Links http://docs.sun.com/source/816-6154-10/contents.htm

9. Mr. Gopal Sakarkar RSA Invented by R ivest , S hamir & A dleman of MIT in 1977 It is a best known & widely used public-key scheme. It is a block cipher algorithm in which palintext and ciphertext integers between 0 to n-1 for some n. A typical size for n is 1024 bits or 309 decimal digits.

10. Mr. Gopal Sakarkar RSA Algorithm

11. Mr. Gopal Sakarkar

12. Mr. Gopal Sakarkar

13. An Example Let p= 3 and q=5, n= 3 X 5 =15 Q(n)= (3-1) * (5-1) = 2 x 4= 8 Select e such that gcd (Q(n), e) =1 where, 1<e<Q(n) Say e=3 (any prime number) Calculate d , such that d e mod Q(n)=1 8k+1= 9, 17,25, 33, 41……..where k=1,2,3,4…. Now check which number is divisible by 3. 33 is divisible by 3 .So, d=33/3=11. //9 is also divisible by 3. Now k1=(3,15) and K2=(11,15) Take plan text M = 13 , where (M<n) Encryption C= 13 3 mod 15 =7 Decryption D= 7 11 mod 15 = 13 Mr. Gopal Sakarkar Video

14. Mr. Gopal Sakarkar Exercise Perform encryption and decryption using the RSA algorithm for the following 1. p=3, q=11, e=7, M=5 2. P=5,q=11, e=3 , M=9 Explain various Asymmetric Encryption Algorithms . Draw an algorithm, flowchart for implementing the RSA Algo .

15. Mr. Gopal Sakarkar Diffie –Hellman Key Exchange in 1976 It is used by two users to securely exchange a key that can be used for subsequent encryption of messages. a public-key distribution scheme cannot be used to exchange an arbitrary message rather it can establish a common key known only to the two participants value of key depends on the participants (and their private and public key information) based on mathematical principles security relies on the difficulty of computing discrete logarithms (similar to factoring) – hard

16. Mr. Gopal Sakarkar Diffe -Hellman Key Exchange Algorithm Global Public Elements q = prime number (300 decimal, i.e. 1024 bits)  = Integer User A key Generation Select private Xa , Xa < q Calculate public Ya , Ya =  Xa mod q User B Key Generation Select private Xb , Xb < q Calculate public Yb , Yb =  Xb mod q

17. Mr. Gopal Sakarkar Generation of secret key by user A K=( Y b ) X a mod q Generation of secret key by user B K=( Y a ) X b mod q Diffe-Hellman Key Exchange Algorithm Video

18. Mr. Gopal Sakarkar users Alice & Bob who wish to swap keys: agree on prime q= 353 and  = 3 select random secret keys: A chooses x A = 97 , B chooses x B = 233 compute respective public keys: y A = 3 97 mod 353 = 40 (Alice) y B = 3 233 mod 353 = 248 (Bob) compute shared session key as: K AB = y B xA mod 353 = 248 97 = 160 (Alice) K AB = y A xB mod 353 = 40 233 = 160 (Bob)

19. Mr. Gopal Sakarkar Diffie –Hellman Key Exchange

20. Exercise Mr. Gopal Sakarkar users Alice & Bob who wish to swap keys: agree on prime q=5 and  =7 select random secret keys: A chooses x A = 8, B chooses x B = 13

21. Mr. Gopal Sakarkar Exercise Using diffie - hellman key exchange techniques ,Find A’s public key Y A and B’s public key Y B . If, q=71 and  = 7 , X A =5 and X B = 12 Draw an algorithm, flowchart and write C++ program to implement Diffe -Hellman Key Exchange Algorithm

22. Mr. Gopal Sakarkar For Further Reading http://postdiluvian.org/~seven/diffie.html AES links http://www.youtube.com/watch?v=SFXYCT9-SeM (AES) http://www.youtube.com/watch?v=ySq88y0e8u4&feature=related

23. Send your all PPT, Posters, IEEE papers on KnowledgeWealth at Facebook Mr. Gopal Sakarkar

24. Mr. Gopal Sakarkar Digital Signature Encryption , message authentication and digital signatures are all tools of modern cryptography. A signature is a technique for non-repudiation based on the public key cryptography. The creator of a message can attach a code, the signature, which guarantees the source and integrity of the message.

25. Mr. Gopal Sakarkar Digital signature process

26. Mr. Gopal Sakarkar Properties of Signatures Similar to handwritten signatures, digital signatures must fulfill the following: Recipients must be able to verify them Signers must not be able to repudiate them later In addition, digital signatures cannot be constant and must be a function of the entire document it signs

27. Mr. Gopal Sakarkar Types of Signatures Direct digital signature – involves only the communicating parties Assumed that receiver knows public key of sender. Signature may be formed by (1) encrypting entire message with sender’s private key or (2) encrypting hash code of message with sender’s private key. Further encryption of entire message + signature with receiver’s public key or shared private key ensures confidentiality.

28. Mr. Gopal Sakarkar The message with sender’s private key

29. Mr. Gopal Sakarkar The hash code of message with sender’s private key

30. Mr. Gopal Sakarkar Types of Signatures Arbitrated digital signature – involves a trusted third party or arbiter Every signed message from sender, X, to receiver, Y, goes to an arbiter ( authority ), A, first. A subjects message + signature to number of tests to check origin & content A date the message and sends it to Y with indication that it has been verified to its satisfaction

31. Mr. Gopal Sakarkar

32. Mr. Gopal Sakarkar Public-key technique. User applies the Secure Hash Algorithm (SHA) to the message to produce message digest. User’s private key is applied to message digest using DSA to generate signature. Digital Signature Standard

33. Mr. Gopal Sakarkar Global Public-Key Components p A prime number of L bits where L is a multiple of 64 and 512  L  1024 q A prime divisor of( p -1) g = h ( p -1)/ q mod p , where h is any integer with 1< h < p -1, such that ( h ( p -1)/ q mod p )>1 User’s Private Key x A random or pseudorandom integer with 0< x < q User’s Public Key y = g x mod p User’s Per-Message Secret Number k A random or pseudorandom integer with 0< k < q Signing r = ( g k mod p ) mod q s = [ k -1 (H(M) = xr )] mod q Signature = ( r , s ) Verifying w = ( s ’) -1 mod q u 1 = [H(M’) w ] mod q u 2 = ( r ’) w mod q v = [( g u 1 y u 2 ) mod p ] mod q Test : v = r ’

34. Mr. Gopal Sakarkar Digital Signature Standard Exp:LIC Doc

35. Mr. Gopal Sakarkar DSA/DSS Key Generation have shared global public key values ( p,q,g ): choose a large prime p with 2 L-1 < p < 2 L where L= 512 to 1024 bits and is a multiple of 64 choose q with 2 159 < q < 2 160 such that q is a 160 bit prime divisor of (p-1) choose g = h (p-1)/q where 1<h<p-1 and h (p-1)/q mod p > 1 users choose private key & compute public key: choose x<q //Private Key compute y = g x mod p //Public Key

36. Mr. Gopal Sakarkar DSA Signature Creation to sign a message M the sender: generates a random signature key k, k<q k must be random, be destroyed after use, and never be reused then computes signature pair: r = (g k mod p)mod q s = [k -1 (H(M)+ xr)] mod q sends signature (r,s) with message M

37. Mr. Gopal Sakarkar DSA Signature Verification having received M & signature ( r,s ) to verify a signature, recipient computes: w = s -1 mod q u1= [H(M)w ]mod q u2= ( rw )mod q v = [(g u1 y u2 )mod p ]mod q if v=r then signature is verified

38. Mr. Gopal Sakarkar DSA creates a 320 bits signature with 512-1024 bit data security. smaller and faster than RSA a digital signature scheme only security depends on difficulty of computing discrete logarithms Summary

39. Number theory Mr. Gopal Sakarkar

40. Mr. Gopal Sakarkar Group a set of elements or “numbers” , denoted by {G,.} Rules: associative law: (a.b).c = a.(b.c) Closure : if a and b belong to G then a.b also in G identity e: e.a = a.e = a inverses a -1 : a.a -1 = e if commutative a.b = b.a then forms an abelian group The . i s generic can be addition, multiplication , substraction etc.

41. Mr. Gopal Sakarkar Ring a set of “numbers” denoted by {R,+, X} with two operations (addition and multiplication) which form: an abelian group with addition operation and multiplication: has closure :is a and b belong to R , then ab is also in R is associative : a( bc )=( ab )c for all a,b,c in R distributive over addition: a( b+c ) = ab + ac ( a+b )c = ac + bc if multiplication operation is commutative, it forms a commutative ring i.e. ab = ba for all a, b in R

42. Mr. Gopal Sakarkar Prime Factorisation to factor a number n is to write it as a product of other numbers: n=a x b x c note that factoring a number is relatively hard compared to multiplying the factors together to generate the number the prime factorisation of a number n is when its written as a product of primes eg . 91=7x13 ; 3600=2 4 x3 2 x5 2

43. Mr. Gopal Sakarkar Modular Arithmetic define modulo operator “a mod n” to be remainder when a is divided by n eg . 11 mod 7=4 congruent modulo Two integer a and b are said to be congruent modulo n if, a mod n = b mod n eg. 75 mod 10 = 85 mod 10

44. Mr. Gopal Sakarkar Divisors say a non-zero number b divides a if for some m have a=mb (a,b,m all integers) that is b divides into a with no remainder denote this b|a and say that b is a divisor of a eg. all of 1,2,3,4,6,8,12,24 divide 24

45. Mr. Gopal Sakarkar Modular Arithmetic Operations Properties of Modular Arithmetic (a+b) mod n = [a mod n + b mod n] mod n <proof> (a-b) mod n = [a mod n - b mod n] mod n (a X b) mod n = [a mod n X b mod n] mod n Eg. (11 + 15 ) mod 8 = [11 mod 8 + 15 mod 8] mod 8

46. Mr. Gopal Sakarkar Modulo 8 Addition Example + 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 2 3 4 5 6 7 1 3 3 4 5 6 7 1 2 4 4 5 6 7 1 2 3 5 5 6 7 1 2 3 4 6 6 7 1 2 3 4 5 7 7 1 2 3 4 5 6

47. Mr. Gopal Sakarkar Exercise 1.Draw a flowchart and an algorithm and write a C ++ program for Modulo of n Addition. 2. Proved that (a-b) mod n and (a X b) mod n .

48. Mr. Gopal Sakarkar Greatest Common Divisor (GCD) GCD (a,b) of a and b is the greatest number that divides evenly into both a and b eg GCD(60,24) = 12 The positive integer c is said to be the greatest common divisor of a and b if C is a divisor of a and of b Any divisor of a and b is a divisor of c It is denoted by gcd(a,b)= max[k, such that k/a and k/b]

49. Mr. Gopal Sakarkar Find the gcd of 36 and 15 a/b gives a remainder of r b/r gives a remainder of s r/s gives a remainder of t ... w/x gives a remainder of y x/y gives no remainder H/w gcd (25,10)

50. Mr. Gopal Sakarkar Exercise Draw a flowchart and an algorithm and write a C++ program to find the GCD of numbers.

51. Mr. Gopal Sakarkar Euclid Algorithm In mathematics , the Euclidean algorithm (also called Euclid's algorithm) is an efficient method for computing the greatest common divisor (GCD), also known as the greatest common factor (GCF) or highest common factor (HCF). It is named after the Greek mathematician Euclid (in BC 300) The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder .

52. Mr. Gopal Sakarkar Euclidean Algorithm an efficient way to find the GCD(a,b) uses theorem that: GCD(a,b) = GCD(b, a mod b) Euclidean Algorithm to compute GCD(a,b) is: EUCLID(a,b) 1. A = a; B = b 2. if B = 0 return ; A = gcd(a, b) 3. R = A mod B 4. A = B 5. B = R 6. goto 2

53. Mr. Gopal Sakarkar Euler Theorem Swiss mathematician noted both for his work in analysis and algebra, including complex numbers and logarithms, and his introduction of much of the basic notation in mathematics.

54. Mr. Gopal Sakarkar Relatively Prime Numbers Two numbers a, b are relatively prime if have no common divisors apart from 1 eg . 8 & 15 are relatively prime since factors of 8 are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only common factor.

55. Mr. Gopal Sakarkar Euler Totient Function ø(n) It is define as the number of positive integer less than n and relatively prime to n. Since a number less than or equal to and relatively prime to a given number is called a totative . A totient function can be simply defined as the number of totatives of n. For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so ø(24)=8

56. Mr. Gopal Sakarkar Euler Totient Function ø(n) Eg . Determine ø(35) Now find out list of all positive integer less than 35 that are relatively prime to it: 1,2,3,4,6,8,9,11,12,13,16,17,18,19,22, 23,24,26,27,29,31,32,33,34 Science there are 24 numbers so, ø(35)=24

57. Mr. Gopal Sakarkar Euler's Theorem Theorem : Euler’s theorem states that for every a and n ,and if they are relatively prime then, a ø (n) ≡ 1 (mod n) The theorem may be used to easily reduce large powers modulo n . consider finding the last decimal digit of 7 222 , i.e. 7 222 (mod 10). Note that 7 and 10 are relatively prime , and φ(10) = 4. So Euler's theorem yields 7 4 ≡ 1 (mod 10), and we get 7 222 ≡ 7 4x55 + 2 ≡ ( 7 4 ) 55 x7 2 ≡ 1 55 x7 2 ≡ 49 ≡ 49 (mod 10) = 9 Exp of Totient RSA

58. Mr. Gopal Sakarkar In general, when reducing a power of a modulo n (where a and n are relatively prime ), one needs to work modulo φ( n ) in the exponent of a : if x ≡ y (mod φ( n )), then a x ≡ a y (mod n ) Euler's Theorem Cont…..

59. Mr. Gopal Sakarkar Video

60. Mr. Gopal Sakarkar Story behind CRT An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had? Problems of this kind are all examples of what universally became known as the Chinese Remainder Theorem .

61. Mr. Gopal Sakarkar Chinese Remainder Theorem Find a number x such that it has remainders of 0 when divided by 2, and 3 when divided by 5. i.e. X= a mod n and X =b mod m, Where , gcd (n, m) =1 Video

62. Mr. Gopal Sakarkar used to speed up modulo computations it working modulo to product of numbers eg . mod M = m1m2.. mk Chinese Remainder Theorem lets us work in each moduli mi separately since computational cost is proportional to size, this is faster than working in the full modulus M. This can be useful when M is 150 digits or more. Chinese Remainder Theorem

63. Mr. Gopal Sakarkar CRT statement Let m1, m2, …, mk be pairwise relatively prime integers. That is, gcd (mi, mj ) = 1 for 1  i , j k. Let aiZmi for 1i k and set M=m1m2…mk. Then there exists a unique A  Zm , such that ai A mod mi for i = 1…k. then A can be computed as: Where for 1ik .

64. Mr. Gopal Sakarkar Proof: A is a solution Since for any j i Therefore,

65. Mr. Gopal Sakarkar Properties: (A+B) mod M  ((a 1 + b 1 ) mod m 1 , … , ( a k + b k )mod m k ) (A-B) mod M  ((a 1 - b 1 ) mod m 1 , … , ( a k - b k )mod m k ) (A  B) mod M  ((a 1  b 1 ) mod m 1 , … , ( a k  b k )mod m k ) If X1= Y1mod n and X2=Y2 mod n then X1+X2 = Y1+Y2 mod n and X1- X2 = Y1-Y2 mod n

66. Tutorial-1 “Study of Chinese Reminder Theorem ” Submission: submission of tutorial 1 is on and before 21/8/2013. Mr. Gopal Sakarkar

67. Mr. Gopal Sakarkar Exercise Draw a flowchart and an algorithm and write a C++ program to find out given numbers are Relatively Prime Number or not. Draw a flowchart and an algorithm and write a C++ program to implement the Euclidean Algorithm. Draw a flowchart and an algorithm and write a C++ program to find out Euler Totient Function ø(n) for given number n . Draw a flowchart and an algorithm and write a C++ program to find the last decimal digit of 7 222 using the Euler's Theorem.

68. Mr. Gopal Sakarkar Today’s Agenda Message Digests Hash Functions Message Authentication Secure Hash Function

69. Mr. Gopal Sakarkar Message digests A technique used to establish whether text sent over a network has been tampered or not. It consists of a mathematical rule which, when applied to a piece of text, generates a relatively short number, usually between 128 and 512 bits. This number is then sent with the text to a recipient who reapplies the mathematical rule to the text and compares the result with the original number. If they are the same then there is a very high probability that the message has not been tampered with during the sending process; if it does differ it is virtually certain that the message has been tampered with. It is not useful for active attack.

70. Mr. Gopal Sakarkar MD4 A one-way hash function that produces a 128-bit hash, or message digest. If as little as a single bit value in the file is modified, the MD4 checksum for the file will change. Forgery of a file in a way that will cause MD4 to generate the same result as that for the original file is considered extremely difficult. MD5 An improved, and more complex, version of MD4 circa 1992 128-bit hash "almost broken" by Hans Dobbertin circa 1995 Fully broken by collision attack Wang et. al. 2004 Data Encryption Standard (DES) Symmetric, feistel cipher Key size (in bits): 112 or 168 Time to crack (assume a machine could try 255 keys per second - NIST): 4.6 billion years Advanced Encryption Standard (AES) Symmetric, block cipher Key size (in bits): 128, 192, 256 Time to crack (assume a machine could try 255 keys per second - NIST): 149 trillion years Secure Hash Algorithm (SHA) produces a 160-bit hash, longer than MD5. The algorithm is slightly slower than MD5, but the larger message digest makes it more secure against brute-force collision and inversion attacks.

71. Mr. Gopal Sakarkar Exercise Draw an algorithm , a flowchart and write a C ++ program for MD.

72. Mr. Gopal Sakarkar For Further Reading http://www.faqs.org/rfcs/rfc1321.html http://www.java2s.com/Code/Java/Spring/MessageDigestExample.htm http://docs.sun.com/app/docs/doc/816-4863/6mb20lvls?a=view

73. Mr. Gopal Sakarkar Checksums A checksum or hash sum is a fixed-size data computed from an arbitrary block of digital data for the purpose of detecting accidental errors that may have been introduced during its transmission or storage. The integrity of the data can be checked at any later time by recomputing the checksum and comparing it with the stored one. If the checksums do not match, the data was almost certainly altered (either intentionally or unintentionally).

74. Mr. Gopal Sakarkar Checksum Applications First, checksum value can be used to check data integrity when data is sent through telecommunication networks such as Internet . Second, checksum value can be used to check data integrity of stored data to see if the data has been modified or changed in any way over time. Third, checksum values can be used to verify data burned to CDROM, CD-R (Compact Disc-Recordable), OR DVD, DVD-R.

75. Mr. Gopal Sakarkar http://www.geeksengine.com/article/checksum.html http://www.keil.com/download/docs/54.asp http://computer.howstuffworks.com/encryption7.htm http://www.accuhash.com/what-is-checksum.html For Further Reading

76. Mr. Gopal Sakarkar Message Authentication Message authentication is a mechanism or service used to verify the integrity of a message . Most common techniques for message authentication are 1.Message Authentication Code (MAC) 2. Secure Hash Function .

77. Mr. Gopal Sakarkar Message Authentication Code It is used to generate a fix –size block of data. Let A and B share a common secret key K. When A has to send to B , it calculate the MAC as a function of the message and the key : MAC= C(K,M). The message M pulse MAC are transmitted to the intended recipient. The received MAC is compared to the calculated MAC. Eg : Find out how many times r is occurred in the given message . Now , here counting a occurrence of alphabet is a function i.e C( ) and r is acting as secret key K.

78. Mr. Gopal Sakarkar

79. Mr. Gopal Sakarkar Hash functions Reduce arbitrary message to fixed size h = H(M) Usually assume that the hash function is public and not keyed Hash used to detect changes to message Can use in various ways with message Most often to create a digital signature

80. Mr. Gopal Sakarkar Hash Functions Take an input from a large domain and return an output in a smaller range. Easy to compute. Eg: Collect the alphabets , which is available at odd position in word of the message M . i.e. h = H(M)

81. Mr. Gopal Sakarkar Basic Uses of Hash Functions

82. Mr. Gopal Sakarkar Use a “Keyed Hash” 1010100101010 1010101010101 1010101000101 0101001010001 1010010101010 Alice Bob HA 100010 010101 100011 Shared Secret

83. Mr. Gopal Sakarkar Requirements for Hash Functions Can be applied to any sized message M Produces fixed-length output h Is easy to compute h=H(M) for any message M Given h is infeasible to find x s.t. H(x)=h one-way property Given x is infeasible to find y s.t. H(y)=H(x) weak collision resistance Is infeasible to find any x,y s.t. H(y)=H(x) strong collision resistance

84. Mr. Gopal Sakarkar For example, a simple hashing algorithm would be to add up all digits in a number, and take the remainder when divided by 7. Let the hashing function be f(x) f(13) = (1+3) % 7 = 4 f(26) = (2+6) % 7 = 1 f(78) = (7+8) % 7 = 1

85. Mr. Gopal Sakarkar Digital Signature

86. Mr. Gopal Sakarkar For Further Reading http://www.faqs.org/rfcs/rfc3174.html http://cboard.cprogramming.com/cplusplus-programming/110600-working-bits-sha-1-a.html http://www.codeproject.com/KB/recipes/csha1.aspx Bit-Commitment with Secure Hashes http://citeseer.nj.nec.com/halevi96practical.html SHA-1 Specification http://www.itl.nist.gov/fipspubs/fip180-1.htm MD5 Specification (rfc1321) http://andrew2.andrew.cmu.edu/rfc/rfc1321.html Keyed Hashes: HMAC http://www-cse.ucsd.edu/users/mihir/papers/hmac.html

87. Mr. Gopal Sakarkar Secure Hash Algorithm 1993 The hash function SHA-0 was issued as a federal standard by NIST 1995 SHA-1 published as the successor to SHA-0 2002 SHA-2 variants SHA-256, SHA-384, and SHA-512 published 2004 SHA-224 published * No known weaknesses have been found with the SHA-2 variants (at this time)

88. Mr. Gopal Sakarkar SHA-1, SHA-256, SHA-384, and SHA-512 All four of the algorithms are iterative, one-way hash functions process a message to produce a condensed representation called a message digest These algorithms enable the determination of a message’s integrity any change to the message will, with a very high probability, result in a different message digest This property is useful in the generation and verification of digital signatures and message authentication codes, and in the generation of random numbers (bits). Secure Hash Algorithm cont…

89. Mr. Gopal Sakarkar Flavors of SHA SHA-0 SHA-1* SHA-224* SHA-256* SHA-384* SHA-512* *FIPS-approved algorithm for generating a condensed representation of a message (message digest)

90. Mr. Gopal Sakarkar The Algorithm Each algorithm can be described in two stages: preprocessing Preprocessing involves padding a message, parsing the padded message into m-bit blocks, and setting initialization values to be used in the hash computation hash computation The hash computation generates a message schedule from the padded message and uses that schedule, along with functions, constants, and word operations to iteratively generate a series of hash values The final hash value generated by the hash computation is used to determine the message digest.

91. Mr. Gopal Sakarkar Algorithm – cont’d Step 1. Padding - padding bits to original message -to make a original message equal to a value which is 64 bits less than an exact multiple of 512. Exp. Let the length of the message is 1000 bits , add a padding of 472 bits to make the length of the message 1472 bits. i.e. when we add 64 to 1472 we got 1536 (512 X 3). -padding is always added even if message length is already 64 bits Less than a multiple of 512. Exp. If length of message is 448 bits, add a padding 512 bits to make its length 960 bits, padding is always between 1 to 512. Original Message Padding 1-512 + Original Message Padding Padding 1-512

92. Mr. Gopal Sakarkar Step 2. Appending Length now calculate the original length of message and add it to the end of the message, after padding. Exp.: let original message is 1000 bits and we add padding of 472 bits to make the length of message 64 bits less than 1536 , here the length is consider as 1000 not 1472 bits. Original Message Padding Padding 1-512 + Length Original Message Padding Padding 1-512 Length the length is expressed as a 64 bit value and these 64 bits are appending to the end of original message + padding

93. Mr. Gopal Sakarkar Step 3: Divide the Input Now divide the input message into block, each of the length 512 bits. Data to be hashed Block 1 Block 2 Block 3 Block n 512 bits 512 bits 512 bits 512 bits

94. Mr. Gopal Sakarkar Step 4: Initialize chaining variable - Now , five chaining variables A to E are initialized , each of 32 bits number. in SHA we want to produce a message digest of length 160 bits , for that we have five chaining variables(5 X 32= 160 bits.) Step 5: Copy the chaining variables. now copy the chaining variable A-E into variable a-e. The combination of a-e treated as single register for storing the temporary intermediate as well as final result. A a B b C c D d E e

95. Mr. Gopal Sakarkar Step 6: Divide a block -now divide the current block 512 bits into 16 sub blocks , each of 32 bits. Step 7: Round and Iterations SHA consists of four rounds , each round containing 20 iteration This make it total of 80 iterations Mathematical representation is: abcde= (e + Process P + S^5 (a) +W [t] + K[t]) ,a , S^30 (b) ,c,d Where, abcde= The registers Process P = The logical operation S ^t = Circular –left shift of the 32 bit sub block by t bits W[t] = A 32 bit derived from the current 32 bit sub block K[t] = one of the five additive constant

96. Mr. Gopal Sakarkar Secure Hashes Algorithm One-Way Given f(x) , hard to find x . Collision-Free Hard to find x and y so that f(x)=f(y) Hard to bias output Hard to generate a set {x i } so that we can differentiate between f({x i }) and f(U) where U is a uniformly distributed input.

97. Mr. Gopal Sakarkar Uses for SHA Message Authentication Checksums Prevent an attacker from changing messages Faster Digital Signatures Faster Bit-Commitment Schemes

98. Mr. Gopal Sakarkar Related References http://www.packetizer.com/security/sha1/ http://www.itl.nist.gov/fipspubs/fip180-1.htm ( IMP )

99. Mr. Gopal Sakarkar Tutorial 2 “Study and implementation of various Hashing functions ”-Exercise Write a comparison between MD5 and SHA-1 Explain the various authentication requirements for context communication across a network. Differentiate between Message Encryption, Message Authentication Code, and Hash Function. Explain various applications of MAC. Explain in details working of SHA 512. Submission: Submit the Tutorial-2 on and before 28/8/2013 .

100. Mr. Gopal Sakarkar Exercise Download a DES and AES encryption software http://www.progressive-coding.com/tutorial.php#aes_description For further Reading

101. Mr. Gopal Sakarkar Today’s Agenda Intrusion Intrusion Techniques Intrusion Detection Intrusion Detection Techniques

102. Mr. Gopal Sakarkar

103. Mr. Gopal Sakarkar

104. Mr. Gopal Sakarkar

105. Mr. Gopal Sakarkar Intruders Intruders: Intruder is a person whose objetive is to gain access to system or to increase the range of privilege accessible on a system either via network or local Classes of intruders: • Masquerader : An individual who is not authorized to use the computer (outsider) • Misfeasor : A legitimate user who accesses unauthorized data, programs, or resources (insider) • Clandestine user : An individual who grab supervisory control of the system and uses this control to avoid auditing and access controls or to suppress audit collection (either)

106. Mr. Gopal Sakarkar Intrusion Techniques Aim to gain access and/or increase privileges on a system Basic attack methodology target acquisition and information gathering initial access enlarge the privilege , covering tracks Key goal often is to acquire passwords So then exercise access rights of owner

107. Mr. Gopal Sakarkar Intrusion Detection System Need also to detect intrusions so can block if detected quickly act as deterrent(prevention) collect info to improve security Assume intruder will behave differently to a legitimate user but will have imperfect distinction between

108. Mr. Gopal Sakarkar

109. Mr. Gopal Sakarkar

110. Mr. Gopal Sakarkar

111. Mr. Gopal Sakarkar Approaches to Intrusion Detection Statistical anomaly detection threshold profile based Rule-based detection anomaly penetration identification

112. Mr. Gopal Sakarkar Audit Records It is a fundamental tool for intrusion detection native audit records part of all common multi-user O/S already present for use may not have info wanted in desired form detection-specific audit records created specifically to collect wanted info at cost of additional overhead on system

113. Mr. Gopal Sakarkar Statistical Anomaly Detection Threshold detection count occurrences of specific event over time if exceed reasonable value assume intrusion alone is a crude & ineffective detector Profile based characterize past behavior of users detect significant deviations from this profile usually multi-parameter

114. Mr. Gopal Sakarkar Rule-Based Intrusion Detection Observe events on system & apply rules to decide if activity is suspicious or not Rule-based anomaly detection analyze historical audit records to identify usage patterns & auto-generate rules for them then observe current behavior & match against rules to see if conforms like statistical anomaly detection does not require prior knowledge of security flaws

115. Mr. Gopal Sakarkar Rule-Based Intrusion Detection Rule-based penetration identification uses expert systems technology with rules identifying known penetration, weakness patterns, or suspicious behavior compare audit records or states against rules rules usually machine & O/S specific rules are generated by experts who interview & codify knowledge of security admins quality depends on how well this is done

116. Mr. Gopal Sakarkar Distributed Intrusion Detection Traditional focus is on single systems but typically have networked systems More effective defense has these working together to detect intrusions issues dealing with varying audit record formats integrity & confidentiality of networked data centralized or decentralized architecture

117. Mr. Gopal Sakarkar Distributed Intrusion Detection

118. Mr. Gopal Sakarkar Tutorial-3 Last date of submission : 6/09/2013 Survey of Current Network Intrusion Detection Techniques Explain various metrics useful for profile-based detection. Explain various techniques for learning others passwords. Discuss and explain the various intrusion attacks in real life world .

119. Mr. Gopal Sakarkar Computer “Viruses ” and related programs have the ability to replicate themselves on an ever increasing number of computers. They originally spread by people sharing floppy disks. Now they spread primarily over the Internet (a “Worm”). Viruses and Malicious Programs Other “ Malicious Programs ” may be installed by hand on a single machine. they may also be built into widely distributed commercial software packages. these are very hard to detect before the payload activates (Trojan Horses, Trap Doors, and Logic Bombs).

120. Mr. Gopal Sakarkar Taxanomy of Malicious Programs

121. Mr. Gopal Sakarkar Definitions Virus - code that copies itself into other programs. A “ Bacteria ” replicates until it fills all disk space, or CPU cycles. Payload - harmful things the malicious program does, after it has had time to spread. Worm - a program that replicates itself across the network (usually riding on email messages or attached documents (e.g., macro viruses). Trojan Horse - instructions in an otherwise good program that cause bad things to happen (sending your data or password to an attacker over the net). Logic Bomb - malicious code that activates on an event (e.g., date). Trap Door (or Back Door) - undocumented entry point written into code for debugging that can allow unwanted users. Easter Egg - extraneous code that does something “cool.” A way for programmers to show that they control the product.

122. Mr. Gopal Sakarkar Virus Phases Dormant phase - the virus is idle Propagation phase - the virus places an identical copy of itself into other programs Triggering phase – the virus is activated to perform the function for which it was intended Execution phase – the function is performed

123. Mr. Gopal Sakarkar A Compression Virus 1.Program P1 is infected with virus CV When this program invoke ,control passes to its virus . 2. Virus first compresses uninfected file P2 to P2’, which is shorter than original size. 3. Copy of virus is prepended to compressed program.. 4. The compress version of infected program P1’ is uncompressed.. 5 . The uncompressed original program is executed

124. Mr. Gopal Sakarkar Types of Viruses Parasitic Virus - attaches itself to executable files as part of their code. Runs whenever the host program runs. Memory-resident Virus - Lodges in main memory as part of the residual operating system. Boot Sector Virus - infects the boot sector of a disk, and spreads when the operating system boots up (original DOS viruses). Stealth Virus - explicitly designed to hide from Virus Scanning programs. Polymorphic Virus - mutates with every new host to prevent signature detection.

125. Mr. Gopal Sakarkar Antivirus Approaches 1st Generation, Scanners: searched files for any of a library of known virus “signatures.” Checked executable files for length changes. 2nd Generation, Heuristic Scanners: looks for more general signs than specific signatures (code segments common to many viruses). Checked files for checksum or hash changes. 3rd Generation, Activity Traps: stay resident in memory and look for certain patterns of software behavior (e.g., scanning files). 4th Generation, Full Featured: combine the best of the techniques above.

126. Mr. Gopal Sakarkar Advanced Antivirus Techniques

127. Mr. Gopal Sakarkar Summary Intruder’s aim to gain access and/or increase privileges on a system There are two type of detection techniques statistical anomaly detection rule-based detection Taxanomy of Malicious Programs Advanced Antivirus Techniques

128. Tutorial-4 last date of submission: 13/9/2013 Explain in detail classification of Viruses. Mr. Gopal Sakarkar

129. Mr. Gopal Sakarkar Authentication e-mail security PGP,S/MIME. Firewalls

130. Mr. Gopal Sakarkar Password file User exrygbzyf kgnosfix ggjoklbsz … … kiwifruit hash function Authentication

131. Mr. Gopal Sakarkar

132. Mr. Gopal Sakarkar Password based authentication Setup User chooses password Hash of password stored in password file Authentication User logs into system, supplies password System computes hash, compares to file Attacks Online dictionary attack Guess passwords and try to log in Offline dictionary attack Steal password file, try to find p with hash(p) in file

133. Mr. Gopal Sakarkar

134. Mr. Gopal Sakarkar Dictionary Attack – some numbers Typical password dictionary 1,000,000 entries of common passwords people's names, common pet names, and ordinary words. Suppose you generate and analyze 10 guesses per second Dictionary attack in at most 1,00,000 seconds = 28 hours, or 14 hours on average If passwords were random Assume six-character password Upper- and lowercase letters, digits, 32 punctuation characters 689,869,781,056 password combinations. Exhaustive search requires 1,093 years on average

135. Mr. Gopal Sakarkar

136. Mr. Gopal Sakarkar

137. Mr. Gopal Sakarkar

138. Mr. Gopal Sakarkar

139. Mr. Gopal Sakarkar

140. Mr. Gopal Sakarkar

141. Mr. Gopal Sakarkar Web Authentication Problems Malicious or weak-security website Phishing Common password problem Pharming – DNS compromise Malware on client machine Spyware Session hijacking, fabricated transactions Browser Server password cookie

142. Mr. Gopal Sakarkar Password Phishing Problem User cannot reliably identify fake sites Captured password can be used at target site Bank A Fake Site pwd A pwd A

143. Mr. Gopal Sakarkar Common Password Problem Phishing attack or break-in at site B reveals pwd at A Server-side solutions will not keep pwd safe Solution: Strengthen with client-side support Bank A low security site high security site pwd A pwd B = pwd A Site B

144. Mr. Gopal Sakarkar Defense: Password Hashing Generate a unique password per site HMAC fido:123 (banka.com)  Q7a+0ekEXb HMAC fido:123 (siteb.com)  OzX2+ICiqc Hashed password is not usable at any other site Protects against password phishing Protects against common password problem Bank A hash( pwd B , SiteB ) hash( pwd A , BankA ) Site B pwd A pwd B =

145. Tutorial -5 Last date of submission : 20/9/203 Explain in details working of client-server based architecture. Mr. Gopal Sakarkar

146. Mr. Gopal Sakarkar Today’s Agenda Email Overview : SMTP, POP , MIME Secure E-Mail Standard : PGP, S/MIME Firewall

147. Mr. Gopal Sakarkar

148. Mr. Gopal Sakarkar RFC 822 Published in 1982 Support for text format only. Messages are viewed as having an envelope and contents. Envelop having transmission and delivery information. Contents has the object to be delivered.

149. Mr. Gopal Sakarkar RFC 822 Mail Format A message consists of some number of header line ( the header ) followed by unrestricted text ( the body ). A blank line is used for separation. Lines no longer than 1000 char Message body - plain US-ASCII text Message header lines - plain US-ASCII text Limit on message length

150. Mr. Gopal Sakarkar RFC Example Date: Tue,25 feb 1985 13:45:97 From: [email protected] To: [email protected] Subject: A demonstration of the RFC 822 message format. This is the message body , which is delimited from the message heading by a blank line. Blank line for Separation

151. Mr. Gopal Sakarkar http://www.rfc-editor.org/rfc/rfc822.txt

152. Mr. Gopal Sakarkar MIME MIME refers to an official Internet standard that specifies how messages must be formatted so that they can be exchanged between different email systems. MIME permits the inclusion of virtually any type of file or document in an email message. Specifically, MIME messages can contain text images audio video application-specific data. spreadsheets word processing documets

153. Mr. Gopal Sakarkar MIME Features Support of character sets other than ASCII Support of non-text content in e-mail messages Support for compound documents

154. Mr. Gopal Sakarkar MIME Example From: John Doe <[email protected]> To: [email protected] Subject: Hello Word MIME-Version : 1.0 Content-Type : multipart/mixed; boundary =" XXXXboundary text" This is a multipart message in MIME format. -- XXXXboundary text  Content-Type : text/plain this is the body text -- XXXXboundary text  Content-Type: text/plain; Content-Disposition: attachment; filename ="test.txt" this is the attachment text -- XXXXboundary text--

155. Mr. Gopal Sakarkar The "MIME-Version :" header tells the receiving UA to treat this as a MIME message. The"Content -Type: “ header specifies "multipart/mixed". The message has parts separated by the string argument defined in "boundary=" The " Content-Type :" header identifies it as "text/plain", meaning US-ASCII characters are used exclusively and any UA should be able to display this body part. The "Content-Disposition: attachment " header has a parameter, "filename=", which specifies a suggested name for the file.

156. Mr. Gopal Sakarkar

157. Mr. Gopal Sakarkar SMTP (Simple Mail Transfer Protocol) is the procedure by which email data packets are transferred from one networked machine to another. SMTP defines the message format and the message transfer agent (MTA), which stores and forwards the mail. SMTP is a relatively simple, text-based protocol, where one or more recipients of a message are specified and then the message text is transferred. SMTP: Introduction

158. Mr. Gopal Sakarkar Transfer email between mail servers reliably and efficiently . In order to send email, the client sends the message to an outgoing mail server, which in turn contacts the destination mail server for delivery. For this reason, it is necessary to specify an SMTP server when configuring an email client. Purpose

159. Mr. Gopal Sakarkar SMTP uses persistent connections SMTP uses TCP port 25. SMTP requires message (header & body) to be in 7 -bit ASCII SMTP server uses CRLF.CRLF to determine end of message Unsecured against spam. Features

160. Mr. Gopal Sakarkar Mail client is configured with the name of a local mail gateway (SMTP server) Mail client does not have to know how to deliver mail to everywhere Sending E-mail using SMTP

161. Mr. Gopal Sakarkar Scenario: Alice sends message to Bob 1)Alice uses UA to compose message and “to” [email protected] 2)Alice’s UA sends message to her mail server; message placed in message queue 3)Client side of SMTP opens TCP connection with Bob’s mail server Work Flow

162. Mr. Gopal Sakarkar 4)SMTP client sends Alice’s message over the TCP connection 5)Bob’s mail server places the message in Bob’s mailbox 6)Bob invokes his user agent to read message Continued>>

163. Mr. Gopal Sakarkar Overview of SMTP Work Flow

164. Mr. Gopal Sakarkar REPLY CODES MEANING 211 System status, or system help reply 214 Help message 220 <domain> Service ready 221 <domain> Service closing transmission channel 250 Requested mail action okay, completed 354 Start mail input; end with <CRLF>.<CRLF> 421 <Domain> Service not available, closing transmission channel List of SMTP Reply Codes

165. Mr. Gopal Sakarkar REPLY CODES MEANING 450 Requested mail action not taken: mailbox unavailable 451 Requested action aborted: local error in processing 500 Syntax error, command unrecognized 501 Syntax error in parameters or arguments 503 Bad sequence of commands 550 Requested action not taken: mailbox unavailable 551 User not local; please try <forward-path> 554 Transaction failed List of SMTP Reply Codes

166. Mr. Gopal Sakarkar SMTP Procedure

167. Mr. Gopal Sakarkar This SMTP example shows how mail is sent by Smith at host Alpha.ARPA, to Jones and Green at host Beta.ARPA S: MAIL FROM: [email protected] R: 250 OK S: RCPT TO: [email protected] R: 250 OK S: RCPT TO: [email protected] R: 550 No such user here S: RCPT TO: [email protected] R: 250 OK S: DATA R: 354 Start mail input; end with <CRLF>.<CRLF> S: Blah blah blah... S: ...etc. etc. etc. S: <CRLF>.<CRLF> R: 250 OK Example of SMTP Procedure

168. Mr. Gopal Sakarkar HELLO: Sent by a client to identify itself, usually with a domain name EHLO: Enables the server to identify its support for Extended Simple Mail Transfer Protocol (ESMTP) commands MAIL FROM: Identifies the sender of the message; used in the form MAIL FROM: RCPT TO: Identifies the message recipients; used in the form RCPT TO: TURN: Allows the client and server to switch roles and send mail in the reverse direction without having to establish a new connection Basic Commands

169. Mr. Gopal Sakarkar ATRN: The ATRN (Authenticated TURN) command optionally takes one or more domains as a parameter. The ATRN command must be rejected if the session has not been authenticated DATA: Sent by a client to initiate the transfer of message content RSET: Nullifies the entire message transaction and resets the buffer VRFY: Verifies that a mailbox is available for message delivery HELP: Returns a list of commands that are supported by the SMTP service QUIT: Terminates the session Continued>>

170. Mr. Gopal Sakarkar

171. Mr. Gopal Sakarkar

172. Mr. Gopal Sakarkar Simple Mail Transport Protocol (SMTP) is the network protocol used to send email across the Internet. SMTP provides reliability as it uses TCP connection. Current research focuses on the security issues of SMTP. Summary

173. Mr. Gopal Sakarkar Tutorial –6 last date of submission : 27/9/2013 Briefly explain the POP, IMAP protocols. What are the advantages and disadvantages of SMTP. List and explain the various applications of SMTP.

174. Mr. Gopal Sakarkar The first version of PGP was programmed in 1991 by Phil R. Zimmerman, who later founded PGP Security Consulting. PGP is one of the most popular encryption and authentication algorithm world-wide. PGP is more widely used in electronic mail security than any other areas. Phil R. Zimmerman Pretty Good Privacy (PGP)

175. Mr. Gopal Sakarkar Pretty Good Privacy (PGP) "If all the personal computers in the world - 260 million - were put to work on a single PGP-encrypted message, it would still take an estimated 12 million times the age of the universe, on average, to break a single message.”   - Deputy Director William Crowell National Security Agency 3/20/1997

176. Mr. Gopal Sakarkar Notation K s = session key used in symmetric encryption scheme PR a = Private key of user A. PU a = public key of user A. EP = public key encryption DP = public key decryption EC =symmetric encryption DC = symmetric decryption

177. Mr. Gopal Sakarkar Notation cont… H = hash function || = concatenation Z = compression using ZIP algorithm R64 = conversion to radix 64 ASCII format

178. Mr. Gopal Sakarkar PGP Working PGP offers 5 services: Authentication Confidentiality Compression E-mail compatibility Segmentation

179. Mr. Gopal Sakarkar PGP Authentication This is a digital signature scheme with hashing. Alice has (private/public) key pair (Ad/ Ae ) and she wants to send a digitally signed message m to Bob. Alice hashes the message using SHA-1 to obtain SHA(m). Now the original message m is compressed to obtain M=ZIP(m) Alice generates a session key k and encrypts the compressed message and the signature using the session key C= sk.encrypt k ( M,c ) 4. The session key is encrypted using Bob ’ s public key as before.

180. Mr. Gopal Sakarkar Alice encrypts the hash using her private key Ad to obtain ciphertext c given by c= pk.encrypt Ad (SHA(m)) Alice sends Bob the pair ( m,c ) Bob receives ( m,c ) and decrypts c using Alice's public key Ae to obtain signature s s= pk.decrypt Ae (c)

181. Mr. Gopal Sakarkar He computes the hash of m using SHA-1 and if this hash value is equal to s then the message is authenticated. Bob is sure that the message is correct and that is does come from Alice. Furthermore Alice cannot later deny sending the message since only Alice has access to her private key Ad which works in conjunction with the public key Ae .

182. Mr. Gopal Sakarkar Message authentication based on digital signatures supported algorithms: RSA/SHA and DSS/SHA hash enc hash dec compare accept / reject m h s K snd -1 K snd m h s h sender receiver

183. Mr. Gopal Sakarkar PGP Confidentiality Alice wishes to send Bob a confidential message m. Alice generates a random session key k for a symmetric cryptosystem. Alice encrypts k using Bob ’ s public key Be to get k ’ = pk.encrypt Be (k) Alice encrypts the message m with the session key k to get ciphertext c c= sk.encrypt k (m) Alice sends Bob the values ( k ’ ,c ) Bob receives the values ( k ’ ,c ) and decrypts k ’ using his private key B d to obtain k k= pk.decrypt Bd (k ’ )

184. Mr. Gopal Sakarkar Bob uses the session key k to decrypt the ciphertext c and recover the message m m= sk.decrypt k (c) Public and symmetric key cryptosystems are combined in this way to provide security for key exchange and then efficiency for encryption. The session key k is used only to encrypt message m and is not stored for any length of time.

185. Mr. Gopal Sakarkar PGP Authentication and Confidentiality (at the same time) The schemes for authentication and confidentiality can be combined so that Alice can sign a confidential message which is encrypted before transmission. The steps required are as follows: Alice generates a signature c for her message m as in the Authentication scheme c= pk.encrypt Ad (SHA(m)) Alice generates a random session key k and encrypts the message m and the signature c using a symmetric cryptosystem to obtain ciphertext C C= sk.encrypt k ( m,c ) She encrypts the session key k using Bob ’ s public key k ’ = pk.encrypt Be (k) Alice sends Bob the values ( k ’ ,C )

186. Mr. Gopal Sakarkar Bob recieves k ’ and C and decrypts k ’ using his private key Bd to obtain the session key k k= pk.decrypt Bd (k ’ ) Bob decrypts the ciphertext C using the session key k to obtain m and c ( m,c ) = sk.decrypt k (C) Bob now has the message m. In order to authenticate it he uses Alice ’ s public key Ae to decrypt the signature c and hashes the message m using SHA-1. If SHA(m) = pk.decrypt Ae (c) Then the message is authenticated.

187. Mr. Gopal Sakarkar Working flow of PGP

188. Mr. Gopal Sakarkar