Constructing algebraic attacks on lightweight symmetric ciphers using functions with small number of output bits

We propose a new class of algebraic attacks on lightweight cryptographic functions. The main idea is based on the use of special functions that produce significantly fewer output bits than the original functions specified by the ciphers under consideration (hereafter referred to as standard functions). Examples of similar functions can be found in the so-called cube attacks. The inversion of such special functions is much simpler compared to the inversion of standard ones, but the image of a special function has more than one preimage. To achieve uniqueness, a cloning procedure is proposed: several special functions are constructed for different fragments of the plaintext and a common secret key, and then they are combined into a new function for which the inversion problem has a unique solution. The cloning is performed using the And-Inverter Graphs (AIGs) representing the considered special functions. In addition, we use the well-known AIG minimization algorithms to reduce the size of the resulting representations. The combined application of the mentioned techniques made it possible to construct new algebraic attacks which turned out to be more efficient compared to standard SAT-based attacks for some well-known lightweight stream ciphers with truncated initialization phase.