2
$\begingroup$

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?

$\endgroup$
  • $\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$ – Kim-Yannick Jürs 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
1
$\begingroup$

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.

$\endgroup$
  • $\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
0
$\begingroup$

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

$\endgroup$
  • $\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

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