Implementation of the key distribution protocol described in Secure Communications over Insecure Channels (Merkle 1978)

client.py

#!/usr/bin/env python

"""Puzzle Key Exchange Client.

Usage:
  puzzle.py [--n=<n>] [--c=<c>] --host=<hostname> [--port=<port>] [-v]

  puzzle.py -h | --help

Options:
  --n=<n>            Number of puzzles [default: 30]
  --c=<c>            Key space multiplier [default: 8]
  --host=<hostname>  Hostname or IP to connect to
  --port=<port>      Port to connect to [default: 3000]
  -v                 Be verbose
  -h, --help         Display this text

Symmetric key exchange system, as described in [Merkle 1978]. Key
negotiation requires O(n) work by both parties, but cracking requires
O(n²) work by an attacker. Obviously, this is not a very good system,
but there is no reason that this couldn't be adapted to use an
exponential method.

This program implements the client part, which retrieves a number of
keys from a server, and picks a random one.

Dependencies:
  docopt
  pycrypto

[Merkle 1978]: Secure Communications over Insecure Channels.
"""

from docopt import docopt
from random import randrange
from Crypto.Cipher import AES
import binascii
import socket
import sys

arguments = docopt(__doc__)

N = int(arguments['--n'])
C = int(arguments['--c'])

ENCODING = 'utf-8'
KEY_BYTE_SIZE = 32
IV = b'0000000000000000'

verbose = arguments['-v']

def int_to_key(value, bytelen, endianness='little'):
    """Turn an integer into a key, padding remaining bytes with
    zeroes.
    """

    return value.to_bytes(bytelen, byteorder=endianness)

def receive(socket):
    """Receive an encrypted puzzle from a socket.
    """

    buffer = b''
    while True:
        buffer += socket.recv(1)
        if buffer[-2:] == b'::':
            return buffer[:-2]

def decrypt(key, message, iv=None, encoding=None):
    """Decrypt a message.
    """

    cipher = AES.new(key, AES.MODE_CFB, iv or IV)
    return str(cipher.decrypt(message), encoding or ENCODING)

def hex(bytes):
    """Convert bytes to a hex string representation.
    """

    return "0x{}".format(str(binascii.hexlify(bytes), 'utf-8'))

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

key = None

try:
    sock.connect((arguments['--host'], int(arguments['--port'])))

    constant  = receive(sock)
    thepuzzle = b''
    puzzleid  = randrange(N)

    if verbose:
        print("Got constant {}".format(hex(constant)))
        print("Chosen puzzle {}".format(puzzleid))

    # Get the chosen puzzle
    if verbose:
        print("Receiving puzzles")
    for i in range(0, N):
        puzzle = receive(sock)
        if i == puzzleid:
            thepuzzle = puzzle

    # Brute force it!
    if verbose:
        print("Brute-forcing puzzle")
    for i in range(0, C * N + 1):
        key = int_to_key(i, KEY_BYTE_SIZE)
        try:
            # Ewww, eval.
            puzzle = [eval(x) for x in decrypt(key, thepuzzle).split(' ')]

            if len(puzzle) == 3 and puzzle[2] == constant:
                key = puzzle[1]
                sock.sendall(puzzle[0])
                break
        except:
            continue
finally:
    sock.close()

if key:
    print("Selected symmetric key: {}".format(hex(key)))
else:
    print("Could not successfully decode puzzle.")

server.py

#!/usr/bin/env python

"""Puzzle Key Exchange Server.

Usage:
  puzzle.py [--n=<n>] [--c=<c>] [--host=<hostname>] [--port=<port>] [-v]
  puzzle.py -h | --help

Options:
  --n=<n>            Number of puzzles [default: 30]
  --c=<c>            Key space multiplier [default: 8]
  --host=<hostname>  Hostname or IP to listen on
  --port=<port>      Port to listen on [default: 3000]
  -v                 Be verbose
  -h, --help         Display this text

Symmetric key exchange system, as described in [Merkle 1978]. Key
negotiation requires O(n) work by both parties, but cracking requires
O(n²) work by an attacker. Obviously, this is not a very good system,
but there is no reason that this couldn't be adapted to use an
exponential method.

This program implements the server part, which sends a number of
puzzles to a client upon connection.

Dependencies:
  docopt
  pycrypto

[Merkle 1978]: Secure Communications over Insecure Channels.
"""

from docopt import docopt
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
import socketserver
import math
import binascii

arguments = docopt(__doc__)

def rand(max, bytelen, endianness='little'):
    """Generate a random number in the range [0, max] inclusive, with
    a byte length of bytelen. Remaining bytes are padded to zero.

    Warning: This may never terminate.
    """

    # Get the number of bytes requried to hold our max value
    blen = int(math.ceil(math.log(max) / math.log(2)) / 8)

    # Repeatedly generate random numbers until we get one <= the maximum
    while True:
        bytes = get_random_bytes(blen)
        if int.from_bytes(bytes, byteorder=endianness) > max:
            continue

        # Return the padded bytestring
        return bytes + b'\0' * (bytelen - blen)

def hex(bytes):
    """Convert bytes to a hex string representation.
    """

    return "0x{}".format(str(binascii.hexlify(bytes), 'utf-8'))

class PuzzleServer(socketserver.BaseRequestHandler):
    # Character encoding
    ENCODING = 'utf-8'

    # Size in bytes of the secret keys used for puzzle generation.
    KEY_BYTE_SIZE = 32

    # Size of the constant
    CONSTANT_BYTE_SIZE = 4

    # Initialisation vector.
    IV = b'0000000000000000'

    # Number of puzzles to transmit
    N = int(arguments['--n'])

    # Key multiplier
    C = int(arguments['--c'])

    # Verbosity
    verbose = arguments['-v']

    def encrypt(self, key, message, iv=None, encoding=None):
        """Encrypt a message.
        """

        cipher = AES.new(key, AES.MODE_CFB, iv or self.IV)
        return cipher.encrypt(
            bytes(str(message), encoding or self.ENCODING))

    def handle(self):
        """A client has connected, generate the N puzzles, send them,
        and wait for a response.
        """

        if self.verbose:
            print("Received connection, generating puzzles...")
        
        K1 = get_random_bytes(self.KEY_BYTE_SIZE)
        K2 = get_random_bytes(self.KEY_BYTE_SIZE)
        constant = get_random_bytes(self.CONSTANT_BYTE_SIZE)

        if self.verbose:
            print("    {}".format(hex(constant)))
        
        self.request.sendall(constant + b'::')

        puzzles = {}

        # Generate all and transmit the puzzles
        for i in range(self.N):
            # Get the puzzle ID and key
            pid  = self.encrypt(K1, str(i))
            pkey = self.encrypt(K2, pid)

            # Get the key for encrypting the puzzle, and pad it to
            # the length required.
            randkey = rand(self.N * self.C, self.KEY_BYTE_SIZE)

            # Encrypt the puzzle and store the ID/key
            puzzle = self.encrypt(randkey, "{} {} {}".format(
                pid, pkey, constant))

            puzzles[pid] = pkey

            if self.verbose:
                print("    {}: {} {} {} {}".format(
                    i, hex(pid), hex(pkey), hex(randkey), hex(puzzle)))

            self.request.sendall(puzzle + b'::')

        # Wait for the client to send back an ID, and print the
        # corresponding key.
        pid = self.request.recv(1024).strip()
        print("Selected symmetric key: {}".format(hex(puzzles[pid])))

# Start the server
server = socketserver.TCPServer(
    (arguments['--host'] or '', int(arguments['--port'])),
    PuzzleServer)
server.serve_forever()