MIT talk on Cipher breaking

[Alan Wexelblat]

[As usual I have no more information than presented here.  Contact
joanne at 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