# If classical ciphers are used with compressed plaintext, how much does it make frequency analysis attack harder?

Classical ciphers, such as the Vigenère cipher, are weak and no longer used. They can be broken by using frequency analysis, which is a well-known fact.

However, frequency analysis often depends on the number of captured ciphertexts and/or their duplication. What if the ciphertext was compressed by an algorithm such as Huffman encoding，zlib, or lzma before encrypting the plaintext? For better security, assume there is no constant header, magic number, or any identifier in the plaintext.

How much more difficult does compression make attack by frequency analysis?

• Classical cryptography doesn't use bit strings, instead they use strings from some alphabet (perhaps with 26 characters, maybe more, maybe less). Are you assuming that we modify the compression to work with this alphabet? Mar 13 '15 at 21:45
• @poncho Yes. Apparently so. Aug 9 '15 at 16:16
• What is your motivation for this question? Because making it "more secure" doesn't make it "secure" in today's terms. Such a modification would do nothing against known plaintext attacks (the attacker can reconstruct the encoding from the plaintexts), and even that is not enough in today's sense. 5 sheets of paper are not more bullet-proof than a single sheet of paper.
– tylo
Mar 10 '20 at 0:06

Compression works by approximating an optimal code—one where if the probability of a given message is $$p$$, its encoded length is $$-log(p)$$. This means that the lengths of the encryptions of compressed messages potentially leak information about the plaintexts.

Also, the way a scheme like Huffman coding works is by outputting shorter code words for more frequent source symbols than for less frequent ones. This means that the relative frequencies of Huffman code words will be the same as that of the frequencies of the source symbols. It does nothing to disguise those frequencies.

A good real-life example to consider is attacks tht break the confidentiality of some encrypted voice-over-IP codecs that use variable bit rate encoding (which is a form of compression):

Despite the rapid adoption of Voice over IP (VoIP), its security implications are not yet fully understood. Since VoIP calls may traverse untrusted networks, packets should be encrypted to ensure confidentiality. However, we show that when the audio is encoded using variable bit rate codecs, the lengths of encrypted VoIP packets can be used to identify the phrases spoken within a call. Our results indicate that a passive observer can identify phrases from a standard speech corpus within encrypted calls with an average accuracy of 50%, and with accuracy greater than 90% for some phrases.

Frequency analysis requires a prior knowledge of the entropy of the plaintext data. For languages like English, the entropy of English is easily known to attackers.

However, the compression will change the entropy of the plaintext data. This means that the compressed data has a higher entropy (the compressed data is more random) than the original data. This is how compression works - it achieves a more concise representation of the data by increasing the entropy of the data.

This change in entropy when compression is used, makes the frequency analysis impossible for the attacker, given that they will not know what compression is used, or what entropy to use for their estimate when conducting frequency analysis on the compressed data.

Note that the ciphers should not be trusted - they may still be susceptible to other attacks, such as differential cryptanalysis, etc. This answer is only concerned with frequency analysis specifically.

• There is no deterministic algorithm, which "increases entropy" - it doesn't even make sense to think about entropy of a single message: the entropy is 0. What you mean is called the Kolmogorov complexity. But regarding the topic: A compressed text without the matching encoding table makes no sense. And if that is part of the text or publicly known, the compressed text is easier to break: The compression algorithm is based on frequency analysis and knowledge of it's result can be used.
– tylo
Nov 9 '19 at 16:44

Classical ciphers typically reveal the key effortlessly with even a small amount of known plain text. Most compressed file formats will reveal enough in their headers alone. Frequency analysis will not work well, definetly not easily on compressed data. But this does not make classical ciphers secure to use on compressed data.

Traditional encryption is weak and no longer be used. They can be easily broken by using frequency analysis is a well-known fact.

Im no crypto expert, so I cannot answer the full of your question-- but this part is not correct. Encryption using algorithms such as 3DES, RC4, AES, etc is secure to the point where it is not possible to determine from looking at a block of data whether it is random or encrypted. Further, if properly designed there will be an avalanche effect: a very minor change in key or plaintext will have a drastic effect on the encrypted text.

If an algorithm's output is attackable by frequency analysis, it is not suitable for production. I will note that there are some historical computer crypto algorithms (such as AES ECB) which HAVE been susceptible to frequency analysis; and when they are, they are marked as "not safe" and they fall out of use.

Regarding compression, if changing the plaintext increases the difficulty of cracking your encryption, then your algorithm is not secure. I will leave explanations for why that is to others with more knowledge on the topic.

• The OP is talking about classical ciphers, not modern ones. Mar 13 '15 at 19:00
• Additionally, you are mixing up things: first you list symmetric ciphers, then put that on equal footing like a mode of operation.
– tylo
Nov 9 '19 at 16:50