1
$\begingroup$

I saw the paper 'Rotational Cryptanalysis of ARX', it is effective against design primitives using XOR, addition, and rotation.

http://www.iacr.org/archive/fse2010/61470339/61470339.pdf

However about those that use modulo multiplication (e.g. Multiplication modulo $2^{16}+1$, where the all-zero word (0x0000) is interpreted as $2^{16}$ (denoted by a circled dot ⊙))?

$\endgroup$

1 Answer 1

6
$\begingroup$

The rotational cryptanalysis considers applying the transformation $E$ to both $X$ and $\overrightarrow{X}$, where $$ \overrightarrow{(x_1, x_2,x_3,\ldots, x_n)} = (x_{r+1},x_{r+2},\ldots, x_n, x_1,\ldots, x_r) $$ for some integer $r$. You know that $\overrightarrow{X} \oplus \overrightarrow{Y} = \overrightarrow{X\oplus Y}$ always, and $$ \overrightarrow{X} \boxplus\overrightarrow{Y} = \overrightarrow{(X\boxplus Y)} $$ with quite high probability.

For the modulo multiplication the property does not seem to hold. I guess you were thinking of applying it to the IDEA block cipher. However, in some situations a modified property holds. For instance, if $X = q2^l$ and $Y = p2^t$ for some small $q,l,t,p$, then $$ \overrightarrow{X} \odot \overrightarrow{Y} = (q2^{l+r}) (p2^{t+r}) = (pq)2^{t+l+2r} = \overrightarrow{\overrightarrow{(X\odot Y)}}, $$ i.e. you have double rotation (again with some probability). I wonder if you could exploit in the attacks, because generally we want the same rotation distance $r$ in all internal variables.

To summarize, no one has yet applied rotational cryptanalysis to the multiplication, though there are hopes.

$\endgroup$
5
  • $\begingroup$ Yeah you are right!. Since the input $X$ is split to 2 parts: $(x_1,x_2)$ for the MA structure, should we consider rotational cryptanalysis for each $x_i$? $\endgroup$ Commented Dec 15, 2014 at 6:14
  • $\begingroup$ I never tried a rotational attack with distinct rotation distances, so I do not know how it could work.. $\endgroup$ Commented Dec 15, 2014 at 12:12
  • $\begingroup$ Also, please mark the answer as valid if you consider it so. $\endgroup$ Commented Dec 15, 2014 at 12:12
  • 1
    $\begingroup$ Hi Dmitry, just curious. Can we apply rotational cryptanalysis for bitwise permutation operations in ciphers? $\endgroup$ Commented Dec 29, 2014 at 7:47
  • 1
    $\begingroup$ Bitwise permutations usually do not preserve the rotation distance. $\endgroup$ Commented Jan 3, 2015 at 10:22

Your Answer

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

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