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:

"Entropy preservation": we don't lose randomness as the algorithm progresses. If you give up some key randomness with each crypto operation, you're giving up security--run long enough, and you'll converge to a single key (often zero).
"Nonlocality": if we flip one bit of the input, lots of bits in the output change (ideally half).
"Inverses": each crypto operation needs an inverse function, or else we'll have a hard time building the decryption function!
"Analysis": it shouldn't be easy to look at the output of the function and determine the inputs.

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:

Operation	Inverse	Entropy Preservation	Nonlocality	Analysis for fixed K
Addition C=P+K;	Subtraction P=C-K;	Perfect (even with wraparound).	Poor--except for carries, totally bit-local.	Trivial: compare plaintext and ciphertext histograms.
Multiplication C=P*K;	Division P=C/K;	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	Perfect	Terrible--bits are in 1:1 correspondence.	Trivial: compare plaintext and ciphertext bit histograms.
Bitwise XOR C=P^K;	Bitwise XOR again P=C^K;	Perfect	Terrible (bitwise)	Trivial if K is reused.
Bitwise AND C=P&K;	Does not exist	Not good--zeros in either input will cancel out any entropy in the other input.	Terrible (bitwise)	Not invertible.
Bitwise OR C=P\|K;	Does not exist	Not good--ones in either input cancel entropy in other input.	Terrible (bitwise)	Not invertible.
Either-or 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") C=T[P,K];	Inverse table C=I[P,K];	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.