Diffie-Hellmann key exchange in D-BUS

Introduction

A and B want to communicate sensitive data between them securely, both of them need to have a key to be used in the encryption/decryption algorithm that they want to implement. A says, ok i can generate a random number send it to B and we both use this key for encryption/decryption, but B says, if the message containing the key gets intercepted by C, then C can decrypt all the messages going between A and B.

B proposes to use Diffie-Hellmann key exchange, the idea is that A and B communicate some data between them, this data is enough only for A and B to generate exactly the same key, but if C intercept this data then it is very hard to calculate the key.

Diffie-Hellmann Key Exchange Protocol

p is a prime number in
g is a number in , called generator.

The idea of the protocol is the following:
x [p] means a class of the element in

Both A and B know g and p.

If A has then the key is , same for B, having , then:

  • A generates a random number x and calculate , A needs from B, y generated by B.
  • B generates a random number y and calculate , B needs from A, x generated by A.
  • A sends to B
  • B sends to A
  • A receives from B and calculates 
  • B receives from A and calculates 

Then is the key that both can use to encrypt/decrypt messages, let’s see what is the position of C here, if C intercepts all the messages going between A and B then C has g, p, and   , from these information C cannot calculate  easily, actually there is no fast way for C to calculate the key (in addition we don’t know how to proof that there is no one).

The only one solution for C is to guess the key, having to loop over all possible values, for A and B this means choosing a big prime number p+a big generated numbers x and y, for a 128 bits for p and 100 bits for x and y, C has to spend a lot of time trying guess the key, even on modern computers, in addition, C has to know the encryption/decryption algorithm that both A and B are using.

C code, D-Bus example

Let’s implement the Diffie-Hellmann key exchange in practice, for this we need to write two applications and then to securely communicate data between them, so we need to connect the two applications, best is to the use D-Bus, the widely used IPC (inter process communication), refer to this this post for more information.

We were speaking above about a prime numbers bigger than 128 bits, we know that we can maximum fit 32 (or 64) bits integer in a 32 (or 64) bits processor, most of the processor these days are or 32 or 64 bits, this range is no sufficient for us, specially if we are going one day to be in need of more than 128 bits prime number, say 256, or even more…, so we need arithmetics without limitations, here comes the GNU Multiple Precision Arithmetic Library as the fastest big number arithmetic library on the planet!

GMP basics

For readers that are not familiar with the the GNU Multiple Precision Arithmetic Library, here are the basic calls that we are going to use.

Any big num variable should be initialized and cleared after usage.

mpz_t var;
mpz_init (var);
/*do something with it*/
mpz_clear (var);

You can assign big number by setting a string to an mpz_t variable.

mpz_set_str (va, "38056780635923065837528533360", 10); /* base 10, use 2 for binaries*/

You can also use mpz_init_set_str and omit the mpz_init usage.

Modulo power e.g 

mpz_powm (res, g, x, p);

This library is featureful, it has function calls for all the big-num arithmetic operations, see GNU Multiple Precision Arithmetic Library Documentation

A application 

#include <stdio.h>
#include <stdlib.h>
#include <dbus/dbus-glib-lowlevel.h>
#include <gmp.h>
 
#define PRIME_SIZE 128
 
typedef struct 
{
    DBusConnection *bus;
    GMainLoop *loop;
 
    mpz_t g;
    mpz_t x;
    mpz_t g_x;
    mpz_t g_y;
    mpz_t g_y_x;
    mpz_t prime;
    mpz_t key;
 
} Adata;
 
static void
init_srand (void)
{
    unsigned int time_elapsed;
 
    time ((time_t*)&time_elapsed);
 
    srand (time_elapsed);
}
 
static char *
get_random_string (int size)
{
    char *str;
    int i;
 
    str = g_new0 (char, size + 1);
 
    init_srand ();
 
    for ( i = 0 ; i < size; i++)
    {
	str[i] = (int)(2.0*rand()/(RAND_MAX+1.0)) + 48;
    }
 
    str[i] = '\0';
 
    return str;
}
 
static gboolean
send_gx_idle (gpointer data)
{
    DBusMessage *msg;
    DBusMessage *ret;
    Adata *A;
    gchar *str;
 
    A = (Adata *) data;
 
    /*Let's calculate g^x[p]*/
    mpz_powm (A->g_x, A->g, A->x, A->prime);
 
    /*In Z/pZ g_x is maximum the size of p so allocated PRIME_SIZE*/
    str = (char *) malloc (PRIME_SIZE);
    mpz_get_str (str, 10, A->g_x);
 
    /*Send g^x[p], we should get g^y[p] as a reply*/
    msg = dbus_message_new_method_call ("org.diffie.hellman.B",
					"/org/diffie/hellman/B",
					"org.diffie.hellman.B",
					"gx");
    dbus_message_append_args (msg, 
			      DBUS_TYPE_STRING, &str,
			      DBUS_TYPE_INVALID);
 
    ret = dbus_connection_send_with_reply_and_block (A->bus, msg, -1, NULL);
 
    if ( ret )
    {
	char *str_gy;
	dbus_message_get_args (ret, NULL,
			       DBUS_TYPE_STRING, &str_gy,
			       NULL);
	printf ("Received g^y[p] from B...\n");
	mpz_set_str (A->g_y, str_gy, 10);
 
	/*(g^y)^x[prime]*/
	mpz_powm (A->key, A->g_y, A->x, A->prime);
 
	gmp_printf ("The key is=%Zd\n", A->key);
 
    }
    else
    {
	printf ("didn't get response from B, key is not generated\n");
    }
 
    dbus_message_unref (msg);
    free (str);
 
    g_main_loop_quit (A->loop);
 
    return FALSE;
}
 
static void
send_g_and_prime (Adata *A, DBusMessage *msg)
{
    DBusMessage *ret;
    char *str;
    char *g_str;
    char *x_str;
    int g;
 
    str = get_random_string (PRIME_SIZE);
    x_str = get_random_string (100);
 
    mpz_set_str (A->x, x_str, 2);
 
    mpz_set_str (A->prime, str, 2);
    mpz_nextprime (A->prime, A->prime);
 
    g = g_random_int_range (10, 100);
    g_str = g_strdup_printf ("%i", g);
 
    mpz_set_str (A->g, g_str, 10);
 
    gmp_printf ("Sending prime=%Zd g=%Zd\n", A->prime, A->g);
 
    ret = dbus_message_new_method_return (msg);
 
    dbus_message_append_args (ret, 
			      DBUS_TYPE_STRING, &str,
			      DBUS_TYPE_STRING, &g_str,
			      DBUS_TYPE_STRING, &x_str,
			      DBUS_TYPE_INVALID);
 
    dbus_connection_send (A->bus, ret, NULL);
 
    dbus_message_unref (ret);
 
    free (str);
    free (g_str);
    free (x_str);
 
    g_idle_add ((GSourceFunc) send_gx_idle, A);
}
 
static DBusHandlerResult 
dbus_filter (DBusConnection *bus, DBusMessage *msg, void *data)
{
    if ( dbus_message_is_method_call (msg, "org.diffie.hellman.A", "Ready") )
    {
	Adata *A;
	A = (Adata *)data;
 
	printf ("Received ready call from B...\n");
 
	send_g_and_prime (A, msg);
	return DBUS_HANDLER_RESULT_HANDLED;
    }
 
    return DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
}
 
int main (int argc, char **argv)
{
    Adata *A;
    DBusError error;
 
    A = (Adata*) malloc (sizeof (Adata));
 
    mpz_init (A->g);
    mpz_init (A->prime);
    mpz_init (A->x);
    mpz_init (A->g_x);
    mpz_init (A->g_y);
    mpz_init (A->g_y_x);
    mpz_init (A->key);
 
    dbus_error_init (&error);
 
    A->bus = dbus_bus_get (DBUS_BUS_SESSION, &error);
 
    if ( !A->bus )
    {
	g_error ("Failed to connect to the session bus %s", error.message);
    }
 
    dbus_bus_request_name  (A->bus, "org.diffie.hellman.A", DBUS_REQUEST_NAME_REPLY_PRIMARY_OWNER, NULL);
 
    A->loop = g_main_loop_new (NULL, FALSE);
 
    dbus_bus_add_match (A->bus, "type='method_call', interface='org.diffie.hellman.B'", NULL);
    dbus_connection_add_filter (A->bus, dbus_filter, A, NULL);
 
    dbus_connection_setup_with_g_main (A->bus, NULL);
 
    g_main_loop_run (A->loop);
 
    dbus_connection_unref (A->bus);
 
    mpz_clear (A->prime);
    mpz_clear (A->g);
    mpz_clear (A->x);
    mpz_clear (A->g_x);
    mpz_clear (A->g_y);
    mpz_clear (A->g_y_x);
    mpz_clear (A->key);
    free (A);
    return 0;
}

B application 

#include <stdio.h>
#include <stdlib.h>
#include <dbus/dbus-glib-lowlevel.h>
#include <gmp.h>
 
typedef struct 
{
    DBusConnection *bus;
    GMainLoop *loop;
    mpz_t g;
    mpz_t y;
    mpz_t g_y;
    mpz_t g_x;
    mpz_t g_x_y;
 
    mpz_t prime;
    mpz_t key;
 
} Bdata;
 
static void
init_srand (void)
{
    unsigned int time_elapsed;
 
    time ((time_t*)&time_elapsed);
 
    srand (time_elapsed);
}
 
static void
send_gy (Bdata *B, DBusMessage *msg)
{
    DBusMessage *ret;
    char *str;
 
    dbus_message_get_args (msg, NULL,
			   DBUS_TYPE_STRING, &str,
			   DBUS_TYPE_INVALID);
 
 
    mpz_set_str (B->g_x, str, 10);
 
    /*Calculate g^y[p]*/
    mpz_powm (B->g_y, B->g, B->y, B->prime);
 
    str = (char *) malloc (128);
    mpz_get_str (str, 10, B->g_y);
 
    ret = dbus_message_new_method_return (msg);
 
    dbus_message_append_args (ret, 
			      DBUS_TYPE_STRING, &str,
			      DBUS_TYPE_INVALID);
 
    dbus_connection_send (B->bus, ret, NULL);
 
    /*(g^y)^x[prime]*/
    mpz_powm (B->key, B->g_x, B->y, B->prime);
    gmp_printf ("The key is=%Zd\n", B->key);
 
    free (str);
    dbus_message_unref (ret);
 
    g_main_loop_quit (B->loop);
}
 
static DBusHandlerResult 
dbus_filter (DBusConnection *bus, DBusMessage *msg, void *data)
{
    /*A send g^x[p]*/
    if ( dbus_message_is_method_call (msg, "org.diffie.hellman.B", "gx") )
    {
	Bdata *B;
	B = (Bdata *)data;
 
	printf ("Received g^x[p] from A...\n");
 
	send_gy (B, msg);
 
	return DBUS_HANDLER_RESULT_HANDLED;
    }
 
    return DBUS_HANDLER_RESULT_HANDLED;
}
 
static gboolean 
start_communication (gpointer data)
{
    DBusMessage *msg;
    int try = 0;
    gboolean connected = FALSE;
 
    Bdata *B = (Bdata *)data;
    printf ("Starting communication\n");
    do 
    {
	if ( dbus_bus_name_has_owner (B->bus, "org.diffie.hellman.A", NULL) )
	{
	    connected = TRUE;
	    break;
	}
	else
	{
	    printf ("'org.diffie.hellman.A' not connected re-trying\n");
	    try++;
	}
 
	g_usleep (1000000); /*sleep for one second*/
 
    } while (try < 5 );
 
    if ( connected == FALSE )
    {
	printf ("Maximum number of tries exceeded, A is not connected\n");
	g_main_loop_quit (B->loop);
	return FALSE;
    }
 
    msg = dbus_message_new_method_call ("org.diffie.hellman.A",
					"/org/diffie/hellman/A",
					"org.diffie.hellman.A",
					"Ready");
    DBusMessage *ret;
    ret = dbus_connection_send_with_reply_and_block (B->bus, msg, -1, NULL);
 
    char *str;
    char *g_str;
    char *x_str;
    dbus_message_get_args (ret, NULL,
			   DBUS_TYPE_STRING, &str,
			   DBUS_TYPE_STRING, &g_str,
			   DBUS_TYPE_STRING, &x_str,
			   DBUS_TYPE_INVALID);
 
    mpz_set_str (B->prime, str, 2);
    mpz_nextprime (B->prime, B->prime);
 
    mpz_set_str (B->g, g_str, 10);
 
    gmp_printf ("Using prime=%Zd and g=%Zd\n", B->prime, B->g);
 
    dbus_message_unref (msg);
 
    return FALSE;
}
 
static char *
get_random_string (int size)
{
    char *str;
    int i;
 
    str = g_new0 (char, size + 1);
 
    init_srand ();
 
    for ( i = 0 ; i < size; i++)
    {
	str[i] = (int)(2.0*rand()/(RAND_MAX+1.0)) + 48;
    }
 
    str[i] = '\0';
 
    return str;
}
 
int main (int argc, char **argv)
{
    Bdata *B;
    DBusError error;
    char *y_str;
 
    B = (Bdata*) malloc (sizeof (Bdata));
 
    mpz_init (B->prime);
    mpz_init (B->y);
    mpz_init (B->g);
    mpz_init (B->g_y);
    mpz_init (B->g_x);
 
    mpz_init (B->g_x_y);
    mpz_init (B->key);
 
    y_str = get_random_string (100);
 
    mpz_set_str (B->y, y_str, 2);
 
    free (y_str);
 
    dbus_error_init (&error);
 
    B->bus = dbus_bus_get (DBUS_BUS_SESSION, &error);
 
    if ( !B->bus )
    {
	g_error ("Failed to connect to the session bus %s", error.message);
    }
 
    dbus_bus_request_name  (B->bus, "org.diffie.hellman.B", DBUS_REQUEST_NAME_REPLY_PRIMARY_OWNER, NULL);
 
    B->loop = g_main_loop_new (NULL, FALSE);
 
 
    dbus_bus_add_match (B->bus, "type='method_call', interface='org.diffie.hellman.A'", NULL);
    dbus_connection_add_filter (B->bus, dbus_filter, B, NULL);
 
    dbus_connection_setup_with_g_main (B->bus, NULL);
 
    g_idle_add ((GSourceFunc) start_communication, B);
 
    g_main_loop_run (B->loop);
    dbus_connection_unref (B->bus);
 
    mpz_clear (B->prime);
    mpz_clear (B->y);
    mpz_clear (B->g);
    mpz_clear (B->g_y);
    mpz_clear (B->g_x);
 
    mpz_clear (B->g_x_y);
    mpz_clear (B->key);
 
    free (B);
    return 0;
}

Try it out

Save the above code into two files A.c and B.c, now compile them as follows:

gcc -Wall -g2 `pkg-config --libs --cflags dbus-glib-1` -lgmp A.c -o A
gcc -Wall -g2 `pkg-config --libs --cflags dbus-glib-1` -lgmp B.c -o B

Now you can run them from two different terminal windows, you need to run A first, the generated key will serve both A and B as an encryption key, you can try to implement for example exclusive disjunction (XOR) based encryption using the generated key, an example code could be as follows:

mpz_t xor;
mpz_t pass;
mpz_init (xor);
mpz_init (pass);
char password[] = "PasswordToEncrypt";
 
mpz_xor (xor,  key, pass);
 
mpz_clear (xor);
mpz_clear (pass);

To decrypt the password encrypted above you need to apply (XOR) once more on the pass and the key and you get the initial password.

Comment (RSS)  |  Trackback

Leave a Reply