Diffie hellman key exchange algorithm

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

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

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.

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

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

Primitive root • Primitive root of a prime number ‘n’ is a number ‘a’ where a <n and follows the below criteria: ai 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

Discrete Logarithm • If a is a primitive root of the prime number p,then the numbers ▫ a mod p , a2 mod p …….. ap-1mod 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=ai (mod p) where 0<= i <=(p-1) Exponent “i” is referred to as the discrete logarithm of b 12=329 (mod 17) Here for integer 12 where 1<12<17……29 is the discrete logarithm.

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

1. A and B agrees on two large prime numbers p and g. 2. such that g is the primitive root of p. 3. A selects a random integer a where a<p and computes f(a)= ga mod p (public key) 4. B selects a random integer b where b<p and computes f(b)=gb mod p (public key) 5. A sends ga mod p to B. 6. B sends gb mod p to A 7. B evaluates (ga mod p)b to be used as the key. 8. A evaluates (gb mod p)a to be used as the key. 9. So now both parties have the common number gab 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, ga mod p, gb mod p but still they cannot evaluate the key because they do not know either a or b

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.

• 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 = ga mod p ▫ A = 56 mod 23 = 8 • Bob chooses a secret integer b = 15, then sends Alicepublic key, B = gb mod p ▫ B = 515 mod 23 = 19 • Alice computes s = Ba mod p ▫ s = 106 mod 23 = 2 • Bob computes s = Ab mod p ▫ s = 415 mod 23 = 2 • Alice and Bob now share a secret (the number 18). • that is : Ab mod p= gab mod p= gba mod p=Ba mod p 106 mod 23 = 2 = 415 mod 23 or (ga mod p)b mod p = (gb mod p)a mod p • Both Alice and Bob have arrived at the same values because under mod p, Only a, b, and (gab mod p = gbamod p) are kept secret. All the other values – p, g, ga mod p, and gb mod p – are sent in the clear.

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

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. 329 mod 17 =12 ga 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, ga mod p and gb mod p would take longer than the lifetime of the universe, using the best known algorithm. This is called the discrete logarithm problem.

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 ga mod p, Z captures them and sends p, g and gz mod p to B. • On receiving this, B sends p, g and gb mod p but again Z captures these and sends p, g and gz mod p to A. • So A will use the key (gz mod p)a and B will use the key (gz 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.

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.

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 (KA) KDC is sure that the message it received has come from A. We show the implementation through this diagram :

• 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.

Diffie hellman key exchange algorithm

More Related Content

What's hot

Similar to Diffie hellman key exchange algorithm

Recently uploaded

In this document

Diffie hellman key exchange algorithm