Moshe Rubin’s Cryptologia Chaocipher article, now viewable online…

by ⋅ 11 Comments

Moshe Rubin just emailed me to let me know that his extensive October 2011 Cryptologia article “John F. Byrne’s Chaocipher Revealed: An Historical and Technical Appraisal” (vol. 35 issue 4, pp.328-379 [!!!]) can currently be viewed and downloaded for free from Taylor & Francis (who publish Cryptologia), via the “Download full text” button there.

If (like me) you’re into both the social and technical aspects of historical cryptography, it’s a cracking old read, covering both Byrne’s life and his numerous attempts to get the US military to accept his “Chaocipher” invention. Yet Moshe’s article is far from all ra-ra-pro-Byrne stuff: it also makes clear…
* the system’s inherent fragility (because each step changed the state of the two rotors, it suffered from near-worst-case error propagation);
* Byrne’s cryptographic inexperience (the way that he proposed concealing the indicator settings was far from secure); and
* Byrne’s cryptologic naivety (he believed that the flat letter distribution of the ciphertext made it explicitly unbreakable).

If you’ve read Ratcliff’s “Delusions of Intelligence” (a book the GCHQ Historian recommended I read, thanks for that!), you’ll know that this last mindset was precisely what the various German agencies using the Enigma machine suffered from: and if Chaocipher had been extensively used by the Allies in WW2, who’s to say that Hitler’s fragmented array of codebreaking agencies wouldn’t have eventually found a way of breaking into it, just as they did with virtually all the Allies’ low-to-medium-echelon ciphers?

One thing that strikes me most about the whole saga is that even though Byrne (who sometimes wrote under the anagrammatic pseudonym “J. F. Renby”, I was amused to see) seems to have envisaged Chaocipher as an expensive-to-build set of mechanical rotors, I think it is actually very easy to use with two Scrabble alphabets arranged in horizontal rows. (OK, Scrabble wasn’t devised until the 1930s, but my basic point still stands regardless). All the sliding operations (zenith / nadir, etc) then become immediately straightforward, arguably far more so than if you were using a machine to do the same.

Regardless of whether or not Scrabble tiles are the best way to Chaocipherify your plaintext, I’d argue that what sets Byrne’s cryptographic ideas apart most is the way he conceptualized his crypto system in terms that mesh peculiarly well with modern computer science: in fact, it’s quite hard to describe it at all without lapsing into contemporary CompSciSpeak. It’s almost as if Byrne were projecting himself forward into a software world: but then again, one of the chapters of his autobiography was SciFi, so perhaps the future was where he felt most at home! 🙂

Chaocipher updates…

by ⋅ 3 Comments

Like hourly buses on a wet winter morning, here’s a pair of Chaocipher pages that arrived at my stop one after the other, both discussing how to break John Byrne’s Exhibit 1, and both strongly recommended reading for those interested in the Chaocipher.

First to arrive was Carl Scheffler’s page on Exhibit 1 (but you might perhaps want to read his introductory page on the Chaocipher first, complete with nice coloured disk diagrams). By looking for long sequences of repeated symbols, he managed to reduce the staggeringly-large search space down to a mere ~457,000 permutations to check: in fact, he further managed to reduce the space to only 444 permutations, which would probably be achievable even without the aid of computers. Furthermore, once he had discovered the initial ring state, Carl went on to reverse engineer the keyphrase used to set the disks up (‘THINKTHINK’, with the sequence of letters applied to the disks with the pattern LLRLLRLRRLR). He has a further page planned on Exhibit 4 – I’ll let you know when he posts this.

Subsequently, Moshe Rubin’s near-definitive update on Exhibit 1 turned up. As usual, Moshe’s 12-page PDF manages to answer more or less every question you find yourself asking along the way (though admittedly he doesn’t yet know to whom Byrne’s enciphered “CORDIALTHANKSTOLO” was referring). From this, you can also see that Byrne used ‘Q’ and ‘W’ for ‘,’ and ‘.’ (plus ‘Z’ for ‘end-of-line’), hence the plaintext begins “ALLGOODQQUICKBROWNFOXESJUMPOVERLAZYDOGTOSAVETHEIRPARTYW“.

Incidentally, though the idea of encoding punctuation as rarely-used letters is a well-known cipher trick, I find the historical question of when this mechanism was first used particularly intriguing. This is because I’ve long wondered whether the “am” letterpair frequently found at Voynich line-ends might also encipher a rare letter (such as ‘X’). True, there are some Milanese ciphers with letters for scribal abbreviations and contractions (the 1450 cipher for Tristano Sforza enciphers ‘-9’, while the 1455 cipher for Ludovico Petronio Senen has a cipher for ‘subscriptio’), but these seem to belong to a quite different family. I can’t see this in Kahn or al-Qalqashandi, so… what was the earliest cipher to replace punctuation with rarely used letters?

The Chaocipher got Slashdotted!

by ⋅ 3 Comments

The Internet is a strange thing, a virtual photographer’s jacket crammed with countless pockets of enthusiasts. For example, you beautiful cipher mysteries fans circulate within one bijou (but nicely-appointed) pocket, while the massed legions of Slashdot fans have a Tardis-style hyperzoom lens pocket all of their own. But… what would happen if these two worlds collided?

A chance to find out came in December 2009, when Edith Sherwood’s The-Voynich-Manuscript-was-made-by-Leonardo-da-Vinci-so-it-was website got picked up by Slashdot. From the 4900 overspill visits Cipher Mysteries got at the time, I estimated that she must have had “(say) 30000 or more” visits. This was probably about right, because in the few days since the same thing happened to Cipher Mysteries last weekend, its visit counter has lurched up by 38,000+. The onslaught started on Saturday night, when at its peak the Cipher Mysteries server was getting a new visitor roughly every second. By late Sunday, however, the story had finally slid off the bottom of the Slashdot front page (which only ever lists the ten most recent news items), at which point the tsunami turned into merely a large river. 🙂

According to the server logs, my Slashdotted Chaocipher page was read in 132 countries (USA 52%, Canada 8%, UK 7.5%, Australia 5.4%, etc), while US Slashdotters were mainly from California, Texas, New York, Washington, followed by another long tail. And OK, I know it’s a biased sample, but it was nice to see Internet Explorer in less than 8% of the browsers. One long-standing stereotype did fall by the wayside, though: there was a relative absence of trolls leaving snarky comments. Might Slashdot be *gasp* growing up? 😉

Actually, the nicest thing about the whole episode for me was that Moshe Rubin’s brother in Florida was unbelievably impressed when he saw Moshe’s name pop up on Slashdot. I know it’s only a small thing, but I’m really pleased for the guy, he deserves credit for his hard work and persistence bringing the Chaocipher out into the light.

* * * * * * *

Some quick follow-up thoughts on the Chaocipher…

It strikes me that Byrne’s neologism “Chaocipher” was remarkably prescient for 1918, because the whole idea of “chaos theory” – as per Wikipedia, “the behavior of dynamical systems that are highly sensitive to initial conditions“, AKA ‘the butterfly effect’ – had not long before that been started by Henri Poincaré. The French mathematician had shown that the classical three-body problem sometimes yielded tricksy outcomes that never converged (i.e. to a collision) nor diverged (i.e. to increasing distance from each other), but where the three bodies were somehow trapped in a dynamically constrained yet utterly mad-looking (OK, he actually said ‘nonperiodic’) manner. Yet after this promising beginning in the 1880s, the ‘chaos’ concept’s journey onwards was a particularly arduous (and non-obvious) one: even though people noticed the signatures of this odd behaviour in many different contexts, they had no comfortable vocabulary to describe it until well after Benoit Mandelbrot and Edward Lorenz in the 1960s.

And so I find it neatly uncanny that the Chaocipher appropriates the “chaos” word 50 years earlier than it should, while at the same time exactly demonstrating the properties that contemporary mathematicians now ascribe to it (i.e. “deterministic chaos”). As the cipher’s twizzling steps subtly mangle the order of the letters on the two rotors, both the error propagation and the cipher system complexity sharply ramp up over time, in a (quite literally) chaotic way: to my eyes, Byrne’s Chaocipher is no less artful and pleasing than any Mandelbrot set I’ve ever seen. However, because its mechanism was not disclosed until this year (2010), it is perhaps best thought of part of the secret history of applied chaos: by way of comparison, the earliest paper on “chaotic cryptography” I’ve found was Baptista’s “Cryptography with chaos” in Physics Letters A (1998) [mentioned online here].

So, it might be that as the full story behind the Chaocipher emerges from Byrne’s papers, we’ll discover that he cleverly applied Poincaré’s and Hadamard’s ideas to cryptography: but – between you and me –  I somehow doubt that this is what really happened. In my mind, there’s something both ham-fistedly mathematical and deviously mechanical about the Chaocipher, that makes its mongrelly combination of Alberti’s cipher wheel and movable circular type something that could (in principle, at least) have been devised any time since about 1465. All the same, I think that the single aspect of the Chaocipher that most makes it resemble an out-of-place artifact is that it is a pure algorithm made solid – a bit like a programming hack devised by someone who had never seen a computer. Perhaps programming is closer to carpentry than we think!

Without doubt, the Chaocipher lies just outside the rigid mathematical confines of the cipher development path laid down by the sequence of crytographers since Alberti: and so for me, the most inspiring lesson to be learned from it is that genius need take only a single step sideways to become utterly unrecognizable to the mainstream. Thinking again about the Voynich Manuscript’s cipher, might that too merely stand a single conceptual step beyond our tightly-blinkered mental range? Furthermore, might that also ultimately turn out to be part of the same secret history of applied chaos? It’s certainly an interesting thought…

The Chaocipher revealed!

by ⋅ 42 Comments

“The Chaocipher” is a devious cipher system invented in 1918 by John F. Byrne: allegedly, it was so complex that nobody could crack his challenge ciphertexts (even with the plaintext to refer to!), yet was so simple that its mechanism was claimed to comprise only two rotating disks small enough to fit in a cigar box, and could be operated by a ten-year-old (admittedly a diligent, determined and well-practised one) to encipher and decipher texts.

Hence, the Chaocipher’s long-standing mystery revolved around three questions:

  1. Was the Chaocipher for real? (i.e. could something so simple really produce such tricksy ciphertext)?
  2. Was it more secure than, say, the Enigma machine?
  3. More to the point, is the Chaocipher actually an unbreakable cipher?

As of a few years ago, only three people knew the Chaocipher’s secrets – John Byrne Jr (the inventor’s son), and two Cryptologia editors (who saw it in 1990 but were sworn to silence). Yet as Chaucer noted, time and tide wait for no man (not even Cryptologia editors) – so there was a very real (and growing) possibility that the secrets of the Chaocipher might somehow get lost forever.

Hence last August, Moshe Rubin – who CM readers may well recall as the zesty Israeli software / crypto guy who not long before had set up the Chaocipher Clearing House website – decided to try to contact John Jr before it was too late, and so cold-called his way through the list of Byrnes living in Vermont. Before long, Moshe found himself in contact with Patricia Byrne (John Jr’s wife) from whom he discovered the sad news that her husband had passed away a year or two previously.

However, because Pat Byrne was already looking for a buyer for her husband’s cryptological material, Moshe put her in contact (via David Kahn) with David D’Auria, the chairman of the National Cryptological Museum’s Acquisitions Commitee. Somewhat surprisingly, after a couple of months Pat Byrne very generously decided to donate the whole set to the NCM, a terrific gesture which I (for one) highly appreciate (and I hope that you do too!)

And so it came to be that Moshe Rubin found himself allowed what he describes as “preview access to some of the material“.  Although he found that the precise setup John Byrne Sr had employed was not immediately obvious from the material to hand, Moshe burnt a load of midnight oil (is elbow grease more or less inflammable?) before finally managing to reconstruct the original algorithm in all its subtly obfuscatory glory.

Just as Byrne had described, his Chaocipher used two rotors (with the plaintext alphabet on the right rotor and the ciphertext alphabet on the left rotor) BUT with both alphabets altered slightly (let’s call this process ‘twizzling’, for want of a better word) after processing each letter. I’ve hacked together a 30-second Chaocipher animation on YouTube to try to demonstrate Byrne’s twizzlification…

Rather than go through the fine details here, I’m happy to refer you to Moshe’s detailed (and very readable) description of the process here: the only significant difference between my video and his text is that because the rotors mesh (and hence physically rotate in opposite directions to each other), the numbering sequence on each rotor is reversed relative to the other – i.e. even though #1 is at the top of each rotor, #2 and #3 proceed clockwise on the right (plaintext) rotor but anticlockwise on the left (ciphertext) rotor. Whereas in his text, both numbering systems run in parallel to each other (which might confuse you, it certainly confused me a little).

Of course, the obvious practical weakness of the Chaocipher is that any errors in enciphering, transmission, and deciphering get near-irreversibly propagated through the rest of the message: which probably makes the whole system too fragile to use in wartime, however cryptographically secure it may be (and, answering the second question above, I suspect that it may well prove to be more complex than Enigma, for it really is quite a fiendish system).

But is it (practically) unbreakable? Well, the obvious answer would be that if it has now been released into the wild, you’d have thought someone in a three-letter-agency (or GCHQ, naturally) would have worked out a clever way in. However, I’m not 100% sure that has happened yet… so, interesting times.

All credit to Moshe Rubin, then, for his persistence and hard work bringing this cipher mystery into the light: he has a Cryptologia paper coming up, and plenty more work to do over coming months (or years?) fleshing out the behind-the-scenes story from the stack of Byrne’s papers now in the NCM. It’s a fascinating slice of cipher history, and I wish him the very best of luck with the inevitable book and selling the movie rights! 😉

* * * * * * *

Update: I’ve added a follow-on Chaocipher post here, discussing the intriguing parallels between the Chaocipher and chaos theory…

All about the Chaocipher…

by ⋅ 8 Comments

I’m getting a bit cheesed off with the Internet: every time I do a search for anything Cipher Mysteries-ish, it seems that half Google’s hits are for ghastly sites listing “Top 10 Unsolved Mysteries” or “10 Most Bizarre Uncracked Codes“. Still, perhaps I should be more grateful to the GooglePlex that I’m not getting “Top 10 Paris Hilton Modesty Tips” and its tawdry ilk.

Realistically, there is only one uncracked code/cipher listing on the web from which all the rest get cut-and-pasted: Elonka’s list of famous unsolved codes and ciphers. But Elonka Dunin has long since moved on (coincidentally, she went from cryptography into computer game production at about the same time that I made the reverse journey), which is perhaps why all of these lists look a bit dated. Perhaps I should do my own list soon (maybe, if I had the time).

Happily, Elonka did manage to nail most of the usual suspects: the Beale Papers, the Voynich Manuscript, Dorabella, Zodiac Killer, d’Agapeyeff, Phaistos Disk, and so on… each typically a piece of ciphertext which we would like to decipher in order to crack a historical mystery. However, one of the items on her list stands out as something of an exception.

For John F. Byrne’s 1918 “Chaocipher”, we have a description of his device (the prototype fitted in a cigar box, and allegedly contained two wheels with scrambled letters), and a fair few examples of both Chaocipher ciphertext and the matching plaintext. So, the mystery isn’t so much a whodunnit as a howdunnit. Though a small number of people are in on the secret mechanism (Lou Kruh, for one), Byrne himself is long dead: and the details of how his box of tricks worked have never been released into the public domain.

Was Byrne’s Chaocipher truly as unbreakable as he believed, or was it no more than the grand delusion of an inspired cryptographic outsider? This, really, is the mystery here – the everything-or-nothing “hero-or-zero” dramatic tension that makes it a good story. Yet hardly anybody knows about it: whereas “Voynich” gets 242,000 hits, “Chaocipher” only merits 546 hits (i.e. 0.0022% as much).

Well, now you know as well: and if you want to know a little more about its cryptography, I’ve added a Chaocipher page here. But the real site to go to is Moshe Rubin’s “The Chaocipher Clearing House“, which is so new that even Google hasn’t yet found it (Moshe emailed me to tell me about it, thanks!) Exemplary, fascinating, splendid – highly recommended. 🙂

OK, enough of the raw factuality, time for the obligatory historical riff. 🙂

I’m struck by the parallels between John Byrne’s device and Leon Battista Alberti’s cipher wheel. Both men seem to have caught the leading edge of a wave and tried to harness its power for cryptography, and made high-falutin’ claims as to their respective cipher systems’ unbreakability: whereas Alberti’s wave was mathematical abstraction, Byrne’s wave was (very probably) algorithmic computing.

Circa 1920, this was very much in the air: when J. Lyons & Co. hired the mathematician J.R.M. Simmons in 1923, the company was thinking about machines, systems, and operational management: mathematical calculators were absolutely de rigeur for them. The first Enigma machines were constructed in the early 1920s (and used in a commercial environment), and there were doubtless many other broadly similar machines being invented at the same time.

Do I think that there was anything unbreakable in Byrne’s box? No, not really: the real magic in there was most likely a programmatic mindset that was cutting-edge in 1918, but might well look somewhat simplistic nearly a century later. But I could be wrong! 😉