5
$\begingroup$

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?

$\endgroup$
3
  • 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, 2015 at 21:45
  • $\begingroup$ @poncho Yes. Apparently so. $\endgroup$ Aug 9, 2015 at 16:16
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Mar 10, 2020 at 0:06

5 Answers 5

1
$\begingroup$

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.

$\endgroup$
1
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\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, 2019 at 16:44
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

When I initially asked this question, my motivation was a thought experiment: Could a cryptographer from the early 20th century break the "Rube Goldberg" cipher machine in my question? At that time, I knew little about cryptography. Several years later, I've learned a lot about security, and now I can answer my own question.

Data compression, especially when an unknown dictionary is used, appears to be already an effective method of data obfuscation by itself. It, by no means, provides real security by modern standard, but it does make cryptanalysis a lot harder than a classic substitution cipher.

Recently, there was a real-world attack of this nature during the reverse engineering effort of Intel ME firmware, providing a good case study. Intel ME is a coprocessor on modern Intel CPUs. Because it can perform many low-level hardware operations, it was seen as a huge attack vector and attracted many critical examinations by security researchers. CPU initialization and bring-up are the most critical functions executed by Intel ME, however, their corresponding firmware modules, BUP and KERNEL were compressed by Huffman encoding with an unknown dictionary. It made analysis impossible for a while before it was cracked using a known plaintext attack, as described by the researchers in this article.

  1. It was discovered that several modules were have been compressed by LZMA and Huffman simultaneously. The LZMA copies could be decompressed and allowed one to obtain a large collection of known plaintext.

    [...] identically named modules in different versions of ME 11 firmware can be compressed with different algorithms. If we take the Module Attributes Extension for identically named modules that have been compressed with LZMA and Huffman encoding, and then extract the SHA256 value for each module version, we find that there is no LZMA/Huffman module pair that has the same hash values. But one should remember that for modules compressed with LZMA, SHA256 is usually computed from compressed data. If we calculate SHA256 for modules after LZMA decompression, a large number of pairs appears. Each of these module pairs yields several pairs of matching pages, both with Huffman encoding and in unpacked form.

  2. After a large set of plaintext-ciphertext pairs were collected, the meaning of 70% of sequences from the code table and 68% from the data table was determined by using linear algebra.

    Having a large set of pages in both compressed and uncompressed form (separately for code and for data) allows recovering all of the code sequences used in those pages. The methods needed for this task combine linear algebra and search optimization. [...] we can set up a system of linear equations: the unknowns are the lengths of encoded values, the coefficients are the number of times a particular code sequence is found in the compressed page, and the constant equals 4096. Code and data pages can both be "plugged in" at the same time, since for identical code sequences, the lengths of encoded values should be the same. Once we have enough pages (and equations), Gaussian elimination provides the one valid solution. And once we have the uncompressed plaintext, length of each value, and their order, we easily derive which sequence codes for which value.

  3. However, the previous method couldn't be used if the length of the codeword is unknown. Fortunately, the SHA-256 checksum of a module allowed one to launch a brute-force attack. Additional heuristics were used to increase its effectiveness.

    If we have a sequence of unknown length, another row is added to our system of equations and we can quickly determine its length. But if we don't have the plaintext, how can we determine the value? [...] Fortunately for us, the metadata contains the SHA256 value for the unpacked module. So if we correctly guess all unknown code sequences on all the pages that make up a module, the SHA256 value should match the value from the Module Attributes Extension.

Conclusion

With a computer, it's entirely possible for a good cryptanalyst to crack such a cipher. However, without a computer, it would be extremely difficult for a cryptographer from the early 20th century to crack Huffman-compressed data with an unknown table by hand, even without the use of classical cryptography. But since compressing messages is equally impossible without a computer, my original question was self-contradictory and ill-formed.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ The OP is talking about classical ciphers, not modern ones. $\endgroup$ Mar 13, 2015 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, 2019 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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