Diffie hellman key exchange algorithm

The presentation include:
-Diffie hellman key exchange algorithm
-Primitive roots
-Discrete logarithm and discrete logarithm problem
-Attacks on diffie hellman and their possible solution
-Key distribution center

1. CRYPTOGRAPHY AND NETWORK SECURITY Submitted by : Sunita Kharayat DIFFIE-HELLMAN KEY EXCHANGE

2. Table of Content Diffie hellmen key exchange Introduction Founder Primitive root Discrete Logarithm Diffie Hellman Key Exchange Cryptographic Explanation The discrete Logarithmic problem Attacks on diffie hellmen Man in the middle attack Solution Key distribution center

3. DIFFIE-HELLMAN KEY EXCHANGE

4. Introduction Diffie –Hellman key exchange  is a method of securely exchanging cryptographic keys over a public channel  was one of the first   public-key protocols  as conceived by  Ralph Merkle  and named after  Whitfield Diffie  and  Martin Hellman in 1976. DH is one of the earliest practical examples of public  key exchange  implemented within the field of  cryptography . The Diffie –Hellman key exchange method allows two parties to jointly establish a  shared secret  key over an  insecure channel . This key can then be used to encrypt subsequent communications using a  symmetric key   cipher .

5. Founder Figure 1: Founder : Ralph Markle , Martin Hellman , Whitfied Diffie

6. The main idea behind the algorithm is to agree on a key that two parties can use for a symmetric encryption, in such a way that an eavesdropper cannot obtain the key . It also depend on the difficulty to compute discrete logarithms

7. Primitive root Primitive root of a prime number ‘n’ is a number ‘a’ where a <n and follows the below criteria: a i mod n   gives a unique result for every a= 1 to (n-1) and i =1,2,3…… Eg : for n=7 and a=1,2,3,4,5,6

8. Discrete Logarithm If a is a primitive root of the prime number p,then the numbers a mod p , a 2 mod p …….. a p-1 mod p Are distinct and consist of the integer from 1 to (p-1) in some permutation . Eg : for any integer b and primitive root a of prime number p , we can find unique exponent i such that b= a i   (mod p) where 0<= i <=(p-1) Exponent “ i ” is referred to as the discrete logarithm of b 12 = 3 29   (mod 17) Here for integer 12 where 1<12<17……29 is the discrete logarithm.

9. Diffie - Hellman Key Exchange Basic idea : A and B are two persons wishing to communicate. Both of them generate a random number each, say a and b respectively. Now A sends f(a) to B B sends f(b) to A . So now have A knows a and f(b) B knows b and f(a) There is another function g such that g(a,   f(b)) = g(b, f(a)). The key used by A is g(a, f(b)) B is g(b, f(a)). Both are actually same

10. A and B agrees on two large prime numbers   p  and  g .   such that g is the primitive root of p . A selects a random integer a where a <p and computes f(a)= g a  mod p (public key) B selects a random integer b where b<p and computes f(b)= g b  mod p (public key ) A sends g a  mod p  to B . B sends  g b  mod p   to A B evaluates ( g a  mod p) b   to be used as the key. A evaluates  ( g b  mod p) a  to be used as the key. So now both parties have the common number  g ab  mod p . This is the symmetric (secret communication) key used by both A and B now.   This works because though the other people know  p , g,   g a  mod p, g b  mod p   but still they cannot evaluate the key because they do not know either a or b

11. Figure 2 : Block diagram

12. Cryptographic explanation The simplest and the original implementation of the protocol uses the  multiplicative group of integers modulo   p , where  p  is  prime , and  g  is a  primitive root modulo   p . These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to  p –1 .

13. Here is an example of the protocol, and secret values in   red . Alice and Bob  publicly agree to use a modulus  p  = 23 and base  g  = 5 (which is a primitive root modulo 23). Alice chooses a secret integer   a  = 6 , then sends Bob  public key , A  =  g a  mod  p A  =  5 6  mod 23 =  8 Bob chooses a secret integer   b  = 15 , then sends Alicepublic key,   B  =  g b  mod  p B  =  5 15  mod 23 =  19 Alice computes  s  =  B a  mod  p s  =  10 6  mod 23 =  2 Bob computes  s =   A b  mod  p s  =  4 15  mod 23 =  2 Alice and Bob now share a secret (the number 18 ). that is : A b  mod  p =   g a b  mod  p = g b a  mod  p=B a  mod  p   10 6  mod 23 =  2 =   4 15  mod 23  or ( g a  mod  p) b mod p = ( g b  mod  p) a mod p Both Alice and Bob have arrived at the same values because under mod p, Only   a ,   b , and ( g a b  mod  p  =  g ba mod   p ) are kept secret. All the other values –  p ,   g ,  g a  mod  p , and  g b  mod  p  – are sent in the clear .

14. It is difficult for eve to calculate ( a,b ) using only p,g,A,B

15. The discrete logarithm problem Clearly , much larger values of a , b , and p are required. An eavesdropper cannot discover this value even if she knows p and g and can obtain each of the messages . 3 29  mod  17 =12 g a  mod  p =B Given 12 find the value of a for prime number 17 and primitive root 3 Suppose p is a prime of around 300 digits , and a and b at least 100 digits each. Discovering the shared secret given g, p , g a  mod  p and g b  mod  p would take longer than the lifetime of the universe, using the best known algorithm. This is called the discrete logarithm problem.

16. ATTACKS ON DEFFIE-HELLEMAN

17. Man In The Middle Attack We assume that there is a guy Z in between A and B. Z has the ability to capture packets and create new packets. When A sends  p , g and g a  mod p,     Z captures them and sends  p , g and g z  mod p   to B. On receiving this, B sends  p , g and g b  mod p   but again Z captures these and sends  p , g and g z  mod p   to A. So A will use the key  ( g z  mod p ) a     and B will use the key  ( g z  mod p ) b   . Both these keys are known to Z and so when a packet comes from A, Z decrypts it using A's key and encrypts it in it's own key and then sends it to B. Again when a packet comes from B, it does a similar thing before sending the packet to A. So effectively there are two keys - one operating between A and Z and the other between Z and B.

18. Block diagram

19. Solution : We use a policy that A only sends half a packet at a time . M cannot decrypt half a packet and so it is stuck . A sends the other half only when it receives a half-packet from B . M has two options when it receives half a packet : It does not send the packet to B at all and dumps it. In this case B will anyway come to know that there is some problem and so it will not send it's half-packet. It forwards the half-packet as it is to B . Now when B sends it's half-packet, A sends the remaining half. When B decrypts this entire packet it sees that the data is junk and so it comes to know that there is some problem in communication . Here we have assumed that there is some application level understanding between  A and B like the port number . If A sends a packet at port number 25 and receives a packet at port number 35, then it will come to know that there is some problem. At the very least we have ensured that M cannot read the packets though it can block the communication.

20. Continued…. There is another much simpler method of exchanging keys which we now discuss :   Key Distribution Center There is a central trusted node called the Key Distribution Center ( KDC ). Every node has a key which is shared between it and the KDC. Since no one else knows A's secret key ( K A ) KDC is sure that the message it received has come from A. We show the implementation through this diagram :

21. Figure 4: Block diagram

22. When A wants to communicate with B , it sends a message encrypted in it's key to the KDC . The KDC then sends a common key to both A and B encrypted in their respective keys . A and B can communicate safely using this key . There is a problem with this implementation also. It is prone to  replay attack . The messages are in encrypted form and hence would not make sense to an intruder but they may be replayed to the listener again and again with the listener believing that the messages are from the correct source. To prevent this, we can use: Timestamps :  which however don't generally work because of the offset in time between machines. Synchronization over the network becomes a problem. Nonce numbers:  which are like ticket numbers. B accepts a message only if it has not seen this nonce number before.

23. THANKYOU