[As usual I have no more information than presented here. Contact joanne@theory.lcs.mit.edu for more information. --AW]

MIT TOC SEMINAR

Thursday, May 12, 1994

Refreshments at 4:00pm, Talk at 4:15pm in NE43-518

``How to Break Gifford's Cipher''

by Alan T. Sherman* University of Maryland Baltimore County

(* Joint work with Thomas R. Cain. Part of this work was carried out while Sherman was a member of the Institute for Advanced Computer Studies, University of Maryland College Park.)

ABSTRACT

We present and implement a ciphertext-only algorithm to break Gifford's cipher, a stream cipher designed in 1984 by David Gifford of MIT and used to encrypt New York Times and Associated Press wire reports. Applying linear algebra over finite fields, we exploit a time-space tradeoff to separately determine key segments derived from the primary rational canonical decomposition of the feedback function This work, the first proposed attack on Gifford's cipher, illustrates a powerful attack on stream ciphers and shows that Gifford's cipher is ill-suited for encrypting broadcast data in the MIT-based {\it Boston Community Information System (BCIS)}.

Gifford's cipher is a {\it filter generator}---a linear feedback shift register with nonlinear output. Our cryptanalytic problem is to determine the secret 64-bit initial fill, which is changed for each news article. Our attack runs in $2^{27}$ steps and $2^{18}$ bytes of memory, which is a significant shortcut over the $2^{64}$ steps required for a straightforward exhaustive search of all initial fills. Given ciphertext only from one encrypted article, our prototype implementation running on a loosely-coupled network of eight Sparcstations finds the article key within approximately four hours on average. Exploiting a key-management flaw of the BCIS, we also compute at no additional cost the corresponding master key, used for one month to encrypt all article keys in the same news section. In addition, from the decomposition of $f$, we compute the exact probability distribution of the leader and cycle lengths of all state sequences generated by Gifford's cipher.

Host: Shang Hua-Teng