Key Splitting in Practice

Page Header
There are numerous methods of sending sensitive information across untrusted channels. This is the exact problem that Asymmetric encryption algorithms were created to solve.

However, if you don’t want to have to deal with asymmetric key generation and key exchanges you can use a much more primitive, but still highly secure method of protecting your data in transit. This method is known as secret sharing.

This isn’t anything new, but if you want to utilise it yourself, it’s very easy to implement in code. Let’s say we want to send an AES key to a friend, so that we both have the same key to encrypt and decrypt some data.

We first generate the key (we’ll refer to it as k) on our side, and hold it as a byte array.

We then create 2 more byte arrays of exactly the same length (we’ll call them x and y), and we fill them with random bytes.

We then perform exclusive OR operations on the key with our 2 random byte arrays (k XOR x XOR y) to yield a new value, which we’ll call z.

So now we have 3 values, x, y and z which we can then send to our friend. Individually, these parts are completely useless. If you obtain any one of them, it is nearly impossibly with today’s technology to try to derive the original value k. So, to make sure that they arrive safely to our friend, we can just print x out and send it via courier, send y via Email, and z via fax (or any other method of transport that is desired).

Now when our friend gets the parts, they can just reverse the process (x XOR y XOR z) to retrieve the original value, k.

Talk is cheap, show me the code

It’s one thing to explain the process, but it’s better to see it in code. I wrote a small example of this process in Python a while ago:

The encryption function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def encrypt(s):
	length = len(s)

	s = bytearray(s)
	x = bytearray(os.urandom(length))
	y = bytearray(os.urandom(length))
	z = bytearray(os.urandom(length))

	for i in range(length):
		z[i] = s[i] ^ x[i] ^ y[i]
	
	x = binascii.hexlify(x)
	y = binascii.hexlify(y)
	z = binascii.hexlify(z)

	pieces = [x, y, z]
	return pieces

And then the decryption function:

1
2
3
4
5
6
7
8
9
10
def decrypt(x, y, z):
	s = bytearray(os.urandom(len(x) / 2)) # filled with random data to set the length
	x = bytearray(binascii.unhexlify(x))
	y = bytearray(binascii.unhexlify(y))
	z = bytearray(binascii.unhexlify(z))

	for i in range(len(x)):
		s[i] = x[i] ^ y[i] ^ z[i]

	return s.decode('utf-8')

As you can see it’s really quite a simple process, but it provides a near-unbreakable form of protection for your secret. You just need to ensure that:

  • the random numbers need to be random. Most languages will use the pseudo-RNG that the operating system provides, which may not be random enough for some usages, and
  • you’re careful about the communication channels you send the parts over. It’s all well and good to ensure your key generation is perfect but if you send them all in the mail with the same postal company, you might as well assume they’ve been intercepted.

If you’ve got a sensitive piece of data to send, it’s also best to be performing all splitting/combining operations on trusted, air-gapped machines.