[Cryptography] Exotic Operations in Primitive Construction

[John Denker]

On 9/28/20 9:50 PM, Sid Spry wrote:

> 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.

Let's talk about DES in particular.  At the time it came along, it was
common to implement crypto in SSI (small scale integration) hardware.
In that world, a rotate is the opposite of irregular, the opposite of
exotic.  It is easy to implement.  The hierarchy looks like this:
  — bitwise and, or, xor, etc.
  — shift and rotate
  — arithmetical add and subtract
  — multiply
  — divide

Let's be clear, add and subtract are very much more complicated than
shift and rotate.  Multiplication is eeenormously more complicated still.
When you hear that the hardware can do a multiply (or a multiply-add) in
a single clock cycle, please do not underestimate the amount of on-chip
acreage, electrical energy, and cleverness go into making that possible.

Subtle bugs have been found in hardware floating point algorithms.  It
is hard to imagine a subtle bug in shift or rotate.  (There are ways of
misusing the instructions, but they're not subtle.)

With bitwise operations plus shift and rotate, it is particularly easy
to prove that all bits in the word are encrypted equally strongly.  With
arithmetical operations this is a lot trickier, because the lower-order
bits are inherently dissimilar to the high-order bits.  So there are good
reasons why bit-wise thinking has persisted for decades.

So from this viewpoint, especially when looking at the bare metal (as
opposed to high-level compiled code), shift and rotate are regular, and
arithmetic is exotic.