Picking Crypto Operations: Inverses, Analysis, and Entropy Preservation

CS 463 Lecture, Dr. Lawlor

The standard problem in cryptographic work is to make ciphers difficult to read without the key, but easy to read with the key.  Our only reliable tool to do this is randomness--entropy--but the problem is we normally want to use a cipher to stretch a little bit of randomness (like a password) across a long sequence of messages.  Clearly we really want:
There's quite a bit of theoretical debate as to whether these last two properties are at all compatible: if a function *has* an easy to compute inverse, can you *find* the inverse in a reasonable length of time?   One implication of the P=NP question is we don't really know the mathematical answers to questions like this; we just know some examples of easy to compute functions, the rest are "hard"(?).

Here are the properties of some commonly used operations:
Entropy Preservation
Analysis for fixed K
Perfect (even with wraparound).
Poor--except for carries, totally bit-local.
Trivial: compare plaintext and ciphertext histograms.
Depends on high bits: throwing away high bits loses entropy; modulo a large relatively prime value can preserve it.
Good, especially with wraparound.
Trivial--every ciphertext value differs by a multiple of the key.
Bit rotation
C=(P>>K) | (P<<(bits-K));
Rotate other way
Terrible--bits are in 1:1 correspondence.
Trivial: compare plaintext and ciphertext *bit* histograms.
Bitwise XOR
Bitwise XOR again
Terrible (bitwise)
Trivial if K is reused.
Bitwise AND
Does not exist
Not good--zeros in either input will cancel out any entropy in the other input.
Terrible (bitwise)
Not invertible.
Bitwise OR
Does not exist
Not good--ones in either input cancel entropy in other input.
Terrible (bitwise)
Not invertible.
C=(P1&K) | (P2&~K);

Does not exist
Actually good, although either P1 or P2 is thrown away.
Terrible (bitwise)
Not invertible.
Substitution table ("S box")
Inverse table
Perfect (it's typically a permutation). Good with a well-designed table.
For a reasonably big well-designed table, analysis can be hard.

S boxes would be used more often, except that locality-free table lookups are not high performance operations on most computers, so S boxes are limited to a small size, typically only 8-10 bits of input with modern ciphers.  Often folks combine several of these operations, for example using an S box to make analysis more difficult, then a bit permutation to reduce locality by mixing bits from different boxes.