You are looking at a specific version 20080709:030453 of this paper. See the latest version.

Paper 2007/242

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

Khoongming Khoo, Guanhan Chew, Guang Gong and Hian-Kiat Lee

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.

Note: This is a revised version of a paper "The Rainbow Attack on Stream Ciphers based on Maiorana-McFarland Functions" presented at the ACNS 2006 conference \cite{acns06}. The computation of the time-memory-data (TMD) trade-off and rainbow attack complexities in \cite{acns06} were errorneous, and we found that the rainbow attack with multiple data does not improve on the TMD attack. This paper presents the corrected TMD attack on Maiorana-McFarland based stream ciphers.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Revised version of a paper published at ACNS 2006 conference
Keywords
Time-memory-data trade-off attackMaiorana-McFarland functions.
Contact author(s)
kkhoongm @ dso org sg
History
2008-07-09: last of 4 revisions
2007-06-19: received
See all versions
Short URL
https://ia.cr/2007/242
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.