human readable unpredictable & no collision uid based on time

Question

I need to create an unpredictable uid based on time. I plan to allow it to work during a time frame of 100,000,000 seconds. So the seconds will go from 00000000 to 99999999.

I need an algorithm that will "convert" the seconds to another 8 digit number. 8 digits in, 8 digits out. Example : algorithm(00000001) returns 87981278 algorithm(00000002) returns 57941047

The returned number must be unpredictable and there musn't be collisions

If we run the algorithm with the 100,000,000 possible number, we will get 100,000,000 different results (sort of randomization of the 100,000,000 possibilities)

The security does not need to be bulletproof. I just want to avoid id's being in sequence ...

It has to be human readable ... people will need to manually type this id, so big hashes aren't an option.

Any direction you can point me to ?

Thx !

Answer 1

A bijective function that maps elements from one set to random elements from the same set is called a permutation. A pseudorandom permutation (PRP) is a family of permutations where a (uniformly) randomly chosen member of that set is indistinguishable from an ideal random permutation.

Block ciphers are modeled as PRPs. Choosing a secret unpredictable key is analogous to choosing a random member of a PRP. If you were to encrypt a sequence of 128-bit blocks $(0, 1, 2, ... 2^{128} - 1)$ using a 128-bit block cipher then the sequence of ciphertext blocks would contain every number in the range $[0, 2^{128}-1]$ exactly once in a (pseudo)random order. These new blocks can be converted back to the original values if you know the key, by decrypting each block.

Using a block cipher (with no padding or mode of operations^*) gives you a function that is collision free. The relationship should be unpredictable to anyone that doesn't know the key.

If you look at block ciphers then you'll notice that almost all of them work on a fixed number of bits. The range of the inputs/outputs are a power of two. "Format preserving encryption" (FPE) is the name given to encryption methods designed to work on data of a specific format and leave ciphertext in the same format as the plaintext.

One generic FPE scheme you can use to create a PRP with a range that isn't a power of two is to create a kind of Feistel cipher. (Note that you should encrypt the numeric value of a timestamp, not the ASCII value.)

Example

You need two variables. Split a 8 digit number into two 4 digit numbers as follows.

x = n % 10000;
y = n / 10000;

Then you'll want to perform four rounds like so

x = (x + F(k, 0, y)) % 1000;
y = (y + F(k, 1, x)) % 1000;
x = (x + F(k, 2, y)) % 1000;
y = (y + F(k, 3, y)) % 1000;

Where F is some function that returns a random number in the range [0, 9999], k is a secret key, and the second parameter of F is the round number.

Then convert x and y back to a 10 digit number. For example,

n = 10000 * y + x;

F needs to have a range that is a multiple of 10,000. If security is not a concern then you can just return a random 64-bit number mod 10,000. There is some bias because 10,000 does not divide the range evenly, but it wouldn't be noticeable to casual observers. F could be defined like

$$F(key, round, n) = \operatorname{mod}(\operatorname{AES}_{key}(n + 10000 \cdot round), 10000)$$

^{_{* Normally block ciphers are used with a mode of operation and a single use initialization value. For normal encryption use a standard authenticated mode of operation. Do not use ECB.}}

Answer 2

The problem can be reduced to generating a random permutation of the numbers 0 to 99,999,999. One way to do it is to use something like the Fisher-Yates shuffle but this will require you to store 12,500,000 bytes (one bit for every possible number in your sequence). Adapted for your use, what you would do is every time you want a number for your sequence, the Fisher-Yates shuffle would have you:

1. Pick a random number k from 1 to the number of unstruck numbers remaining.
2. In your your 100 million bit array, set to 1 the kth remaining 0 bit. Use the position of that bit as the hashed number.

I can't think of a way to assure no collisions without using that much storage.

A cheap solution if you don't mind getting only a small subset of the 100 million factorial possible sequences would be to choose some number relatively prime to 100 million and repeatedly modulo add it to generate your sequence. If you choose a big enough number it will look unpredictable to a human. In abstract algebra terms, we choose a generator of the cyclic group of order 100 million and use it to generate all the elements of the group.