How to thwart a cleartext message's size?

Question

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!

Answer 1

Here is a question I don't find addressed in my cryptography books

That's because it's not cryptography per se. It's communications intelligence (COMINT) and traffic analysis. It may also relate to Pattern of Life (POL) analysis where they track your every move via what you do on a daily basis.

There is a surprisingly simple yet highly effective masking technique, in two flavours. You just transmit constantly (on average). So either burst mode, say a rapid 10Mbit burst every quarter of the hour, or constant mode at lower rate but transmitting all the time. These figures are chosen to suit the capacity of the communications channel and the data sizes. Packet ham radio might do 200 bits/s over 1000km, but ADSL might be 1MBit/s around the globe. Whilst this might seem exorbitant, standard BBC HD TV streams at 2.8 Mbit/s yet ADSL endowed people leave that on constantly. A consideration in this choice is that virtually all important communications are relatively short. This is a counter-intelligence messaging technique and not for sending ripped UltraHD movies.

Any genuine message is interleaved with the background transmissions and identified with some sort of header. A CSPRNG can be used as the source of the masking traffic. An issue here would be to ensure that the CSPRNG doesn't run out of entropy if you're transmitting at a nippy rate. Or you can send plain padding and then encrypt, again ensuring to not exceed safe encryption limits. As long as the genuine and fake bytes are seamless, Alice's N becomes invisible.

An additional benefit is that the frequency of interactions between Alice and Bob become unknown. This masks the inevitable increase in communications traffic approaching a particular event (clearly within the overall bandwidth agreed upon). You can also incorporate a one time pad system for the (shortish) genuine messages. The CSPRNG /padding conserves precious key material and creates a third benefit of unbreakable communication.

Whilst it would seem that this "constant on" channel infers a relationship between Alice and Bob, national metadata retention laws and subsequent analysis can already detect this. However, the more people that use masking, a quasi Metcalfe's law develops to thwart specifically identifying Alice and Bob out of the maelstrom.

Answer 2

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.

Answer 3

To answer this question we need better understanding of the distribution of N and the hiding requirement. Are you alllowed to leak something about the rough order of magnitude of N or nothing at all.

If you are not allowed to leak any information about N, each encrypted message you send must be at least the size of the maximal message $maxN$.

If in addition you don't have a reasonable bound on N you are out of luck.

If you are willing to leak some information about order of magnitude you can round up to the nearest bin. You can pad with anything for instance zeros before encryption which us the safe option.

It is worth perhaps mentioning some inferior techniques I have seen used:

Adding uniformly random length suffix usually does a poor job of hiding length(leaks a lot of information on order of magnitude or pads much more than needed).

Padding with random data after encryption: It's only cheaper than encryption if you use weak random source, and even with a strong but different cipher you are open to distinguishability attacks for no need.