I'm currently interested in the problem of generating random-looking URLs from sequential database IDs, like how they do it in link shorteners. One way to do this is to encrypt the sequential database ids using a 32 bit block cypher and base62 encode the result so it can be written to the URL.
foo.com/1 foo.com/2 -- Original sequential IDs foo.com/142365 foo.com/226340 -- Encrypt IDs using a permutation function foo.com/b2D foo.com/wse -- Encode in base62 format - looks random + compact.
Now here is the catch: Whenever we encrypt the a new database ID and publish the URL, that plaintext-ciphertext pair become public knowledge. Is it possible to create an encryption system that makes it hard to guess what will be the next URL we will generate? That is, can we make it so the attacker can't guess the value of $F(1000000)$ even if he knows the values of $F(n)$ for $n \leq 999999$?
Some things that I think are important to note:
- The cypher must have a 32 bit block size. Otherwise, the resulting URLs get too long.
- The secret key is allowed to be any size.
- Each number is only be encrypted once and all the messages I encrypt are 32 bits in length. (None of the stream-cypher stuff applies)
My actual use case – and most people's, to be honest – won't really need that kind of security. A bijective mapping from sequential IDs to URLs that looks scrambled at first glance is good enough. However, I am now curious if that unpredictability requirement is possible to achieve. In my searches, I found a lot of people saying that 32 bit blocks are too small due to the birthday problem but I am not sure that caveat applies here. On the other hand, none of the 32-bit block cyphers I found say anything about their resistance to known cyphertext attacks…