6 ms·

Imagine a voice call, using a variable-bitrate codec, broken into small packets (not necessarily over the internet), of interest to a passive eavesdropper who c

Imagine a voice call, using a variable-bitrate codec, broken into small packets (not necessarily over the internet), of interest to a passive eavesdropper who cannot decrypt the content, but can observe metadata: the timing of packets and their sizes. Feed that information into a prebuilt phoneme-in-context model trained on that codec and language, and said eavesdropper could probably reconstruct a pretty good estimated transcript - different phonemes compress differently. There is no reason this would not work in bulk: I am under the impression GCHQ have done a fair amount of research in this area, for example.

belorn 10y ago
Thanks, its good to have specifics when thinking about security. I would guess that the phones and voip is a perfect target to do this, as those system are often designed to filter out noise. I guess it also would be almost impossible to use this to transcribe a encrypted movie or music, as the unpredictable sounds would break the prediction model.
kbenson 10y ago
So, it's not just compression per se, but compression plus real-time plus some knowledge about the underlying information. These sorts of attacks don't matter against a compressed and then encrypted file of indeterminate data, correct? Similarly, an amalgamation of many types of data, such as a disk or archive?
- danbruc 10y ago
  If you know absolutely nothing about the uncompressed original, then it seems indeed pretty hard to infer anything from the compressed version. But as soon as you know something, for example the rough size of the uncompressed original, you can for example start to infer that the content is either more like AAA or more like ABC because repetitions will compress better. And in reality it is really unlikely that an attacker knows nothing at all about the content. You know the type of data, you know what the header structure of the file format looks like. Or you could try to learn something from the statistics of the observed messages. Maybe the data contains a time stamp that correlates with the time you observe the message. The possibilities are endless.
  - kbenson 10y ago
    Sure, but isn't there more implied by what you just said? It's not just that you know the size, but if you know the header format, then you also know the type (which you might). But, I'm not sure how much more of less information compression provides for non-trivial size files. Where individual packets are encrypted, you have quite a bit of information. Where you have one file of non trivial size, there is much less information exposed. For example, you know its type, and it's 150KB. Even if you know it's a text document, or a WAV file, or bitmap, I think you get far less information from the compressed version than from the non-compressed version. The non-compressed version of the text document may give you approximate word count, and the WAV file will give you some probable lengths of the recording at common sampling rates, and the bitmap will give you some probable dimensions. Compressed versions hide this information within the natural variance of the compression. The problem seems less to do with compression, and more to do with splitting larger data (or streams of data) into smaller chunks to encrypt, which in itself loses some of the benefits of hiding information in the variance of the data presented. Compression seems to exacerbate this situation by amplifying variances in very small data sets in a way that yields additional information, but it seems to me that's just a natural progression of encrypting very small amounts of data being not nearly as effective as large amounts of data. At least, that's what I can intuit about the situation. It may be partly (or totally) wrong given some more advanced security theory (I am not a security professional).
- cellularmitosis 10y ago
  Thank you, that was the tldr I was looking for in this thread.
smaddox 10y ago
Could this threat be neutralized by salting before compressing?
- IncRnd 10y ago
  No. Salting is to keep stop pre-image attacks in encryption. It doesn’t affect compression.
  - crpatino 10y ago
    And bottles are used for holding liquids rather than smashing heads... until you find yourself in a bar fight. I might be wrong, but I think the parent had something like this in mind: Assuming you are encrypting with AES-CFB your each plaintext block P[i] produces a ciphertext block C[i] (with key K and initialization vector IV) according to rule: C[0] = AES_encrypt(K, IV) ^ P[0], C[i] = AES_encrypt(K, C[i-1]) ^ P[i]. Given that IV is assumed to be known by the attacker, if the plaintext is a vanilla-compressed stream, it is more likely than not that most of bits in P[0] are going to be known as well, which might allow some sort of prunned brute-force attack on key K, given a small set of (C[0] ^ P'[0]), for all P'[0] that satisfy the known bits in P[0]. This particular implementation would benefit then from adding a pseudorandom P[0] block (a "salt", if I understood correctly) that the receiver is to discard on arrival. I don't know enough cryptanalysis to tell if the above scenario is valid or not, but it sounds like a legitimate question at least.

belorn 10y ago

Thanks, its good to have specifics when thinking about security. I would guess that the phones and voip is a perfect target to do this, as those system are often designed to filter out noise. I guess it also would be almost impossible to use this to transcribe a encrypted movie or music, as the unpredictable sounds would break the prediction model.

kbenson 10y ago

So, it's not just compression per se, but compression plus real-time plus some knowledge about the underlying information. These sorts of attacks don't matter against a compressed and then encrypted file of indeterminate data, correct? Similarly, an amalgamation of many types of data, such as a disk or archive?

danbruc 10y ago
If you know absolutely nothing about the uncompressed original, then it seems indeed pretty hard to infer anything from the compressed version. But as soon as you know something, for example the rough size of the uncompressed original, you can for example start to infer that the content is either more like AAA or more like ABC because repetitions will compress better. And in reality it is really unlikely that an attacker knows nothing at all about the content. You know the type of data, you know what the header structure of the file format looks like. Or you could try to learn something from the statistics of the observed messages. Maybe the data contains a time stamp that correlates with the time you observe the message. The possibilities are endless.
- kbenson 10y ago
  Sure, but isn't there more implied by what you just said? It's not just that you know the size, but if you know the header format, then you also know the type (which you might). But, I'm not sure how much more of less information compression provides for non-trivial size files. Where individual packets are encrypted, you have quite a bit of information. Where you have one file of non trivial size, there is much less information exposed. For example, you know its type, and it's 150KB. Even if you know it's a text document, or a WAV file, or bitmap, I think you get far less information from the compressed version than from the non-compressed version. The non-compressed version of the text document may give you approximate word count, and the WAV file will give you some probable lengths of the recording at common sampling rates, and the bitmap will give you some probable dimensions. Compressed versions hide this information within the natural variance of the compression. The problem seems less to do with compression, and more to do with splitting larger data (or streams of data) into smaller chunks to encrypt, which in itself loses some of the benefits of hiding information in the variance of the data presented. Compression seems to exacerbate this situation by amplifying variances in very small data sets in a way that yields additional information, but it seems to me that's just a natural progression of encrypting very small amounts of data being not nearly as effective as large amounts of data. At least, that's what I can intuit about the situation. It may be partly (or totally) wrong given some more advanced security theory (I am not a security professional).
cellularmitosis 10y ago
Thank you, that was the tldr I was looking for in this thread.

smaddox 10y ago

Could this threat be neutralized by salting before compressing?

IncRnd 10y ago
No. Salting is to keep stop pre-image attacks in encryption. It doesn’t affect compression.
- crpatino 10y ago
  And bottles are used for holding liquids rather than smashing heads... until you find yourself in a bar fight. I might be wrong, but I think the parent had something like this in mind: Assuming you are encrypting with AES-CFB your each plaintext block P[i] produces a ciphertext block C[i] (with key K and initialization vector IV) according to rule: C[0] = AES_encrypt(K, IV) ^ P[0], C[i] = AES_encrypt(K, C[i-1]) ^ P[i]. Given that IV is assumed to be known by the attacker, if the plaintext is a vanilla-compressed stream, it is more likely than not that most of bits in P[0] are going to be known as well, which might allow some sort of prunned brute-force attack on key K, given a small set of (C[0] ^ P'[0]), for all P'[0] that satisfy the known bits in P[0]. This particular implementation would benefit then from adding a pseudorandom P[0] block (a "salt", if I understood correctly) that the receiver is to discard on arrival. I don't know enough cryptanalysis to tell if the above scenario is valid or not, but it sounds like a legitimate question at least.