Practical attack on 8 rounds of the lightweight block cipher KLEIN. (English) Zbl 1291.94053

Bernstein, Daniel J. (ed.) et al., Progress in cryptology – INDOCRYPT 2011. 12th international conference on cryptology in India, Chennai, India, December 11–14, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25577-9/pbk). Lecture Notes in Computer Science 7107, 134-145 (2011).
Summary: KLEIN is a family of lightweight block ciphers presented at RFIDSec 2011 that combines a 4-bit Sbox with Rijndael’s byte-oriented MixColumn. This approach allows compact implementations of KLEIN in both low-end software and hardware. This paper shows that interactions between those two components lead to the existence of differentials of unexpectedly high probability: using an iterative collection of differential characteristics and neutral bits in plaintexts, we find conforming pairs for four rounds with amortized cost below \(2^{12}\) encryptions, whereas at least \(2^{30}\) was expected by the preliminary analysis of KLEIN. We exploit this observation by constructing practical (\(\approx 2^{35}\)-encryption), experimentally verified, chosen-plaintext key-recovery attacks on up to 8 rounds of KLEIN-64-the instance of KLEIN with 64-bit keys and 12 rounds.
For the entire collection see [Zbl 1228.94001].


94A60 Cryptography
Full Text: DOI


[1] Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: An Ultra-Lightweight Block Cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007) · Zbl 1142.94334 · doi:10.1007/978-3-540-74735-2_31
[2] De Cannière, C., Dunkelman, O., Knežević, M.: KATAN and KTANTAN – A Family of Small and Efficient Hardware-Oriented block Ciphers. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 272–288. Springer, Heidelberg (2009) · Zbl 1290.94060 · doi:10.1007/978-3-642-04138-9_20
[3] Knudsen, L., Leander, G., Poschmann, A., Robshaw, M.J.B.: PRINTcipher: A Block Cipher for IC-Printing. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 16–32. Springer, Heidelberg (2010) · Zbl 1297.94080 · doi:10.1007/978-3-642-15031-9_2
[4] Engels, D., Saarinen, M.J.O., Smith, E.M.: The Hummingbird-2 lightweight authenticated encryption algorithm. In: RFIDsec (2011)
[5] Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED Block Cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326–341. Springer, Heidelberg (2011) · Zbl 1291.94092 · doi:10.1007/978-3-642-23951-9_22
[6] Shibutani, K., Isobe, T., Hiwatari, H., Mitsuda, A., Akishita, T., Shirai, T.: piccolo: An ultra-lightweight blockcipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 342–357. Springer, Heidelberg (2011) · Zbl 1291.94154 · doi:10.1007/978-3-642-23951-9_23
[7] Aumasson, J.-P., Henzen, L., Meier, W., Naya-Plasencia, M.: quark: A lightweight Hash. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 1–15. Springer, Heidelberg (2010) · Zbl 1297.94043 · doi:10.1007/978-3-642-15031-9_1
[8] Lindell, Y., Oxman, E., Pinkas, B.: The IPS Compiler: Optimizations, Variants and Concrete Efficiency. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 259–276. Springer, Heidelberg (2011) · Zbl 1288.68023 · doi:10.1007/978-3-642-22792-9_15
[9] Bogdanov, A., Knežević, M., Leander, G., Toz, D., Varıcı, K., Verbauwhede, I.: spongent: A Lightweight Hash Function. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 312–325. Springer, Heidelberg (2011) · Zbl 05954906 · doi:10.1007/978-3-642-23951-9_21
[10] Gong, Z., Nikova, S., Law, Y.W.: KLEIN: a new family of lightweight block ciphers. In: RFIDSec (2011)
[11] Gong, Z., Nikova, S., Law, Y.W.: KLEIN: a new family of lightweight block ciphers (2011), http://doc.utwente.nl/73129/
[12] Biham, E., Chen, R.: Near-Collisions of SHA-0. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 290–305. Springer, Heidelberg (2004) · Zbl 1104.94307 · doi:10.1007/978-3-540-28628-8_18
[13] Biham, E., Biryukov, A., Dunkelman, O., Richardson, E., Shamir, A.: Initial Observations on Skipjack: Cryptanalysis of Skipjack-3XOR. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, p. 362. Springer, Heidelberg (1999) · Zbl 0929.94009 · doi:10.1007/3-540-48892-8_27
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.