Improved conditional differential attacks on lightweight hash family QUARK

Abstract

Abstract Nonlinear feedback shift register (NFSR) is one of the most important cryptographic primitives in lightweight cryptography. At ASIACRYPT 2010, Knellwolf et al. proposed conditional differential attack to perform a cryptanalysis on NFSR-based cryptosystems. The main idea of conditional differential attack is to restrain the propagation of the difference and obtain a detectable bias of the difference of the output bit. QUARK is a lightweight hash function family which is designed by Aumasson et al. at CHES 2010. Then the extended version of QUARK was published in Journal of Cryptology 2013. In this paper, we propose an improved conditional differential attack on QUARK. One improvement is that we propose a method to select the input difference. We could obtain a set of good input differences by this method. Another improvement is that we propose an automatic condition imposing algorithm to deal with the complicated conditions efficiently and easily. It is shown that with the improved conditional differential attack on QUARK, we can detect the bias of output difference at a higher round of QUARK. Compared to the current literature, we find a distinguisher of U-QUARK/D-QUARK/S-QUARK/C-QUARK up to 157/171/292/460 rounds with increasing 2/5/33/8 rounds respectively. We have performed the attacks on each instance of QUARK on a 3.30 GHz Intel Core i5 CPU, and all these attacks take practical complexities which have been fully verified by our experiments. As far as we know, all of these results have been the best thus far.

Keywords

• Conditional differential attack
• Lightweight hash function
• Automatic condition imposing algorithm
• NFSR
• QUARK