Cryptanalysis of TWOPRIME

Don Coppersmith, David Wagner, Bruce Schneier, and John Kelsey

Fast Software Encryption, Fifth International Workshop Proceedings (March 1998), Springer-Verlag, 1998, pp. 32-48.

ABSTRACT: Ding et al. [DNRS97] propose a stream generator based on several layers. The linear combination step allows us to recover half the key with minimal effort. Next, we show that the various bytes are insufficiently mixed by these layers, enabling an attack similar to those on two-loop Vigenere ciphers to recover the remainder of the key. Combining these techniques lets us recover the entire TWOPRIME key. We require the generator to produce 233 blocks 235 bytes), or 19 hours worth of output, of which we examine about one million blocks (223 bytes); the computational workload can be estimated at 228 operations. Another set of attacks trades off texts for time, reducing the amount of known plaintext needed to just eight blocks (64 bytes), while needing 232 time and 232 space. We also show how to break two variants of TWOPRIME presented in the original paper.

[full text – postscript] [full text – PDF (Acrobat)]

Categories: Algorithm Analyses

Sidebar photo of Bruce Schneier by Joe MacInnis.