What encryption schemes to hide the plaintext length exist besides padding?

From this answers comments a statement came up about padding that I don't understand: "If we need to keep the length of the plaintext confidential to some degree, there are better methods."

Are there any methods of hiding the plaintext length besides padding?

Assuming:

• The data to be sent is incompressible.
• If Steganography is used then leaving random data unchanged is equivalent to padding with random data.
• Plaintext length and plaintext rate are related, |2x| every hour is equivalent to |4x| every two hours.
• I think fgrieu was referring to padding obligatory for CBC mode (say, PKCS#7 padding), which operates on messages of lengths that are integer multiples of 128 bits. I don't think he was objecting to the concept of padding in general. If you're extremely bandwidth-constrained, you might want to pad all messages up to exactly 187 bits. You can do that with AES-CTR, but not AES-CBC. But I'll let him speak for himself to answer this. – Squeamish Ossifrage Apr 7 '18 at 8:23
• You can also use a constant stream of message fragments (which is basically just another padding scheme). This not only targets message length detection but also traffic patterns. – eckes May 13 '18 at 4:26

There are two basic ways to hide the length of a message. And one probably bad way.

1. Expand (pad with non-message bytes) the message to a constant length. Or multiple of a large constant.
2. Shrink the length of a message to a constant or multiple of a large constant.

Fgrieu is definitely talking about padding on a block cipher level. CBC mode leaks the length of a message accurate to within one multiple of the block size (say 128 bits). CTR mode leaks the length accurate to within one byte (normally) or (potentially) one bit. 128 bits is too accurate a level to hide the plaintext length well.

There are a lot of parts to the conversation. What you're thinking of is probably what I listed as method one. That's a different type of padding. Over a low bandwidth channel this method is likely unusable. With unconstrained bandwidth or for data at rest this type of padding works fine. There are just the obvious problems of wasted bytes and what to do if you go over a constant length.

Method 2 seems impossible. You can't shrink a message that's uncompressible. If you can compress data, though, and then you use method 1 to pad the compressed data, then this doesn't leak any more information about the message than not compressing/padding does. Uncompressed unpadded messages leak the length of a message's encoding in bytes and puts an upper bound on what the entropy of the message is. Using compression and padding leaks only an upper bound on the entropy of the message.

Where he notes that compression can be dangerous he's referring to things like VOIP that do not use constant bit rate compression. If you use variable bit rate with real time audio then you leak how compressible the audio data is. Silence is highly compressible so a passive observer would notice short packets and conclude that the person is probably silent. (Or if the packets are frequent and shorter the silence between words/syllables.) And it's possible that harder entropy/packet-length analysis could reveal something more valuable. It's probably harder to do a distinguishing attack on someone saying spoken digits. One might be able to steal ID numbers or credit card information sent through the channel that way.

A constant bit rate encrypted protocol can either use no compression (and use more bandwidth) or use lossy compression that keeps only a constant amount of information. Constant bit rate compression will discard information if a signal contains more information than can fit in a constant signal-bandwidth (meaning a symphony would not sound right) and it transmits more data than necessary when a signal is less complex. (For good bit rates you won't notice a difference in quality between no compression, lossless compression, and constant bit rate compression of voice audio data.)

Note fgrieu also says "duration of encryption/decryption will leak some indication about the nature of plaintext". This is another problem. If your constant bit rate compression algorithm isn't also a constant time algorithm, then data related to message entropy is leaked via packet timing unless you transmit infrequently enough to transfer at fixed intervals.

If you're transmitting say HTTP data instead of a signal you can reduce to constant bandwidth, then compression can be dangerous. BREACH and CRIME are examples. Both are active attacks that exploit partial known plaintext data and partial chosen plaintext data. You could steal cookies if the attacks work.

Those types of attacks are a good reason to disable compression on the protocol level. Not all compression is bad. If you're a website serving static constant and send no cookies to steal, then it doesn't make a difference whether you serve compressed data or not. (It's still probably safer to recommend compressing at a file level.) For a public, crawlable, static websites that don't perform message length padding (specifically to defeat message length leaks) it's simple for a passive observer of a network to eliminate the secrecy you expect from encryption. Such an attacker can crawl every page of the static website, build a database that relates paths on a website to the length of the pages returned by a query for that path. If there is one file on the website that is about 25.33 megabytes and you see the server send about 25.33 megabytes to the client over a short period of time, this will give them a big clue concerning what specific content you are viewing on the website. This type of attack works whether you're sending an uncompressed file, an uncompressed file compressed at the protocol level, or a pre-compressed gzip file; as long as the stream lengths are fairly distinct.

There are two more, more advanced, methods you could use that are a combination of methods 1 and 2. If you don't want to leak metadata such as when you're communicating with other computers, the length of the message you want to send, or the messages entropy, then you can build a communications channel that sends fixed size packets at fixed intervals regardless of how the channel is being used. You put message data into a first in first out queue. When its time to send a packet, then take out as much as you can up to the packet length minus say a byte, set the first byte of a packet to the number of message bytes, set the remaining packet bytes to zero, and encrypt the entire packet, including the length field and the zero padding. This scheme pads when you're transmitting less data than there is available bandwidth and chops messages into smaller constant size segments when you're transmitting faster than bandwidth allows. This is analogous to the purpose number stations probably serve.

The second advanced scheme I can think of is to get together a group of friends you trust and agree to send your message data all at the same time from the same computer. Each sender uses their own personal secret key but the entire aggregate of encrypted messages gets sent to every recipient. The recipients try decrypting every message addressed to them and throw out data they can't decrypt. If Alice and Bob trust each other not to leak their personal message length and they're addressing two recipients they trust not to leak their message length, then instead of leaking $|M_A|$ and $|M_B|$ only the value $|M_A| + |M_B|$ leaks. The RetroShare and ZCash projects may do something with a similar philosophy, but for anonymity purposes instead. I'm not sure about them.

• A good read, your second last paragraph could possibly do better sending random data instead of encrypted zero padding, for cases where random data isn't too expensive and the padding gets huge enough to create a problem for your encryption method (for CBC "2^32 blocks or so", for a paper based OTP way less) – daniel May 8 '18 at 9:29