International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Improved cryptanalysis of Py

Authors:
Paul Crowley
Download:
URL: http://eprint.iacr.org/2006/030
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21523,
  title={Improved cryptanalysis of Py},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Py, symmetric cryptanalysis, hidden Markov model},
  url={http://eprint.iacr.org/2006/030},
  note={SASC 2006 workshop without proceedings paul@ciphergoth.org 13173 received 25 Jan 2006},
  author={Paul Crowley},
  year=2006
}