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

But, the frequency analysis often depends on the number of captured ciphertext, and/or the duplication of the text. What if the text was compressed by some types of algorithms (such as Huffman encoding,zlib or lzma) before encrypting plaintext? For better security, assume there is no constant header, magic number, or any identifier in the plaintext.

How much difficulty was increased for frequency analysis attack?

  • 2
    $\begingroup$ 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? $\endgroup$ – poncho Mar 13 '15 at 21:45
  • $\begingroup$ @poncho Yes. Apparently so. $\endgroup$ – 比尔盖子 Aug 9 '15 at 16:16

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.

  • $\begingroup$ 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. $\endgroup$ – tylo Nov 9 '19 at 16:44

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.