Thursday, November 29, 2018

Charles Babbage: Codebreaker

Few names stand out in the history of computing as do Charles Babbage and his Difference Engine. The Difference Engine was only a demonstration model in his lifetime. Larger more complete engines have been built in our time by museums. He also proposed a more complex and sophisticated Analytical Engine, again, never built at all in his own time but constructed in our time by museums from his plans. You may also know about his work with Lady Ada Augusta Lovelace. The daughter of George Gordon, Lord Byron, she was arguably the first computer programmer. What you may not know is that among Babbage’s hobbies were cryptology and lock picking. He said that lock picking and cryptology were very similar pursuits intellectually. 

(This is based on a presentation to the Austin OWASP Crypto Party held at National Instruments Bldg. C, January 23, 2018.)

At this time – we are talking the middle third of the 19thcentury, say 1823 to 1868—codes and ciphers were all the rage. In America, Edgar Allen Poe’s “The Gold-Bug” laid bare for public consumption the means for breaking any mono-alphabetic substitution cipher. 

Newspapers ran columns known as “Miseries.” They were Lonely Hearts messages by which lovers set up rendezvous, and they typically relied on some kind of encryption, most often single alphabet substitutions, sometimes transpositions. 
This is where Babbage comes in and wherein lies some mystery about his work. The polyalphabetic cipher goes back to the late Renaissance. We call them Vigenere ciphers. They are commonly attributed to Blaise de Vigene in the year 1585. However, the first publication can be attributed to Gian Battista Belaso in 1553. In fact, the means of breaking monoalphabetic ciphers also goes back to this time, but was not widely known outside of the black chambers of governments.

This is a 26x26 Vigenere Table. German with its umlauts would have 29 letters. Greek would have 24 letters. You encipher your message down the rows, the 13th letter being encrypted against the 13th row.

As you can see, the two Es are enciphered differently. The consecutive Rs in MARRY are enciphered to different outputs.

The man sees the end of the line.
The most common letter in English is E. The most common trigraph is THE. As you can see, the letters E all are encrypted differently. The three instances of THE have different outputs. It is for this reason that for 300 years, the Vigenere cipher was called the indecipherable cipher. It could not be broken.

But there was a war on.  The Crimean War saw Russia pitted against the UK, France, and the Ottoman Empire. Secret codes were essential to military communication. 

Enter Babbage.

First of all, Babbage promised but never published his treatise on cryptanalysis. That was unusual because he had an ego big enough to fill this room. Babbage was one of a handful of liberal scientists who purposely and purposefully restructured their society. Among them were Lady Ada Augusta Lovelace and Charles Darwin, William Herschel, and William Whewell. It was Whewell who coined the word scientist in an ad hoc debate with the poet Samuel Taylor Coleridge at the first meeting of the British Association for the Advancement of Science on June 24, 1833. 

Several scholars today theorize that Babbage was working for the War Department. So, he did publish some insights and suggestions in his autobiography of 1864. But he never let the cat out of the bag.

Babbage created a massive set of dictionaries of the English language organized by word length and then sorted by initial letters and then printed up by their second letters. He made tables of common digraphs and trigraphs. He listed all of the words with repeated letters. He could do this because he was independently wealthy, having inherited from his father an estate valued at £100,000, call it $50 million in our money. All of that just prepared his mind to attack the unbreakable cipher, which he did.

Not Babbage but a hacker at DefCon 512
Like all codebreakers, Babbage attacked the human element. We say in hacking that amateurs target systems while professionals target people. Babbage’s study of language and cryptography opened the door … and we do not know for sure just what door that was. He kept it secret. But he did mention it in passing in his autobiography. As big as his ego was, he was a man of his word. He meant what he said and proved it with mathematics. He held the same Lucasian Chair at Cambridge as Sir Isaac Newton.

The way the Vigenere worked in practice is that each agent, each minister or other user would be given a word, preferably a long word, and ideally with no repeating letters.

In the example above…

The message was I LOVE YOU. MARRY ME and the key word was UNPREDICTABLY which gave us 13 different ciphers. However, the longer the message the more likely that you will cycle through the key and eventually encipher the same words or at least the same letters with the same keys. 

Babbage figured out that you do not need to find the key of you can find the length of the key.
 “It may have been as efficacious as it is formidable,
but neither an index to its symbolism,
nor any clue to its purpose exist.” 

David Kahn, The Codebreakers, Chapter 6,
“The Contributions of the Dilettantes,” pg. 207
Babbage had a lifelong interest in cryptology and cryptanalysis. He and his friends William Whelwell and William Herschel among other savants of the day all dabbled in it. Babbage and his nephew exchanged challenges, which Charles Babbage deconstructed to its table based on the word SOMERSET by guessing that it began with DEAR UNCLE and ended with NEPHEW HENRY. That was in 1846. Babbage later took apart another small Vigenere that a dentist, John Thwaite, was attempting to get patented in 1854, shortly after the start of the Crimean War. Babbage broke that cipher, and though he promised to publish fully, he never did.
Passages from The Life of a Philosopher
Edited autobiography of Charles Babbage
Unfortunately, all we have is tantalizing scraps from his personal notes and notebooks. He never published a definitive treatise.

I read through about a dozen books – 14 in all, I think – by and about Babbage. You can get lost in his work. Because of his wealth and station, he was involved in almost every aspect of this revolutionary time from the most advanced mathematics to the most advanced manufacturing. Of all those books, The Philosophical Breakfast Club by Laura J. Snyder (Broadway Books, 2011) is the one volume that I recommend as the best overview. 


No comments:

Post a Comment