You are looking at a specific version 20081129:234524 of this paper. See the latest version.

Paper 2007/230

New Weaknesses in the Keystream Generation Algorithms of the Stream Ciphers TPy and Py

Gautham Sekar and Souradyuti Paul and Bart Preneel

Abstract

The stream ciphers Py, Py6 designed by Biham and Seberry were promising candidates in the ECRYPT-eSTREAM project because of their impressive speed. Since their publication in April 2005, a number of cryptanalytic weaknesses of the ciphers have been discovered. As a result, a strengthened version Pypy was developed to repair these weaknesses; it was included in the category of `Focus ciphers' of the Phase II of the eSTREAM competition. However, even the new cipher Pypy was not free from flaws, resulting in a second redesign. This led to the generation of three new ciphers TPypy, TPy and TPy6. The designers claimed that TPy would be secure with a key size up to 256 bytes, i.e., 2048 bits. In February 2007, Sekar \emph{et al.\ }published an attack on TPy with $2^{281}$ data and comparable time. This paper shows how to build a distinguisher with $2^{268.6}$ key/IVs and one outputword for each key (i.e., the distinguisher can be constructed within the design specifications); it uses a different set of weak states of the TPy. Our results show that distinguishing attacks with complexity lower than the brute force exist if the key size of TPy is longer than 268 bits. Therefore, for longer keys, our attack constitutes an academic break of the cipher. Furthermore, we discover a large number of similar bias-producing states of TPy and provide a general framework to compute them. The attacks on TPy are also shown to be effective on Py.

Note: A shortened version of this paper appears in the proceedings of ISC-2007. We have fixed a typographical error that appears in the ISC proceedings version. Moreover, we found that the upper bound on the bias probability is more than what we had earlier calculated, thereby improving the attack presented at ISC'07. This is also accounted in this revised edition.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. A shortened version of this paper appears in the proceedings of ISC 2007. We have fixed a typographical error that appears in the ISC proceedings version. Moreover, we found that the upper bound on the bias probability is more than what we had earlier calculated, thereby improving the attack presented at ISC'07. This is also accounted in this revised edition.
Keywords
Stream CipherPRBGDistinguisher
Contact author(s)
Gautham Sekar @ esat kuleuven be
History
2008-11-29: last of 4 revisions
2007-06-19: received
See all versions
Short URL
https://ia.cr/2007/230
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.