Weaknesses in ARX block ciphers 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?
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.