HOW TO BREAK GIFFORD'S CIPHER
Thomas R. Cain, Alan T. Sherman · Cryptologia · 1997
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 determine key segments derived from a 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 Gilford's cipher is ill-suited for encrypting broadcast data in the MIT-based Boston Community Information System (BCIS). Gifford's cipher is a 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. Representing the feedback function as a binary matrix F, we decompose the vector space of register states into a direct sum of four F-invariant subspaces determined from the primary rational canonical form of F. The attack computes segments of the key corresponding to these invariant subspaces, which have dimensions 24, 5, 6, and 29, respectively. Because the dimension-24 subspace corresponds to a nilpotent transformation, Gilford's cipher effectively uses only 40 bits of key. With a novel hashing technique, we search these 40 bits in only 227 steps. From the decomposition of F, we also compute the exact probability distribution of the leader and cycle lengths of all state sequences generated by Gifford's cipher. Our attack runs in 227 steps and 218 bytes of memory, which is a significant shortcut over the 264 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.