3
$\begingroup$

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?

$\endgroup$
  • 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
  • $\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 at 0:06
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.

| improve this answer | |
$\endgroup$
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.

| improve this answer | |
$\endgroup$
  • 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 '19 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.

| improve this answer | |
$\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.

| improve this answer | |
$\endgroup$
  • 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.