Paper 2015/1163

A Guess-and-Determine Attack on Reduced-Round Khudra and Weak Keys of Full Cipher

Mehmet Özen, Mustafa Çoban, and Ferhat Karakoç

Abstract

Khudra is a lightweight block cipher designed for Field Programmable Gate Array (FPGA) based platforms. The cipher has an 18-round generalized type-2 Feistel structure with 64-bit block size. The key schedule takes 80-bit master key and produces 32-bit round keys performing very simple operations. In this work, we analyze the security of Khudra. We first show that the effective round key length is 16-bit. By the help of this observation, we improve the 14-round MITM attack proposed by Youssef et al. by reducing the memory complexity from $2^{64.8}$ to $2^{32.8}$. Also, we propose a new guess-and-determine type attack on 14 rounds where only 2 known plaintext-ciphertext pairs are required to mount the attack in a time complexity of $2^{64}$ encryption operations. To the best of our knowledge, this is the best attack in the single key model in terms of time, memory and data complexities where the data complexity is equal to the minimum theoretical data requirement. Moreover, we present two observations on differential probabilities of the round function and the symmetric structure of the cipher. We introduce $2^{40}$ weak keys for the full cipher by exploiting the symmetric structure of the cipher.

Note: This paper has been submitted to a journal. A citation typo in the previous version has been corrected.