0
$\begingroup$

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 !

$\endgroup$
  • $\begingroup$ Is this supposed to be a publicly executable algorithm? $\endgroup$ – Maeher Mar 20 at 11:15
  • $\begingroup$ No. It will run on a kiosk and the software will not be distributed. $\endgroup$ – djib Mar 20 at 13:27
  • $\begingroup$ Not my field, so just a link - en.wikipedia.org/wiki/Format-preserving_encryption#Algorithms. You can even have a secret key for it. $\endgroup$ – Paul Uszak Mar 20 at 13:40
  • $\begingroup$ If p(collision) < $10^{-64}$ you can say that it's negligible, therefore kinda 0. So you don't need a previous record of UIDs and don't need to use time. You can use entropy/randomness as in some IV generation. $\endgroup$ – Paul Uszak Mar 20 at 14:19
  • 1
    $\begingroup$ @djib In that case, what you're looking for is a small domain pseudorandom permutation. Something like eprint.iacr.org/2012/254.pdf $\endgroup$ – Maeher Mar 20 at 14:42
0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your comment. If i understand it right, this imply having some kind of conversion table. That's what i wanted to avoid. + There is no record of previously given codes. That's why it must be time based. $\endgroup$ – djib Mar 20 at 13:28
  • $\begingroup$ Added an alternative cheap solution. $\endgroup$ – 蛟龍Stormwyrm Mar 20 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.