Web Rarely

The other day I was thinking about how to implement a general-purpose Bloom filter for .NET. Bloom filters are based on hashing. All .NET objects support the ability to get a hash code, but the problem is that Bloom filters require multiple hash functions, and it would be unfriendly to require users to create their own set of type-specific hash functions just to use the Bloom filter. I would of course create optimized hash functions for all the typical key types (numbers, strings, dates, GUIDs, arrays of value types, etc.), but there would have to be a fallback method capable of working with any type.

One possibility is to take the standard .NET hash code which every object has and hash that. That's a poor idea in general because if two objects give the same .NET hash code, then they will share hash codes for every hash function. (Of course they would give different values for different hash functions, but for a given function they would both give the same value.) The hash functions would be way too dependent on each other. However, it suffices for Bloom filters of small-to-medium size because, assuming the built-in .NET hash functions are implemented well, the chance of two distinct values returning the same hash code is very small (about one in a few billion, although it is affected by the birthday paradox).

In any case, I still had the problem of creating the hash functions. The best hash functions are injective, meaning that they never map distinct input values onto the same output value. This is impossible whenever the input domain is larger than the output domain, but in my case I would be mapping integers onto integers. Since the input and output domains are the same size, an injective function would necessarily be bijective too. It struck me that what I really needed was a permutation. If I had N random permutations of the integers, then hashing the value k with the nth hash function would simply be a matter of taking the kth element of the nth random permutation.

This left me with the problem of coming up with a way to efficiently select, say, the billionth integer from the billionth random permutation of the integers. I thought about ways of using prime and coprime numbers to generate the permutations. (Given a prime p, a coprime c, and a starting value s, (s+c*n) mod p produces the nth value in a permutation of the numbers 0 through p-1.) Those permutations would be rather predictable, but that might not be a problem. I'd only need one prime number, which I could find beforehand — it would the first prime greater than 2³² — but finding the coprimes seemed like it would be nontrivial. There's also the fact that I'd need to iterate if the output wasn't less than 2³². It just seemed ugly.

Luckily, I stumbled upon the idea of using a block cipher. In fact, block ciphers meet the requirements almost perfectly. The whole purpose of a block cipher is to transform one N-bit value into another N-bit value, based on a K-bit key. It does so uniquely, with every possible N-bit input mapping to only one N-bit output, which is necessary for the cipher to be reversed. In effect, the key is used to select a particular pseudorandom permutation of the N-bit values, and the input value serves as an index into that permutation.

The only problem was that there didn't exist any block ciphers that fit my purposes. They are typically designed to be complex, cryptographically strong transformations. The output size is typically 64 or 128 bits, and the key size is typically much larger than that. (The reason should be clear: the number of potential permutations is 2^N factorial, while the number of keys is only 2^K. So the key size is much larger than the output size to allow more of the possible permutations to be accessible to the cipher.) So I set out to create my own block cipher. Or rather, I set about to strip down and optimize an existing block cipher to take an integer key and produce an integer output. I wanted a cipher that was simple to implement. The Tiny Encryption Algorithm (TEA) looked promising, but I was dissuaded by the fact that it suffers from equivalent keys. Instead, I created a stripped-down version of Skipjack, the NSA algorithm intended to be used in the Clipper chip, chosen because it was also simple, and because I assumed it would be more random. But I was enchanted with the simplicity of TEA and, bolstered by my experience converting Skipjack, I also converted XXTEA (a somewhat stronger but more complex form of TEA).

It works pretty well! I tested several versions of the ciphers by enciphering a bunch of zeros with an all-zero key in CBC mode and running the results through NIST's statistical test suite. The Skipjack-based cipher passed with consistently high scores, while the XXTEA-based cipher had high scores except for a few failures. Neither are suitable for encryption of course, but both manage to generate strongly random-looking output. More importantly, they both work well in the Bloom filter. The generic hashing approach works up to about 10 million items, when the minimum false positive rate starts to become unacceptably high (i.e. greater than 0.1%). To solve this, I implemented custom hash providers for all the common built-in types, but they use block ciphers too. So in short, if you need a way to represent permutations of a large space without having to pre-generate them, consider using block ciphers!

Block ciphers aren't the only way to do this, though. Some techniques for creating random number generators can used, especially those based on XOR and shuffling bits, as those don't lose information. You'd use them to create a random number generator with no internal state. In fact that's what a block cipher is.

Update: For my Bloom filter, although the block cipher approach described above worked pretty well, I eventually switched to some hashing code based on Bob Jenkins' lookup3 hash, which I optimized for 4, 8, and 16 byte values in addition to the general byte string case. It doesn't work for permuting integers or generating bijective functions — the subject of this article — because it has collisions in the output, and the output of the hash is slightly less uniform than the block cipher I was using, but it's faster and, honestly, more trustworthy. The block cipher I developed worked great for a given hash function, but there were some dependencies between hash functions sometimes. That's no slight against the idea of using block ciphers in general, though, and for the problem of generating bijective functions and permutations of integers, I still think they're a perfect fit. Even for hashing, they can work well, if you know how to develop a good one, but I'm not an expert in developing cryptographic algorithms.

Here is the (heavily inlined and nigh-unreadable) code for my own block cipher. I'm sure the round function is poorly designed, but it seems to suffice for permuting integers.

// this is a weak block cipher with a 32-bit key and a 32-bit output based on a 16:16 balanced
// Feistel network. it should be clear from the small key size and poor design that it's insecure,
// but it should serve its purpose of giving us a pseudorandom permutation of the output space
// (i.e. of the 32-bit integers) with the key as the seed
static uint syfer(uint key, uint data)
{
  uint R = (data^key) & 0xFFFF;
  uint L = (data>>16) ^ (((((R>>5)^(R<<2)) + ((R>>3)^(R<<4))) ^ ((R^0x79b9) + R)) & 0xFFFF);
  key = (key>>3) | (key<<29);
  R ^= ((((L>>5)^(L<<2)) + ((L>>3)^(L<<4))) ^ ((L^0xf372) + (L^key))) & 0xFFFF;
  return ((L ^ ((((R>>5)^(R<<2)) + ((R>>3)^(R<<4))) ^ ((R^0x6d2b) + (R^((key>>3)|(key<<29)))))) << 16) | R;
}

And here is the code for the stripped-down version of Skipjack:

// this is a weak block cipher with a 32-bit key and a 32-bit output. it should be clear
// from the small key size that it's insecure, but if that's not enough, it's a greatly
// weakened form of skipjack, which has already been broken. but it should serve its
// purpose of giving us a pseudorandom permutation of the output space (i.e. of the
// 32-bit integers) with the key as the seed
static uint slip32(uint key, uint data)
{
  uint low = data & 0xFFFF, high = data >> 16; // split the data into two parts
  // perform four Feistel rounds. the Luby-Rackoff analysis proves that if the round
  // function is a cryptographically secure pseudorandom function, then 3 rounds
  // suffice to create a pseudorandom permutation and 4 rounds suffice to make a "strong"
  // pseudorandom permutation. i have no idea if the round function is cryptographically
  // secure, but the result will nonetheless be some kind of permutation, and it looks
  // pretty random in statistical tests, which is good enough for my purposes
  high ^= round(key, low);
  // rotate the key bytes here rather than using it as a circular array inside round()
  key = (key>>8) | (key<<24);
  low ^= round(key, high) ^ 1;
  key = (key>>8) | (key<<24);
  high ^= round(key, low) ^ 2;
  key = (key>>8) | (key<<24);
  low ^= round(key, high) ^ 3;
  return (low<<16) | high; // swap the halves and recombine them
}

static uint round(uint key, uint word)
{
  uint g0, g1, g2, g3;
  g0 = permutation[(byte)(word ^ key)] ^ (word>>8);
  g1 = permutation[(byte)(g0 ^ (key>>8))] ^ word;
  g2 = permutation[(byte)(g1 ^ (key>>16))] ^ g0;
  g3 = permutation[(byte)(g2 ^ (key>>24))] ^ g1;
  return (uint)((byte)g2<<8) | (byte)g3;
}

// this is a permutation of all possible bytes (the same used by skipjack)
static readonly byte[] permutation = new byte[256]
{
  0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9,
  0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28,
  0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53,
  0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2,
  0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8,
  0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90,
  0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76,
  0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d,
  0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18,
  0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4,
  0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40,
  0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5,
  0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2,
  0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8,
  0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac,
  0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46
};

Finally, here is an example of how the block ciphers can be used, first in a generic hash and then in a type-specific hash. Obviously the generic approach suffers from the problem, described above, that the hash functions are not independent, but whatcha gonna do?

static int GetHashCode(int hashFunction, T item)
{
  int hash = EqualityComparer<T>.Default.GetHashCode(item);
  // hash function 0 will be the built-in .NET hash function. other hash functions will
  // be constructed using a weak 32-bit block cipher with the hash function as the key
  // and the .NET hash as the data to be encrypted. this effectively uses the .NET hash
  // value as an index into a random permutation of the 32-bit integers
  if(hashFunction != 0) hash = (int)syfer((uint)hashFunction, (uint)hash);
  return hash;
}

static int GetHashCode(int hashFunction, ulong item)
{
  // you could also special case hash function 0 here. use two different hash functions
  // to avoid the result always being zero when 'item' is zero. it would be more efficient
  // to develop fast block ciphers for 64-bit values rather than combining two 32-bit
  // values, but that's an exercise for the reader ;-)
  return (int)(syfer((uint)hashFunction, (uint)item) ^
               syfer((uint)hashFunction+1, (uint)(item>>32)));
}