Cakr: a collision-aware cryptanalysis scheme for lightweight block ciphers

Abstract Partial neural distinguishers limit the available ciphertext bit combinations in differential neural cryptanalysis. When the training data size and the number of bits are not appropriately selected, label collisions can occur, which adversely affects key recovery efficiency. This paper conducts an analysis to investigate the correlation between the number of bits and the data size, aiming to address the aforementioned issue. It develops a strategy to control collisions and mitigate the impact of these collisions on model performance. A Collision-Aware Key Recovery (CAKR) framework is proposed tailored for high-collision data based on this strategy. This framework leverages the distribution characteristics of labels, eliminating the need for training neural distinguishers and significantly reducing both time and resource consumption. Experimental results show that the CAKR framework reduces the key recovery time by 96.8%, 95.5%, and 91.0% for the Speck32/64, Speck64/96, and Speck96/128, respectively. Additionally, a bit search algorithm is proposed that incorporates a differential evolution strategy and uses the non-uniformity of the ciphertext difference distribution among positive samples as the fitness criterion. Frequent calls to the neural distinguisher are avoided by our method, reducing the search time from 3.286 h to 7.464 s for 8-bit combinations in Speck32/64. The CAKR framework also offers a quantum version that theoretically further reduces time complexity.