Cryptology ePrint Archive: Report 2006/030

Improved cryptanalysis of Py

Paul Crowley

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.

Category / Keywords: secret-key cryptography / Py, symmetric cryptanalysis, hidden Markov model

Publication Info: SASC 2006 workshop without proceedings

Date: received 25 Jan 2006

Contact author: paul at ciphergoth org

Available formats: PDF | BibTeX Citation

Version: 20060127:181449 (All versions of this report)

Discussion forum: Show discussion | Start new discussion