International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Time-Memory-Data Trade-off Attack on Stream Ciphers based on Maiorana-McFarland Functions

Khoongming Khoo
Guang Gong
Hian-Kiat Lee
Guanhan Chew
Search ePrint
Search Google
Abstract: In this paper, we present the time-memory-data (TMD) trade-off attack on stream ciphers filtered by Maiorana-McFarland functions. This can be considered as a generalization of the time-memory-data trade-off attack of Mihaljevic and Imai on Toyocrypt. First, we substitute the filter function in Toyocrypt (which has the same size as the LFSR) with a general Maiorana-McFarland function. This allows us to apply the attack to a wider class of stream ciphers. Second, we highlight how the choice of different Maiorana-McFarland functions can affect the effectiveness of our attack. Third, we show that the attack can be modified to apply on filter functions which are smaller than the LFSR and on filter-combiner stream ciphers. This allows us to cryptanalyze other configurations commonly found in practice. Finally, filter functions with vector output are sometimes used in stream ciphers to improve the throughput. Therefore the case when the Maiorana-McFarland functions have vector output is investigated. We found that the extra speed comes at the price of additional weaknesses which make the attacks easier.
  title={Time-Memory-Data Trade-off Attack on Stream Ciphers based on Maiorana-McFarland Functions},
  booktitle={IACR Eprint archive},
  keywords={Time-memory-data trade-off attack, Maiorana-McFarland functions.},
  note={Revised version of a paper published at ACNS 2006 conference 13859 received 17 Jun 2007, last revised 11 Dec 2007},
  author={Khoongming Khoo and Guang Gong and Hian-Kiat Lee and Guanhan Chew},