More generally, our ambition is to do more than just to point out that a major encryption standard is flawed. We would like to present and suggest a new general paradigm for effective symmetric cryptanalysis of so called "Algebraic Complexity Reduction" which in our opinion is going to structure and stimulate substantial amounts of academic research on symmetric cryptanalysis for many years to come. In this paper we will explain the main ideas behind it and explain also the precise concept of "Black-box Algebraic Complexity Reduction". This new paradigm builds on many already known attacks on symmetric ciphers, such as fixed point, slide, involution, cycling, reflection and other self-similarity attacks but the exact attacks we obtain, could never be developed previously, because only in the recent 5 years it became possible to show the existence of an appropriate last step for many such attacks, which is a low data complexity software algebraic attack. This methodology leads to a large number of new attacks on GOST, way more complex, better and more efficient than at FSE 2011. One example of such an attack is given in the present paper.
Category / Keywords: Block ciphers, Feistel schemes, key scheduling, self-similarity, reflection attacks, single-key attacks, algebraic attacks, algebraic complexity reduction, black-box reductions Date: received 2 May 2011, last revised 9 May 2011 Contact author: n courtois at cs ucl ac uk Available format(s): PDF | BibTeX Citation Version: 20110509:205940 (All versions of this report) Discussion forum: Show discussion | Start new discussion