The parallel-cut meet-in-the-middle attack | Cryptography and Communications Skip to main content
Springer Nature Link
Log in

The parallel-cut meet-in-the-middle attack

  • Published:
Cryptography and Communications Aims and scope Submit manuscript

Abstract

We propose a new type of meet-in-the-middle attack that splits a cryptographic primitive in parallel to the execution flow of the operations. The result of the division are two primitives that have smaller input sizes and thus require lower attack complexities. The sub-primitives are not completely independent, but mutually depend on a certain number of bits. When the number of such bits is relatively small, we show a technique based on three classical meet-in-the-middle attacks that can recover the secret key of the cipher faster than an exhaustive search. We apply our findings to the lightweight block cipher Klein and show attacks on 10/11/13 rounds of Klein-64/-80/-96. We note that our approach works in the known-plaintext attack model and requires only one or two pairs of known plaintexts.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. We refer to the proposal of the low-data attack [3] for the importance of practical data complexity for analyzing ciphers.

  2. Actually, we are looking for a division that minimizes the number of guessed bits from the other half.

  3. Note that a simple exhaustive key search requires \(2^{\frac {k}{2} + r\cdot b_{2}}\) encryption queries, hence when \(r\cdot b_{2} > \frac {k}{2}\) the exhaustive search of the subcipher has a higher complexity than the exhaustive search of the cipher. Therefore we present more advanced techniques for recovering the key of the subcipher.

  4. We assume the subciphers are invertible.

  5. This number is in fact the average number of possible k-bit keys that encrypt n-bit plaintext P to ciphertext C, i.e. with our approach we find all the possible keys for the cipher.

  6. One nibble is 4 bits.

  7. This property, only for the key schedule, already has been pointed out in [1]

References

  1. Aumasson, J.-P., Naya-Plasencia, M., Saarinen, M.-J.: Practical attack on 8 rounds of the lightweight block cipher KLEIN. In: Bernstein, D., Chatterjee, S. (eds.) Progress in Cryptology INDOCRYPT 2011, Lecture Notes in Computer Science, vol. 7107, pp. 134–145. Springer, Berlin / Heidelberg (2011)

  2. Biham, E., Chen, R: Near-collisions of SHA-0. In: Franklin, M. (ed.) Advances in Cryptology - CRYPTO 2004, Lecture Notes in Computer Science, vol. 3152, pp. 199–214. Springer, Berlin / Heidelberg (2004)

  3. Bouillaguet, C., Derbez, P., Dunkelman, O., Fouque, P.-A., Keller, N., Rijmen, V.: Low-data complexity attacks on AES. IEEE Trans. Inf. Theory 58(11), 7002–7017 (2012)

    Article  MathSciNet  Google Scholar 

  4. Diffie, W., Hellman, M.E.: Special feature exhaustive cryptanalysis of the NBS data encryption standard. Comput. 10(6), 74–84 (1977)

    Article  Google Scholar 

  5. Dinur, I., Dunkelman, O., Shamir, A.: Improved attacks on full GOST. In: Canteaut, A. (ed.) FSE, Lecture Notes in Computer Science, vol. 7549, pp. 9–28. Springer (2012)

  6. Dunkelman, O., Sekar, G., Preneel, B.: Improved meet-in-the-middle attacks on reduced-round DES. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT, Lecture Notes in Computer Science, vol. 4859, pp. 86–100. Springer (2007)

  7. Gong, Z., Nikova, S., Law, Y.: KLEIN: A new family of lightweight block ciphers. In: Juels, A., Paar, C. (eds.) RFID. Security and Privacy, Lecture Notes in Computer Science, vol. 7055, pp. 1–18. Springer, Berlin / Heidelberg (2012)

  8. Lallemand, V., Naya-Plasencia, M.: Cryptanalysis of KLEIN FSE. To appear (2014)

  9. Leurent, G. In: S. Moriai (ed.) : Cryptanalysis of WIDEA. Springer (2013)

  10. Morita, H., Ohta, K., Miyaguchi, S.: A switching closure test to analyze cryptosystems. In: Feigenbaum, J. (ed.) Advances in Cryptology — CRYPTO 1991, Lecture Notes in Computer Science, vol. 576, pp. 183–193. Springer, Berlin / Heidelberg (1992)

  11. Yu, X., Wu, W., Li, Y., Zhang, L.: Cryptanalysis of reduced-round KLEIN block cipher. In: Wu, C., Yung, M., Lin, D. (eds.) Inscrypt, Lecture Notes in Computer Science, vol. 7537, pp. 237–250 Springer (2011)

Download references

Author information

Authors and Affiliations

  1. Nanyang Technological University, Nanyang, Singapore

    Ivica Nikolić & Lei Wang

  2. Huawei, Singapore, Singapore

    Shuang Wu

Authors
  1. Ivica Nikolić
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lei Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shuang Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ivica Nikolić.

Additional information

The work in this paper is supported by the Singapore National Research Foundation Fellowship 2012 (NRF-NRFF2012-06).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nikolić, I., Wang, L. & Wu, S. The parallel-cut meet-in-the-middle attack. Cryptogr. Commun. 7, 331–345 (2015). https://doi.org/10.1007/s12095-014-0118-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12095-014-0118-1

Keywords

Search

Navigation