Cryptography

Copeland, B. Jack, ed. Colossus. Oxford: Oxford University Press, 2006. ISBN 978-0-19-953680-1.
During World War II the British codebreakers at Bletchley Park provided intelligence to senior political officials and military commanders which was vital in winning the Battle of the Atlantic and discerning German strategic intentions in the build-up to the invasion of France and the subsequent campaign in Europe. Breaking the German codes was just barely on the edge of possibility with the technology of the time, and required recruiting a cadre of exceptionally talented and often highly eccentric individuals and creating tools which laid the foundations for modern computer technology.

At the end of the war, all of the work of the codebreakers remained under the seal of secrecy: in Winston Churchill's history of the war it was never mentioned. Part of this was due to the inertia of the state to relinquish its control over information, but also because the Soviets, emerging as the new adversary, might adopt some of the same cryptographic techniques used by the Germans and concealing that they had been compromised might yield valuable information from intercepts of Soviet communications.

As early as the 1960s, publications in the United States began to describe the exploits of the codebreakers, and gave the mistaken impression that U.S. codebreakers were in the vanguard simply because they were the only ones allowed to talk about their wartime work. The heavy hand of the Official Secrets Act suppressed free discussion of the work at Bletchley Park until June 2000, when the key report, written in 1945, was allowed to be published.

Now it can be told. Fortunately, many of the participants in the work at Bletchley were young and still around when finally permitted to discuss their exploits. This volume is largely a collection of their recollections, many in great technical detail. You will finally understand precisely which vulnerabilities of the German cryptosystems permitted them to be broken (as is often the case, it was all-too-clever innovations by the designers intended to make the encryption “unbreakable” which provided the door into it for the codebreakers) and how sloppy key discipline among users facilitated decryption. For example, it was common to discover two or more messages encrypted with the same key. Since encryption was done by a binary exclusive or (XOR) of the bits of the Baudot teleprinter code, with that of the key (generated mechanically from a specified starting position of the code machine's wheels), if you have two messages encrypted with the same key, you can XOR them together, taking out the key and leaving you with the XOR of the plaintext of the two messages. This, of course, will be gibberish, but you can then take common words and phrases which occur in messages and “slide” them along the text, XORing as you go, to see if the result makes sense. If it does, you've recovered part of the other message, and by XORing with either message, that part of the key. This is something one could do in microseconds today with the simplest of computer programs, but in the day was done in kiloseconds by clerks looking up the XOR of Baudot codes in tables one by one (at least until they memorised them, which the better ones did).

The chapters are written by people with expertise in the topic discussed, many of whom were there. The people at Bletchley had to make up the terminology for the unprecedented things they were doing as they did it. Due to the veil of secrecy dropped over their work, many of their terms were orphaned. What we call “bits” they called “pulses”, “binary addition” XOR, and ones and zeroes of binary notation crosses and dots. It is all very quaint and delightful, and used in most of these documents.

After reading this book you will understand precisely how the German codes were broken, what Colossus did, how it was built and what challenges were overcome in constructing it, and how it was integrated into a system incorporating large numbers of intuitive humans able to deliver near-real-time intelligence to decision makers. The level of detail may be intimidating to some, but for the first time it's all there. I have never before read any description of the key flaw in the Lorenz cipher which Colossus exploited and how it processed messages punched on loops of paper tape to break into them and recover the key.

The aftermath of Bletchley was interesting. All of the participants were sworn to secrecy and all of their publications kept under high security. But the know-how they had developed in electronic computation was their own, and many of them went to Manchester to develop the pioneering digital computers developed there. The developers of much of this technology could not speak of whence it came, and until recent years the history of computing has been disconnected from its roots.

As a collection of essays, this book is uneven and occasionally repetitive. But it is authentic, and an essential document for anybody interested in how codebreaking was done in World War II and how electronic computation came to be.

March 2013 Permalink

Ferguson, Niels and Bruce Schneier. Practical Cryptography. Indianapolis: Wiley Publishing, 2003. ISBN 0-471-22357-3.
This is one of the best technical books I have read in the last decade. Those who dismiss this volume as Applied Cryptography Lite” are missing the point. While the latter provides in-depth information on a long list of cryptographic systems (as of its 1996 publication date), Practical Cryptography provides specific recommendations to engineers charged with implementing secure systems based on the state of the art in 2003, backed up with theoretical justification and real-world experience. The book is particularly effective in conveying just how difficult it is to build secure systems, and how “optimisation”, “features”, and failure to adopt a completely paranoid attitude when evaluating potential attacks on the system can lead directly to the bull's eye of disaster. Often-overlooked details such as entropy collection to seed pseudorandom sequence generators, difficulties in erasing sensitive information in systems which cache data, and vulnerabilities of systems to timing-based attacks are well covered here.

November 2003 Permalink

Haynes, John Earl and Harvey Klehr. Venona: Decoding Soviet Espionage in America. New Haven, CT: Yale University Press, 1999. ISBN 0-300-08462-5.
Messages encrypted with a one-time pad are absolutely secure unless the adversary obtains a copy of the pad or discovers some non-randomness in the means used to prepare it. Soviet diplomatic and intelligence traffic used one-time pads extensively, avoiding the vulnerabilities of machine ciphers which permitted World War II codebreakers to read German and Japanese traffic. The disadvantage of one-time pads is key distribution: since every message consumes as many groups from the one-time pad as its own length and pads are never reused (hence the name), embassies and agents in the field require a steady supply of new one-time pads, which can be a logistical nightmare in wartime and risk to covert operations. The German invasion of the Soviet Union in 1941 caused Soviet diplomatic and intelligence traffic to explode in volume, surpassing the ability of Soviet cryptographers to produce and distribute new one-time pads. Apparently believing the risk to be minimal, they reacted by re-using one-time pad pages, shuffling them into a different order and sending them to other posts around the world. Bad idea! In fact, reusing one-time pad pages opened up a crack in security sufficiently wide to permit U.S. cryptanalysts, working from 1943 through 1980, to decode more than five thousand pages (some only partially) of Soviet cables from the wartime era. The existence of this effort, later codenamed Project VENONA, and all the decoded material remained secret until 1995 when it was declassified. The most-requested VENONA decrypts may be viewed on-line at the NSA Web site. (A few months ago, there was a great deal of additional historical information on VENONA at the NSA site, but at this writing the links appear to be broken.) This book has relatively little to say about the cryptanalysis of the VENONA traffic. It is essentially a history of Soviet espionage in the U.S. in the 1930s and 40s as documented by the VENONA decrypts. Some readers may be surprised at how little new information is presented here. In essence, VENONA messages completely confirmed what Whittaker Chambers (Witness, September 2003) and Elizabeth Bentley testified to in the late 1940s, and FBI counter-intelligence uncovered. The apparent mystery of why so many who spied for the Soviets escaped prosecution and/or conviction is now explained by the unwillingness of the U.S. government to disclose the existence of VENONA by using material from it in espionage cases. The decades long controversy over the guilt of the Rosenbergs (The Rosenberg File, August 2002) has been definitively resolved by disclosure of VENONA—incontrovertible evidence of their guilt remained secret, out of reach to historians, for fifty years after their crimes. This is a meticulously-documented work of scholarly history, not a page-turning espionage thriller; it is probably best absorbed in small doses rather than one cover to cover gulp.

February 2004 Permalink

Holmes, W. J. Double-Edged Secrets. Annapolis: U.S. Naval Institute, [1979] 1998. ISBN 1-55750-324-9.
This is the story of U.S. Naval Intelligence in the Pacific theatre during World War II, told by somebody who was there—Holmes served in the inner sanctum of Naval Intelligence at Pearl Harbor from before the Japanese attack in 1941 through the end of the war in 1945. Most accounts of naval intelligence in the war with Japan focus on cryptanalysis and use of the “Ultra” information it yielded from Japanese radio intercepts. Holmes regularly worked with this material, and with the dedicated and sometimes eccentric individuals who produced it, but his focus is broader—on intelligence as a whole, of which cryptanalysis was only a part. The “product” delivered by his shop to warfighters in the fleet was painstakingly gleaned not only from communications intercepts, but also traffic analysis, direction finding, interpretation of aerial and submarine reconnaissance photos, interrogation of prisoners, translations of captured documents, and a multitude of other sources. In preparing for the invasion of Okinawa, naval intelligence tracked down an eighty-year-old seashell expert who provided information on landing beaches from his pre-war collecting expedition there. The total material delivered by intelligence for the Okinawa operation amounted to 127 tons of paper. This book provides an excellent feel for the fog of war, and how difficult it is to discern enemy intentions from the limited and conflicting information at hand. In addition, the difficult judgement calls which must be made between the risk of disclosing sources of information versus getting useful information into the hands of combat forces on a timely basis is a theme throughout the narrative. If you're looking for more of a focus on cryptanalysis and a discussion of the little-known British contribution to codebreaking in the Pacific war, see Michael Smith's The Emperor's Codes (August 2001).

December 2004 Permalink

Large, Christine. Hijacking Enigma. Chichester, England: John Wiley & Sons, 2003. ISBN 0-470-86346-3.
The author, Director of the Bletchley Park Trust, recounts the story of the April 2000 theft and eventual recovery of Bletchley's rare Abwehr Engima cipher machine, interleaved with a history of Bletchley's World War II exploits in solving the Engima and its significance in the war. If the latter is your primary interest, you'll probably prefer Michael Smith's Station X (July 2001), which provides much more technical and historical detail. Readers who didn't follow the Enigma theft as it played out and aren't familiar with the names of prominent British news media figures may feel a bit at sea in places. A Web site devoted to the book is now available, and a U.S. edition is scheduled for publication later in 2003.

September 2003 Permalink

Smith, Michael. Station X. New York: TV Books, 1999. ISBN 1-57500-094-6.

July 2001 Permalink

Smith, Michael. The Emperor's Codes. New York: Arcade Publishing, 2000. ISBN 1-55970-568-X.

August 2001 Permalink

Stephenson, Neal. Cryptonomicon. New York: Perennial, 1999. ISBN 0-380-78862-4.
I've found that I rarely enjoy, and consequently am disinclined to pick up, these huge, fat, square works of fiction cranked out by contemporary super scribblers such as Tom Clancy, Stephen King, and J.K. Rowling. In each case, the author started out and made their name crafting intricately constructed, tightly plotted page-turners, but later on succumbed to a kind of mid-career spread which yields flabby doorstop novels that give you hand cramps if you read them in bed and contain more filler than thriller. My hypothesis is that when a talented author is getting started, their initial books receive the close attention of a professional editor and benefit from the discipline imposed by an individual whose job is to flense the flab from a manuscript. But when an author becomes highly successful—a “property” who can be relied upon to crank out best-seller after best-seller, it becomes harder for an editor to restrain an author's proclivity to bloat and bloviation. (This is not to say that all authors are so prone, but some certainly are.) I mean, how would you feel giving Tom Clancy advice on the art of crafting thrillers, even though Executive Orders could easily have been cut by a third and would probably have been a better novel at half the size.

This is why, despite my having tremendously enjoyed his earlier Snow Crash and The Diamond Age, Neal Stephenson's Cryptonomicon sat on my shelf for almost four years before I decided to take it with me on a trip and give it a try. Hey, even later Tom Clancy can be enjoyed as “airplane” books as long as they fit in your carry-on bag! While ageing on the shelf, this book was one of the most frequently recommended by visitors to this page, and friends to whom I mentioned my hesitation to dive into the book unanimously said, “You really ought to read it.” Well, I've finished it, so now I'm in a position to tell you, “You really ought to read it.” This is simply one of the best modern novels I have read in years.

The book is thick, but that's because the story is deep and sprawling and requires a large canvas. Stretching over six decades and three generations, and melding genera as disparate as military history, cryptography, mathematics and computing, business and economics, international finance, privacy and individualism versus the snooper state and intrusive taxation, personal eccentricity and humour, telecommunications policy and technology, civil and military engineering, computers and programming, the hacker and cypherpunk culture, and personal empowerment as a way of avoiding repetition of the tragedies of the twentieth century, the story defies classification into any neat category. It is not science fiction, because all of the technologies exist (or plausibly could have existed—well, maybe not the Galvanick Lucipher [p. 234; all page citations are to the trade paperback edition linked above. I'd usually cite by chapter, but they aren't numbered and there is no table of contents]—in the epoch in which they appear). Some call it a “techno thriller”, but it isn't really a compelling page-turner in that sense; this is a book you want to savour over a period of time, watching the story lines evolve and weave together over the decades, and thinking about the ideas which underlie the plot line.

The breadth of the topics which figure in this story requires encyclopedic knowledge. which the author demonstrates while making it look effortless, never like he's showing off. Stephenson writes with the kind of universal expertise for which Isaac Asimov was famed, but he's a better writer than the Good Doctor, and that's saying something. Every few pages you come across a gem such as the following (p. 207), which is the funniest paragraph I've read in many a year.

He was born Graf Heinrich Karl Wilhelm Otto Friedrich von Übersetzenseehafenstadt, but changed his name to Nigel St. John Gloamthorpby, a.k.a. Lord Woadmire, in 1914. In his photograph, he looks every inch a von Übersetzenseehafenstadt, and he is free of the cranial geometry problem so evident in the older portraits. Lord Woadmire is not related to the original ducal line of Qwghlm, the Moore family (Anglicized from the Qwghlmian clan name Mnyhrrgh) which had been terminated in 1888 by a spectacularly improbable combination of schistosomiasis, suicide, long-festering Crimean war wounds, ball lightning, flawed cannon, falls from horses, improperly canned oysters, and rogue waves.
On p. 352 we find one of the most lucid and concise explanations I've ever read of why it far more difficult to escape the grasp of now-obsolete technologies than most technologists may wish.
(This is simply because the old technology is universally understood by those who need to understand it, and it works well, and all kinds of electronic and software technology has been built and tested to work within that framework, and why mess with success, especially when your profit margins are so small that they can only be detected by using techniques from quantum mechanics, and any glitches vis-à-vis compatibility with old stuff will send your company straight into the toilet.)
In two sentences on p. 564, he lays out the essentials of the original concept for Autodesk, which I failed to convey (providentially, in retrospect) to almost every venture capitalist in Silicon Valley in thousands more words and endless, tedious meetings.
“ … But whenever a business plan first makes contact with the actual market—the real world—suddenly all kinds of stuff becomes clear. You may have envisioned half a dozen potential markets for your product, but as soon as you open your doors, one just explodes from the pack and becomes so instantly important that good business sense dictates that you abandon the others and concentrate all your efforts.”
And how many New York Times Best-Sellers contain working source code (p, 480) for a Perl program?

A 1168 page mass market paperback edition is now available, but given the unwieldiness of such an edition, how much you're likely to thumb through it to refresh your memory on little details as you read it, the likelihood you'll end up reading it more than once, and the relatively small difference in price, the trade paperback cited at the top may be the better buy. Readers interested in the cryptographic technology and culture which figure in the book will find additional information in the author's Cryptonomicon cypher-FAQ.

May 2006 Permalink