A multidimensional linear distinguishing attack on the Shannon cipher (Q1017537)

Summary: We present a linear distinguishing attack on the stream cipher Shannon. Our distinguisher can distinguish the output keystream of Shannon from about \(2^{107}\) keystream words while using an array of \(2^{32}\) 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 \(2^{5}\) 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.