Related-Key Rectangle Attack on Round-reduced Khudra Block Cipher

Khudra is a block cipher proposed in the SPACE’2014 conference, whose main design goal is to achieve suitability for the increasingly popular Field Programmable Gate Array (FPGA) implementation. It is an 18-round lightweight cipher based on recursive Feistel structure, with a 64-bit block size and 80-bit key size. In this paper, we compute the minimum number of active F-functions in differential characteristics in the related-key setting, and give a more accurate measurement of the resistance of Khudra against related-key differential cryptanalysis. We construct a related-key boomerang quartet with probability $$2^{-48}$$ for the 14-round Khudra, which is better than the highest probability related-key boomerang quartet of the 14-round Khudra of probability at most $$2^{-72}$$ claimed by the designers. Then we propose a related-key rectangle attack on the 16-round Khudra without whitening key by constructing a related-key rectangle distinguisher for 12-round Khudra with a probability of $$2^{-23.82}$$. The attack has time complexity of $$2^{78.68}$$ memory accesses and data complexity of $$2^{57.82}$$ chosen plaintexts, and requires only four related keys. This is the best known attack on the round-reduced Khudra.