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.

For example:

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…

  • 1
    $\begingroup$ If you use a 36-bit permutation you can encode to 6 6-bit characters, which will fill the character domain much better, seeing as a 32-bit permutation will still require the same. A 42-bit one will allow a 7-bit internal structure and encode to 7 characters. $\endgroup$ Sep 5 '14 at 8:35
  • $\begingroup$ To satisfy my curiosity I created the 42-bit cipher since I had some of the building blocks already created. It will encode to 7 chars just like an Imgur URL. How secure I do not know, but it is similar to the HIGHT cipher in structure. $\endgroup$ Sep 6 '14 at 11:17
  • $\begingroup$ The downside of 6-bit characters is that you need to use 2 symbols because three are only 62 alphanumerics. I think I'm going to use 40-bit permutations with 5-bit characters. $\endgroup$
    – hugomg
    Sep 10 '14 at 3:52
  • $\begingroup$ Just increment the counter till you get something without the non alphanumeric characters. You still get 3.5 trillion out of the 4.4 trillion to use, vs the 1.1 trillion for 40-bit, while saving 1 byte in the URL. 40-bit does allow an 8-bit internal structure however, which allows better s-boxes $\endgroup$ Sep 10 '14 at 4:01
  • $\begingroup$ Im growing fond of the 32 bit version. Lowercase letters don't scream as much as uppercase ones :) $\endgroup$
    – hugomg
    Sep 10 '14 at 4:51

Yes, it is possible to implement the primitive asked, with a 32-bit block cipher that is secure (indistinguishable from a random permutation) no matter how many input-output pairs are known, keyed with a fixed secret randomly-chosen key. That's a standard building block in Format Preserving Encryption.

One such block cipher is: Louis Granboulan and Thomas Pornin, Perfect block ciphers with small blocks (in proceedings of FSE 2007).

Emil Stefanov and Elaine Shi's FastPRP: Fast Pseudo-Random Permutations for Small Domains (Cryptology ePrint Report 2012/254) claim a speed improvement, and review some earlier work.

Update: Ricky Demer kindly pointed another recent paper: Ben Morris and Phillip Rogaway, Sometimes-Recurse Shuffle, Almost-Random Permutations in Logarithmic Expected Time (Cryptology ePrint Report 2013/560).

  • $\begingroup$ Thanks! I didnt know Format Preserving Encryption was a thing so it took a while to be able to understand the papers. They do seem to answer what I asked though and they also give lots of useful references :) $\endgroup$
    – hugomg
    Sep 6 '14 at 3:22

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.