Back in 1918, John F. Byrne invented an encryption machine, which he called Chaocipher. He tried unsuccessfully to sell it to the US government until his death in 1960 while keeping it a secret. He published some samples of its output in his memoirs, mystifying a whole generation of cryptanalysts. Then, in 2010 his son’s widow decided to release the secret papers describing the inner workings of the machine. It turned out to consist of two rotors with movable letters, which shifted according to a simple pattern. The key was the initial position of the letters in both rotors. Simple and surprisingly effective, although it is somewhat doubtful that Byrne ever built a working machine (the only working prototype was allegedly destroyed (?), and only a cardboard mockup and a blueprint of the original have survived). I ran into the concept a couple weeks ago and I haven’t been able to stop thinking on how to improve it, and I believe I’ve found something as powerful and quite a bit simpler to use. I call it the Scrabble cipher because you can run it with the help of letter tiles.
Before I introduce the Scrabble cipher, let me start citing the main reason why I think Chaocipher runs so well: unlike ciphers based on a straight alphabet that gets shifted around based on entropy collected from a pseudo-random number generator or the plaintext itself (as in the Autokey cipher, and those in the Serpentacci family), the Chaocipher alphabets get internally jumbled, so all permutations are possible. In Chaocipher, the entropy added by each new plaintext letter keeps the alphabets from repeating.
But Chaocipher is more complicated than it needs to be, based on what it does. For instance:
- Why disks with moveable letters? It is easier to straighten out the alphabets and shift the letters around. Easily done with letter tiles placed in a row.
- Also, the motion of the disks is such that they end up shifting by just one position relative to each other, before the letter swap step is taken. It would be a lot easier to shift a single alphabet placed in a row by simply moving the first tile to the last position, or vice-versa.
- In Chaocipher, the letter swaps are made at fixed positions relative to the last letter enciphered, for each alphabet. But the initial and final positions don’t seem to have been optimized. Perhaps we can do that if we apply some statistical tools running on modern computers, which Byrne did not have access to.
- Why two mixed alphabets, one for the plaintext and one for the ciphertext? A substitution can be defined equally well with a single mixed alphabet placed against a straight alphabet.
- Are two letter swaps really needed? Maybe just one will do, or some sort of combination?
- And then, it turns out that the Chaocipher is easily vulnerable to a known plaintext attack. Perhaps there is a way to fix this.
To test all this, I started by building a Javascript program to simulate the operation of the Chaocipher, with a few additions:
- The final positions of the letters swapped are variable.
- You can decide whether or not to do the rotation (cut, if you are using tiles placed in a row) for the plaintext or ciphertext alphabets.
- A transposition step, under a separate key, has been added in order to combat the known plaintext attack.
- A number of statistical tests are applied to the output. Most sensitive among them are the Chi-squared test of randomness applied to single letters, and Chi-squared test of independence applied to contiguous letter pairs (no reason to believe there is stronger dependence between letters further apart).
Playing with this while encrypting large pieces of Dickens’s “Oliver Twist” and doing some reading on Chaocipher I discovered the following:
- Encryptions done on the same plaintext with two different ciphertext keys are related to each other by a simple substitution. This means that one could use a straight alphabet on the ciphertext wheel, and then perform a substitution on the Chaocipher output and get the same result as if the substitution key had been used as the initial ciphertext alphabet in Chaocipher.
- It is not the same with the plaintext key, so that the output produced from the same plaintext and ciphertext key but different plaintext key is different, but then there is another problem: if you decrypt a ciphertext with the correct ciphertext key but the wrong plaintext key the result, which is related to the correct plaintext through a simple substitution, has the typical statistical properties of plaintext, which makes it possible to mount an attack to recover the ciphertext key without regard for the plaintext key. After this, the jumbled plaintext obtained this way can be attacked with the typical methods for simple substitutions. In other words, the plaintext key does not add any security at all and should not be considered when calculating the key space size.
I made a number of Javascript prototypes so I could encrypt large chunks of text (usually taken from the Gutenberg project, in several Western languages) in a second or two, and made little changes here and there as I also played with a set of Bananagrams tiles (similar to Scrabble, but without number points) on top of a blank ruler. Here’s a picture of my setup, with key “marvelous” set on the ciphertext alphabet.
Initially I moved the tiles in large groups, much like Chaocipher, which tended to be tricky because the tiles did not want to stay together, but eventually I discovered that I could obtain pretty good randomness by swapping two contiguous vertical groups plus shifting one alphabet just by one tile, which minimized both the work and the chances of making a mistake. So here is the final Javascript app for the Scrabble cipher, and now the description, which uses the default values in the program:
- Take your key phrase and turn it into a mixed alphabet by doing the following: take each key and write the different letters of the alphabet in the order they appear in the key, if a letter has been used already, write instead the immediately preceding letter in the normal alphabet not yet chosen. If there are letters that did not appear in the key, write them now in reverse alphabetical order. If you are going to do a transposition, do the same with the transposition key, except that you don’t add the unused letters at the end. Then arrange a set of letter tiles to make the encryption alphabet above a ruler, and then place above it another set of tiles making a straight alphabet, as shown in the picture above. The top alphabet will be used for plaintext, the bottom one for ciphertext.
- Optionally but highly recommended, especially if you are not going to do a transposition, generate a set of twenty random letters and add them to the beginning of plaintext. This will provide protection against a known plaintext attack.
- For each letter of the plaintext thus modified, ignoring spaces and punctuation (number can be written out in words or encoded as letters), look it up in the top alphabet and write down as output the letter below it. Then take out those two tiles and swap the group with the two letters preceding them. Finally, take the first letter of the top alphabet, move it to the end, and shift that complete alphabet one step to the left so it lines up again with the bottom alphabet. Repeat step 2 until you have encrypted all the plaintext letters. The result is already a valid ciphertext.
- If you are doing a transposition, this is the time for it. Write the result of the previous step by rows under the (perhaps incomplete) transposition alphabet, then read it off by columns in alphabetical order of the letters in the transposition alphabet. This is the final ciphertext.
To decrypt, do step 1 as above so the generated alphabets are the same as for encryption, then do a reverse transposition using the appropriate alphabet, if a transposition was done for encryption. Then do step 3 except that you’ll be looking up ciphertext letters in the bottom alphabet and writing out as output the corresponding plaintext letters in the top alphabet. If the result starts with twenty gibberish characters, you can just ignore them.
Without transposition, the key space has 26! possibilities, which is equivalent to 88.7 binary bits. Not huge, but adequate for many situations. As I said earlier, scrambling the plaintext alphabet with an additional key does not increase security at all, so it’s better to start with a straight alphabet for the plaintext. Adding a transposition doubles that, for a relatively small increase in the total amount of work. This works because the output of the letter tile process is already indistinguishable from random, and so is the “plaintext” obtained with a wrong ciphertext alphabet, even if off by a single letter. Thus, it is not possible to tell when the correct transposition key has been used in a trial decryption, unless the ciphertext alphabet set with the tiles is correct as well. A second transposition under a different key adds another 88.7 bits, because successive transpositions do not combine into a simple transposition. Substitutions do combine, however, so that adding more substitutions on top of the one built into the ciphertext alphabet would not increase the key space, even if separated by transpositions.
In fact, you can obtain exactly the same ciphertext if you set a straight alphabet on the bottom row of the setup, and then apply the substitution represented by the key at the end of everything. The randomization of the ciphertext, therefore, is entirely due to the plaintext itself, not to the initial position of the ciphertext alphabet. The process works because common text contains some randomness (usually measured in “bits of entropy”), which is constantly being added to randomize the alphabets. English contains about 1.56 bits of entropy per letter, which is approximately one-third of what a perfectly random series of letters would contain. The process involving the tiles etc. randomizes the plaintext by itself while remaining reversible.
We have encountered a similar situation before. The Visionnaire cipher combines each plaintext letter with a previous one by subtraction using a Tabula Recta. The result, however, is less than perfectly random. It is remarkable that the Scrabble cipher manages to do so well, and this involving the entropy supplied by only one letter at a time instead of two. I think this is because it actually disturbs the relative order of the letters within the ciphertext alphabet, rather than simply shifting it around. The swap step is what does the trick.
The original Chaocipher is vulnerable to a known plaintext attack, but it is easy to defeat it simply by prepending a number of random characters to the plaintext prior to encryption, and this also applies to Scrabble. An attacker will only be able to obtain the ciphertext alphabet at the point where the proper plaintext begins, but this is not the key. To move one step backward he will have to guess the previous plaintext letter, which now is random so there is no way to get it except by guessing. The possibilities multiply as he goes further back, and they become larger than the number of possible keys when 26^n = 26!, where n is the number of gibberish letters. Solving this equation gives n = 18.8, so nineteen gibberish letters are enough. The spec for the Scrabble cipher is twenty, for a little added security.
Of course, adding a transposition after the main encryption has the same effect since then an attacker won’t be able to match the ciphertext letters to those in the known plaintext, so that in this case the gibberish letters at the beginning wouldn’t really add any security and are better skipped. But a transposition, although fast compared to the moving tile process, still would take more effort than simply adding a few extra letters to a long text.
The program allows you to swap two groups of letters different from those in the description above (besides allowing you to shift the top alphabet forward rather than backward, if you so choose), but this works well only if the distance between the groups to be swapped is an odd number other than 13. The reason is that 2 nd 13 are the factors that make up 26, the length of the alphabets. Letters separated by a multiple of 2 or 13 positions will never swap with letters not in those sets, leading to imperfect mixing of the alphabets. If the alphabet were to contain 27 letters, as is common in some Western languages, then the bad intervals would be all multiples of three.
Let me now address point 4 on the first list. Can we achieve decent security working with a single alphabet rather than two? It turns out we do, almost, and this is what I’m going to address next. In this case you write out the plaintext alphabet, which is fixed, right on the rules, and use tiles just for the ciphertext alphabet. Here’s a picture of the setup for what I call “Half Scrabble” cipher:
The process is the same as above, except that you don’t swap groups of two tiles since there is only one alphabet, and shift the ciphertext alphabet instead. The key space has the same size, and there’s also a Javascript model of it, with optimized parameters. It turns out that Half Scrabble does not work well for certain sets of parameters, while two-alphabet Scrabble always works well so long as the distance between swapped letters is not a multiple of 2 or 13. The default values in the program are those that are easiest to use with good performance for English text. If you are encrypting Spanish, for instance, you will want to swap the letter tile you wrote with the next tile, rather than the preceding one. In French, you can do exactly as in English with good results. This difference is due to the letter frequency distributions proper to each language, which affect the alphabet mixing process. Here’s a list of optimal settings for several Western languages (other values also work with little performance impact):
Letter 1 | Letter 2 | Alphabet shift | |
English | 0 | 25 | fwd |
Spanish | 0 | 1 | fwd |
French | 0 | 25 | fwd |
German | 0 | 1 | bkwd |
Italian | 0 | 25 | bkwd |
Portuguese | 0 | 25 | bkwd |
Dutch | 0 | 25 | bkwd |
Latin | 0 | 25 | bkwd |
In all cases, one of the letters to be swapped is always the one just written, and it swaps with a letter next to it, whether on the right (1) or on the left (25). Sometimes this leads to the letter just written ending up at the same absolute position, so that a repeated plaintext letter will produce a repeated ciphertext letter. This artifact is undesirable because it leaks some information about the plaintext and could be used by an attacker, for instance, to mount a chosen plaintext attack. It would work this way: generate some chatter that includes some names containing double letters separated by known intervals. When the enemy uses those names in their transmission, it becomes easy to spot their location on the ciphertext because of the double letters, which allows the attacker to obtain some of the ciphertext alphabet in use at that point in the message. If this happens a few times, there may be enough to complete the alphabet, which will allow the decryption of the rest of the message from the point where the alphabet is complete.
Another quirk is that the output can be less than perfectly random even with optimized parameters, especially if the plaintext is long (over 20,000 letters). You can always check this if using the program, but obviously this cannot be done easily if encrypting by hand. But again, likely we’re not going to be encrypting by hand anything that long, so this might bot be much of a problem in practice.
Let me finish with a historical note. John F. Byrne spent his entire life trying to get the US Government to use his Chaocipher, which lead to some correspondence between him and William F. Friedman, father of the modern statistical methods used in cryptography. The correspondence spanned several decades, but the last piece of it, a letter from Friedman dated March 3, 1957, contains his most conclusive indictment of the system. He said, according to Moshe Rubin, that he “will make no attempt at solving Exhibit #4,” not because he feels he can’t do it, but because it would serve no purpose. Informs Byrne ‘hand-ciphers’ are passé, no government would be interested. Also advises belief that Chaocipher is not indecipherable, and suggests Byrne’s algorithm has been ‘thought of before’ by Engineers.” But Friedman’s actual letter says ,”It may well be that your system is excellent – I won’t say it is invincible, as you seem to think it is. I shall not even make an attempt to solve your example number 4, not only because I don’t think I could do it,” which sounds like less of an indictment than what Rubin concludes (thanks to G. Arpa for the authentic quote).
Since the Scrabble cipher derives directly from Chaocipher, it would seem that Friedman’s unfavorable opinion should also extend to it. Nevertheless, the Javascript version of Scrabble (and also of Chaocipher) manages to beat Friedman’s own detection statistics—and some even more sensitive—with considerable ease for any normal text. You be the judge. Test it by hand or by computer, and form your own opinion. Who knows, you may need it someday.
What about moving the ciphertext alphabet to the left by the value of the last plaintext letter: 5 if it’s a E,1 if it’s a
A and so on. This makes the moves much more irregular.maybe worthwhile if security is increased.
It may be so, but workload increases. The algorithm produces a near-random keystream without it, which is what’s needed for security. Why complicate it?
Although somewhat belated, I came across your interesting post recently. The post was chock-full of astute observations and novel ideas. There are a few points I believe may need clarification, so I’m taking the liberty of posting my thoughts here.
You wrote that “Chaocipher is more complicated than it needs to be”. Commenting on the numbered list following there:
(1) You state that it is easier to use slides rather than a wheel/disk. Indeed that was the first step in my online paper “Chaocipher Revealed: The Algorithm” (http://chaocipher.com/chaocipher-017.htm), written in July 2010. This is a basic step, often used by William F. Friedman, to simplifying cipher systems (e.g., cipher wheels, Wheatstone’s Cryptograph, Enigma). John F. Byrne probably envisioned a portable device, and his wheels are pretty portable at that.
(2) Yes, one could reduce the amount of alphabet shifting, since the alphabets, when kept together in tandem, remain invariant under rotation. The issue is that a user needs to know where the ‘zenith’ and ‘nadir’ are positioned at all times to be able to encrypt/decrypt. In the slide analog, the alphabets are always shifted to record where these two positions are at any time. You may be interested in knowing that John F. Byrne’s Chaocipher artifacts contain a notebook he meticulously kept when enciphering Exhibit #1. He recorded the alphabets every 55 characters (i.e., at the beginning of every line). The notebook can be seen at https://drive.google.com/open?id=1gsySUoGHD-yzJQzaaDVzw4H0pQfSAlhN. The drawback is that Byrne did not record, for each alphabet pair, where the zenith and nadir are! Their positions change for every alphabet pair. If he needed to return to an earlier line, he would be at a loss to know what the zenith/nadir were. My point is that the alphabet sliding is done to keep the zenith/nadir in constant positions (i.e., positions 1 and 14).
(3) Kudos for discovering that enciphering a given plaintext with the identical plaintext alphabets but with different ciphertext alphabets results in ciphertexts that are isomorphic. Similarly, deciphering ciphertext with identical ciphertext alphabets but different plaintext alphabets results in isomorphic ‘plaintexts’. George Lasry discovered this same principle (see chapter 8 in his book “A Methodology for the Cryptanalysis of Classical Ciphers with Search Metaheuristics”, online at http://www.uni-kassel.de/upress/online/OpenAccess/978-3-7376-0458-1.OpenAccess.pdf). This observation enabled him to solve Exhibit #6 without having to worry about the plaintext (right) alphabet, solving for it as a simple substitution at the end. It did require him to use the Index of Coincidence (I.C.) in his evaluation functions, rather than using actual English letter probabilities.
In the paragraph beginning “The original Chaocipher is vulnerable to a known plaintext attack” you posit that it is easy to defeat by prepending random characters to the plaintext prior to encryption. The theory is that “an attacker will only be able to obtain the ciphertext alphabet at the point where the proper plaintext begins, but this is not the key”. In my opinion, this is empirically inaccurate. As can be seen in my paper in Cryptologia entitled “John F. Byrne’s Chaocipher Revealed: An Historical and Technical Appraisal”, pp. 361-365, if a given plaintext gives both alphabets, one can walk from a given plaintext all the back to the starting settings. Prepending random plaintext is, however, quite effective at preventing solving a large number of in-depth messages.
Following the list of optimal settings for several Western languages, in the paragraph beginning “in all cases”, you mention that the Scrabble cipher can have adjacent identical pt/ct pairs (known as “hits”). A fascinating characteristic of classic Chaocipher is that a hit never occurs in less than seven (7) steps — there will always be a minimum distance of seven between two identical pt/ct pairs (texted empirically on 700 million pt/ct encryptions). I leave it as a challenge to your readers to discover why this is true (this is virgin territory, no one knows why to date).
In your paragraph “let me finish with a historical note”, you correctly point out that the comment on the page does not accurately mirror what Friedman write to Byrne. Although I was not the author of the comment, I accept full responsibility for it and hope to correct it accordingly.
All in all, your post was a most insightful one, and is sure to stimulate your readers to delve into Chaocipher or its cousin, the Scrabble cipher.
I look forward to reading more of your enjoyable posts.
Best regards,
Moshe Rubin
A comment worth making here relates to Professor Ruiz’s correct observation that the scrambled right (cipher) alphabet does not provide significant security. This is because assuming any other right alphabet results in ciphertext that is isomorphic to the true ciphertext. As George Lasry showed, the cryptanalyst can assume a straight alphabet, while using the Index of Coincidence (I.C.) rather than an n-gram computation as a hill climbing scoring function to solve the cipher in certain cases. Once the alphabet is determined, the converted cipher is solved as a monoalphabetic.
If, however, both the left AND the right alphabets alternate as the plaintext alphabet (aka takeoff pattern), the cryptanalytic method above (i.e., assuming a straight alphabet) no longer works. John F. Byrne used just this method to prime his alphabets before enciphering his messages, and Deavours & Kruh used the alternating plaintext alphabet method to encipher their exhibits 5 and 6 (see chaocipher.com, progress reports 23 and 24).
Summarizing, if one uses the improved Chaocipher enciphering method that uses a takeoff pattern to determine which alphabet is the plaintext alphabet, then the second alphabet provides the maximal keyspace size.
I think you have the description of forward and backward reversed on the JavaScript for this. I get the Forward result when moving the first letter to the end of the cipher alphabet. Instead of Forward/Reverse (which needs a reference) perhaps Left/Right would be better adjective to describe that move.
You were right! I corrected the file so now it says “right” instead of “forward” and “left” instead of “backward”. Many thanks!
I would like to note that the half-scrabble method is essentially a position-based Caeser-cipher. Write the letters of the message under the cipher alphabet, 26 at a time. Each letter selects the (i-1)th letter to the right of the letter above it in the cipher alphabet according to its position
i
in the plain alphabet, e.g. A selects the letter directly above it, B selects the letter 1 to the right, C selects the letter 2 to the right, so CAB -> YEZ with the cipher alphabet shown below:KEYZXWVUTSRQPONMLJIHGFDCBA
CAB
To decode the message, write the AZ alphabet above the cipher aphabet. For the
ith
coded message letter, find it in the cipher alphabet and movei-1
letters to the left of it in the plain alphabet, so Y is at position 1 so just find the letter above Y in the cipher alphabet:C. E is at position 2 so select the letter 2-1 to the left of the letter above it: A. Finally, Z is 3rd so select 3-1 letters to the left of what is above it (B is 2 to the left of D).ABCDEFGHIJKLMNOPQRSTUVWXYZ
KEYZXWVUTSRQPONMLJIHGFDCBA
Y -> C – 0
E -> B – 1
Z -> D – 2
The shuffle with letters is less error-prone in application by hand.
Instead of swapping the plain text character and the cipher text character in the cipher alphabet, however, try swapping the plain text character with whatever character is above the letter being encoded. Not sure how this will turn out but the asterisk marks the letter being decoded and the letter below which (in the cipher text) that will be swapped. The text indicates what is happening at each step.
PARSE
*
ABCDEFGHIJKLMNOPQRSTUVWXYZ
KEYZXWVUTSRQPONMLJIHGFDCBA
P -> M and swap K M
PARSE
*
ABCDEFGHIJKLMNOPQRSTUVWXYZ
EYZXWVUTSRQPONKLJIHGFDCBAM
A -> E and swap Y E
PARSE
*
ABCDEFGHIJKLMNOPQRSTUVWXYZ
EZXWVUTSRQPONKLJIHGFDCBAMY
R -> H and swap X H
PARSE
*
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ZHWVUTSRQPONKLJIXGFDCBAMYE
S -> F and swap V F
PARSE
*
ABCDEFGHIJKLMNOPQRSTUVWXYZ
HWFUTSRQPONKLJIXGVDCBAMYEZ
E -> T and swap T T
PARSE -> MEHFT
The additional mixing that this produces can be seen by looking at the encoding of a string of As after the word PARSE with a plain cipher text alphabet:
The half scrabble produces
PBTVIFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZA
The As aren’t providing any new input to the cipher so the shifting of the alphabet is all that is seen in the repeating alphabet. Subtracting a regular alphabet background from this output gives the orginal text:
PARSEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
The modified-half-scrabble produces (from PARSE followed by As)
PBTVIFVHIJFLVNHAIRJEFGLXVZN CCDCKDOCSKWDPOTCQSYKMWBDUP HHIHJIFHLJVINFRHGLZJEVAIXN
The repeating pattern in 26 letters is evident in the 2nd and 3rd groups. If you translate them into canonical form (call the first letter A and the next unique letter B, etc..) they both have the canonical form AABACBDAECFBGDHAIEJCKFLBMG.
Substraction of a regular alphabet background from this gives
PARSEAPAAAVAJATLSARLLLPAXANBAAYFXHUJALRCAEMZAFQRAEFVPGFFDECYZCZKWARCRPTGPJZDKYN
So using a plain text cipher alphabet is a bad idea since early words in the message will be transparent (or else one should preppend a serial text at the beginning — something you have already written about).
.
Thanks for the thorough comment. I want to go over all the things you suggest, but I loaned my tile set to a friend, and I’ve been waiting quite a while now to see it returned. Moral: never loan anything to people who value the item less than you do.
Very insightful. Indeed, the statistics of the Half-Scrabble ciphertext are less than stellar, and here you’re showing why. Have you found similar weaknesses with the full Scrabble cipher?