Meessage authentication and hash functions.pptx

Message Authentication and Hash Functions. This presentation shows how to authenticate a message to have a privacy.

1. Message Authentication and Hash Functions

2. O u t l i n e A u t h e n t i c a t i o n R e q u i r e m e n t , F un c t i on s , M e ss a g e A u t h e n t i c a t i o n C od e , H a s h F un c t i on s , S e c u r i t y O f H a s h F un c t i on s A n d M a c s M D 5 M e ss a g e D i g e s t A l g o r i t h m , S e c u r e H a s h A l g o r i t h m Ripemd-160 Hmac 2

3. Authentication Requirements Disclosure: Release of message contents to any person or process not po ss e ss i n g t h e a pp r op r i a t e c r y p t o g r a p h i c k e y . 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 b e t w ee n p a r t i e s c ou l d b e d e t e r m i n e d . Masquerade: Insertion of messages into the network from a fraudulent source. This includes the creation of messages by an opponent that are supposed to come from an authorized entity. Also included are fraudulent acknowledgments of message receipt or nonreceipt by someone other than the message recipient. 3

4. C o n t d … Content modification: Changes to the contents of a message, including insertion, deletion, transposition, and modification. Sequence modification: Any modification to a sequence of messages between parties, including insertion, deletion, and reordering. 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. 4

5. C o n t d … S o u r ce r e p u d i a t i o n : D e n i a l o f tr a n s m i s s i on o f m e ss a g e b y source. Destination repudiation: Denial of receipt of message by destination. 5

6. Message Authentication Function m e ss a g e a u t h e n t i c a t i on i s c on c e r n e d w i t h : p r o t e c t i n g t h e i n t e g r i t y o f a m e ss a g e v a l i d a t i n g i d e n t i t y o f o r i g i n a t o r non-repudiation of origin (dispute resolution) t h r e e a l t e r n a t i v e f un c t i on s u s e d : m e ss a g e e n c r y p t i on m e ss a g e a u t h e n t i c a t i on c od e ( M A C ) h a s h f un c t i on 6

7. Message Encryption message encryption by itself also provides a measure of authentication if symmetric encryption is used then: r e c e i v e r k n o w s e nd e r m u s t h a v e c r e a t e d i t since only sender and receiver now key used S o , c on t e n t c a nno t o f b ee n a l t e r e d Provides both: sender authentication and message authenticity. 7

8. Message Encryption i f pu b l i c - k e y e n c r y p t i o n i s u s e d : encryption provides no confidence of sender s i n c e a n y on e po t e n t i a l l y k n o w s p u b l i c - k e y h o w e v e r i f sender signs message using his private-key t h e n e n c r y p t s w i t h r e c i p i e n t s p u b l i c k e y have both secrecy and authentication but at cost of two public-key uses on message 8

9. Message Authentication Code (MAC) a s m a l l f i x e d - s i z e d b l oc k o f d a t a : depends on both message and a secret key like encryption though need not be reversible a pp e nd e d t o m e ss a g e a s a s ig n a t u r e receiver performs same computation on message and checks it m a t c h e s t h e M A C provides assurance that message is unaltered and comes from sender 10

10. Message Authentication Code 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: MAC = C(K, M), where M= input message C= MAC function K= shared secret key MAC= message authentication code 11

11. Message Authentication Codes M A C p r o v i d e s a u t h e n t i c a t i on M e ss a g e c a n b e e n c r y p t e d f o r s e c r e c y g e n e r a l l y u s e s e p a r a t e k e y s f o r e a c h can compute MAC either before or after encryption i s g e n e r a l l y r e g a r d e d a s b e tt e r don e b e f o r e w h y u s e a M A C ? s o m e t i m e s on l y a u t h e n t i c a t i on i s n ee d e d sometimes need authentication to persist longer than the encryption 12

12. Mac Encryption The receiver is assured that the message is from the alleged sender. Because no one else knows the secret key, no one else c ou l d p r e p a r e a m e ss a g e w i t h a p r op e r M A C . 13

13. MAC Properties a M A C i s a c r y p t o g r a p h i c c h e c k s u m MAC = C K (M) C i s a f un c t i on c ond e n s e s a v a r i a b le - le n g t h m e ss a g e M u s i n g a s e c r e t k e y K t o a f i x e d - s i z e d a u t h e n t i c a t o r m a n y - t o - on e f un c t i o n po t e n t i a l l y m a n y m e ss a g e s h a v e s a m e M A C but finding these needs to be very difficult 14

14. Requirements for MACs M A C n ee d s t o s a t i s f y t h e f o ll o w i n g : k n o w i n g a m e ss a g e a nd M A C , i s i n f e a s i b l e t o f i nd a n o t h e r m e ss a g e w i t h s a m e M A C M A C s s h ou l d b e un i f o r ml y d i s t r i b u t e d MAC should depend equally on all bits of the message 15

15. Hash Functions A h a s h f un c t i on i s l i k e a M A C c ond e n s e s a r b i t r a r y m e ss a g e t o f i x e d s i z e h = H(M) u s u a l l y a ss u m e t h a t t h e h a s h f un c t i on i s pu b l i c a nd no t keyed - no t e t h a t a M A C i s k e y e d h a s h u s e d t o d e t e c t c h a n g e s t o m e ss a g e can use in various ways with message m o s t o f t e n t o c r e a t e a d i g i t a l s i g n a t u r e 16

16. Hash Functions & Digital Signatures 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. 17

17. Requirements for Hash Functions c a n b e a pp l i e d t o a n y s i z e m e ss a g e M produces a fixed-length output h i s e a s y t o c o m pu t e h=H(M) f o r a n y m e ss a g e M g i v e n h i s i n f e a s i b l e t o f i nd x s . t . H(x)=h g i v e n x i s i n f e a s i b l e t o f i nd y s . t . H(y)=H(x) i s i n f e a s i b l e t o f i nd a n y x,y s . t . H(y)=H(x) 18

18. Simple Hash Functions a r e s e v e r a l p r opo s a l s f o r s i m p l e f un c t i on s b a s e d o n X O R o f m e ss a g e b l oc k s -divide the message into equal size blocks - p e r f o r m X O R op e r a t i o n b l oc k b y b l oc k - f i n a l ou t pu t i s t h e h a s h no t v e r y s e c u r e n ee d a s t r on g e r c r y p t o g r a p h i c f un c t i o n 19

19. Security of Hash Functions and Macs A tt a c k s o n h a s h f un c t i on s a n d M A C s i n t o t w o c a t e g o r i e s : Brute-force attacks Cryptanalysis. 20

20. Brute - Force Attacks Hash Functions: In hash functions there are three desirable properties One-way: For any given code h, it is computationally infeasible to f i nd x s u c h t h a t H ( x ) = h . W e a k c o lli s i o n r e s i s t a n ce : F o r a n y g i v e n b l o c k x , i t i s computationally infeasible to find y≠x with H(y) = H(x). S t r o n g c o lli s i o n r e s i s t a n ce : I t i s c o m pu t a t i on a l l y i n f e a s i b l e t o f i nd a n y p a i r ( x , y ) s u c h t h a t H ( x ) = H ( y ) . For a hash code of length n, the level of effort required, as we have seen i s p r opo r t i on a l t o t h e f o ll o w i n g : 21

21. C o n t d … M e ss ag e A u t h e n t i c a t i o n C o d e s A brute-force attack on a MAC is a more difficult undertaking because it requires known message-MAC pairs. Let us see why this is so. To attack a hash code, we can proceed in the following way. Given a fixed message x with n-bit hash code h = H(x), a brute- force method of finding a collision is to pick a random bit string y and check if H(y) = H(x). The attacker can do this repeatedly off line. Whether an off-line attack can be used on a MAC algorithm depends on the relative size of the key and the MAC. 22

22. C o n t d … If an attacker can determine the MAC key, then it is possible to g e n e r a t e a v a l i d M A C v a l u e f o r a n y i npu t x . Suppose the key size is k bits and that the attacker has one known text-MAC pair. Then the attacker can compute the n-bit MAC on the known text for all possible keys. At least one key is guaranteed to produce the correct MAC, namely, the valid key that was initially used to produce the known text-MAC pair. This phase of the attack takes a level of effort proportional to 2 k . 23

23. Cryptanalysis As with encryption algorithms, cryptanalytic attacks on hash functions and MAC algorithms seek to exploit some property of the algorithm to perform some attack other than an exhaustive search. The way to measure the resistance of a hash or MAC algorithm to cryptanalysis is to compare its strength to the effort required for a brute-force attack. That is, an ideal hash or MAC algorithm will require a cryptanalytic effort greater than or equal to the brute-force effort. 24

24. C r y p t a n al y s i s Hash Functions The hash function takes an input message and partitions it into L fixed-sized blocks of b bits each. If necessary, the final block is padded to b bits. The final block also includes the value of the total length of the input to the hash function. The inclusion of the length m a k e s t h e j o b o f t h e oppon e n t m o r e d i ff i c u l t . M e ss ag e A u t h e n t i c a t i o n C o d e s There is much more variety in the structure of MACs than in hash functions, so it is difficult to generalize about the cryptanalysis of MACs. Further, far less work has been done on developing such attacks. 25

25. Message Digests(Hash) A message digest is a fingerprint or the summary of a m e ss a g e . ( S a m e a s L R C a n d C R C ) It is used to verify integrity of the data (To ensure that m e ss a g e h a s no t b ee n t a m p e r e d ) . E x . L R C - p a r i t y c h e c k i n g 26

26. Idea of a Message Digest E x : C a l c u l a t e t h e m e ss a g e d i g e s t o f nu m b e r 739174 3 Multiply each digit in the number with the next digit (excluding if it is 0) and disregarding the first digit of the m u l t i p l i c a t i o n op e r a t i on , i t t h e r e s u l t i s t w o - d i g i t nu m b e r . 27

27. Calculate MD for 7391743 M u lt ip l y 7 b y 3 - 21 D isc a rd fi r st di g it - 1 M u lt ip l y 1 b y 9 - 9 M u lt ip l y 9 b y 1 - 9 M u lt ip l y 9 b y 7 - 63 D isc a rd fi r st di g it - 3 M u lt ip l y 3 b y 4 - 12 D isc a rd fi r st di g it - 2 M u lt ip l y 2 b y 3 - 6 28 Message digest is 6

28. MD5 (Message Digest 5) MD5 is a message digest algorithm developed by Ron Rivest. MD5 algorithm can be used as a digital signature mechanism. 29

29. Description of the MD5 Algorithm Takes as input a message of arbitrary length and produces as output a 128 bit “fingerprint” or “message digest” of the input. It it is computationally infeasible to produce two messages h a v i n g t h e s a m e m e ss a g e d i g e s t . Intended where a large file must be “compressed” in a secure manner before being encrypted with a private key under a pu b l i c - k e y c r y p t o s y s t e m s uc h a s P G P . 30

30. MD5 Algorithm S uppo s e a b - b i t m e ss a g e a s i npu t , a n d t h a t w e n ee d t o f i n d i t s m e ss a g e d i g e s t . S t e p - 1 P a dd i n g S t e p - 2 A pp e n d l e n g t h S t e p - 3 D i v i d e t h e i npu t i n t o 512 - b i t b l oc k s . S t e p - 4 I n i t i a l i z e c h a i n i n g v a r i a b l e s ( 4 v a r i a b l e s ) S t e p - 5 P r o c e ss b l oc k s 31

31. S t e p - 1 M D 5 i s t o a d d p a dd i n g b i t s t o t h e o r i g i n a l m e ss a g e . The aim of this step is make length of the original message equal to a value, which is 64 bits less than an exact multiple o f 512 . E x : 100 b i t s o f m e ss a g e ( 1000 + 472 + 64 ) T h e p a dd i n g c on s i s t s o f a s i n g l e “ 1 ” b i t i s a pp e nd e d t o t h e m e ss a g e , a n d t h e n “ ” b i t s . 32

32. Step 2 – append length: A 64 bit representation of b is appended to the result of the p r e v i ou s s t e p . The resulting message has a length that is an exact multiple of 51 2 b i t s 33

33. Step-3 Divide the input into 512-bit blocks Data to be hashed (Digested) 1536 bits 51 2 b i t s 51 2 b i t s 51 2 b i t s 34

34. Step-4 Initialize chaining variables A four-word buffer (A,B,C,D) is used to compute the m e ss a g e d i g e s t . H e r e e a c h o f A , B , C , D , i s a 3 2 b i t r e g i s t e r . 35

35. Step-5 Process blocks – C o p y t h e f ou r v a r i a b l e s ( 32* 4 = 128 ) – D i v i d e t h e 512 - b i t b l oc k i n t o 1 6 s u b - b l oc k s . 51 2 b i t s 5 . 3 – P r o c e ss e a c h b l oc k w i t h A , B , C , D . 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 b i t s b i t s b i t s b i t s b i t s b i t s b i t s b i t s b i t s b i t s b i t s b i t s b i t s b i t s b i t s b i t s 36

36. 5.3 - Process each block with A, B, C, D. 37

37. Secure Hash Algorithm (SHA) S H A - 1 p r odu c e s a h a s h v a l u e o f 16 b i t s . S H A i s d e s i g n e d t o b e c o m pu t a t i on a l l y i n f e a s i b l e t o : O b t a i n t h e o r i g i n a l m e ss a g e Find two message producing the same MD. 38

38. Types(Versions) of SHA 39

39. Algorithm S t e p - 1 P a dd i n g S t e p - 2 A pp e n d l e n g t h S t e p - 3 D i v i d e t h e i npu t i n t o 512 - b i t b l oc k s . Step-4 Initialize chaining variables (5 varibles) S t e p - 5 P r o c e ss b l oc k s 40

40. 5.3- Process each block with A, B, C, D, E. 41

41. Comparison of MD5 & SHA-1 Points of D is cu ssio n MD5 SHA-1 M D le n gt h in bi t s 128 160 A tta c k t r y t o find MD 2 128 2 160 A tta c k t r y t o find t w o m e ss age s p r oducing s a me m e ss ag e di ge st 2 64 2 80 Speed Faster Slower 42

42. RACE Integrity Primitives Evaluation Message Digest (RIPEMD-160) RIPEMD is a cryptographic hash based upon MD4. It's been shown to have weaknesses and has been replaced by R I P E M D - 1 2 8 a n d R I P M D - 160 . T h e s e a r e c r y p t o g r a p h i c h a s h functions designed by Hans Dobbertin, Antoon B o ss e la e r s , a n d B a r t P r e n ee l . RIPEMD-160 produces a hash of the same length as SHA1 but is slightly slower. RIPEMD-128 has been designed as a drop-in replacement for MD4/MD5 whilst avoiding some of the weaknesses shown for these two algorithms. It is about h a l f t h e s p ee d o f M D 5 . 43

43. HMAC(Hash-Based MAC) HMAC has been chosen as a security implementation for Internet Protocol (IP) and Secure Socket Layer(SSL), widely used in internet. The fundamental idea of HMAC is to reuse the existing MD5 or SHA-1. 44

44. O r i g i n al message Existing MD5 or SHA-1 M D E n c r y p t HMA C K

45. How HMAC works? M D - M e ss a g e D i g e s t / H a s h f un c t i o n M – I npu t m e ss a g e i p a d - A s t r i n g 0011011 r e p e a t e d b / 8 t i m e s op q d - A s t r i n g 0101101 r e p e a t e d b / 8 t i m e s 46

46. How HMAC works? S t e p - 1 M a k e t h e le n g t h o f K e q u a l t o b L e n g t h K < b ( A pp e nd – le f t s i d e ) L e n g t h K = b ( S t e p - 2 ) L e n g t h K > b ( H a s h K r e du c e i t s le n g t h t o b ) S t e p - 2 X O R K w i t h i p a d t o p r odu c e S 1 S t e p - 3 A pp e nd M t o S 1 S t e p - 4 M e ss a g e D i g e s t a l g o r i t h m S t e p - 5 X O R K w i t h op a d t o p r odu c e S 2 S t e p - 6 A pp e nd H t o S 2 M e ss a g e D i g e s t A l g o r i t h m 47