Title: A multidimensional linear distinguishing attack on the Shannon cipher

Authors: Risto M. Hakala, Kaisa Nyberg

Addresses: Department of Information and Computer Science, Helsinki University of Technology, Konemiehentie 2, Espoo 02150, Finland. ' Department of Information and Computer Science, Helsinki University of Technology, Konemiehentie 2, Espoo 02150, Finland

Abstract: In this article, we present a linear distinguishing attack on the stream cipher Shannon. Our distinguisher can distinguish the output keystream of Shannon from about 2107 keystream words while using an array of 232 counters. The distinguisher makes use of a multidimensional linear transformation instead of a 1D transformation, which is traditionally used in linear distinguishing attacks. This gives a clear improvement to the keystream requirement: we need approximately 25 times less keystream than when a 1D transformation is used. In addition, we give evidence of the correctness of the distinguisher by applying it to a smaller version of Shannon.

Keywords: cryptography; distinguishing attacks; linear cryptanalysis; multiple linear approximations; Shannon cipher; stream ciphers; output keystream.

DOI: 10.1504/IJACT.2009.023463

International Journal of Applied Cryptography, 2009 Vol.1 No.3, pp.161 - 168

Published online: 24 Feb 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article