Paper 2020/1438

Resource Estimation of Grovers-kind Quantum Cryptanalysis against FSR based Symmetric Ciphers

Ravi Anand and Subhamoy Maitra and Arpita Maitra and Chandra Sekhar Mukherjee and Sourav Mukhopadhyay

Abstract

In this paper, we present a detailed study of the cost of the quantum key search attack using Grover. We consider the popular Feedback Shift Register (FSR) based ciphers Grain-128-AEAD, TinyJAMBU, LIZARD, and Grain-v1 considering the NIST's MAXDEPTH depth restriction. We design reversible quantum circuits for these ciphers and also provide the QISKIT implementations for estimating gate counts. Our results show that cryptanalysis is possible with gate count less than $2^{170}$. In this direction, we also study the scenario where initial keystreams may be discarded before using it for encryption so that the Grovers attack on key search becomes costly in terms of circuit repetition. Finally, we connect Grover with BSW sampling for stream ciphers with low sampling resistance. We implement this attack on LIZARD (secret key size of 120 bits, state 121 bits, and security equivalent to 80 bits) and successfully recover the internal states with $2^{40.5}$ queries to the cryptographic oracle and $ 2^{40} $ amount of data. Our results provide a clear view of the exact status of quantum cryptanalysis against FSR based symmetric ciphers.