4
$\begingroup$

There are many ARX ciphers, however most use fixed rotations.

I know data-dependent compared to fixed rotations are:

  • patented (expired)
  • harder to implement constant time
  • more expensive in hardware
  • harder to analyse
  • attacker can control rotation to some degree

Do data-dependent rotations have any advantage over fixed rotations?

$\endgroup$
8
$\begingroup$

Compared to fixed rotations, data-dependent rotations improve resistance to differential and linear cryptanalysis. A fixed rotation has no effect (beyond helping with diffusion) in the probability of a (xor-)differential characteristic, whereas a data-dependent rotation also introduces differences in the rotation amounts, which brings probabilities down. There's a 2000 paper by Scott Contini that quantifies this advantage.

Successful attacks against ciphers using data-dependent rotation have focused on trying to avoid differences in the rotation amounts, or to fix them to some value; this was the case for RC5. Later designs like RC6 and MARS made this harder by using more complex functions as the input to the rotations. This is an interesting paper studying the effect of varying that complex function in RC6, and how it affects the overall security of the cipher.

That said, the disadvantages you listed outweigh the potential advantages, and data-dependent rotations are generally not employed in new designs.

$\endgroup$
  • $\begingroup$ Ignoring patents, implementation problems, hardware do disadvantages still outweigh advantages? $\endgroup$ – LightBit Nov 19 '14 at 6:57
  • 2
    $\begingroup$ Probably. Analysis is still more difficult on data-dependent rotations, and so it may be wise to assume the attacker can force them to have no difference. This is especially the case in hash functions, where the attacker controls almost everything; here's an example. When assuming no differences in the rotations, fixed rotations start to seem like the better choice. $\endgroup$ – Samuel Neves Nov 19 '14 at 7:25
  • 4
    $\begingroup$ I also immediately recalled attacks on DynamicSHA and its relatives. I would also mention that the designers usually want to control diffusion, i.e. to ensure the avalanche effect. Data-dependent rotations make the diffusion probabilistic, thus troubling the upper bounds on differential and linear properties. $\endgroup$ – Dmitry Khovratovich Nov 19 '14 at 14:47

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.