Quantum Computers and Privacy

by Thor R. Mirchandani

As Dave D'Rave points out in the article "Quantum Computers and Bitcoin" in issue 34:4, practical quantum computers are just around the corner.  While quantum computers may not pose an immediate threat to the hashing algorithms such as SHA-256 commonly used by Bitcoin and other cryptocurrencies, the threat to Internet security and privacy as we know it today is another kettle of fish.

There seems to be a consensus among experts that most strong hashing algorithms and strong symmetric key ciphers are resilient to quantum attacks if sufficient key lengths are used, thus Bitcoin's immunity in the short term (several decades).  On the other hand, most public-key ciphers in widespread use today are vulnerable to quantum attacks.  This class of algorithms includes those currently used in Internet privacy and trust protocols including SSL/TLS, HTTPS, digital certificates, digital signatures, and PGP.

Put differently, given a sufficiently large quantum computer, all the Internet data we assumed was private is completely transparent and the trust chains we have relied on are easily broken.  Are you scared yet?  Keep reading.

Post-Quantum Public-Key Ciphers

All cryptography algorithms worth their salt depend on a proof of equivalence to a hard mathematical problem.  Unfortunately, many computationally hard problems, including the algorithms currently in use on the Internet, look "soft" to a quantum computer.

But fortunately, not all hard mathematical problems are trivial in the eyes of a quantum computer.  It appears that the solution to our post-quantum privacy concerns would involve a switch to ciphers that reduce to "quantum hard" math problems.  Luckily, there are several open-source projects that address this issue, and one of the more well known is Open Quantum Safe (OQS).

Getting Started with OQS

Enough of the dry stuff - let's jump right in and get wet!  In other words, let's write some OQS code.  The example we're going to use is a bare-bones quantum safe Internet chat application.  Our application consists of a client and a server.  The client initiates a quantum safe key exchange with the server using a quantum safe public-key cipher called Frodo, which offers a quantum security of 2130 bits in our setup.  In the exchange, the client and server agree on a unique symmetric key that they will use for the duration of the session.  All subsequent messages will be encrypted and decrypted using this key and the well known symmetric key cipher AES.

First we have to download the OQS library, liboqs, from GitHub either by cloning or downloading/extracting the ZIP file.  The URL is: github.com/open-quantum-safe/liboqs

The library has several dependencies that we need to install as well.  I used Ubuntu 16.04 LTS and on that OS I would issue the following command: sudo apt install autoconf automake cmake libtool

On MacOS you would use Homebrew instead, and the download includes a Visual Studio setup to cater to Windows users.

Once the dependencies are installed it's time to build the liboqs library.  On Ubuntu 16.04 LTS: autoreconf -i; ./configure; make clean; make

When the commands complete, you should have a library called liboqs.a that must be linked to the final executable.  You should also have a header file called oqs.h in the include folder.

Building a Chat Application with OQS

The main purpose of this application is to show how we can use a quantum safe public-key algorithm to safely perform a key exchange across a network connection.  In other words, the goal is not to write a full-fledged chat application, and, as you will see, the capabilities of the application are quite limited.

By the same token, the code is kept extremely simple, and thus there are many shortcuts.  In fact, there are some non-quantum related vulnerabilities that I didn't bother to address.  For example, it is vulnerable to side-channel attacks, there are potential buffer overflows, and so on.  It doesn't matter for demonstration purposes, but would be disastrous in a production system.  In other words, it's a toy, so don't use this for real work!  You have been warned.

In the following, please refer to the code which follows this article.

The main() function of the program sets up the OQS infrastructure.  It then checks the command line to see if it should operate in client mode ("Alice") or server mode ("Bob"), -C and -S respectively.  The server listens to a TCP/IP socket on port 36000, and the client communicates on the same port.

The first step is the interesting one: Together the client and server perform a quantum safe key exchange using Frodo.  This results in both client and server having a 256 bit (32 bytes) shared key.

This shared key is used by the client to encrypt messages using plain old AES.  The client then sends the encrypted message across the TCP/IP socket to the server.  The server decrypts and displays the message, adds some text to it, encrypts the message, and sends it back to the client.  The client then decrypts the response and displays it.  And that's it.

To run the application, open a terminal window and start the program in server mode.  Then open another terminal and start the program in client mode.  Type some text in the client terminal and you should see the encrypted and plain text in the server terminal.  Then the encrypted and plain text response should appear in the client window momentarily.  Below is a sample session:

$ ./phqchat -S
starting server...

Creating socket
Listening
Accepted incoming connection
Reading first message
Starting key exchange
Bob message               (11288 bytes): 9C211D538E335F5FF276156071598FF4D399BFD6...
4229C83CDBC03595EF844D49474634D28F39ED3C
Bob session key      (  32 bytes):  A26EE735B15F28FB47ECF6F096E661BC418601BA8FE2
F3EDF62579045F42646B
Key exchange complete

Encrypted message from client:
ffffffa8ffffff89ffffffd170fffffffeffffffa86c68ffffffddffffffac174bffffffc1ffffff
927069fffffff6ffffffda4c341d4f43ffffff965affffffd57dffffff946cffffff8563 b30ffff
ffc3ffffffd8fffffff1ffffffb2ffffffa2ffffffacfffffff8165b75ffffffdf 4ffffffa0ffff
ffbeffffffc4
Decrypted message: Hello Bob. Typing something for you.

$ ./phqchat -C
starting client...
Creating a socket
Starting key exchange
Alice initial message (11280 bytes):    72E12292ECCD6911B3A93D6A6C7B7051B8E3CFB6
...09B337FA6487B088B5127A0CF44EF023A484D973
Alice session key    (  32 bytes): A26EE735B15F28FB47ECF6F096E661BC418601BA8FE2
F3EDF62579045F42646B
Key exchange complete

Hello Bob. Typing something for you.

Encrypted response from server:
ffffffd951763c7fffffffc7bffffff8cffffff9a 9fffffffdffffffcb30fffffff56266ffffff
fc20ffffff8dffffffb23affffff9349ffffff9d76 c3e2fffffffcbffffffe3ffffffeafffffff6
72 c25556746ffffff80ffffff98ffffffd4ffffffbd4dffffffa6535bffffffb765ffffff97ffff
ffbeffffffd427ffffffed6fffffffc9ffffff89ffffff9bffffffeeffffffe011fffffff8555b13
Decrypted response: Dear Alice,
You typed Hello Bob. Typing something for you.

The Road Ahead

As I mentioned, the program we built is a cheap parlor trick.  The real value of quantum safe public-key encryption technology will be realized when it's incorporated in mainstream applications and tools for quantum secure communications, encryption, digital signatures, and certificates.  That has not happened yet, but there are efforts underway.  For example, the OQS team has created a version of OpenSSL that uses quantum safe ciphers.  It's also available on GitHub.  The URL is: github.com/open-quantum-safe/openssl

In addition to Frodo, OQS contains several other quantum safe ciphers and tools that you can use to implement communications apps, digital signatures, encryption apps, and anything else you can dream up.  Happy hacking!

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include "oqs.h"

#define LETS_USE_FRODO
#ifdef  LETS_USE_FRODO

/* Use Frodo (Learning With Errors) for the key exchange */
static int algorithm = OQS_KEX_alg_lwe_frodo;

/* Length of the seed */
static const size_t seedLen = 16;

/* The seed (16 bytes ) */
static const uintt8_t *seed = "qwertyuiopasdfgh";

/* Use the "recommended" parameter for >= 128 bits of security */
static const char *namedParms = "recommended";
#endif

/* Host IP adress */
static const char *host = "127.0.0.1";
/* Port number */

static const int port = 36000;
/* Some data buffers */

static char buffer[16384] = { 0 };
static char plainText[16384] = { 0 };
static char cipherText[16384] = { 0 };

/* Prototypes */
int bob (OQS_KEX * kex);
int alice (OQS_KEX * kex);
int calculatePaddedLength (int len);

int
main (int argc, char **argv)
{
  int rc = 0;
  /* Initialize random numbers */
  OQS_RAND *rand = OQS_RAND_new (OQS_RAND_alg_urandom_chacha20);
  /* Initialize key exchange */
  OQS_KEX *kex = NULL;
  kex = OQS_KEX_new (rand, algorithm, seed, seedLen, namedParms);
  if (NULL == kex)
    {
      return -1;
    }

  /* Check command line parms */
  if (argc < 2)
    {
      printf ("Command line args:\n-C for client mode\n-S for server mode\n");

    }
  else if (0 == strcmp (argv[1], "-C"))
    {
      printf ("starting client...\n");
      rc = alice (kex);
    }
  else if (0 == strcmp (argv[1], "-S"))
    {
      printf ("starting server...\n\n");
      rc = bob (kex);
    }
  else
    {
      printf ("Command line args:\n-C for client mode\n-S for server mode\n");
    }
  /* Clean up */
  OQS_RAND_free (rand);
  OQS_KEX_free (kex);
  return rc;
}

/* This is for AES. A block has to be exact ly 128 bits (16 bytes) */
int
calculatePaddedLength (int len)
{
  if (0 == len % 16)
    {
      return len;
    }
  int n = len / 16;
  return 16 * (n + 1);
}

/* Set up and run chat program in client mode */
/* Client is Alice by convention */

int
alice (OQS_KEX * kex)
{
  void *alicePrivate = NULL;    /* Alice's private key */
  uint8_t *aliceMsg = NULL;     /* Alice's message */
  size_t aliceMsgLen = 0;       /* Alice's message length */
  uint8_t *aliceKey = NULL;     /* Alice's final key */
  size_t aliceKeyLen = 0;       /* Alice's final key length */
  int rc = 0;

/* Open a socket */
  printf ("Creating a socket\n");
  struct sockaddr_in address;
  int sock = 0, numChars;
  struct sockaddr_in serv_addr;
  if (0 > (sock = socket (AF_INET, SOCK_STREAM, 0)))
    {
      printf ("Socket creation error \n");
      rc = -1;
      goto client clean;
    }
  memset (&serv_addr, '0', sizeof (serv_addr));
  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons (port);

  if (0 >= inet_pton (AF_INET, host, &serv_addr.sin_addr))
    {
      printf ("Invalid address\n");
      rc = -1;
      goto client_clean;
    }

  if (connect (sock, (struct sockaddr *) &serv_addr, sizeof (serv_addr)) < 0)
    {
      printf ("Connect failed\n");
      rc = -1;
      goto client_clean;
    }

/* BEGIN KEY EXCHANGE */
/* Alice sends the Diffie Hellman initial message */
  printf ("Starting key exchange\n");
  rc = OQS_KEX_alice_0 (kex, &alicePrivate, &aliceMsg, &aliceMsgLen);
  if (OQS_ SUCCESS != rc)
    {
      fprintf (stderr, "ERROR: OQS_KEX_alice_0 failed!\n");
      goto client_clean;
    }

  OQS_print_part_hex_string ("Alice initial message", aliceMsg, aliceMsgLen,
                             20);
  send (sock, aliceMsg, aliceMsgLen, 0);

/* Get response back from server */
  numChars = read (sock, buffer, sizeof buffer);

/* process the response */
  uint8_t *bobMsg = NULL;       // Bob's message
  size_t bobMsgLen = 0;         // Bob's message length
  bobMsg = buffer;
  bobMsgLen = numChars;

  rc =
    OQS_KEX_alice_1 (kex, alicePrivate, bobMsg, bobMsgLen, &aliceKey,
                     &aliceKeyLen);
  if (OQS_SUCCESS != rc)
    {
      printf ("ERROR: OQS_KEX_alice_1 failed!\n");
      goto client_clean;
    }

  OQS_print_hex_string ("tAlice session key", aliceKey, aliceKeyLen);
  printf ("Key exchange complete\n\n");
  /* END KEY EXCHANGE */

/* Now start the chat */
  while (1)
    {
/* Get input from keyboard */
      memset (buffer, '\0', sizeof buffer);
      fgets (buffer, sizeof buffer, stdin);
      numChars = strlen (buffer);
      int len = calculatePaddedLength (numChars);

/* Encrypt using session key */
      memset (cipherText, '\0', sizeof cipherText);
      OQS_AES128_ECB_enc (buffer, len, aliceKey, cipherText);

/* Send encrypted message */
      send (sock, cipherText, len, 0);

/* Get response */
      memset (buffer, '\0', sizeof buffer);
      numChars = read (sock, buffer, sizeof buffer);
      len = calculatePaddedLength (numChars);
      printf ("\nEncrypted response from server:\n");
      for (int i = 0; i < len; i++)
        {
          printf ("%2x", buffer[i]);
        }

/* Decrypt using session key */
      memset (plainText, '\0', sizeof plainText);
      OQS_AES128_ECB_dec (buffer, len, aliceKey, plainText);
      printf ("\nDecrypted response: %s\n", plainText);
    }

client_clean:
  OQS_MEM_secure_free (aliceMsg, aliceMsgLen);
  OQS_MEM_secure_free (aliceKey, aliceKeyLen);
  OQS_KEX_alice_priv_free (kex, alicePrivate);
  OQS_MEM_secure_free (bobMsg, bobMsgLen);
  return rc;
}

/* Set up and run chat program in server mode */
/* Server is Bob by convention */
int
bob (OQS_KEX * kex)
{
  uint8_t *bobMsg = NULL;       // Bob's message
  size_t bobMsgLen = 0;         // Bob's message length
  uint8_t *bobKey = NULL;       // Bob's final key
  size_t bobKeyLen = 0;         // Bob's final key length
  uint8_t *aliceMsg = NULL;     // Alice's message
  size_t aliceMsgLen = 0;       // Alice's message length
  int rc = 0;

/* Set up a listen socket */
  int server_fd, new_socket, numChar;
  struct sockaddr_in address;
  int opt = 1;
  int addrlen = sizeof (address);

/* Creating socket file descriptor */
  printf ("Creating socket\n");
  if (0 == (server_fd = socket (AF_INET, SOCK_STREAM, 0)))
    {
      printf ("socket failed\n");
      exit (EXIT_FAILURE);
    }

/* Bind listening socket to the port */
  if (setsockopt
      (server_fd, SOL_SOCKET, SO_REUSEADDR | SO_REUSEPORT, &opt, sizeof (opt)))
    {
      printf ("setsockopt failed");
      exit (EXIT_FAILURE);
    }
  address.sin_family = AF_INET;
  address.sin_addr.s_addr = INADDR_ANY;
  address.sin_port = htons (port);

  if (0 > bind (server_fd, (struct sockaddr *) &address, sizeof (address)))
    {
      printf ("bind failed");
      exit (EXIT_FAILURE);
    }

/* Wait for a connection */
  printf ("Listening\n");
  if (listen (server_fd, 3) < 0)
    {
      printf ("listen");
      exit (EXIT_FAILURE);
    }

  if (0 >
      (new_socket =
       accept (server_fd, (struct sockaddr *) &address,
               (socklen_t *) & addrlen)))
    {
      perror ("accept");
      exit (EXIT_FAILURE);
    }
  printf ("Accepted incoming connection\n");

/* BEGIN KEY EXCHANGE */
/* Read the first incoming message */
  printf ("Reading first message\n");
  memset (buffer, '\0', sizeof buffer);
  numChar = read (new_socket, buffer, sizeof buffer);

  /* Process first incoming message, which is part of key exchange */
  printf ("Starting key exchange\n");
  aliceMsg = buffer;
  aliceMsgLen = numChar;
  rc =
    OQS_KEX_bob (kex, aliceMsg, aliceMsgLen, &bobMsg, &bobMsgLen, &bobKey,
                 &bobKeyLen);
  if (OQS_SUCCESS != rc)
    {
      fprintf (stderr, "ERROR: OQS_KEX_bob failed!\n");
      goto server_clean;
    }

  OQS_print_part_hex_string ("Bob message", bobMsg, bobMsgLen, 20);
  OQS_print_hex_string ("Bob sess ion key", bobKey, bobKeyLen);

/* Send the message to client */
  send (new socket, bobMsg, bobMsgLen, 0);
  printf ("Key exchange complete\n\n");
/* END KEY EXCHANGE */

  while (1)
    {
      /* Wait for next message */
      memset (buffer, '\0', sizeof buffer);
      numChar = read (new_socket, buffer, sizeof buffer);
      int len = calculatePaddedLength (numChar);
      printf ("\nEncrypted message from client:\n");
      for (int i = 0; i < len; i++)
        {
          printf ("%2x", buffer[i]);
        }

/* Decrypt using session key */
      memset (plainText, '\0', sizeof plainText);
      OQS_AES128_ECB_dec (buffer, len, bobKey, plainText);
      printf ("\nDecrypted message: %s\n", plainText);


/* Compose a response */
      memset (buffer, '\0', sizeof buffer);
      sprintf (buffer, "Dear Alice,\nYou typed %s\n", plainText);
      numChar = strlen (buffer);
      len = calculatePaddedLength (numChar);

/* Encrypt  it using  session key */
      memset (cipherText, '\0', sizeof cipherText);
      OQS_AES128_ECB_enc (buffer, len, bobKey, cipherText);

/* Send to client */
      send (new_socket, cipherText, len, 0);

    }

server_clean:
  OQS_MEM_secure_free (bobMsg, bobMsgLen);
  OQS_MEM_secure_free (bobKey, bobKeyLen);
  OQS_MEM = secure_free (aliceMsg, aliceMsgLen);
  return rc;

}

Code: phqchat.c

Return to $2600 Index