**Practical Polynomial Time Known Plaintext Attacks on a Stream Cipher Proposed by John Nash**

*Adi Shamir and Eldad Zinger*

**Abstract: **In this paper we present two known plaintext attacks on a stream cipher
which was developed by John Nash in the early 1950's but whose design
was declassified by the NSA only in 2012. The main attack reduces
the claimed security of the scheme from $\left(\left(n-1\right)!\cdot2^{n}\right)^{2}$
to $O\left(n^{2}\log^{3}n\right)$, where $n$ is a security parameter.
This attack succeeds with high probability for randomly chosen keys
even when the only thing we know about the plaintext is that a small
fraction of isolated plaintext bits are slightly biased, but always
fails for a certain well defined class of keys which is exponentially
large but a negligibly small fraction of all the possible keys. To
show that it would not suffice to simply restrict the choice of keys
to this class, we develop a different attack which works best for
the subset of keys which are hardest to find by the first attack.
This attack reduces the security of the scheme from $2^{O\left(n\right)}$
to $O\left(n^{2}\right)$. Both attacks were verified with actual
simulations, finding cryptographic keys which are thousands of bits
long in just a few minutes on a single PC.

**Category / Keywords: **Cryptanalysis, Stream cipher, Permutation, John Nash

**Date: **received 14 Jun 2012, last revised 13 Nov 2012

**Contact author: **eldad z1 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20121113:153112 (All versions of this report)

**Short URL: **ia.cr/2012/339

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]