#### by John Burroughs, David Lieberman, and Jim Reeds

Andrew Gleason was a senior at Yale on December 7, 1941, when the
Japanese bombed Pearl Harbor. He applied for a commission in the navy;
upon his graduation the following June he reported to their
crypanalytic service: the Office of Chief of Naval Operations (OPNAV),
20th Division of the Office of Naval Communications, G Section,
Communications Security (OP-20-G). There he joined a group of eight to
ten mathematicians working to crack enemy codes. The group included
Robert E. Greenwood
and
Marshall Hall, Jr.,
one of Andy’s Yale
professors. The National Archives contains declassified documents
describing much of the wartime work of OP-20-G. We found there a set
called *Enigma Studies*
[e2],
which describes the group’s contributions
to the attack on the German Enigma machine. These documents showcase
that part of Gleason’s work which we will describe.

The Enigma ciphers presented diverse and rapidly mutating challenges. The Germans used several different models of the Enigma machine. Each day they changed the keys on each of perhaps a hundred or so different communications networks. Three of those networks were “Shark”, used by the Atlantic U-boat fleet; “Sunfish”, by blockade runners and the German U-boats in the Pacific; and “Seahorse”, for traffic between German navy HQ and their attaché in Tokyo. Breaking one system or one day’s traffic provided only clues towards breaking the others, clues which were sometimes misleading. Several times during the war the Germans made significant modifications to the Enigma.

OP-20-G worked on Enigma in collaboration with the British cryptanalysts at the Government Code and Cypher School at Bletchley Park, in particular, with “Hut 8”, whose most famous member was Alan Turing. Shortly before the U.S. entered the war the British code breakers began teaching their American counterparts about the Enigma problem: the general theory and notation (largely due to Turing), a host of particular solution methods, and the design of a special-purpose electromechanical computing machine, the “Bombe”, which carried out one of the steps of the arduous constrained trial-and-error solution process. Some of these lessons the British had learned from the Poles just before the war; some they had developed during the first two years of the war. At about the time the U.S. entered the war the German navy began using a four-wheel model of the Enigma machine, against which the existing Bombes (designed for attacking three-wheel Enigmas) were comparatively ineffective. This ended the Allies’ ability to read Shark in a timely manner during 1942 and early 1943, with devastating consequences to Allied shipping.

In November 1942 Turing visited the U.S. to assist the Americans in mastering Bletchley’s methods and to consult on the construction of the American Bombes designed to attack the four-wheel Enigma. Andrew Hodges’s biography of Turing discusses Turing’s report back to Bletchley, in which he expresses some dismay that the Americans really had not grasped the British work-saving algorithmic ideas, relying instead on technological overkill. Nevertheless, he was impressed with the mathematicians being hired at OP-20-G, in particular “the brilliant young Yale graduate mathematician, Andrew Gleason” ([e3], p. 243). Hodges relates an anecdote from this visit:

Gleason and Joe Eachus “looked after Alan during his period in Washington. Once Gleason took Alan to a crowded restaurant on 18th Street. They were sitting at a table for two, just a few inches from the next one, and talking of statistical problems, such as that of how to best estimate the total number of taxicabs in a town, having seen a random selection of their license numbers. The man at the next table was very upset by hearing this technical discussion, which he took to be a breach of ‘security’. …Alan said, ‘Shall we continue our conversation in German?’ ”

At first OP-20-G was the junior partner to Hut 8, but later it took the lead in attacking Seahorse. A recent paper [e6] describes the Seahorse story in considerable detail. We draw on that account. The Hut 8 team had failed to solve Seahorse because traffic externals convinced them that encryption was being done not by a standard naval Enigma machine but by a simpler version of Enigma. In March 1943 the problem was turned over to OP-20-G. Their analysis revealed new structure in the traffic that allowed them to reject the hypothesized simpler version of Enigma to correctly diagnose an underlying naval Enigma and to specify a menu (i.e., a program) for the naval Bombes so they could efficiently read the traffic.

Reading the first-hand accounts of this work in the *Enigma Studies* E-2
and E-4, one can share the excitement, the frustrations, and finally
the elation when success was achieved. Greenwood’s “History of
Kriegsmarine attack” (paper 6 in E-2) describes how the group first
discovered the working of Seahorse’s “indicators”, which told the
message recipient how to set up his receiving Enigma machine. These
were appended to the message, encrypted in a “throw-on” cipher. The
standard method of attack required interception of a large number of
messages from the same day. A successful attack revealed which set of
four wheels was being used in the machine and the setting used to
encipher all the indicators. One could then decipher the indicators
and in turn use them to decipher all the day’s messages.

Marshall Hall noticed an interesting feature of the throw-on indicators. On a given day the set of first letters of encrypted indicators for Berlin-to-Tokyo messages was disjoint from the set of first letters for Tokyo to Berlin, but the sets changed from day to day. Gleason came up with and statistically tested a simple hypothesis explaining this, namely, that the wheel settings — the unencrypted form of the indicators — started with letters A–M for messages from Tokyo to Berlin and letters N–Z for the opposite direction.

In “Kriegsmarine indicators” (paper 5 in E-2) Gleason, Greenwood, and Hall show how this structure allowed one to derive extra equations, which led to much more efficient Bombe runs. The practical implication was that far fewer messages needed to be intercepted in any one day to be able to work out that day’s key. In August 1943 a Bombe run at Bletchley using these ideas broke the first Seahorse messages. This confirmed the model for the underlying Enigma and its indicator system and verified the correctness of their attack programs. This concluded the research phase. The problem was then turned over to a development team. Using the newly available four-wheel naval Bombes and the special tricks discovered for Seahorse, they were able to read Seahorse sporadically in 1943 and almost continuously in 1944 and 1945, resulting in the decryption of thousands of messages.

An excellent discussion of the application of group theoretic ideas to
the solution of Enigma problems is given in Greenwood, Gleason,
Clifford,
and
Hanson’s
“Enigma wiring recovery from the reading of a
depth” (paper 7 in E-4, dated 19 April 1945).1
Simplifying slightly, they reduce the problem of finding the four
permutations performed by the Enigma wheels to one of solving a system
of simultaneous equations in permutations. The right side of the
__\( t \)__-th equation is the permutation effected by Enigma to encipher the
__\( t \)__-th plain text character. These are assumed “known” (at least in
part) by “depth reading”. The left side of the __\( t \)__-th equation
expresses the known way the Enigma machine composes the unknown rotor
wirings at time __\( t \)__. The paper shows how this problem can be broken
into a series of subproblems of the form “given several permutation
pairs __\( (\pi_i , \sigma_i) \)__, find a single permutation __\( x \)__ for which __\( \pi_i =
x\sigma_i x^{-1} \)__ for all __\( i \)__.” Interestingly, one of these subproblems is solved
by exhibiting an isomorphism of a pair of labeled graphs. The
explanation, unlike most technical Enigma exposition of the era, such
as found in
[e1],
is couched in standard mathematical terminology.2
According to one modern commentator,
[e7],
the method in this paper “is
a lot more powerful than the ‘Rodding’ and ‘Buttoning-up’ methods
described by Alan Turing, mainly because it allows recovery of the
wiring even when the Stecker is unknown.” The exposition is both
compelling and charming. One can imagine one is listening to the young
Andy Gleason in some of
the informal asides:

The reader may wonder why so much is left to the reader. A book on swimming strokes may be nice to read, but one must practice the strokes while actually in the water before one can claim to be a swimmer. So if the reader desires to actually possess the knowledge for recovering wiring from a depth, let the reader get his paper and pencils, using perhaps four colors to avoid confusion in the connecting links, and go to work…. Note: the writing of\( C^{-1} C^2 \)instead of\( C^1 \)is a whim of the writer. Please humor him to this extent….

The final page of the typescript (shown to the right) concludes:

The recovery of wiring from a depth can be a very interesting problem. Let the reader surround himself with pleasant working conditions and try it.

— as if this were a problem in pure mathematics, not an urgent wartime endeavor.

The mass production of four-wheel Bombes led to dramatic successes against Seahorse and the other naval Enigma problems. Research then focused on Japanese machine ciphers. A major achievement of this effort was the diagnosis of the naval cipher Coral and the subsequent decryption of Coral traffic throughout 1944–45. This required, as in Enigma, a painstaking examination of the traffic to find and explain statistical structure and the design and programming of new special purpose machines. Gleason’s mathematical contributions to this work included the eponymous “Gleason crutch”, a method for estimating extreme tail probabilities for sums of random variables. It can be regarded as a version of Chernoff’s theorem in large deviations theory, and like it, it is based on the idea of exponential tilting.

As the war came to an end, Gleason participated in efforts to systematically document the techniques developed by OP-20-G and to set up a postwar curriculum for training cryptanalysts. He also participated in courses and seminars on both applied methods and mathematical foundations, including (prophetically) one based on Pontrjagin’s new book on topological groups.3

Gleason’s codebreaking work exhibits some of his characteristic traits. One is his extraordinary quickness in grasping the heart of a problem and rethinking how to solve it from first principles. He says of himself, “I have always felt that it’s more crucial for me to come to grips on my terms with the most elementary aspects of a subject. I haven’t worried much about the advanced aspects” ([e4], p. 88). He was particularly effective as a cryptanalyst, because (in his own words) he “learned to do something that a lot of pure mathematicians don’t know how to do…how to do quick and dirty mathematics. It’s an interesting knack to be able to make a quick appraisal as to whether there is sufficient statistical strength in a situation so that hopefully you will be able to get an answer out of it” ([e4], p. 87).

Gleason’s insight into the mathematics underlying cryptography was greater than that of most of his colleagues. Even during the war he prepared lectures and notes for them to help develop their understanding and working knowledge of the mathematical fundamentals. His OP-20-G lecture notes and exercises on probability and statistics were later gathered up and edited into a short textbook used for years in introductory courses at NSA and subsequently reprinted commercially [3]. We were amused to find that one of the exercises in the book is to estimate the number of taxicabs in a town, having seen a random selection of their license numbers.

Legend has it that, in general, the cryptanalysts in World War II did not think much of the mathematicians down the hall, who were always telling them what was wrong with their counts and suggesting “proper” statistics, which in the end didn’t produce plain text. But Gleason was different. He was approachable. He listened carefully to their problems and ideas, and his advice was always useful.

After the war Gleason began his academic career at Harvard. He was reactivated in 1950, at the start of the Korean War, and served at the naval facility on Nebraska Avenue. Cryptographic systems had increased in complexity, incorporating digital technology that posed new challenges and dramatically increased the need for trained mathematicians. Many of Gleason’s colleagues at Nebraska Avenue went on to significant careers at the newly formed NSA and in emerging academic areas of mathematics and computer science. These included Marshall Hall, Joe Eachus, Dick Leibler, Oscar Rothaus, Howie Campaigne, Bill Blankinship, and Ned Neuburg. In the spring of 1951, Lt. Cmdr. Gleason, Lt. Cmdr. Hall, and Cmdr. Miller4 were sent to visit mathematics departments around the country to recruit mathematicians with advanced degrees. They found sixty to eighty. One of them, R. Highbarger, told us, “After a few weeks at training school we located in a basement room next to the kitchen grease pit at Arlington Hall Station…. There, we took various CA [cryptanalysis] courses and a bunch of math courses, the best of which were taught by Andy Gleason.” Some twenty of these “junior mathematicians” were to become the professional leaders of the nation’s cryptanalytic effort in the 1960s and 1970s.

Most of Gleason’s applied work during this period remains classified. In his spare time he worked on Hilbert’s Fifth Problem. He later said, “there wasn’t a single day that I didn’t think about it some of the time…. I made a real breakthrough on the problem around February of 1952” ([e4], p. 91). R. A. Leibler drove Gleason to Princeton to present a talk on his new result at the Institute for Advanced Study. It was snowing hard. Going up Alexander Road they were nearly hit when their car slid through a red light. Leibler told us that Gleason came in dressed in his navy uniform. This caused some initial surprise, which soon turned to excitement and enthusiasm. Gleason lectured all day.

After the Korean War, Gleason returned to the Harvard faculty but continued as an advisor to the nation’s intelligence and security programs for fifty years. He served on the NSA Scientific Advisory Board from the mid-1950s through the mid-1960s, where he helped shape the NSA’s response to the evolving challenges of the cold war. He continued as an active recruiter for the NSA and for the Communications Research Division (CRD) of the Institute for Defense Analyses, often writing or calling the director to recommend a mathematician who might be particularly well suited for an appointment to the program. He participated in NSA summer research projects (SCAMP) and in the formative technical programs of the CRD. He was a member of the first CRD advisory committee in 1959, then served from 1976 to 1979, from 1986 to 1988, and again from 2004 to 2006.

L. P. Neuwirth, writing in 1992, recalled Gleason’s participation in the CRD programs:

He invariably had something useful to contribute, and the work of others benefited enormously, either directly or indirectly(sometimes with attribution, sometimes without)from his ideas. His contributions have in many cases been lasting, and were made in sufficient generality and depth that they still find application 45 years later. His name is associated with some of these notions…the Gleason semigroup, Gleason weights, and the Gleason crutch…[his]22 papers in cryptologic mathematics span the time period from 1945 to 1980. Their content range is wide, and includes algebra, combinatorics, analysis, statistics and computer science.

Gleason did pioneering work in computational algebra in response to
the emerging need for good pseudorandom number generators and
efficient error correcting codes. In 1955 the Gleason–Marsh Theorem
[1]5
provided a method for generating irreducible polynomials of huge
degree over __\( \mathrm{GF}(q) \)__. (For any __\( d \)__, one could generate irreducibles of
degree __\( q^d - 1 \)__.) In 1961 in a 10-page typescript
[2]
Gleason
described algorithms he devised for factoring and irreducibility
testing of univariate polynomials over __\( \mathrm{GF}(q ) \)__. Programs implementing
these ideas had many years of utility. We do not undertake to compare
Gleason’s unpublished approach to other methods soon to follow:
Berlekamp
(1967),
Zassenhaus
(1969),
Cantor–Zassenhaus (1981). For a
recent historical survey of the field, see, for example,
[e5].
Neuwirth concluded:

This unfortunately restricted list of some of the ideas he had and some of the areas to which he contributed perhaps sheds a little light on his many contributions to a very much hidden science, and gives some understanding of the unusually high regard in which he is held by the intelligence community… ([4], pp. 65–66).

Note on the references: [e2] is a nine-volume anthology of technical papers, compiled at the end of the war, covering all of OP-20-G’s Enigma research activities. The volume titles are E-1, Click Process; E-2, Indicator Attacks; E-3, Statistical Studies; E-4, Wiring Recovery; E-5, Bomb Computation; E-6, Duenna; E-7, Miscellaneous; E-8, Reports from England; and E-9, Bulldozer. Each bears a Radio Intelligence Publication (RIP) number. Volumes 1 through 8 are RIP numbers 603 through 610, and volume 9 is RIP 601. We will make available online articles from E-2, E-4, and E-9 written by Gleason and his colleagues.6

#### Acknowledgements

We are also grateful to R. Erskine and F. Weierud for searching through the wartime diaries of OP-20-G and the history of Coral, which they had copied at the National Archives. They located information about Gleason’s activities and forwarded many interesting items to us.