SASC 2006 workshop without proceedings

**Abstract.**
We improve on the best known cryptanalysis of the stream cipher Py by using
a hidden Markov model for the carry bits in addition operations where a
certain distinguishing event takes place, and constructing from it an
"optimal distinguisher" for the bias in the output bits which makes more use
of the information available. We provide a general means to efficiently
measure the efficacy of such a hidden Markov model based distinguisher, and
show that our attack improves on the previous distinguisher by a factor of
2^16 in the number of samples needed. Given 2^72 bytes of output we can
distinguish Py from random with advantage greater than 1/2, or given only a
single stream of 2^64 bytes we have advantage 0.03.

- Improved cryptanalysis of Py (PDF)
- Slides from the talk (PDF)
- Expanded slides from RHUL seminar (PDF)
- ePrint

- eSTREAM page on Py
- Eli Biham and Jennifer Seberry, Py specification (PS)
- Gautham Sekar, Souradyuti Paul and Bart Preneel, Distinguishing Attacks on the Stream Cipher Py (PDF)
- Wikipedia page on Py