Paper 2013/530

The Parallel-Cut Meet-In-The-Middle Attack

Ivica Nikolic, Lei Wang, and Shuang Wu

Abstract

We propose a new type of meet-in-the-middle attack that splits the cryptographic primitive in parallel to the execution of the operations. The result of the division are two primitives that have smaller input sizes and thus require lower attack complexities. However, the division is not completely independent and the sub-primitives depend (output of one is the input for the other) mutually 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. Our approach requires only one or two pairs of known plaintexts and always recovers the secret key.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
meet-in-the-middle attackcryptanalysisparallel-cutblock cipherhash functionKlein
Contact author(s)
inikolic @ ntu edu sg
History
2013-09-23: last of 2 revisions
2013-08-30: received
See all versions
Short URL
https://ia.cr/2013/530
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/530,
      author = {Ivica Nikolic and Lei Wang and Shuang Wu},
      title = {The Parallel-Cut Meet-In-The-Middle Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2013/530},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/530}},
      url = {https://eprint.iacr.org/2013/530}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.