5
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Ignoring patents, implementation problems, hardware do disadvantages still outweigh advantages? $\endgroup$
    – LightBit
    Nov 19, 2014 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, 2014 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, 2014 at 14:47
  • $\begingroup$ @SamuelNeves Do you know the DOI of the 2000 research paper? The link is down. $\endgroup$
    – forest ♦
    Apr 9, 2019 at 0:01
  • 1
    $\begingroup$ Fixed the link. $\endgroup$
    – Samuel Neves
    Apr 9, 2019 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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