Compression and Security

As far as is known in the open community, David Scott formulated the idea. He also implemented the first one-on-one compression algorithm.

He has vocally supported the idea over an extended period of time - in the face of a large volume of fairly hostile criticism of the approach.

No non-trivial one-on-one compression algorithms predating David's discovery are currently known.

We would love to have more information about any such algorithms.

One-on-one compression has been criticised because normal compression techniques can offer some protection against chosen-plaintext attacks, while one-on-one compression does not.

IF an attacker can choose plaintexts to be encyphered, this can sometimes assist him in determining the internal workings of a cypher in ways that a simple knowledge of plaintext would not allow.

Metaphorically speaking, the use of such a technique can be like using a narrow and bright torch to observe obscure, dark corners of a cypher, which might otherwise need large volumes of known plaintext to illuminate.

Alternatively, such a technique might allow the attacker to completely avoid the parts of the cypher they had not yet found weaknesses in - and thus succeed in finding a key.

The attacker would like to be able to choose the input to the cypher. This is the output from the compressor.

If the attacker can choose the output from a one-on-one compressor, he can usually find a decompressed plaintext that corresponds to it.

If an ordinary compressor is used, there is no guarantee that a decompressed file corresponding to the compressed target file chosen by the attacker exists.

It has been argued that this prevention of chosen plaintext attacks is actually one of the purposes of compression. It provides a security benefit that hinders attackers choose plaintexts.

In fact compression routines are not generally designed to hinder chosen-plaintext attacks. Consequently they are not very effective at doing so.

Methods exist for preventing chosen plaintext attacks. These typically involve appending a known volume of "random" information to the message, and applying diffusion, so that the randomness is evenly distributed throuout the file.

Use of such techniques introduces security problems if the source of randomness is less than perfectly random. It should be used with caution.

This technique is the best known method of preventing chosen-plaintext attacks. It may be applied in conjunction with one-on-one compression techniques, just as well as any other type.

The use of non-one-on-one compression to prevent known plaintext attacks, is a primitive, dangerous technique, which we cannot recommend. Instead of adding random information to the file - and having this information evenly distributed, compression typically adds ordered information to the file, with an uncertain distribution. This is not what is required.

In practice, defending against chosen plaintext attacks are not terribly important anyway. For one thing, diffusion can easily prevent an attacker controlling a plaintext, unless he can control every single last bit of it.

If the attacker can control the entire plaintext, the only method of defense against chosen plaintexts involves adding information to the file. Unless done extremely carefully, this is likely to introduce weaknesses which cryptanalysis can target. Consequently, any such a "defense" only barely qualifies as such.

This is a generally desirable aim on security grounds, but typically needs a source of "real" random numbers to be performed without introducing more security problems than it solves.

If a secure source of "real" random numbers were available, a system based on sending every message with an equal frequency would be more secure than the systems under discussion here.

However, under some circumstances, it would also take up large quantities of bandwidth - the very opposite of the effect of compressing.

If you use a signature that may be publicly verified, and the origin of your message may be traced to you, and you sign your message before it's encrypted - you may be providing attackers with a method of mechanically rejecting the vast majority of keys.

On the other hand, if you sign on the outside of the message, there is some possibility that a message may be faked.

Bearing these issues in mind when signing messages is recommended.

Nobody knows if there are any modern block cyphers that will withstand cryptanalytic attack for an extended period. Since the security of these systems is not known with any certainty, additional security which hinders cryptanalysis can only be welcome.

Attacks directly on the underlying cyphers are not the only way of compromising a system's keyspace.

A bad random number generator behind the keys can allow the analyst to narrow the keyspace to the point where brute force is possible.

Similarly keys may be partially obtained through noisy channels - such as looking at keyboards through binoculars.