Strengthening the KLEIN Cipher

In 2011, Gong, Nikova, and Law introduced the lightweight block cipher KLEIN, designed for 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. The weakness stems from the combination of the byte-oriented AES MixColumns operation together with 4-bit S-boxes. The branch number of the AES MixColumns is 5, which is optimal for byte-oriented designs, but insufficient in a nibble-oriented setting, where the upper bound is 9. To address this vulnerability, we evaluate the implementation cost of four MDS and near-MDS matrices over GF(2^4), which improve diffusion due to having branch numbers 9 and 8, respectively. We select an involutory near-MDS matrix for which we present an implementation with s-XOR count of 135, the lowest reported for an involutory near-MDS matrix of order 8 over GF(2^4). By pairing the new mixing step with a modified key schedule, we obtain a variant of KLEIN that is secure against previously published attacks and offers comparable efficiency.