I am searching for a secure algorithm to encrypt base62 (or any other base) data for ids in urls.

It should feature:

  • No blocksize etc, limiting the length of the message to a factor of n
  • If you have the decryted and the encrypted message you should not be able to guess the key
  • An avalanche effect
  • Any size of charset, not only 256 like in AES, DES etc.
  • High performance on modern CPUs

This is not required:

  • Streaming, it is only for small data

Is this possible?

  • $\begingroup$ I have a few ciphers like that, BUT they each have a very specific block size (35, 40, 42, 48 bits) and have i/o in 5 or 6-bit character sets, their purpose to be a secure permutation for URL generation from a counter $\endgroup$ – Richie Frame Nov 16 '14 at 11:23
  • $\begingroup$ Pastebin uses 8 base62 characters for his IDs. Does Pastebin uses random IDs which are also stored in the database? $\endgroup$ – user18296 Nov 16 '14 at 11:32
  • $\begingroup$ are you looking for format preserving encryption ? $\endgroup$ – sashank Nov 16 '14 at 14:52
  • $\begingroup$ they probably do not store the counter used to generate it, it is not a necessity. i do not know the precise method that pastebin and imgur use, or if it is cryptographically secure $\endgroup$ – Richie Frame Nov 17 '14 at 2:49
  • $\begingroup$ So, important question: is it required that the result remains the same size or is the ciphertext allowed to be larger than the encoded URL? $\endgroup$ – Maarten Bodewes Jun 6 '15 at 14:38

If you define your encryption to be $C=E_{62}(E_k(D_{62}(P)))$ and your decryption to be $P=E_{62}(D_k(D_{62}({C})))$ where $P$ is your encoded URL then you've brought back your problem to finding an encryption function for $l$ bits, where $l$ is the size of $D_{62}(P)$. After that you can "just" look for a Format Preserving Encryption primitive for those $l$ bits. If the encrypted URL is allowed to be larger than the unencrypted URL then you could use CTR mode with a nonce of 8 random bytes.

| improve this answer | |
  • $\begingroup$ An 8-byte random nonce has a birthday bound of only $2^{32}$, which doesn't offer a lot of margin unless encrypting very few items. I would be more comfortable with either a counter value or a 128-bit nonce. $\endgroup$ – otus Jul 7 '15 at 11:37
  • $\begingroup$ Also, would you mind defining your operators? $\endgroup$ – otus Jul 7 '15 at 11:38
  • 1
    $\begingroup$ $E_{62}$ is encoding of data, $D_{62}$ is decoding, while $E_k$ is the encryption transformation using the FPE or the CTR cipher. I thought these functions would be clear. The 8 byte IV is the absolute minimum which indeed carries a risk. This risk could be worth it if the amount of data is small ("it is only for small data" can either be read as small packets or a minimal amount of data). Of course if there are many packets then the IV/nonce should be larger as the chance of a collision of the counter rises with the amount of blocks due to the birthday "paradox". Thanks for the warning @otus. $\endgroup$ – Maarten Bodewes Jul 7 '15 at 17:55

If I'm understanding things right you want something that can encrypt data at abritrary size with high speed. You have several options here:

  • CTR mode. This turns any block cipher into a stream cipher allowing you to encrypt arbitrary amounts of data at high speeds. (cipher would be AES-128)
  • a dedicated streamcipher like Salsa20 or ChaCha. They are high-speed and can encrypt arbitrary amounts of data

The only thing you'd need is an unique IV

| improve this answer | |
  • $\begingroup$ CTR mode with truncated output has collisions $\endgroup$ – Richie Frame Jun 6 '15 at 3:38
  • $\begingroup$ @RichieFrame, Indeed if you truncate the output of the encryption of the counter it has indeed collisions after $2^{64}$ blocks and without the truncations collisions will occur after $2^{128}$ blocks. But the OP stated that's only for small amounts of data and hence collisions shouldn't be a problem if CTR is used as a proper stream cipher. $\endgroup$ – SEJPM Jun 6 '15 at 10:15

Your Answer

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