Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers

摘要

In 1980 Hellman introduced a general technique for breaking arbitrary block ciphers with N possible keys in time T and memory M related by the tradeoff curve TM{sup}2=N{sup}2 for 1≤T≤N. Recently, Babbage and Golic pointed out that a different TM=N tradeoff attack for 1≤T≤D is applicable to stream ciphers, where is the amount of output data available to the attacker. In this paper we show that a combination of the two approaches has an improved time/memory/data tradeoff for stream ciphers of the form TM{sup}2 D{sup}2=N{sup}2 for any D{sup}2≤T≤N. In addition, we show that stream ciphers with low sampling resistance have tradeoff attacks with fewer table lookups and a wider choice of parameters.