Web Rarely

Still looking for the glorious results of my misspent youth. Say, do you have a map to the next joint?

Permuting Integers and Creating Bijective Functions using Block Ciphers

2011-06-09

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 232 — 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 232. 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 2N factorial, while the number of keys is only 2K. 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)));
}

Comments

Test vectors? 2014-09-06 12:43AM
Hi!
Great idea, it just saved me!
I too, needed a simple pseudo random permutation without any security requirements.

Ok, when pasted into a c# solution your functions compile right away and produce output.

Still, just to be sure, maybe you yould post a handful of random test vectors?

Lots of Greetings!
Volker
an anonymous Volker Hetzer
RE: Test vectors? 2014-09-10 07:44PM
Hi Volker,

Sure, I don't mind posting some test vectors. I think if you copy and paste the code you'll get the same output that I do. In fact, I'm going to copy and paste the code in order to create the test vectors. Nonetheless, here they are. Each line gives the name of the algorithm, the key, and the first ten values from the permutation selected by that key.

syfer 00000000: 25CE7D54 041A7FD3 1E3A7F84 9F49789F 05AB7FDA 37687EC4 35447EAA 16878124 486185C1 7EB2845A
slip32 00000000: 78CE18C0 5AEFA907 0607E508 43102198 628506BA 1E4AB673 3DCE2A1A 6FB97AA8 D39E0070 85271B0E

syfer 000003E8: 464526D7 AF9025E4 D56A38E3 B83A265C 9B6A3649 CAD93955 FDD33795 65F53155 993B3562 F299370E
slip32 000003E8: A0A880BF 2F18BF44 E71FA259 38384D89 2AA1B40D A5796515 EA6D19C2 351BCEB5 7437E9F1 3B1CE19E

syfer C4653600: 5FFBFAF7 CF09F219 0CAFF18F 2758F029 0345F7E7 614AF650 EC6DFC33 FC04FD28 B2CECD8A 4EFBCCEE
slip32 C4653600: 28C8EE0F 8CDA07E7 E6FA3392 B41E533D 003F2C52 DD865E6B 7D5C7D57 67BA8617 14BAE312 5BC8C2C3

They were generated with this code:
static void Main()
{
  foreach(int key in new int[] { 0, 1000, -1000000000 })
  {
    PrintVector((uint)key, "syfer", syfer);
    PrintVector((uint)key, "slip32", slip32);
  }
}

static void PrintVector(uint key, string name, Func<uint,uint,uint> cipher)
{
  Console.Write("{0} {1:X8}:", name, key);
  for(uint i=0; i<10; i++) Console.Write(" {0:X8}", cipher(key, i));
  Console.WriteLine();
}

Add a comment

Note: The information you enter (including your name and email address) will be displayed publicly.




Line breaks are converted to <br>'s, and all HTML tags except b, u, i, tt, and pre are filtered out.