# rotational cryptanalysis on modulo multiplication?

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 ⊙))?

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.
• 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$? Dec 15, 2014 at 6:14