A New General Method of Searching for Cubes in Cube Attacks

摘要

Cube attack, proposed by Dinur and Shamir at EURO-CRYPT 2009, is one of general and powerful cryptanalytic techniques against symmetric-key cryptosystems. However, it is quite time consuming to search for large cubes using the existing techniques, e.g., random walk, and practically infeasible to execute the cube attack when the size of cube exceeds an experimental range, e.g., 50. Thus, how to find favorite cubes is still an intractable problem. In this paper, a new general method of searching for cubes in cube attacks, called iterative walk, is proposed. Iterative walk takes the technique numeric mapping proposed at CRYPTO 2017 as a tool, which is used to test cubes and find out the best cubes among them. This new method consists of two concrete techniques, called incremental iterative walk and decremental iterative walk, respectively. Both of them split the process of searching for cubes with large size into several iterative processes, each of which aims at searching for a 'best' set of input variables with small size. After each iterative process, the input variables in the obtained 'best' set are added to (or dropped from) the cube in incremental (or decremental) iterative walk. As illustrations, we apply it to the authenticated encryption cipher ACORN v3, which was selected as one of seven finalists of CAESAR competition. Some new distinguishing attacks on round reduced variants of ACORN v3 are obtained.