Question

Diffie-Hellman Key Exchange: Alice and Bob wants to agree on a key. First, both agree on p = 23 and g = 5 which is public. Alice chooses her secret key xA = 8 and Bob xB = 14.

(a) What will be the shared secret key?

(b) DH Key exchange is vulnerable to the following attack. Adversary sits between Alice and Bob, intercepting all messages. Alice and Bob thinks they talk to each other while in fact both talking to the adversary. Draw the scenario of the attack and find out the final shared key(s).

Answer 1

What is Diffie-Hellman Key Exchange:

• The Diffie-Hellman key exchange was the first widely used method of safely developing and exchanging keys over an insecure channel.
• The most common solution would be to encrypt the message with a code. The easiest way is to prearrange whichever type of code and key you plan on using beforehand, or to do it over a safe communication channel.
• Let’s say that you are a particularly bad spy, and you and your headquarters decide to use a weak shift-cipher to encode your messages. In this code, every “a” becomes “b”, every “b” becomes “c”, every “c” becomes “d”, and so on, all the way up to the “z” becoming an “a”.
• Under this shift cipher, the message “Let’s get dinner” becomes “Mfu’t hfu ejoofs”. Thankfully, in our hypothetical situation, your adversaries are just as incompetent as you are and are unable to crack such a simple code, which keeps them from accessing the contents of the message.
• The main purpose of the Diffie-Hellman key exchange is to securely develop shared secrets that can be used to derive keys. These keys can then be used with symmetric-key algorithms to transmit information in a protected manner. Symmetric algorithms tend to be used to encrypt the bulk of the data because they are more efficient than public key algorithms.
• The Diffie-Hellman key exchange is frequently implemented in security protocols such as TLS, IPsec, SSH, PGP, and many others. This makes it an integral part of our secure communications.

How does the Diffie-Hellman key exchange work?

Refer the following diagram for the process:

Alice Bob Common paint Secret colours Public transport 10.00 0.00 (assume that mixture separation is expensive) + Secret colours = Common secret

C++ program to demonstrate the Diffie-Hellman Key Exchange Algorithm:

#include <iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

/* This program calculates the Key for two persons using the Diffie-Hellman Key exchange algorithm */
// Power function to return value of a ^ b mod P
long long int power(long long int a, long long int b, long long int P)
{
if (b == 1)
return a;
else
return (((long long int)pow(a, b)) % P);
}
  
//Main program
int main()
{
long long int P, G, x, a, y, b, ka, kb;
// Both the persons will be agreed upon the public keys G and P
P = 23;
// A prime number P is taken
printf("The value of P : %lld\n", P);
  
G = 5;
// A primitve root for P, G is taken
printf("The value of G : %lld\n\n", G);
  
// Alice will choose the private key a
a = 8;
// a is the chosen private key
printf("The private key a for Alice : %lld\n", a);
x = power(G, a, P);
// gets the generated key
  
// Bob will choose the private key b
b = 14;
// b is the chosen private key
printf("The private key b for Bob : %lld\n\n", b);
y = power(G, b, P);
// gets the generated key
  
// Generating the secret key after the exchange of keys
ka = power(y, a, P);
// Secret key for Alice
kb = power(x, b, P);
// Secret key for Bob
  
printf("Secret key for the Alice is : %lld\n", ka);
printf("Secret Key for the Bob is : %lld\n", kb);
  
return 0;
}

Output for the program:

Online C++ Compiler - online ed X + -ox 0 0 f = c onlinegdb.com/online_C++_compiler Run $ Debug Stop Share Save {} Beautify Language C++ OnlineGDB beta main.cpp online compiler and debugger for c/c++ x = power(G, a, P); // gets the generated key IDE My Projects // Bob will choose the private key b b = 14; // bis the chosen private key printf("The private key b for Bob : %lld\n\n", b); y = power(G, b, P); // gets the generated key Learn Programming Programming Questions Jobs new Sign Up Login fy + 24.4K // Generating the secret key after the exchange of keys ka = power(y, a, P); // Secret key for Alice kb = power(x, b, P); 1 Carnet bou fan Bob input The value of P : 23 The value of G: 5 + 24.4K The private key a for Alice : 8 The private key b for Bob : 14 Sustain Podcast #27 Creating Dracula PRO, clipboard.js, and more! ads served ethically Secret key for the Alice is : 2 Secret Key for the Bob is : 2 ... Program finished with exit code o Press ENTER to exit console. About - FAQ - Blog – Terms of Use . Contact Us • GDB Tutorial - Credits . Privacy © 2016-2020 GDB Online 4:06 PM 'e ex 90 ^ 1» ? 3/9/2020 F,

Diagram for attack scenario i.e. MAN IN THE MIDDLE ATTACK:

Alice Mallory) Bob ----- ¡A= g amod pi 12 = g ?mod pa B = g bmod p! z = g ?mod p! --- --- Ka= Zºmod p K = Amod p Ko=Bmod p K = Z'mod p

Step by step algorithm (Refer the attached notes for refrence):

ALICE BOB Public keys available = P, G Public keys available = P,G Private key selected = a Private key selected = b Key generated = Key generated = X=G2 mod P Y=Gb mod P Exchange of generated keys takes place Key received = Y Key received = X Generated secret key = Generated secret key = Ka= Ya mod P Kv=Xb mod P It can be shown that Ka = Kb

G STEPS : 1. Public keys available = P p=23 G=5 2. Private keys selected Alice Bob a = 8 b = 14 3. Key generated X = Ga mod P and Y = Go mod p X = 58 mod 23 y=514 mod 23 = 390625 mod 23 = 16 - 6103515625 mod 23 -13 4. keys Exchange of generated takes place

Key received by Alice y i.e. 13 by Bob =* i.e. 16 6. Generated secret taey: Alice - Ka = ya mod p ko and Bob - Kb = xb mod p Ka: 138 mod 23 - 2 Kb = 16 mod 23 = 2 7. Ka = Kb