Paper 2012/339

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
CryptanalysisStream cipherPermutationJohn Nash
Contact author(s)
eldad z1 @ gmail com
History
2012-11-13: revised
2012-06-22: received
See all versions
Short URL
https://ia.cr/2012/339
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/339,
      author = {Adi Shamir and Eldad Zinger},
      title = {Practical Polynomial Time Known Plaintext Attacks on a Stream Cipher Proposed by John Nash},
      howpublished = {Cryptology ePrint Archive, Paper 2012/339},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/339}},
      url = {https://eprint.iacr.org/2012/339}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.