Symbolic-Like Computation and Conditional Differential Cryptanalysis of QUARK

At ASIACRYPT 2010, Knellwolf et al. proposed a general analysis of NFSR-based cryptosystems, called conditional differential cryptanalysis. The main idea of this technique is to impose conditions on the internal state to get a deterministic differential characteristic for a large number of rounds. In this paper, we propose a method, called symbolic-like computation, to simulate the differential propagation of an iterated cryptosystem. By coding the internal state bits and modeling the bit operations, it can determine the constantness of the differential expression with linear time complexity. Based on this method, we can obtain a list of good input differences. We apply this technique to the conditional differential cryptanalysis of QUARK, a family of lightweight hash functions proposed by Aumasson et al. at CHES 2010. By controlling the propagation of differences both backwards and forwards, we can observe the bias of output difference at a higher round. Eventually, we can distinguish U-QUARK/D-QUARK/S-QUARK/C-QUARK up to 155/166/259/452 rounds respectively. Our distinguishers are very practical and have been fully verified by experiments on a single PC. To the best of our knowledge, all these results are the best thus far.