Symbolic-like computation and conditional differential cryptanalysis of QUARK. (English) Zbl 1398.94182

Inomata, Atsuo (ed.) et al., Advances in information and computer security. 13th international workshop on security, IWSEC 2018, Sendai, Japan, September 3–5, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-97915-1/pbk; 978-3-319-97916-8/ebook). Lecture Notes in Computer Science 11049, 244-261 (2018).
Summary: In Asiacrypt 2010 [Lect. Notes Comput. Sci. 6477, 130–145 (2010; Zbl 1253.94056)], S. 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 J.-P. Aumasson et al. [ CHES 2010, Lect. Notes Comput. Sci. 6225, 1–15 (2010; Zbl 1297.94043)]. 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.
For the entire collection see [Zbl 1392.68020].


94A60 Cryptography
Full Text: DOI