A multidimensional linear distinguishing attack on the Shannon cipher

摘要

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 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.