Paper 2011/285

Exploiting Linear Hull in Matsui’s Algorithm 1 (extended version)

Andrea Röck and Kaisa Nyberg

Abstract

We consider linear approximations of an iterated block cipher in the presence of several strong linear approximation trails. The effect of such trails in Matsui’s Algorithm 2, also called the linear hull effect, has been previously studied by a number of authors. However, he effect on Matsui’s Algorithm 1 has not been investigated until now. In this paper, we fill this gap and examine how to exploit the linear hull in Matsui’s Algorithm 1. We develop the mathematical framework for this kind of attacks. The complexity of the attack increases with the number of strong linear trails. We show how to reduce the number of trails and thus the complexity using related keys. Further, we illustrate our theory by experimental results on a reduced round version of the block cipher PRESENT

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. This is a draft full version of the paper presented at WCC 2011.
Keywords
block cipherslinear cryptanalysislinear hullkey recoveryMatsui's Algorithm 1
Contact author(s)
andrea rock @ aalto fi
History
2011-06-03: received
Short URL
https://ia.cr/2011/285
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/285,
      author = {Andrea Röck and Kaisa Nyberg},
      title = {Exploiting Linear Hull in Matsui’s Algorithm 1 (extended version)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/285},
      year = {2011},
      url = {https://eprint.iacr.org/2011/285}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.