2
$\begingroup$

I want to be able to encrypt some data like [email protected]|1234|A in a form that I can send to a user as a clickable link like:

https://example.com/click/this/NiUGgvamNOVmI1SzlTN0ZIRlQ0WklCazI3LzRxY09RVFRjOTByZ1o1OFJyT0lUeWd3PQ2....

Then the user clicks the link and when I receive the token, I can decrypt it and operate on the data.

I'm using the RijndaelManaged cipher, with a password and salt, and then Base64 encoding and then UrlToken encoding it, to avoid characters that would cause trouble in a url.

This all works fine, but it creates really long tokens, about 4 times the length of the original data, which makes sense, as it's smearing the information across all 256 possible bytes and then reducing to only 64 possible bytes for output.

What I am wondering is if there's a way to encrypt the data, possibly not as securely, but enough for limited application, that would not be 4 times longer than the input string. Could there be an algorithm that encrypts text AS text and without requiring vastly more size?

$\endgroup$
3
  • 1
    $\begingroup$ RijndaelManaged? Wow? What is the block size, 256? Use CTR mode for any block cipher, done! CTR mode doesn't require padding, so ciphertext size equal to plaintext size + IV $\endgroup$
    – kelalaka
    Apr 13, 2021 at 18:38
  • 1
    $\begingroup$ Basically RijndealManaged will just perform AES by default (although block sizes of 192 and 256 seem available as well, and the other 32 bit increments are not). There seems to be an unhealthy tendency to go for implementation classes instead of e.g. Aes.Create() although different platforms may have different sets of classes. $\endgroup$
    – Maarten Bodewes
    Apr 14, 2021 at 11:33
  • 1
    $\begingroup$ The base64url scheme that you should be using only has a 33% expansion rate. The rest is either static overhead (IV, authentication tag) of implementation mistakes such as using Unicode encoding (a misnomer of UTF16LE for our non-programmers) or performing base64 encoding followed by URL encoding. Presuming symmetric encryption of course. $\endgroup$
    – Maarten Bodewes
    Apr 14, 2021 at 11:37

2 Answers 2

4
$\begingroup$

TL;DR You should use format-preserving encryption which is designed to solve your problem.

There are various solutions some of which are easier than others to implement. I'll estimate their sizes based on your example token and url.

Some less than perfect solutions

As suggested in the comments, a bitwise stream cipher (such as ChaCha) or block cipher in streaming mode (such as AES-CTR) followed by base 64 encoding and url tokenising will only make your string about 42% longer plus any IV overhead. You may or may not want to worry about the ability of the user to modify the data. A user who can identify their token data could then forge tokens of the same or shorter length. Estimated token length with 128-bit IV: 61 characters. Estimated url length: 92 characters.

By adding a MAC you can defend against token manipulation but add another 21-22 characters to both lengths. Modern authenticated encryption methods may integrate authentication codes automatically.

You can shave off some characters with shorter IVs and MACs, but I wouldn't recommend going below 64-bits. These would save you 10-11 characters. Estimated token length with 64-bit IV: 50 characters (61 with 64-bit MAC). Estimated url length: 81 characters (92 with 64-bit MAC).

If we assume that your tokens use a character set of size 65 {A-Za-z0-9@|.} You could index the set and use a mod 65 stream cipher which would preserve the character set. Again IVs and MACs would be advisable, but could be expressed in the character set. There aren't any off the shelf mod 65 stream ciphers, but one could be constructed based on established stream cipher designs. Estimated token length: 40 characters (52 with short MAC) Estimated url length: 71 characters (73 with short MAC)

My laptop browser has a 65 character address bar and so I like urls with fewer than 64 characters to inhibit malicious url suffixes such as @http://evil.com/malware.exe. None of these solutions manage to achieve this for your example.

The designed and standardised solution

You can create url-friendly tokens and then use format-preserving encryption for 0 overhead. NIST have a standard for FPE and googling for "FF3-1 open source" should find an implementation in your language of choice. Estimated token length: 27 characters Estimated url length: 58 characters

58 character urls are still longer than the address bar on my phone browser, but this is still pretty good.

$\endgroup$
4
  • $\begingroup$ Actually, ChaCha produces 512-bit per counter, not a bitwise cipher. FF3-1 also has an overhead as 8-times slower to the cipher used. AES-NI with CTR then Base64 will be much faster. No wasting energy! $\endgroup$
    – kelalaka
    Apr 13, 2021 at 20:13
  • 2
    $\begingroup$ By bitwise, I mean that the stream is combined with bitwise XOR and there’s no obligation to use the full 512 bits of ChaCha output. I agree that FPE is slower. It does however prevent someone who knows that their token is [email protected]|1234|A from forging a token for [email protected]|9876|X. Both power and forgery could be relevant to the solution. $\endgroup$
    – Daniel S
    Apr 13, 2021 at 20:22
  • $\begingroup$ CTR and ChaCha by themselves not authenticated, which I think makes them a risky recommendation without lots of extra information about the application. In particular, lay developers extremely often assume that encryption guarantees authenticity. $\endgroup$ Apr 14, 2021 at 0:24
  • $\begingroup$ @Luis Casillas: I agree that stream ciphers are not a good choice, but wanted to acknowledge the suggestion. For similar reasons I did not mention mod 65 stream ciphers. I'll tidy up to make some of the issues clearer. $\endgroup$
    – Daniel S
    Apr 14, 2021 at 6:04
2
$\begingroup$

The way the encryption and the encoding parts work really are orthogonal problems, with orthogonal solutions.

First: You want to make sure your plaintext strings (e.g. [email protected]|1234|A are represented in binary with a reasonably compact character encoding. UTF-8 is likely just fine, just be sure you're not for example encrypting something like the internal UTF-16 representation some languages use (e.g., Java).

Second: Lots of ciphers feature plaintext expansion, which is the property that can produce ciphertexts longer than the input plaintexts. You almost certainly don't want to completely eliminate expansion because you almost certainly want (a) non-deterministic encryption (encrypting the same message twice with the same key should produce different ciphertexts; this often requires an IV or nonce value to be sent with the ciphertext) and (b) authenticated encryption, which generally requires some fixed expansion, but given how you wish to minimize the size of short messages, you want to make sure you choose a cipher whose expansion isn't more onerous than it needs to be.

(Advanced topic I don't want to get into: it could possibly be feasible to reduce the fixed overhead of authenticated encryption by using short tags. It's advanced because the security analysis can get a bit complicated.)

Third: Instead of URL-encoding a regular Base64 text, there are special, URL-compatible modified versions of Base64:

Using standard Base64 in URL requires encoding of +, / and = characters into special percent-encoded hexadecimal sequences (+' becomes %2B, / becomes %2F and = becomes %3D), which makes the string unnecessarily longer.

For this reason, modified Base64 for URL variants exist (such as base64url in RFC 4648), where the + and / characters of standard Base64 are respectively replaced by - and _, so that using URL encoders/decoders is no longer necessary and has no impact on the length of the encoded value, leaving the same encoded form intact for use in relational databases, web forms, and object identifiers in general. Some variants allow or require omitting the padding = signs to avoid them being confused with field separators, or require that any such padding be percent-encoded. Some libraries will encode = to ., potentially exposing applications to relative path attacks when a folder name is encoded from user data.

The neat thing about this is that you can implement these with textual substitution on regular Base64 strings.

$\endgroup$
2
  • 1
    $\begingroup$ Java doesn't always use 16 bit encoding anymore. That's an implementation detail and it isn't exposed to the user. You can of course retrieve char and int (for a full codepoint) from a string or convert to char[] but that will still not get you the bytes. On the other hand, Mickeysoft created the ill named Unicode encoding which is usually UTF16LE (nobody uses Mickeysoft on a big endian machine, so I guess the LE part is pretty sure). $\endgroup$
    – Maarten Bodewes
    Apr 14, 2021 at 11:50
  • $\begingroup$ Now that .NET is fully open source, is it true that nobody is using it on a big endian machine? Not relevant to me, as I'm using Windows, but now I'm curious. $\endgroup$ Apr 15, 2021 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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