3
$\begingroup$

So I'm trying to find a method of encryption that not only obfuscates text, but also compresses the result.

For example, if I encrypted ninechars, the ideal result would be less than nine characters.

Otherwise, if this is not possible, is there a method where I can set a limit on the amount of characters in the result? In other words, no matter how long the input is, the result will always be 50 characters long.

The closest results that I have found are Caesar Encrypt and XOR Encrypt, but they seem to simply result in the same amount of characters as the original input. The others I have found increase the size.

TL;DR I pretty much need a "hash function" that is reversible.

$\endgroup$
  • 1
    $\begingroup$ Are you instead looking for a hash function? $\;$ $\endgroup$ – user991 Oct 21 '15 at 6:26
  • $\begingroup$ @RickyDemer The more I look into it, I think you're right. The problem is that I will need to be able to reverse the hash function. I looked into MD5 and SHA-1 but it seems like you have to have a massive database of possible solutions. Any recommendations? $\endgroup$ – Grant Miller Oct 21 '15 at 7:23
  • 2
    $\begingroup$ If "reverse" means "find the original input", then see otus's answer. $\:$ If "reverse" means "find something that when given as input will yield the right output", then there's a fairly straight-forward transformation from digital signatures to such hash families. $\;\;\;\;$ $\endgroup$ – user991 Oct 21 '15 at 7:43
  • 1
    $\begingroup$ @IlmariKaronen, or use e.g. CMAC which allows the key-owner to find messages that give a particular MAC value. $\endgroup$ – otus Oct 21 '15 at 9:03
  • 2
    $\begingroup$ Related question: Crypto-Compression Algorithms?. Your otherwise part is known as Format-preserving encryption. $\endgroup$ – CodesInChaos Oct 21 '15 at 10:12
12
$\begingroup$

So I'm trying to find a method of encryption that not only obfuscates text, but also compresses the result. For example, if I encrypted ninechars, the ideal result would be less than nine characters.

Even without encryption, it's not possible for a reversible data compression scheme to shorten all of its inputs. This can be easily proven using the pigeonhole principle: for any given length $\ell$, there are fewer strings of length strictly less than $\ell$ than there are strings of length at most $\ell$. Thus, if the compression scheme maps all strings of length at most $\ell$ to strings of length less than $\ell$, it must necessarily map some distinct input strings to the same output string, and thus be irreversible.

(In fact, a similar argument can be used to show a stronger result, namely that, if a lossless compression scheme makes any input string shorter, then it must also make some input string longer. I'll leave proving that as an exercise.)

Otherwise, if this is not possible, is there a method where I can set a limit on the amount of characters in the result? In other words, no matter how long the input is, the result will always be 50 characters long. TL;DR I pretty much need a "hash function" that is reversible.

This is also impossible, by a similar argument. There is a finite, fixed number of strings of length 50 (namely, $k^{50}$ for a $k$-letter alphabet), whereas the number of possible input strings of unbounded length is infinite. Thus, not only does any function mapping arbitrary unbounded inputs to 50-character outputs need to map some distinct inputs to the same output, but it actually has to map infinitely many inputs to some output.

In fact, to show that such a function cannot be reversible, it's enough to consider only inputs that are 51 characters long. Clearly, there are more 51-character inputs than there are 50-character outputs, so some distinct inputs have to map to the same output.


Of course, if you allow some inputs to increase in size, then you can make other inputs shorter. This is basically what ordinary data compression algorithms like LZW do — they rely on the fact that most of the possible inputs to the compressor look essentially like random noise, whereas most of the typical inputs (like plain text, program code, uncompressed image or audio data, etc.) have a lot of repetitive, non-random structure. Such repetitive data can be encoded more compactly, making it a lot shorter; meanwhile, if the input does not happen to be repetitive enough to compress well, the compressor will just insert a short marker (at a minimum, a single bit, but in practice usually a few bytes) indicating that the data could not be compressed, and then include the input verbatim. Thus, the compressor can compress some common types of inputs significantly, at the cost of very slightly increasing the length of the random-looking inputs that make up the bulk of the full input space.

Anyway, none of this really has anything to do with cryptography. If you want to both compress and encrypt data, the standard way is to first compress it, and then encrypt it. (You cannot compress it after encryption, since encrypted data does look random to anyone who doesn't know the key, and has no apparent structure that a compressor could exploit.)

As other answers have pointed out, though, even this standard method has risks. One risk comes from the fact that any encryption scheme that can handle arbitrarily long messages must necessarily reveal at least some information about the length of the message. This may allow an attacker to, say, distinguish the message YES (three characters) from the message NO (two characters).

This is true even without compression, and needs to be kept in mind when designing any cryptosystem, but adding compression to the mix makes it harder to predict and defend against. For example, even if you were careful to always use fixed-length messages (like, say, POSITIVE and NEGATIVE instead of YES and NO), it's quite likely that running such messages through a compressor will produce output whose length varies.

More importantly, if the attacker can control some of the data being compressed and encrypted, they may be able to learn information about the other parts by observing the length of the compressed message. For example, let's say the attacker can make you generate, compress and encrypt messages of the form TO <ID>: STATUS <POSITIVE/NEGATIVE>, where <ID> can be controlled by the attacker. The attacker may then be able to request two encrypted messages, one for <ID> = POSITIVE and one for <ID> = NEGATIVE, and see which one compresses better.

Of course, these are all just toy examples, but similar weaknesses have led to real attacks. For example, as mentioned in otus's answer, the CRIME and BREACH attacks on SSL are based on the same principle as the chosen-plaintext toy attack described in the previous paragraph. Even the passive attack described earlier above, based on just observing naturally occurring message lengths, may be used to e.g. eavesdrop on encrypted VoIP conversations.

That said, the lesson to take home here is not just that data compression is dangerous and should be avoided. Rather, it's that the leakage of plaintext length is dangerous, and, since it cannot be completely avoided, must be kept in mind when analyzing any crypto protocol. Compression is an additional complication on top of that, since it can make the message length depend on its content in non-trivial and non-local ways.

$\endgroup$
  • $\begingroup$ By definition, if you could compress encrypted data, that would be a massive indicator of a flaw in the encryption. $\endgroup$ – corsiKa Oct 21 '15 at 19:52
  • $\begingroup$ One workaround: if the input has fewer bits of entropy than total bits (such as if one or more possible inputs are known to simply not occur), then it is possible to compress the bits, then encrypt them, and meet the OP's needs. However, it is never possible to do so beyond the number of bits of entropy in the original message (as the OP worded the scenario, one doesn't get to make the assumption needed for my little workaround, but it seemed worth mentioning as a loophole) $\endgroup$ – Cort Ammon Oct 22 '15 at 2:00
  • $\begingroup$ One thing I've wondered about is whether anyone during World War II ever tried to avoid the "opposite" issue when sending encrypted messages over Morse code; I would think transmission efficiency could be improved by replacing certain common pairs of letters (e.g. EE, ET, TE, etc.) with letters like Q, W, or Z and vice versa before encryption and again after, since sending a single Q, W, or Z takes longer than sending EE, ET, or TE. $\endgroup$ – supercat Oct 22 '15 at 2:35
  • $\begingroup$ @supercat: The closest thing I can think of, off the top of my head, is the use of straddling checkerboards in some WWII-era and later Soviet ciphers. But those ciphers had numerical ciphertext anyway, so they weren't particularly quick to transmit by Morse anyway. $\endgroup$ – Ilmari Karonen Oct 22 '15 at 10:23
  • $\begingroup$ @IlmariKaronen: That sounds similar to what I had in mind, though that raises another interesting question: since Morse Code optimizes the pulse patterns for letters at the expense of those for digits, did any operators use shorter representations for digits when sending non-alphabetic transmissions? If a dot or letter space is one unit and a dash is two, digits will take 6 to 11 units to send, with an average of 8.5, but there are eleven patterns which are five units or less (including the letter space). $\endgroup$ – supercat Oct 22 '15 at 16:03
8
$\begingroup$

The way this is usually done is to use a separate compression algorithm, then encrypt the compressed (shorter) message.

However, compression has some disadvantages and nowadays its use is discouraged. Compression can leak information about the plaintext, like in CRIME and BREACH attacks on TLS. Arguably it is the protocol that combines the compression and encryption that is to blame, but a generic compression algorithm (like anything based on lz77) allows an attack if the attacker can control a part of the message to be encrypted.

Of course, you cannot compress every message, only those with redundancy. And you cannot ensure they will always fit 50 "characters" (which you should define), unless you are willing to truncate long messages.

$\endgroup$
2
$\begingroup$

If the $plaintext$ is $n$ bits the $ciphertext$ should be atleast $n$ bits, otherwise there would be information loss and you cannot get the $plaintext$ back !In simpler terms , encryption is randomized mapping from $plaintext$ to $ciphertext$ if both are $n$ bits its a random permutation of bits. Ideally it is suggested for good security that $ciphertext$ should be larger than $plaintext$ to ensure enough entropy. If you have for some reason fixed the $ciphertext$ length and either the $plaintext$ length should be either equal or smaller but definitely cannot be greater.

On a side note , you cannot compress after encryption too, A good encryption algorithm's goal is to make $ciphertext$ as random as possible. So it defeats any compression algorithms.

You could compress and then encrypt, but that is considered harmful in certain scenarios , check here.

$\endgroup$
  • 5
    $\begingroup$ "If the plaintext is n bits the ciphertext should be atleast n bits, otherwise there would be information loss and you cannot get the plaintext back" This statement is obviously false as this would undermine any compression algorithm. $\endgroup$ – Roy T. Oct 21 '15 at 7:43
  • $\begingroup$ @RoyT. Not false at all. It's a fundamental cryptology concept, and it's one underlying difference between encryption, hashing, encoding and even compression. Note that for a difference between encryption and hashing, reversibility is important. It should be seen intuitively. Compression is very different from encryption; yet it's also true that no compression algorithm can shorten all messages (without losing info). $\endgroup$ – user2338816 Oct 21 '15 at 9:55
  • 1
    $\begingroup$ The statement is correct, just somewhat awkwardly phrased. It is obvious that you cannot compress every single $n$-bit string into less than $n$ bits. You can compress some of them by exploiting redundancy (like repeated patterns of bits and so on), but others with less structure have to become larger after compression, at least by a single bit, to compensate, because information theory. So on average (and hence to guarantee correctness in all cases) the output must be as large as the input, or you will eventually truncate some input that didn't compress well (like, say, random bits). $\endgroup$ – Thomas Oct 21 '15 at 10:21
  • 1
    $\begingroup$ @Thomas you're right. A series of truly random bits cannot be represented in a different way without at least as many bits. I see now that wether or not that means the statement was false or is akwardly phrased depends on context. Re-reading the statement I'd still lean towards false, but I understand how it can also be read like you've explained. $\endgroup$ – Roy T. Oct 21 '15 at 11:52
1
$\begingroup$

You can simply approach it in two separate steps: Compress the data, then encrypt it. But compression won't do much with short data, like your nine-character example. In fact that one will probably get longer due to some overhead. Compression needs a reasonable amount of data so that it can find patterns that repeat. Otherwise, the best it can do is trim some bits off your ASCII characters.

Regarding, "no matter how long the input is, the result will always be 50 characters long" ... I could write you an encryption program that does that, for free. But you can't afford the decryption utility. Ha!

Seriously, you can't compress data at-will, unless you're willing to live with losses. For example, you can compress a JPG pic or MP3 song to configurable degrees, but it's "lossy"... i.e. you lose data. (The JPG gets blurry/pixelated. The MP3 sounds like a bad robot singing.) It would be interesting if someone's created a lossy text compressor, but I imagine it would just skip some letters and hope you can still read it.

$\endgroup$

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.