I have not seen much about algebraic attacks against ARX ciphers.

How would ARX ciphers compare in algebraic security to AES or Present or Simon?

  • 2
    $\begingroup$ I'm not sure Algebraic analysis of an abstract class of algorithm design is possible. You might need to pick an actual example of an ARX design in order to begin algebraic analysis; It seems that the actual order, quantity, and type of operations would have to be specified in order to write an equation. Your question may be too broad, if it can even be answered as is. $\endgroup$ – Ella Rose Oct 3 '16 at 18:37
  • $\begingroup$ not true. The multiplicative complexity of each modular addition is n-1, according to Courtois. For a given cipher with a given number of modular additions, lower bounds could be estimated. $\endgroup$ – user3201068 Oct 4 '16 at 6:00
  • $\begingroup$ "A given cipher with a given number of modular additions" - this would be an example of an actual, specific ARX design, not the abstract class of design itself. If we had an actual specific design with a specific quantity of additions, we could use the result by Courtois you cite to establish the bound you're interested in. Until you have a specific quantity of additions, all you will have is the formula for calculating the bound (with no numbers to plug into it, which is what you have already). $\endgroup$ – Ella Rose Oct 4 '16 at 16:47
  • $\begingroup$ I'm perfectly happy with that. A formula of how many terms would result, and how many terms would result in a 2^n computational complexity. $\endgroup$ – user3201068 Oct 4 '16 at 19:43
  • $\begingroup$ Addition modulo 2n of two n-bit quantities can be expressed as 2n−1 XOR, 2n−3 AND, n−2 OR of individual Boolean variables, using the well-known ripple carry adder construction. In the end, the whole block cipher boils down to Boolean equations. Hint: start with the equations involving the low-order bit of each 8-bit quantity. Prove that you can find the low-order bit of K1 and K2 from the the low-order bit of each halves of a single P/C pair. Then move on to higher-order bits crypto.stackexchange.com/questions/58136/… $\endgroup$ – abraza Apr 7 '18 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.