Explosive Knowledge: Cryptology in the 20th Century

In August 1960 the Pentagon announced that William Martin and Bernon Mitchell had not returned from vacation and said “there is a likelihood that they have gone behind the Iron Curtain”. On September 6 they appeared at a joint news conference at the House of Journalists in Moscow and announced they had requested asylum and Soviet citizenship. They revealed that they had worked for the National Security Agency (NSA). In this way the mission and activities of the NSA were made public for the first time [1]. Although these activities are much more wide-ranging than cryptology, this post will only be concerned with that small part.

All branches of knowledge had vigorously developed in the first half of the 20th century. All of it had been sustained by what I like to call a conversation: an open exchange of knowledge in books and journals. Before World War I this was also true for cryptology; afterwards, traffic on that channel fell silent. By the end of the 20th century the cryptology conversation was intense, wide-ranging, and immensely productive of innovations, of which bitcoin technology is but one example. In this post I trace the chain of events that led cryptology from its dark age, which lasted from 1918 to 1967, to its renaissance. My material is obtained, unless otherwise noted, from Crypto, a book by Steven Levy, published in 2001 [2].

The first of these events is the effect of the 1960 defection of Martin and Mitchell on David Kahn, a journalist for Newsday. Although Kahn was, like many others, an avid cryptology hobbyist and although as a journalist he kept eyes and ears open for anything to do with his pet subject, the existence of the NSA, as revealed by the Martin-Mitchell defection, was a revelation to Kahn.

After writing a background article for the New York Times Book Review, Kahn received offers from publishers to write a book. MacMillan, the one selected by Kahn, sent the manuscript to the Department of Defense for review. In his exposé of the NSA, The Puzzle Palace, James Bamford wrote that “innumerable hours of meetings and discussions, involving the highest levels of the agency, including the director, were spent in attempts to sandbag the book”. The reaction of the Department of Defense was that “publication would not be in the national interest”. When MacMillan did not respond by undertaking to refrain from publication, the director of the NSA met with the chairman of MacMillan, the editor, and the legal counsel to make a personal appeal for three specific deletions. Kahn considered these surprisingly inconsequential, and agreed. In return, the book was allowed to include the statement that it had been reviewed by the Department of Defense.

Kahn’s The Codebreakers [1] never became a bestseller, but sales remained steady for a long time. Its importance is due to the second link in the chain of events recounted here: it was found by the one person who desperately needed it and who was destined to change the course of the history of cryptology. That person was Whitfield Diffie

As a high-school student, Diffie had been fascinated by turning messages into cipher-encrypted mysteries. When he was an undergraduate at MIT, the aura of cryptology was eclipsed by the glamour of modern mathematics. When Diffie graduated in 1965, he found an effective way of evading the draft by taking a job at the Mitre Corporation, also in Cambridge, Massachusetts. His supervisor was a mathematician named Roland Silver. The work was for a project jointly undertaken with the MIT AI Lab, which became Diffie’s work location. This was the time when computer time-sharing systems were still experimental. But they were also used. CTSS, one of the systems, required users to have passwords. Many were opposed, with the result that the password file, in care of the system administrator, kept being hacked. Another timesharing system, confined to an inner circle of hackers, was called ITS, for Incompatible Timesharing System (CTSS stands of Compatible Time Sharing System), did not require passwords: every file was accessible to anyone.

Diffie was strongly in favour of privacy, but was not satisfied with CTSS where he had to trust his password to the system administrator. This reminded him of his boyhood hobby, cryptography. But this only tells you how to encrypt your files. If you want to share these files with someone else, you need to share the key, which could not be done securely in CTSS.

When Diffie discussed this problem with his boss, it transpired that a lot more was known about cryptology than was familiar from the hobbyist literature. Silver could infer this much, without being party to any indiscretions, from his contacts at NSA. Diffie was hit as by a lightning bolt by the twin insights: Cryptography is vital to privacy, clear from his experience with computer time-sharing at the AI lab, and now: Crucial information is being withheld on purpose. In fact, this organization acted as if it were the sole proprietor of the relevant mathematical truths. Diffie was electrified by the challenge to rediscover enough of the mathematics to rescue privacy of computer users, a category of people that, Diffie felt, would soon include many more than the researchers of the AI lab.

By 1969 Diffie was approaching draft cut-off age, so no longer needed the shelter of a defense contractor like Mitre. Diffie found a job at John McCarthy’s AI lab at Stanford. It is hard to overrate McCarthy’s stature in computer science. As a fresh PhD in mathematics he had invented the concept of Artificial Intelligence. As a young faculty member at MIT he discovered/invented the unique programming language LISP and pioneered computer time sharing. At SAIL, the Stanford AI Lab, he presided over a wide range of eclectic path breaking projects. One of the new arrivals, Diffie, found himself in conversations with the boss where they explored concepts beyond file encryption, such as key distribution and digital signatures.

Neither McCarthy nor Diffie knew enough about cryptology to gain any idea about how such concepts could be realized. By 1972 Diffie had read The Codebreakers [1]. With his girlfriend Mary Fischer he crisscrossed the country in search of people who knew or could provide pointers. Kahn responded to his cold call with an invitation to visit and allowed him to copy some reports by William Friedman. A rare event occurred in 1974 when Bill Reeds conducted a seminar at Harvard on cryptology. Being back in Cambridge led to new contacts, like with Bill Mann working on cryptography at BBN on a contract for the ARPAnet. Larry Roberts, the leader at ARPA of this project, had been rebuffed when he approached NSA for help with the necessary cryptography.

Inquiries led to Alan Tritter, a researcher at IBM knowledgeable about Identification Friend or Foe (IFF) devices. The way these devices used encryption nudged Diffie a bit closer to his later joint breakthrough with Hellman. Tritter pointed Diffie to his colleague at IBM, Horst Feistel, who had spent years of research on IFF when at Mitre. It turned out that Feistel had left early to spend the weekend at Cape Cod. Next stop Alan Konheim, the head of the mathematics group. Konheim knew a lot. For such people it is hard to know what they can say, so he said nothing. As a consolation prize Diffie got the suggestion to get in touch with one Martin Hellman, who had worked briefly in the IBM lab.

As it happened, Hellman was at Stanford. Everything fell in place: Hellman and Diffie got on like a house of fire, Diffie and Fischer got to live in the house of McCarthy, who left for a year’s sabbatical. The next year, 1975, Diffie and Hellman got their breakthrough: public-key cryptography was born.

When Kahn started his research in the New York Public Library in 1961, there was a lot to catch up on. Just at the time when publication failed to resume after World War I, a spate of inventions came to fruition. In 1919 Gilbert Vernam was granted a patent on an encrypting teletype, soon enhanced to the truly unbreakable one-time tape method. Independently, four inventors patented rotor machines: Arthur Scherbius (Germany) 1918, Hugo Koch (the Netherlands) 1919, Arvid Damm (Sweden) 1919, and Edward Hebern (US) 1921. Several of these names are associated with multiple patents; the simplest account is in Friedrich Bauer’s book [3]. Given these inventions, the combination of Vernam and rotors was but a small step.

With these breakthroughs the balance between code making and code breaking was gone. Nobody had any idea how to break messages encrypted by rotor machines. Moreover, these machines operated at greater speed and accuracy than the manual methods they replaced. Before World War II, research started on the analysis of rotor machines in Poland and in the US. The work of the Polish group escaped to England just before the German assault on Poland in September 1939 (look under “Rejewski” in [1]). The British started a massive code-breaking operation at that time. Primed by the Polish material and the efforts of top mathematicians such as A.M. Turing and I.J. Good, the British became, in deep secrecy, the most advanced in breaking traffic encrypted by rotor machines. Included in the Polish legacy was the use of “bombes”, mechanical devices for automatically trying out large numbers of hypothetical rotor settings.

Developments in the US between the wars were different, mainly due to one person, William Friedman. He was probably by far the most powerful cryptanalyst in the world. He worked for the military starting in the 1920s. In the 1930s he assembled a small group of well-trained people. By the time the war started in Europe this group was reading traffic encrypted with PURPLE, a rotor machine, the highest grade cipher of the Japanese. The contrast with the British effort is stark: no help from the Poles, without mechanical aids, and with only a small group of people.

The post-World War I developments were not secret in the sense of the Secrecy Act in the UK that was to keep the work in Bletchley Park hidden from view. In 1930 rotor machines were for sale by the owners of the Damm and Scherbius patents. These companies may have advertised the excellence of their methods, but not their substance; it was up to qualified organizations to get in touch and it was they who would be briefed.

Vernam was granted a patent in 1919 for a “Secret Signalling System”. The idea is that one can modify a teletype to transmit the exclusive OR (XOR) of two tapes, one containing the message and the other containing the key. At the receiving end an identical key tape is mounted and combined by XOR with the received encrypted message giving as result the message in the clear. When the key tape is random and has never been used, the Vernam system is secure. The Vernam patent was public, as intended by the founding fathers. Yet its description in The Codebreakers contributed to making this book a dangerous one from the point of view of NSA.

It may well be that Kahn’s book contained the state of the art when its first edition was published. This is a remarkable feat for a book aimed at the general public. The next publication to help end the dark period of cryptology was also aimed at the general public: in May 1973 Scientific American published “Cryptography and Computer Privacy” by Horst Feistel [4]. This article described the first advance in cryptography since 1919: the block cipher. The present encryption standard, AES, is a refined and scaled-up version of the device described by Feistel.

In 1934, when Horst Feistel was twenty years old, he immigrated into the US from Germany and started his studies at MIT. The 1941 declaration of war by by Germany on the US turned Feistel into an enemy alien; he was placed under house arrest. This meant he could move around Boston, but needed permission to visit his mother in New York. On January 31, 1944 his fortunes changed abruptly: the restraints were lifted and he became a US citizen. The next day he was given a security clearance and began work at the Air Force Cambridge Research Center [5].

Feistel had been interested in cryptography since his teens and mentioned this shortly after arriving at his new job. After a few years he had built a cryptography research group at AFCRC. According to [5] “over a period of several years it made a major contribution to modern cryptography, developing the first practical block ciphers”. They believe that it was the NSA who succeeded in shutting down the cryptographic work at AFCRC. The same fate befell Feistel’s attempts to set up a cryptographic group at the MIT Lincoln Lab and at Mitre Corporation, where Feistel moved next. Only when he was hired by IBM Research around 1970, could he pursue without interference his lifelong interest, cryptography.

When Feistel’s article appeared in 1973, it was only the second publication on the subject, after Kahn’s book, since cryptology entered into it dark age fifty years earlier. Soon after, something happened that put cryptography into the centre of the limelight: the 1975 promulgation by the National Bureau of Standards (NBS, now NIST for National Institute of Standards and Technology) of DES, the proposed federal data encryption standard. It turned out that shortly before, NBS had published a competition for an encryption standard. Apparently in that short period entries had closed, had been evaluated, and DES, IBM’s entry had been declared the winner.

This raised several questions:

  1. Who were the other entrants in the competition?
  2. What did their entries look like?
  3. Where did NBS get the expertise to evaluate their designs?
  4. What, if any, was the role of NSA?
  5. Why was the key shorter than the 128 bits of the “Lucifer” cipher described in Feistel’s Scientific American article?
  6. A natural key length for a little brother of Lucifer would have been 64 bits. Why was the key shortened further to 56 bits? (The shortening of “only 8 bits” amounted to the significant reduction in the work factor by a factor of 256.)
  7. What was the rationale behind the random-looking wiring of the S-boxes and the P-boxes? (Here we use “wiring” in the same metaphoric sense as “boxes”.)

Speculation was rife that the whole thing had been rigged between IBM, NBS, and NSA. Grist to the mill of an investigative journalist, who appeared in the form of Steven Levy, whose articles became his Crypto published in 2001 [2]. Some of the questions, though not all, were answered to my satisfaction by his findings.

First a bit of background. Around 1970 banks had become increasingly in need of cryptography, what with interbank funds transfer and automated clearing by telex. They needed guidance, which, in the absence of public research in cryptology, could only be supplied by NSA. They needed standardization: banks did not want to have to rely on in-house research groups and were not interested in competing on security. Only NBS could provide a standard.

As it happened, it was not some Bankers’ Association that set the process in motion, but the company who supplied most of them with technology: IBM. And within IBM it was a contract with Lloyd’s bank of London to provide automatic teller machines [5, p. 66]. Strong encryption was essential, and IBM was on its own. The only expertise existed in NSA, which had probably plenty strong encryption algorithms. But all this was classified, so could not be put in the hands of uncleared users. NSA declined to design a new, unclassified algorithm, possibly concerned that such an algorithm would reveal their design philosophy.

A group in IBM in Kingston, New York, headed by Walter Tuchman got the task of developing the algorithm. He learned about Lucifer on a visit to IBM research in Yorktown Heights and decided to use it, but adapted to the constraints imposed by the need to implement the algorithm in a compact hardware unit. The resulting algorithm became known as DSD-1, which IBM decided to enter in the NBS competition for the federal encryption standard. No matter that the deadline had passed: a call from the right person to the head of NBS sufficed to get the call for entries in the competition re-issued and to get IBM’s DSD-1 accepted.

NBS passed DSD-1 on to NSA, which summoned Tuchman and presented him with a list of demands amounting to the creation of a virtual annex of NSA within IBM to which all further work was to be confined. IBM has no choice in the matter if it were not to abandon the whole project: deployment of the technology would require export licenses. Ergo, by twisting IBM’s arm, DES (which is how DSD-1 was renamed), the federal Data Encryption Standard was finalised in a process under control of NSA.

Let us summarize by reviewing the above questions.

  1. As far as I know there were no other entrants. This is plausible, because the first call for entries closed without attracting any. By finding and employing Feistel IBM was a pioneer in cryptography at the time.
  2. Not applicable; see above.
  3. There was no cryptological expertise at NBS.
  4. The absence of expertise at NBS makes it clear that it was decided a priori that NSA would be involved.
  5. Hardware constraints.
  6. Tuchman gave as reason the need for eight parity bits. Levy quotes several sources who find this implausible.
  7. None even attempted. There was plenty of opportunity for NSA to modify the wiring.

As of 1975 there were still only Kahn (1967) and Feistel (1973) as lone harbingers of the end of the dark age in cryptology. On 17 March 1975, the proposed DES was published in the Federal Register. Public comments were requested; plenty were received. A furore arose about the opaqueness of the process and the eight missing bits of the key. IBM’s failure to provide a rationale for the wiring of the S-boxes caused critics like Diffie and Hellman to let paranoid interpretations run wild. The Washington Post and the New York Times provided plenty of coverage.

1975 was also the year that Diffie and Hellman got their breakthrough in public-key cryptography, as I noted earlier. The concept was published the next year as “New Directions in Cryptography”, IEEE Transactions on Information Theory, November 1976. It was only the concept; no implementation was provided. Ronald Rivest, Adi Shamir, and Leonard Adleman published one in April 1977 as an MIT technical report. It was what has since become famous as RSA public-key cryptography.

The authors took the unusual step of sending a copy of the report to Martin Gardner, who ran the “Mathematical Games” column in Scientific American. Gardner was in the habit of ending his column with some homework for his readers, with feedback in the next issue for selected successful solutions. For the RSA column, which appeared in the August 1977 issue, the puzzle was to solve a brief message encrypted with RSA. Because this time not all of the needed details were in the column, readers were invited to send a stamped, self-addressed envelope to MIT to receive a copy of the report.

Thousands of such requests arrived from all over the world. Before R, S, or A could organize an envelope-stuffing party, things started happening. The program for the IEEE International Symposium on Information Theory at Cornell University, scheduled for October, featured a presentation of the RSA work. IEEE received a letter from one Joseph A. Meyer, not identified by any affiliation, but with a home address and a member number, expressing concern about some of the presentations announced. This was the first time that academics heard of ITAR, the US International Traffic in Arms Regulation, of the fact that cryptographic devices were classified as munitions. Not only devices were deemed to be munitions, but also information facilitating them. And presenting such information in the US with non-US nationals present amounted to export. Violations of ITAR could result in fines, arrests, or jail terms.

Thanking Mr Meyer for the timely warning, IEEE took the position that, as long as they notified the presenters, this was not their problem. The notifications went out. In addition to pondering whether it was prudent to present new work in cryptography with non-US nationals in the room, MIT was presented with the fait accompli of a non-US national, in the form of Adi Shamir, not only having been in the room, but being one of the creators of the new work. And what was to be done about the envelope-stuffing party? Include relevant sections of ITAR? The 35-cent stamps provided by Scientific American readers were not going to be enough.

The administrations of MIT and Stanford decided to stick their necks out and assured the scheduled speakers that they would provide legal defense if needed. In their turn, the speakers decided to stick their necks out and decided to ignore the Meyer letter. The Cornell meeting went ahead as scheduled in October. In December of 1977 the envelope-stuffing party took place, with pizza (as reported in [2]) and beer (as imagined by me). None of the readers solved the message. By the time it was solved, decades later, column was no more, and none of R, S, and A could remember what the message was.

The new flood of publication in cryptology had started and has continued unabated to the present day. What has also continued, at least for the period covered in Levy’s book, was harassment. This took several forms.

  • ITAR. As an example, Philip Karn obtained permission under ITAR to export Bruce Schneier’s 1994 book Applied Cryptography, but not for the accompanying floppy disk, which contained no material that is not in the book.
  • Secrecy orders. George Davida had applied for a patent for a stream cipher. A Secrecy Order was placed on it. This implied two things: a patent would not be issued and the application and related research was deemed to be secret, with violation subject to fine, arrest, or jail term. Davida’s patent was based on his own research and had not relied on any classified material. The same was true of Carl Nicolai’s invention, the “Phasor Phone”. A Secrecy Order was also placed on his patent application.
  • Interference with funding. Adleman, the A of RSA, found that his application to NSF was approved, except with the note that NSA would supply the funds.
  • Retroactive classification. John Gilmore discovered works on cryptanalyis by William Friedman available in publicly accessible libraries and obtained copies of them. He was notified by the government that any further distribution would violate the Espionage Act, so could result in a fine, arrest, or a jail term.

In all these cases the government backed down, but only after a vigorous campaign by the victims, which involved paying for lawyers, engaging the media, and writing letters to representatives in congress.

Those who continue research in the field profit from these successful counter actions.

References

[1] The Codebreakers by David Kahn. MacMillan, New York, 1967; revised edition, Scribner, New York, 1996.
[2] Crypto by Steven Levy. Viking Penguin, 2001.
[3] Decrypted Secrets by F.L. Bauer. Springer-Verlag, Berlin-Heidelberg, 1997.
[4] “Cryptography and computer privacy” by Horst Feistel. Scientific American 228 (1973): 15-23.
[5] Privacy on the Line: the Politics of Wiretapping and Encryption by Whitfield Diffie and Susan Landau. MIT Press 1998; second edition 2007.
~

2 Responses to “Explosive Knowledge: Cryptology in the 20th Century”

  1. Lúthien Says:

    Very interesting read, thanks!
    Cheers from the Netherlands!

  2. Blissex Says:

    An interesting aspect of the discussion is that it is very NSA/GHCQ centered, but obviously the USA and UK are not the only players.

    Among traditional players Germany and Russia have very strong mathematical and cryptology communities, even if all their secrets were confiscated after the WW2 defeat for Germany and sold after the Cold War defeat for Russia. But they may have had time to rebuild. France and Italy have also strong and creative mathematical communities, but I doubt their governments spend much effort on cryptology.

    What will be really interesting to know, and perhaps in 100-300 years it will come out, is what is happening in the cryptology communities of China and India. Both countries have exceptionally strong mathematical communities, and low wages.
    Their governments are quite obsessed with secret services and can afford to have cryptology departments with at least 10 times the staff that the NSA can afford to have. They may well have thousands and probably dozens of thousands of very good cryptography and cryptanalysis researchers.
    Plus a very large part of the world’s software is written in Indian or by indians, and a nearly all of the world’s electronic products are designed and made in China, and I doubt that the secret services of either country are too lazy or stupid to miss the relevant opportunities.

Leave a Reply to Lúthien Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: