[dns-operations] IP address encryption: pseudonymization

[Paul Hoffman]

I started a thread on the CFRG mailing list about ipcrypt. (CFRG is the 
Crypto Forum Research Group, part of the IRTF, and is the place where 
the IETF goes for crypto advice.) The results may instill caution in 
using ipcrypt.

The first reply was from Jean-Philippe Aumasson, the author of ipcyrpt.

> Hi!
>
> I designed ipcrypt as a low-security toy cipher to encrypt IPv4 
> addresses for some log analysis application. It may be good enough for 
> this purpose, however it has very low security:
>
> * because of 32-bit blocks, a chosen-plaintext codebook attack will 
> work in time 2^32 (or much less for specific IP ranges)
>
> * known-plaintext codebook attacks will work similarly but in O(n log 
> n), or 2^37 (coupon collector problem)
>
> * there is a generic ~2^16 distinguisher that works by looking for a 
> collision in a sequence of blocks
>
> * worse, Jason just found a high-probability differential that seems 
> detectable with fewer than 2^24 chosen-plaintext pair, and which may 
> speed up key recovery

Next was from Jason Donenfeld, the "Jason" that JP referred to. I have 
attached his code to this message; it is called "ipcrypt-broken.c".

> Found this last night shortly after you posted this message. The
> attached program Samuel (CC'd) and I just drummed up may be cause for
> concern. You may not want to use ipcrypt.

--Paul Hoffman

-------------- next part --------------
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <sys/random.h>

#define IPCRYPT_BYTES 4
#define IPCRYPT_KEYBYTES 16

#define ROTL(X, R) (X) = (unsigned char)((X) << (R)) | ((X) >> (8 - (R)))

static void
arx_fwd(unsigned char state[4])
{
	state[0] += state[1];
	state[2] += state[3];
	ROTL(state[1], 2);
	ROTL(state[3], 5);
	state[1] ^= state[0];
	state[3] ^= state[2];
	ROTL(state[0], 4);
	state[0] += state[3];
	state[2] += state[1];
	ROTL(state[1], 3);
	ROTL(state[3], 7);
	state[1] ^= state[2];
	state[3] ^= state[0];
	ROTL(state[2], 4);
}

static void
arx_bwd(unsigned char state[4])
{
	ROTL(state[2], 4);
	state[1] ^= state[2];
	state[3] ^= state[0];
	ROTL(state[1], 5);
	ROTL(state[3], 1);
	state[0] -= state[3];
	state[2] -= state[1];
	ROTL(state[0], 4);
	state[1] ^= state[0];
	state[3] ^= state[2];
	ROTL(state[1], 6);
	ROTL(state[3], 3);
	state[0] -= state[1];
	state[2] -= state[3];
}

static inline void
xor4(unsigned char *out, const unsigned char *x, const unsigned char *y)
{
	out[0] = x[0] ^ y[0];
	out[1] = x[1] ^ y[1];
	out[2] = x[2] ^ y[2];
	out[3] = x[3] ^ y[3];
}

int
ipcrypt_encrypt(unsigned char out[IPCRYPT_BYTES],
		const unsigned char in[IPCRYPT_BYTES],
		const unsigned char key[IPCRYPT_KEYBYTES])
{
	unsigned char state[4];

	xor4(state, in, key);
	arx_fwd(state);
	xor4(state, state, key + 4);
	arx_fwd(state);
	xor4(state, state, key + 8);
	arx_fwd(state);
	xor4(out, state, key + 12);

	return 0;
}

int
ipcrypt_decrypt(unsigned char out[IPCRYPT_BYTES],
		const unsigned char in[IPCRYPT_BYTES],
		const unsigned char key[IPCRYPT_KEYBYTES])
{
	unsigned char state[4];

	xor4(state, in, key + 12);
	arx_bwd(state);
	xor4(state, state, key + 8);
	arx_bwd(state);
	xor4(state, state, key + 4);
	arx_bwd(state);
	xor4(out, state, key);

	return 0;
}

uint8_t random_byte(void)
{
	static uint8_t pool[256];
	static size_t i = sizeof(pool);

	if (i == sizeof(pool)) {
		i = 0;
		assert(!getentropy(pool, sizeof(pool)));
	}
	return pool[i++];
}

int main(int argc, char *argv[])
{
	const uint8_t delta_i[IPCRYPT_BYTES] = { 0x0a, 0x02, 0x00, 0x00 };
	const uint8_t delta_o[IPCRYPT_BYTES] = { 0x60, 0x70, 0x4d, 0x0c };
	const size_t total = 1UL << 24;
	uint8_t key[IPCRYPT_KEYBYTES];
	size_t counter = 0, r, i;

	assert(!getentropy(key, IPCRYPT_KEYBYTES));

	for (r = 0; r < total; ++r) {
		uint8_t p0[IPCRYPT_BYTES], p1[IPCRYPT_BYTES];

		for (i = 0; i < IPCRYPT_BYTES; ++i) {
			p0[i] = random_byte();
			p1[i] = p0[i] ^ delta_i[i];
		}
		ipcrypt_encrypt(p0, p0, key);
		ipcrypt_encrypt(p1, p1, key);

		for (i = 0; i < IPCRYPT_BYTES; ++i)
			p0[i] ^= p1[i];

		counter += !memcmp(p0, delta_o, IPCRYPT_BYTES);
	}

	printf("%f\n", (double)counter / total);
	return 0;
}