How to thwart a cleartext message's size? Here is a question I don't find addressed in my cryptography books:


let's say Alice want to send Bob a message of length N.
what is the proper way for Alice to hide N?


I am thinking Alice should do something prior to encrypting her message.
Let's say N is the length of Alice's cleartext message, along
with its cryptographic signature.

I guess Alice can prepend her N bytes with some M random bytes, and
append P random bytes at the end.
But, how to choose M and P?
Should they even be chosen according to N?

Thanks!
This is a complex question. There exists no formal treatment of this question and the parameters you choose will depend on your application. A method that is typically used is, like you said, to append some padding to your plaintext. Note that you don't need to both append and prepend; appending is sufficient. Also, the padding doesn't have to be random, it can be deterministic (for instance 0x0000 or something else that is convenient for your file format).

A method that is typically used is to split your data into certain prespecified buckets of a certain size; for instance 1KB, 10KB, 50KB, 1MB and 10MB. Then when your data is transmitted, you round up to the nearest bucket by appending padding.

A few years ago, I worked for the Twitter Product Security team where I performed length-based attacks and defences. This "bucket" technique is something the Twitter product security team does nowadays to avoid profile fingerprinting.

Here's the attack. Suppose I'm your ISP and I want to find out if a certain "suspicious" Twitter profile belongs to one of my customers (we suspect that this attack has actually happened in the real world with devastating consequences [0]). The way I do this is I monitor all of the HTTPS responses that contain the twitter.com SNI. I look at the length of these responses and I count how many times you visit a page of a particular length during a short period of time, say, a few minutes. Specifically, I look at "bursts" of responses which correspond to a particular mouse click and contain multiple files such as HTML, CSS, and JPG. For all of these files, I can calculate the length of the ciphertext. In case of newest HTTPS protocol versions, I can only get a global length for this particular "burst", but this should be enough to fingerprint.

The length I see you visit most often likely corresponds to the length of the page corresponding to your own twitter feed (i.e., what you see when you go to twitter.com). Now, because the "suspicious" Twitter profile I'm interested in has a public list of people they follow, I can reconstruct that feed, because all it contains are tweets by the people they publicly follow (assuming here that secret tweets are rare). In this reconstruction, I know which avatars of which people should appear in the feed. Those will have to be transmitted as images over HTTPS and their sum is added to what I see. I can also reasonably predict if and when some of them are being cached so that they're not retransmitted. Therefore, if the page you visit most often has a similar length to the feed of the "suspicious" Twitter profile feed, I can deduce that it's you.

In the bucket defence, avatars always have a certain size among 10 different sizes. The way this is achieved is that padding is added as needed. There's also a maximum size that you can't upload beyond.

If you have rigorous requirements about what kind of thing you want to hide, you can look at differential privacy [1]. This can help you understand exactly how much noise you need to add in order to confuse the adversary to a certain degree. It will also allow you to quantify how many queries the adversary would need to perform in order for them to get to your length within a specified margin of error. This depends on your application. If you provide more comments about what you're trying to do and what your threat model is, it would be helpful.

There are some details related to this attack that are interesting and can cause engineering challenges, but they can be overcome. The first is that stream ciphers preserve byte length between plaintext and ciphertext, but block ciphers do not preserve it exactly. This can cause problems in measurements, but they only delay the attack, because there is still enough information to be gained if you just round up to the closest 256th bit. This is something we explored in our work [2] where we augmented BREACH to work against AES and not only RC4. The second is that data is compressed and compression is a complex thing which composes multiple algorithms which can compress across different sources of data. Again, this may make things more difficult, but still allows statistics to be run. Last, there's noise in all of these pages, such as ads, recommendations and so on that the adversary cannot predict. But these do not affect the page lengths dramatically, and in any case they can be modelled as "uniformly random noise" which, on average, adds a constant length to the response. In fact, the existence of appropriate compression and the adversarial manipulation of noise can allow an adversary to vastly improve their attack. For some of the techniques we developed to this end, as well as some defences, see our collaborative work at [3, 4, 5, 6].

For a formal treatment, you can consult our incomplete and unreadable manuscript on the theory [7]. Sadly, I do not think this manuscript will ever be finished and I don't think I can take the security games and proofs to where I wanted.

[0] McGahan, Jason. "She Tweeted Against the Mexican Cartels, They Tweeted Her Murder". October 2014. Accessed May 2018.

[1] Dwork, Cynthia. "Differential privacy: A survey of results." International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2008.

[2] Karakostas, Dimitris and Zindros, Dionysis. "Practical New Developments on BREACH". Black Hat Asia 2016. Presentation.

[3] Grigoriou, Dimitris. "Extending the Rupture compression attack framework against real world systems". University of Athens 2017.

[4] Karakostas, Dimitris and Kiayias, Aggelos and Sarafianou, Eva and Zindros, Dionysis. "CTX: Eliminating BREACH with Context Hiding". Black Hat Europe 2016.

[5] Karakosats, Dimitris. "Probabilistic Attacks Against Compressed Encrypted Protocols". National Technical University of Athens 2016.

[6] Sarafianou, Eva. "Creating a Tool for Attacking Compressed Encrypted Protocols". National Technical University of Athens 2017.

[7] Karakostas, Dimitris and Kiayias, Aggelos and Zindros, Dionysis. "On the (in)security of encryption over compression in TLS". Unfinished manuscript. Source.