[Cryptography] Exotic Operations in Primitive Construction

[Jerry Leichter]

> I noticed the other day that bit shifts and rotates are very popular in
> primitive construction. Why is this the case? Intuitively it seems to me like
> these operations are some of the most irregular that a computer has to offer.
> Bit shifting is related to division, but bit rotation does not seem closely
> related to any other easy to analyze operation. But I have no explanation for
> why it feels this way.
> 
> Perhaps the only more irregular operation I can think of is a lookup.
> 
> Are any operations particularly hard to analyze? I realize some of this is
> irrelevant, lots of attacks operate on the statistical properties of the output
> and the input. But it is still important.
Cryptographic algorithms tend to have two parts:
1.  Something that maintains and mutates an internal state.  A cryptographic random number generator is an obvious example; it's pure mutation, with no input.  A cryptographic checksum looks like a random number generator except that it keeps feeding in the information to be checksummed.  Most block cipher algorithms mutate a key-based state to create round keys.
2.  A combiner that takes output from the mutator and combines it with an input stream to create an output stream.  Random number generators don't have a combiner, but if you use one to build a stream cipher, it's right there.  With block ciphers the combiner is determined by the mode.

Rotates, in particular, are common in the mutator.  You want to combine a series of simple, fast primitives to make a primitive that's hard to invert.  A basic idea going all the way back to Shannon is to alternate primitives that don't commute.  (In fact, it's pretty obvious that primitives the *do* commute are a bad idea, because an attacker can simply move them around to the most convenient form to attack.  Often, chains of repetitions of a simple primitive can simply be folded together.)

Using something like rotates and additions is a good choice because not only don't these commute, but they come from entirely different groups so their interactions are complex.  The same is true for shifts, but rotates have an advantage:  They don't lose any information.  A shift always discards some bits.

XOR is also widely used, but it's just addition in a different group.  Logical negation is just XOR with a constant.  Other logical operators all lose information.

Lookups have certainly been used - RC4 is an obvious example - but access to memory is way more expensive on modern CPU's than computational operations, so you have to keep them small.  And as differential cryptography shows us, just because a lookup table looks disordered doesn't mean it's strong.

Multiplication has been suggested for some special uses (a long discussion on this group of using multiplication in random number generators in a way that guarantees uniform distribution), but doesn't otherwise seem to be used often, perhaps for performance reasons.

Division is very expensive and has no obvious advantages.

It's not clear what other "exotic" operations you might use.  The only other primitive not in any of these classes I can think of is bit count, which loses so much information it doesn't seem useful.

AES has an internal structure that is more amenable than many to expression in  clean mathematical terms, but that hasn't helped anyone prove much of significance about its security properties.  We really don't have much in the way of "proofs of security" for cryptographic algorithms.  Rather, we are still at the point of showing immunity to various known attacks - though the attacks we understand today are very general and powerful.  So amenability to neat mathematical characterization doesn't really help - and in fact there were early arguments that AES was rendered *weaker* by its clean structure.  That hasn't panned out ... perhaps illustrating how little we actually understand about the sources of security and insecurity in cryptographic algorithms.
                                                        -- Jerry