The Chaocipher

The Chaocipher is a mechanical encryption algorithm invented in 1918. No one was able to reverse-engineer the algorithm, given sets of plaintexts and ciphertexts -- at least, nobody publicly. On the other hand, I don't know how many people tried, or even knew about the algorithm. I'd never heard of it before now. Anyway, for the first time, the algorithm has been revealed. Of course, it's not able to stand up to computer cryptanalysis.

Posted on July 13, 2010 at 7:21 AM • 21 Comments

Comments

Clive RobinsonJuly 13, 2010 8:56 AM

Hmm,

It uses two fairly simple "card shuffling" algorithms.

You could with a little patience do this with a single deck of cards split into two packs of red cards and black cards.

I'll have a think to see how difficult it is to do the shuffeling by hand. On the face of it it is quite simple for the left deck and does not need the use of jokers or other cards etc.

StevecJuly 13, 2010 9:24 AM

Is this for real? The picture of the device in Figure 1 looks suspiciously like a pair of Bakewell tarts to me

Clive RobinsonJuly 13, 2010 10:52 AM

@ Stevec

"... looks suspiciously like a pair of Bakewell tarts to me"

I don't think many people on this list would be that familiar with a couple of tarts from Bakewell...

SamJuly 13, 2010 12:14 PM

"Of course, it's not able to stand up to computer cryptanalysis."

What makes you say that, Bruce?

chabuhiJuly 13, 2010 1:02 PM

Would be grateful for a link to C++ source implementation of this if anybody can find one.

Clive RobinsonJuly 13, 2010 1:50 PM

@ Chabuhi,

There is Perl code in the back of the paper that being said it's quite a bit longer than I would expect from the description.

I'd need to take a proper look at it but it should not be to difficult to translate or code up from scratch.

Not Bruce, honestJuly 13, 2010 7:29 PM

@Sam:

In general, mechanical rotor ciphers really can't stand up to modern cryptanalysis. They can only generate a fraction of the possible plaintext-to-ciphertext mappings, so they are much easier to decipher.

Clive RobinsonJuly 14, 2010 12:45 AM

@ Sam,

One of the reasons Bruce says,

"Of course, it's not able to stand up to compute cryptanalysis."

Is the maximum possible number of states the system can be in.

Without doing an indepth analysis you can simply say,

I have two independent wheels of 26 charecters that store state.

You can assume an upper bound on the number of states each wheel can be in of 26! or a little under 4.033 x 10^26, which is about 89bits (if my brain is working at "Oh my Gawd" in the morning).

Now there is the question of how the two wheels interact with each other and the resulting number of states. For the sake of simplicity you can just assume that either wheel can be in any state against the other, so you get 26! x 26! ~= 1.62644 x 10^53 or 178bits as an upper bound.

In practice it will actually be a lot less than this. But for comparison a full pack of 52 cards gives you 8.06582 x 10^67 or a little over 227bits of state. And ARC4's 256 bytes and two pointers gives the equivalent of 1700 bits.

However this is an upper bound on state only and says nothing about the usage of the state or the complexity of the state transitions.

To see why this is important imagine if you will the system was a stream cipher that had a 178bit counter the last 5bits of which where XORed with the plain text. In reality the state becomes the equivalent of a counter that rolls over to zero after thirty one. Which would be the equivalent of using a Ceaser Cipher of 32 alphabets one after each other which would be trivial to break with just a pencil and paper and a message of just a short plain text sentance. Even if you XOR'd in more bits of state for each bit of plain text the situation would only be fractionaly better because the mapping from the full state to each alphabet is highly linear and highly predictable.

To be secure not only do you need to use the full range of possible alphabets but the transition between them needs to be as near unpredictable as possible.

I'm not going to analyse the cipher in depth but if you look at the way the first wheel evolves it's alphabet (state) it is very slow and easily testable from state to state. Effectivly take out one letter and move it down the current alphabet and then rotate the alphabet the same number of places.

The hard part is determining the actual starting or current alpabet and what the "shift" value is for moving to the next state.

As for the alphabet change, it is the equivalent of holding 26 cards in your hand (faned out) counting down to a card pulling it out counting down further and putting it in a new place then closing the hand and counting off cards from the top to the bottom of the deck and then fanning it out again (it's like an Alberti disk where you move a letter around the alphabet on each encipherment of a plain text char).

I know from having designed a similar deck of cards system (it uses the whole deck and reverses the order of cards for a given count) that you can do this very quickly with a little practice. And with a bit more practice you can encipher a message (running key) in your head as you are doing it and write the cipher text down.

Filias CupioJuly 14, 2010 3:07 AM

How on earth would you implement this with early 20th century technology, reliably and moderately cheaply?

Clive RobinsonJuly 14, 2010 5:11 AM

@ Filias Cupio,

"How on earth would you implement this with early 20th century technology, reliably and moderately cheaply"

I can think of several ways...

But first "cheaply" would not have been a design consideration in the early part of the last century.

The forerunner of the Enigma machine cost about twice that a skilled craftsman would earn so you could be looking at about 100,000 USD in todays money.

As for reliably it was just after the Victorian era of great mechanical engineering, standardisation of components had happened and WWI had shown that industrialisation and mass production could be brought to bare on what was once a highly skilled manual job of making guns.

There are patents around some where for both a calculator and a cipher system using hydraulics rather than electricity. Remember dry cell batteries where virtualy unknown technology at the time, and lead acid cells where little more than large very glass containers that where extreamly heavy and very fragile. They where also very dangerous as they could not be sealed (they exploded on charging) and thus escape of concentrated sulfuric acid was virtualy guaranteed in all but the most controled environments.

However mechanical engineering ruled supreme of all mens endevors at the time, and toy manufacture was industrialised with pressed tin toys taking over from cast lead and wood.

One such novelty toy we still see today and that is the square of interlocking tiles that can be slid up down left and right with a picture on. even though one tile of the 9 or 16 was missing they did not fall out of the frame.

So the design of even quite a small wheel with letter tiles that could be slid in and out of it's periphery would have been a well understood technology. A simple mechanical system to slide a tile out of the frame and move 12 tiles by rotation past it would have been fairly easy to do as would slotting the tile back into the wheel periphery.

We know since the time of Alberti (and his disk) that craftsmen could certainly make the wheels and based on some mechanical calculators we know they could have made a sliding mechanisum (and actually had for other things).

It amazes me quite frequently just how many simple mechanical skills that have become effectivly unknown since the 1980's. Which is actually quite sad as pulling apart mechanical toys, clocks and locks, etc teaches a young mind a lot about what is possible and quite practical.

I learnt a lot of my engineering skills before I was even a teenager and getting old and broken valve radios and televisions and fixing them taught me a lot of fault finding skills before I was 13. It also provided me with a nice little income of a pound or two a week before I went on to "further education".

Having had the oportunity to play a little with a pack of cards I can safely say you can split into two decks and do the required shuffling on both without putting them down (hint unlike the PDF description with it's awkward lose card (P on the left wheel example) simply put it out of the way on the botom of the deck count 12 cards off into the other hand and slide the top card across from thbe new deck to the old deck and put the new deck back ontop of the old deck (and if you realy want move the lose card from the bottom of the deck back to the top).

rosettastone30July 15, 2010 10:48 PM

I'm not going to analyse the cipher in depth but if you look at the way the first wheel evolves it's alphabet (state) it is very slow and easily testable from state to state. Effectivly take out one letter and move it down the current alphabet and then rotate the alphabet the same number of places.
rosetta stone

RogerJuly 17, 2010 12:17 PM

Very interesting to see a new "classical" cipher -- although I think it has some coincidental resemblance to RC4.

The dynamic modification of the substitution tables may make it significantly difficult to attack under a known pt model. The author has clearly tried out, or at least thought through, some basic cryptanalysis; for example, the z+2 shift on the ct wheel (instead of z+1 as it is on the pt wheel) is very important. If both wheels did z+1 I'm pretty sure I could break it on known pt and may be ct only (for a sufficiently long text.) OTOH the fact that the table perturbation is controlled by the last pt and ct may make it very vulnerable to an adaptive chosen pt attack.

@rosettastone:
I don't think it's correct to say that the state evolves slowly. At every operation, fully half of the cells change, as well as the offsets / rotations changing by large, pseudorandom amounts. This is really pretty good for a classical cipher.

What you may have meant to say is that the intervals (set of distances from neighbour to neighbour) evolve slowly.

@Clive:
"There is Perl code in the back of the paper that being said it's quite a bit longer than I would expect from the description."

I don't want to come over all code-snobbish but the code in the appendix is really not very good perl code at all. For example, several *pages* of it consists of implementing their own parser for switches/options from the command line -- something which of course is already available in a standard (and quite well known) library.

Elonka DuninJuly 18, 2010 3:46 PM

I've taken a quick look at the PDF, but haven't gone in and looked at the algorithm in detail yet. Has anyone actually worked through it to verify the mechanism? The reason I ask, is because with another famous unsolved code, "Kryptos", I get multiple contacts per month from people who are claiming a solution, but then it turns out to be at best, mistaken, or at worst, fraud. Sometimes they send extensive spreadsheets and diagrams, and it takes time to sort through them.

Rubin's explanation and solution so far appear plausible, but I note he didn't go so far as to actually decipher any of the encrypted messages that are in Byrne's book "Silent Years". Instead, "The author deliberately did not describe how to decipher [the messages] to enable would-be decipherers to try their hands..." This kind of "exercise for the reader" approach raises a red flag for me. I'd feel better about updating my "Famous Unsolved Codes" page and marking this one as solved, if there was solid independent third-party verification that this is a valid algorithm, and someone actually produced a readable plaintext?

Elonka
http://www.elonka.com/UnsolvedCodes.html

Nick PellingJuly 19, 2010 11:54 PM

@Elonka - Moshe Rubin's for real, the Chaocipher algorithm has been verified by multiple people in multiple computer languages, and it all works exactly as described... for Byrne's Exhibits 1 and 4.

Having said that, Byrne's Exhibits 2 & 3 and the Exhibit 5 from Kruh & Deavour's 1990 Cryptologia paper seem to work differently, so probably (?) use a variant of Byrne's algorithm. Of course, people are actively trying to crack these, but at least some of the mystery remains. ;-)

Cheers, ....Nick Pelling....

Elonka DuninJuly 20, 2010 2:04 PM

@Nick:

Thanks, could you point me at any of these verifications? Or even better, at the plaintext of those last two lines of part 4, for which Rubin had offered the prize?

PordeusAugust 5, 2010 2:53 PM

The Chaocipher presented works likely my algorithm designed at my master thesis, some modifications over the Move-To-Front Heuristics.

Mike CowanAugust 21, 2012 9:55 AM

It's two years down the track (2012) and nobody has solved Chaocipher Exhibits 2 & 3. So much for the several claims in these postings that the cipher is easy to break. What is easy is to make these statements -- not so easy to back them up it seems. Excuses are generally predictable: too busy, not sufficiently interested, no incentive....

Aaron ToponceOctober 7, 2014 12:53 AM

... And now we are four years down the road. As of March this year, the last exhibit was cracked.

I recently had an email discussion with Moshe. Given enough plaintext and ciphertext, about 50 characters of each, the starting alphabets can be discovered. However, there is no known break of a ciphertext only message using the Chaocipher.

Making the claim that it can't withstand modern computer cryptanalysis is a big claim. As mentioned, the key space is 26!^2, or about 178 btis of entropy. This is sufficient no take it out of the reach of a brute fore search for the key. And no known weakness with better efficiency at cracking the algorithm is known.

While there are known weaknesses with Solitaire. :-)

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Resilient Systems, Inc.