Paper 2006/030 Original: eprint.iacr.org/2006/030 ↗
Improved cryptanalysis of Py
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.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2006-01-27: last updated
- 2006-01-27: published
- Short URL
- https://ia.cr/2006/030
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2006/030,
author = {Paul Crowley},
title = {Improved cryptanalysis of Py},
howpublished = {Cryptology {ePrint} Archive, Paper 2006/030},
year = {2006},
url = {https://eprint.iacr.org/2006/030}
}