Encrypting messages without revealing length?

Question

In various messengers, we have end-to-end encryption, making it hard to know what the message said.

But do these messengers have to pad the message to some maximum length every time, in order to hide the length of the message?

In a block cipher, there is a minimum length that you have to pad to, right?

My question is how do WhatsApp, Telegram, and Signal actually do this? How effective are they are hiding the length of the message?

And are there good ways to hide this type of metadata (length of the message and how often it is being sent) by doing some sort of steganography (eg posting message chunks to different endpoints depending on a hash of some variables available only to the participants, and sometimes also posting decoy garbage prefixed with “disregard:” in order to obfuscate patterns, etc.)

Answer 1

This is a complementary answer to the Model Nest's answer, and will concentrate on how to achieve the constant size for messages. We assume that the files have confidentiality, integrity, and authentication while sending/ receiving.

First of all, in the security proofs like the CPA game, we assume the messages have the same length, otherwise, the advantage of the adversary is 1.

With 10 MB file limit

• Encryption time

  Here we assume that the application limits the message size to 10MB. This makes 10485760 bytes and therefore one needs 655360 AES encryptions per file.

  If you have the AES-NI then the time is not the issue see AES-NI can reach 5.4107GB per second on my machine. That is far from the 10MB. Some ARM has the AES-NI instructions, and the performance is not included in this answer.

• Sending time The 4G LTE

  • Download: 20Mbps and theoretical ones of 150Mbps and it will take 4 seconds with 20Mbps to download
  • Upload: 8Mbps on average and 50Mbps that will make 10 seconds to upload.

If the message size is fixed to 10MB then the chatting will be slow and people will start to complain. An alternative method is using two sizes if the leaked information that is the distinction of a message is sent or a file is sent then this is applicable.

Therefore here we can say that the limit does not come from the encryption time but due to the network speed. 5G calculations are not included.

Padding options

• PKCS#7: When we talk about padding the first that comes to mind is the PKCS#7 padding. However, that is not applicable here since it can support up to 256 bytes since each byte represents the length of the padding.

• Zero one padding: This is fine as long as the underlying Encryption algorithm is CPA secure and the (Key,IV) is not reused as in AES-GCM. If used this padding will produce a cheap reveal of some part of the messages. One can use a nonce misuses resistant scheme like AES-GCM-SIV or a faster version AES-PMAC-SIV to mitigate this problem.

  SHA-3 padding is also applicable

• ANSI X9.23 with a little extension this padding can be used; the last 32 bits can represent the padding size and the space between the data and size is filled with 0.

• ISO 10126 This is similar to ANSI X9.23 except instead of filling with zero, random bytes are filled. This seems like the best candidate.

Results:

• We can hide the length of the messages with a prefixed size.

• The encryption time is not an issue if AES-NI is available.

• The upload and download time can be the issue of chatting.

  As a matter of the fact, constant size is achievable in secure message applications but not preferable for general users.

Answer 2

In a block cipher, there is a minimum length that you have to pad to, right?

A block cipher uses padding to make the plaintext a multiple of the block size. It isn't used to disguise the message length.

My question is how do WhatsApp, Telegram and Signal actually do this? How effective are they are hiding the length of the message?

It doesn't seem that WhatsApp is hiding message length.

And are there good ways to hide this type of metadata (length of message and how often it is being sent) by doing some sort of steganography (eg posting message chunks to different endpoints depending a hash of some variables available only to the participants, and sometimes also posting decoy garbage prefixed with “disregard:” in order to obfuscate patterns, etc.)

I suppose it depends on the particular case, but if you have a maximum message length that isn't too large, and your users can stomach the additional processing time, then you could simply pad all messages to the maximum length. But then you are only disguising message length to an extent (it is between 1 byte and maximum message length).

Extending beyond something like that to what you are suggesting depends even more on the particular case, and would probably impact the user experience. I mean, perhaps setting up some variation of onion routing and sending decoy messages every n seconds would work, but it would quickly drain the battery/etc.