Strengthening the KLEIN cipher

Abstract

In 2011, Gong, Nikova, and Law introduced the lightweight block cipher Klein, which is designed to provide efficient encryption both in hardware and software implementations. Since then, several attacks on Klein have been published, most notably, truncated differential cryptanalysis that exploits the weak mixing of higher and lower nibbles in the cipher's diffusion layer. In this work, we show that the weakness is created by the use of the byte-oriented Rijndael MixColumns step together with nibble-oriented S-boxes. We quantify this using the branch number of the MixColumns operation, which equals five. While it corresponds to the upper bound in a byte-oriented context, it is insufficient in a nibble-oriented setting where the upper bound equals nine. As anticipated by the authors of Klein, nibble-oriented mixing with maximum branch number comes with higher computational cost when compared to MixColumns. However, we show that by using a near MDS matrix by Sajadieh et al. (2021), the mixing step can be done with smaller computational cost than MixColumns while reaching a branch number of eight. Finally, we prove that the new mixing step reduces the probability of the iterative rounds used in previous cryptanalysis from $2^{-6}$ to $2^{-24}$.