Obfuscating an ID

Obfuscate it with some combination of 2 or 3 simple methods:

• XOR
• shuffle individual bits
• convert to modular representation (D.Knuth, Vol. 2, Chapter 4.3.2)
• choose 32 (or 64) overlapping subsets of bits and XOR bits in each subset (parity bits of subsets)
• represent it in variable-length numberic system and shuffle digits
• choose a pair of odd integers x and y that are multiplicative inverses of each other (modulo 2³²), then multiply by x to obfuscate and multiply by y to restore, all multiplications are modulo 2³² (source: "A practical use of multiplicative inverses" by Eric Lippert)

Variable-length numberic system method does not obey your "progression" requirement on its own. It always produces short arithmetic progressions. But when combined with some other method, it gives good results.

The same is true for the modular representation method.

Here is C++ code example for 3 of these methods. Shuffle bits example may use some different masks and distances to be more unpredictable. Other 2 examples are good for small numbers (just to give the idea). They should be extended to obfuscate all integer values properly.

// *** Numberic system base: (4, 3, 5) -> (5, 3, 4)
// In real life all the bases multiplied should be near 2^32
unsigned y = x/15 + ((x/5)%3)*4 + (x%5)*12; // obfuscate
unsigned z = y/12 + ((y/4)%3)*5 + (y%4)*15; // restore

// *** Shuffle bits (method used here is described in D.Knuth's vol.4a chapter 7.1.3)
const unsigned mask1 = 0x00550055; const unsigned d1 = 7;
const unsigned mask2 = 0x0000cccc; const unsigned d2 = 14;

// Obfuscate
unsigned t = (x ^ (x >> d1)) & mask1;
unsigned u = x ^ t ^ (t << d1);
t = (u ^ (u  >> d2)) & mask2;
y = u ^ t ^ (t << d2);

// Restore
t = (y ^ (y >> d2)) & mask2;
u = y ^ t ^ (t << d2);
t = (u ^ (u >> d1)) & mask1;
z = u ^ t ^ (t << d1);

// *** Subset parity
t = (x ^ (x >> 1)) & 0x44444444;
u = (x ^ (x << 2)) & 0xcccccccc;
y = ((x & 0x88888888) >> 3) | (t >> 1) | u; // obfuscate

t = ((y & 0x11111111) << 3) | (((y & 0x11111111) << 2) ^ ((y & 0x22222222) << 1));
z = t | ((t >> 2) ^ ((y >> 2) & 0x33333333)); // restore

You want the transformation to be reversible, and not obvious. That sounds like an encryption that takes a number in a given range and produces a different number in the same range. If your range is 64 bit numbers, then use DES. If your range is 128 bit numbers then use AES. If you want a different range, then your best bet is probably Hasty Pudding cipher, which is designed to cope with different block sizes and with number ranges that do not fit neatly into a block, such as 100,000 to 999,999.

Obfuscation is not really sufficient in terms of security.

However, if you are trying to thwart the casual onlooker, I'd recommend a combination of two methods:

• A private key that you combine with the id by xor'ing them together
• Rotating the bits by a certain amount both before and after the key has been applied

Here is an example (using pseudo code):

  def F(x)
    x = x XOR 31415927       # XOR x with a secret key
    x = rotl(x, 5)           # rotate the bits left 5 times
    x = x XOR 31415927       # XOR x with a secret key again
    x = rotr(x, 5)           # rotate the bits right 5 times
    x = x XOR 31415927       # XOR x with a secret key again
    return x                 # return the value
  end

I haven't tested it, but I think this is reversible, should be fast, and not too easy to tease out the method.

I found this particular piece of Python/PHP code very useful:

https://github.com/marekweb/opaque-id