Cycle experiments on the cryptographic permutation Xoodoo

Abstract

Cryptography is the science of concealing messages, and it provides data security and privacy. A cipher is designed to be as secure as possible, to not be easily broken with the current availability of computational power in a reasonable amount of time. Various attacks have been discovered over time, and recently, the invariant subspace attack was presented on the PRINTcipher. This is a statistical saturation attack which makes use of the weak keys of the cipher.

This report delves into the cryptographic permutation known as Xoodoo, and explores the possibilities of its vulnerability towards the invariant subspace attack. For this, we investigate the cycle structure of the permutation by performing cycling experiments on its round function. We implement the naive Xoodoo round function after stripping off its round constants, and take advantage of the symmetry properties of the Xoodoo state to understand how the symmetry classes behave. The identification and description of symmetry classes of Xoodoo states based on the concept of lattices help us observe some of the symmetry classes that are small enough and can fully determine their entire cycle structure. With an exception for one anomaly case, there were no observed deviations from the behaviour of Xoodoo in comparison to the behaviour of a random permutation, and the cycles were found to have no particular structure. We thus conclude that it is highly unlikely that Xoodoo is vulnerable to invariant subspace attacks. Many factors about the algebraic background of the cipher were taken into consideration for the implementation. The parity of the cycle count, the behaviour of the cipher with different symmetry classes with a given state size, the interaction between bits in the intermediate states of the cycles, and the factors that influenced the number of cycles were all analysed. The concept of symmetry is rigorously described. We establish that the number of cycles increases as the length of the input permutation decreases. The outcomes of the experiments are compared with the theory behind the implementation and anomalies are explained.