What are the weaknesses in a block cipher that uses modular addition, rotations with fixed amounts, and XOR? Can substitution boxes or permutation boxes be replicated with these three operations? Would the weaknesses in an ARX block cipher be present in an ARX stream cipher?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Read the design document of Simon and Speck, they have well explained how they achieved non-linearity using ARX operations and skipped non-linear look table $\endgroup$– cryptCommented Sep 8, 2017 at 19:10
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
9
What are the weaknesses in a block cipher that uses modular addition, rotations with fixed amounts, and XOR? Can substitution boxes or permutation boxes be replicated with these three operations?
The obvious question to ask is "what permutations can you form using those three operations"?
The surprising answer is "you can implement any permutation using a sufficiently large pile of those three operations in the proper sequence"; that is, you can find a sequence of operations which swap two specific entries (and leave everything else alone); you can concatenate those together to form any arbitrary permutation.
Hence, there cannot be any generic weakness that would apply to sufficiently long ARX ciphers. Of course, this doesn't address what "sufficiently long" means; it may be longer than what's in use in practice.
And, yes, there exists an ARX equivalent to any invertible sbox.
Exhaustive search on 3 bit blocks shows that you can reach every permutation with at most 9 operations, which isn't that bad. However, doing a search on 4 bit blocks would require searching over $16! \approx 2^{44.25}$ distinct states; a bit more than I can handle with my current resources.
-
1$\begingroup$ Can you please provide reference to these two statements for further reading. 1)"you can implement any permutation using a sufficiently large pile of those three operations in the proper sequence". 2) there exists an ARX equivalent to any invertible sbox $\endgroup$– cryptCommented Sep 8, 2017 at 19:00
-
$\begingroup$ @Raza: for the first one, no, I can't; AFAIK, nothing in the published literature has considered this. Instead, I put it together myself; to swap values $x, y$, I found a series of ARX operations that would map $x -> 0$ $y -> 1$ (and we don't care about the rest). Then, I do a generic set of 4 operations that swaps 0 and 1, and leaves everything else alone; then, I do $P^{-1}$, which reverses whatever $P$ did (just with the swap; that's why we didn't care what $P$ did with inputs other than $x, y$). As for "it can build any invertable SBOX", that's a consequence of the first statement $\endgroup$– ponchoCommented Sep 8, 2017 at 19:04
-
$\begingroup$ the idea is interesting but an example ARX operations which maps a 3 bits nonlinear looktable will help a lot in undertanding $\endgroup$– cryptCommented Sep 8, 2017 at 19:09
-
$\begingroup$ @Raza: any specific 3 bit sbox you're interested in? I have the program right here; it'd take a few seconds for the search... $\endgroup$– ponchoCommented Sep 8, 2017 at 19:10
-
4$\begingroup$ last line of the Abstract of Rotational Cryptanalysis of ARX(skein-hash.info/sites/default/files/axr.pdf) "ARX with constants are functionally complete, i.e. any function can be realized with these operations." $\endgroup$– cryptCommented Sep 8, 2017 at 19:54
$\begingroup$
$\endgroup$
You ask "what permutations can you form using those three operations?" The answer was: you can create all permutations by ARX. However, you can do even better and need only two of them: the XOR is not necessary: it is even possible to generate every possible permutation (which also means every possible block cipher) with ADD and ROTATE, without XOR. If you try to use another subset of A, R and X, this won't work. For example, XOR together with ROTATE generates only a small subgroup of the symmetric group. Thus, the carry bit of ADD is important. The proof can be found in a paper by Thilo Zieschang, Combinatorial properties of basic encryption operations, Eurocrypt 1997.
$\begingroup$
$\endgroup$
One generic weakness of ARX designs is that for certain inputs $x,\ y$, $x + y \equiv x \oplus y$. This allows you to linearize subsections of the state and view them as if addition were not applied and only xor was. This is easy to see if you examine the bits:
10010101
01000010 +
--------
11010111
If you examine the two input bit strings and the third output, you can see that the output is equivalent to a XOR of the bits, despite the fact that the operation we used was integer addition. By seeking out states where carries do not propagate, you can linearize subsections of the state with a certain probability.
Can substitution/permutation boxes be made with these three operations
A substitution box (usually) provides the non-linearity for a design. The term is often confused with a lookup table; S-boxes do not have to be implemented via lookup table, they simply often times are (used to be?) because non-linear functions are relatively complex and take time to evaluate. You can estimate an ARX function as an S-box, but since the propagation of the carries is not limited to certain well defined subsections of a word, you can only view a subsection as an $N\times M$ mapping with certain probability.
You can certainly develop a linear permutation layer using only rotation and xor - many (not all) linear layers are built exactly this way.
Would the weaknesses in an ARX block cipher be present in an ARX stream cipher?
This is hard to say without seeing the exact designs, but it seems probable that it would. Typically the adversaries goal involves predicting output bits. If your adversary can predict output bits for a block cipher they can conceivably leverage this information to recover key bits. For a stream cipher, it seems more likely that they could leverage the information to recover keystream/message bits (which may or may not imply an attack on the key).
answered Sep 8, 2017 at 16:11