How to encrypt a short string and keep the length secret

Question

I need to encrypt relatively short strings (generally less than 100 characters). If possible, I want to avoid leaking the length of these strings. How can I do that?

The thing that came to my mind is to pad the text to 1 KiB with random data, separating the content from the padding with a 0x00 byte. Is this a good idea?

Answer 1

Instead of saving the padding length as rossum explained, you can also put a length encoding in front of your plain text. A standardized way to do this would be DER encoding (which uses a dynamic number of length bytes), but in your case you could also use a 2 byte short. Then just add 00h bytes padding up to X times the block size, and encrypt using a cipher without padding.

The advantage is that during decryption you can simply discard the bytes, and you don't need no unpadding mechanism, just discard any bytes behind the plain text.

This method is used e.g. in the PKCS#11 standard (for hardware tokens).

Answer 2

1: Your idea of padding the string in order to obscure its length is a good one.

2: The Java API already has encryption capabilities. I suggest using the Cipher class in the javax.crypto.* package. No need to use additional libraries.

Answer 3

Adding almost a kilobyte of padding will limit the types of padding you can use. The main thing is that the padding be cleanly removable. Using a 0 as separator will fail in 50% of cases, because the real text ends in a 0 itself. I would suggest one of these methods:

1 Bit Padding: add a 1 bit, and then pad with 0 bits for as far as you want. Remove all trailing zeros and the single 1 bit. In byte terms this is one 0x80 byte followed by as many 0x00 bytes as needed.

2 Byte Padding: pad almost to the end with zero bytes. Use the last two bytes to record the number of zero bytes added. Make sure you know if those two bytes are big endian or little endian.

Answer 4

Clearly you need to pad the plaintext before encrypting it.

Pad it to some fixed size – optimally this should also be a multiple of the block size (16 bytes are nowadays standard for block ciphers), so you don't have to pad again for encryption.

Make the padding removable. There are several methods of doing this:

• If you now that your message can't contain certain bytes or byte sequences, you can use a separator. A zero byte works if your plaintext contains only printable text in ASCII or some compatible encoding.

  This will not work if the plaintext can contain arbitrary binary data, if you don't escape it first. Not generally recommended.

• If your message has a certain internal structure which tells you when it is finished, you don't need a separator – simply parse it and stop when the message ends.

  Here you'll have to pay attention to buffer overruns and similar. Not generally recommended.

• Encode the length of the message at the start of the message. (Of course, this only works when you have the whole message before starting to encrypt, but for your short messages this seems doable.)

  This is also quite easy to implement.

• Encode the length of the message or the padding at the end of the padding. A popular version is the padding used in PKCS #5, which indicates the padding size repeatedly in all the bytes of the padding. (This limits you to maximally 255 bytes of padding, though.) You can use a similar scheme, indicating the padding size with two bytes.

  This has the advantage to be easy to strip off.

• Have the padding of some fixed format. Rossum's bit padding variant is this: add one one bit, then fill with zeros.

  This makes you parse the message from the end to find the start of the padding. Often backwards parsing is more complicated.

Whatever you do, the actual padding can then be either random, zero, or arbitrary (of course not for the versions with fixed padding format).

Then encrypt the message using a secure encryption algorithm and mode of operation (do not use ECB mode – it is generally broken, and even more in the case of some empty or otherwise fixed padding when you want to hide the size).

Then add authentication (a MAC such like HMAC), of the whole encrypted message. The receiver should reject the message if the MAC is wrong, and not even start decrypting then. Doing otherwise can give an padding oracle when an invalid padding is detected after decrypting, which can lead to loss of confidentiality.

Answer 5

The best thing to do with your strings will depend on what you are using them for.

According to Nate Lawson, who knows a lot more about this than either of us, you should generally use either SSL or GPG:

Designing a crypto protocol is extremely costly due to the careful review that is required and the huge potential damage if a flaw is found. Instead of incurring that cost, it’s often better to keep state on the server or use well-reviewed libraries that provide SSL or GPG interfaces. There are no flaws in the crypto you avoid implementing.