[isonzrbz] ARX and timing attacks on addition

Binary addition is like XOR, except carries cause some bits to affect neighboring bits.  A chain of carries can affect bits very far away.

Despite this long-range data dependency, I'm guessing that in all modern processors (ALUs), addition takes constant time independent of inputs: carry lookahead adder.

However, one can easily imagine a multi-cycle implementation of addition whose timing does depend on its inputs.  First, do carry-lookahead addition of blocks and generate all the carry bits (these can be done in parallel across all the blocks).  Deal with the carries over the next few cycles, taking a variable number of cycles depending on how many times carries generate further carries.

You need to know your addition hardware intimately to know whether addition takes constant or data-dependent variable time, and consequently whether it is safe to use an ARX cipher, which critically relies on addition as its sole nonlinear element, and which would be vulnerable to a side-channel timing attack if addition takes variable time.

Even if addition takes constant time, it still might be vulnerable to power analysis.

Original thought: ARX ciphers seem too good to be true.