The Chaocipher Challenge: Further Work in Progress

Moshe Rubin (mosher@mountainvistasoft.com)

The Goal

This web page is an attempt to make some order in the Chaocipher cryptanalytic work found in the open literature. In addition, I want to present my own findings discovered while working on this fascinating problem. It is my hope that the information here will help someone solve this long overdue challenge.

Background

My own interest in John F. Byrne’s Chaocipher dates back to the seventies when I first read about Byrne’s Chaocipher in David Kahn’s monumental “The CodeBreakers”. A search in the Hebrew University’s National Library in Jerusalem uncovered Albert Einstein’s personal copy of “Silent Years”, sent to him by John F. Byrne himself (link). New to cryptology and cryptanalysis at the time, I attempted to make headway with the plain- and ciphertexts in chapter 21. Failing to do so I put the problem aside.

Over the years I returned to glance at the problem, waiting for a convenient time to “jump in”. In August 2008 I decided that that time had come. Collecting all the material I could find, together with correspondences with several people, I began my own analyses.

A Thought Before Starting

By and large, John F. Byrne's Chaocipher challenge has been curiously ignored by the cryptanalytic community. It would be expected that a system that caught the attention of knowledgeable cryptologists like Colonel Parker Hitt, William F. Friedman, Major Frank Moorman, Bell Labs, and various representatives of the State, War, and Navy departments would catch the fancy of amateur cryptanalysts.

One of the reasons given for not tackling Chaocipher is that, by not revealing the underlying system, Byrne violated the fundamental assumption of military cryptography: that the enemy knows the general system. Continuing this reasoning, it is a waste of time to work on a system which, if revealed, would probably be easy to solve.

I understand this sentiment, but have several comments to make:

Several of the professionals mentioned above are quoted by Byrne as being highly favorable of his system. It would probably not be trivial to solve even if the underlying system were known.
There are very few opportunities available today to duplicate the incredible US effort of breaking the Japanese Purple cipher with no a priori knowledge. Are we up to a similar challenge?

Although Byrne should have divulged his underlying system, the challenge is a fine one, well worth the effort to "prove one's mettle".

Silent Years: Chapter 21

Chapter 21 in Byrnes’s “Silent Years” [1] is the starting point for working on the Chaocipher challenge. It describes the history of Chaocipher, the people Byrne showed it to and, most importantly, the challenge plain- and ciphertexts. I have uploaded a photocopy of the chapter to the Web (link). In addition, I’ve uploaded carefully edited text versions of all the exhibits (link).

Greg Mellen’s excellent article

The place to start is Greg Mellen’s most excellent article in Cryptologia (Volume 3 Number 3, July 1979, pp. 136-154) entitled “J. F. Byrne and the Chaocipher: Work in Progress” [2]. In it, Mellen presented his partial findings after working on the cipher. The article is thorough, giving Mellen’s thoughts, ideas, and comments about the Chaocipher. By the end of the article he presents what he believes in the most probable direction for solving the cipher.

I highly recommend getting a copy of the article. It can be ordered over the Web. In the upcoming sections I will attempt to summarize and relate to the most important results of his research.

Article: Chaocipher’s method is disclosed to Cryptologia Editors

In 1990, John Byrne, son of John F. Byrne, demonstrated Chaocipher to two Cryptologia editors (Lou Kruh and Cipher A. Deavours). Although bound by a non-disclosure agreement, the two wrote an article in Cryptologia entitled “Chaocipher Enters the Computer Age When its Method is Disclosed to Cryptologia Editors” [3]. Kruh and Deavours hint at the possible direction and present three more ciphertexts for would-be solvers.

Taking Inventory

This, then, is what we have to work with:

Byrne’s chapter 21 complete with the original Chaocipher challenge (including ASCII files of all plaintext and ciphertext exhibits).
Greg Mellen’s article summarizing his own research [2]
Kruh and Deavours’s article presenting tantalizing hints about the Chaocipher’s method [3]

Examining Mellen’s Results

In [3] Deavours and Kruh write:

Over the years many hypotheses about the cipher been suggested and most of them were demolished in Mellen’s article, e.g., it is a crude rotor system, contains an element of transposition, autokey cipher, Vernam tape system, and a form of polyalphabetic cipher with a random nonrepeating key.

We can take Deavour’s and Kruh’s word that the Chaocipher is none of these.

My own isomorph search found the following isomorphs in exhibit 1. None of the isomorphic pairs have the same underlying plaintext so they are non-causal:

Offset     Ciphertext
------   ---------------   
    73   ICFUTHXNUVKGIMV
 11010   NLVMYJAHMUGRNSU  

   535   YXFBIUSEYHMLKGOE
 13018   KCSIDGAOKRHWXNPO

   634   DHLUYREUGSKTIMD
  8995   JQXKPTWKBZGULOJ

  2817   ALOVWEXTSVKIYFA
 12180   HLSDJOFVIDKYQCH

  7145   HDHSREXYRUWMBTX
  8962   EWEBSGNQSXVZJRN

  8835   XOMBNKUXIQVGFLPG
 10549   FYKRZJXFUEPTNWDT

 12072   MUVJKOMELGTBPDB
 12190   KYQCHBKJRPDAFNA

This rules out any cipher system that produces isomorphs such as autokeys, progressive polyalphabetics, multiplex (e.g., strip cipher/M-94), the Wheatstone cryptograph, the Kryha, and classic rotor systems (e.g., Hebern, Enigma).

In the same article Deavours and Kruh add:

An overlooked, possibly valuable clue is in The Editor’s Notebook of the American Cryptogram Association 1952-1956 [ed. kept by Henry E. Langen]. … According to Langen, “He [ed. Byrne] did explain that the machine is made up somewhat like a typewriter with two revolving disks with the alphabets arranged along the periphery in a complete disorder.” Langen commented parenthetically that “With only two disks used, I am a bit confused as to how this can result in such utter chaotification of the plaintext message.”

This hints at a form of concentric disks with mixed plain and cipher alphabets. At this point I’d like to mention John Savard’s excellent cryptographic web site [4]. In particular, you should read his page entitled “Polyalphabetic Substitution”. John describes his attempt to devise a cipher disk that approaches the power of a rotor machine. After describing his scheme he writes:

The Byrne Chaocipher, which was mentioned in David Kahn’s The Codebreakers, was subsequently the subject of a Cryptologia article, which indicated that the principle of this wheel may have been used before in that cipher.

In the light of Deavour’s and Kruh’s quote from Langen’s diary, a study of Savard’s cipher disk idea may be beneficial to anyone working on the Chaocipher.

Mellen’s Observation re pt/ct identities

Mellen’s initial insight was that, in exhibits 1, 2, and 3, doubled plain characters are never enciphered by double cipher characters. For example, looking at the first ten lines of Exhibit 1:

A LL G OO D QQ UICKBROWNFOXES...

Line 1: C LY T ZP N ZK LDDQGFBOOTYSNE...
Line 2: L TV F IC O TS SLWYYIHBICFUTH...
Line 3: T BZ X TM V GL TJXCSQXLNJTENC...
Line 4: H KY G QJ T OG YSDBNVDJOWHKEC...
Line 5: R IF F ZA Q NH SOMJPORWTJOIJI...
Line 6: J EO Z IF K JC FMETESYYHZUVLF...
Line 7: W EF R FY H KX OPKXRQSZKLCZKH...
Line 8: B UZ L AG D BC UAMFQLACRWWTUG...
Line 9: R UT K FK A SG VLVYYFVRAIYNIV...
Line10: U KQ A SX K GS PWHRYMTQSOQBAM...

In the mini-example here, enciphering of plaintext “LL” never results in doubled ciphertext letters (e.g., “XX”). This phenomenon is (almost) true for all Chaocipher exhibits. He deduced from this that:

The cipher component necessarily and causally changes from letter to letter. If the cipher component moved at some point, enciphering the same plaintext letter would result in a second, identical ciphertext letter.
There is but one component and not a plurality of different, mixed, cipher components. A plurality of cipher components would make it virtually impossible to avoid a plaintext double being enciphered as a ciphertext double.

He felt he was making progress until he noticed the following in Exhibit 3, Message 5:

pt: O R D E R S W R I T T E N
ct: O Y F C P R V J B Y Y G F

Although this could have been explained away as an enciphering error, Mellen wanted to avoid such an assumption at this point. He noticed that Exhibit 3 is presented in lines of 26 letters. If the Chaocipher algorithm worked on blocks of 26 letters, the two T’s would be in separate blocks. This could explain the doubled pt = doubled ct observed. The question was now whether the Chaocipher indeed worked on blocks of 26 letters.

Mellen began writing Exhibit 1 out in blocks of 26. He knew he would not encounter doubled plain characters as doubled cipher characters. He did, however, expand his search to see if a plain letter which was repeated in the 26-letter line was represented twice within that line by the same cipher letter (coined by Mellen as a “pt/ct identity”). He quickly found negative results. For example, lines 9-10 show:

pt: W A L L G O O D Q Q U I C K B R O W N F O X E S J U
ct: W U K Q A S X K G S P W H R Y M T Q S O Q B A M A P

pt: M P O V E R L A Z Y D O G T O S A V E T H E I R P A
ct: F Q R L I I U G T I V B E B Y X F B I U S E Y H M L

The number of such instances in Exhibits 1 and 2 is so large as to preclude their being errors. He did, however, notice that the pt/ct identities always occurred in different halves of the 26-letter blocks. Mellen revised his 26-letter hypothesis to 13-letter lines, writing the exhibits out in 13-letter blocks.

In Exhibits 1, 2, and 3 there are a total of 1192 13-letter blocks for which there is plaintext. Mellen found only two blocks that have pt/ct identities:

Line 114: pt: P U R S U I T O F H A P P
          ct: J X M L S Q T V Z B Y J O

Line 176: pt: S T E M O F E N G L I S H
          ct: O U Q F O Y U T E V V O D

For the record, Mellen missed six other cases of pt/ct identities:

Line 142: pt: U L D R E L I N Q U I S H
          ct: B F B W Y Z L O Y B S S T

Line 151: pt: P O W E R S Q I N C A P A
          ct: X Q Q R E X S U Z O X X U

Line 156: pt: N G T H E L A W S F O R N
          ct: D S G D Z X O R W J J V D

Line 162: pt: D E O F N E W O F F I C E
          ct: I I X J B C H V M Z C T I

Line 206: pt: I C E A N D M A G N A N I
          ct: R I G A V V X I G Y K F R

Line 215: pt: O F O U R I N T E N T I O
          ct: H H C Y W F P Y M E R D C

Regardless of the actual number of pt/ct identities, Mellen correctly surmised that, given 1192 13-letter blocks, we would statistically expect about 45 blocks with pt/ct identities. The fact that only eight were found is statistically significant.

At the close of his article, Mellen presents a cipher system of his own. The system, based on enciphering blocks of 13 letters, prevents pt/ct identities from occurring within a given block. He concedes that his system excludes phenomena that occur in the Chaocipher texts. He concludes by saying:

Nevertheless, I feel that I am moving in the right direction. I am currently looking at variations of the system described and I am beginning to see, or beginning to imagine, other phenomena in the ciphertext. These await further testing.

Extending Mellen’s Research

This is the jumping-off point for anyone analyzing the Chaocipher challenge.

Mellen’s observation about pt/ct identities is a critical one. There is no doubt that it strongly indicates that the Chaocipher ciphertext is not as random as Byrne believed it was. I backtracked on assuming that the system is based on a block size and wrote a program to collate all pt/ct identities in Exhibit 1, regardless of where they occurred. In parallel I ran the same test, this time substituting Exhibit 1’s ciphertext for a random text of 13,336 characters. The results were eye-opening:

Distance between pt/ct identities	Number of cases observed
Distance between pt/ct identities	Chaocipher	Random
1	0	25
2	0	18
3	0	38
4	0	22
5	0	23
6	0	29
7	0	18
8	0	31
9	4	30
10	7	30
11	20	26
12	57	24
13	46	19
14	81	44
15	38	24
16	20	31
17	21	35
18	15	43
19	4	30
20	9	30
21	20	33
22	19	20
23	22	26
24	34	23
25	42	24
26	51	28
27	27	15
28	12	17
29	28	36
30	28	32
. . .	. . .	. . .

In other words, scanning the 13,336 pt/ct characters of Exhibit 1 produced no pt/ct identities with a distance of less than nine (9). Unlike Byrne’s claim, the ciphertext is not a “jargon of random characters”. The fact that pt/ct identities are never less than nine characters apart is a critical insight into the underlying mechanism.

What system suppresses pt/ct identities with a distance less than 9?

I’ve racked my brains to define a cipher system that never produce pt/ct identities with a distance less than nine. The following system foots the bill nicely:

Two concentric disks of 26 letters apiece representing the plain and cipher alphabets (e.g., a cipher disk).

Two sliding strips are equivalent.

The disks are aligned before enciphering
A plaintext letter is enciphered by noting the ciphertext letter on the other disk.
After enciphering a single plaintext letter the plaintext disk is advanced 1, 2, or 3 positions.
Any method can be used to determine how much to advance the disk.

For example, if the plaintext (or ciphertext) letter is in the range of:

A-I: advance one position
J-R: advance two positions
S-Z: advance three positions

Repeat the encipherment step

It is obvious that a doubled plain letter will never be enciphered as a doubled cipher letter. This is because the disks will have shifted between 1 and 3 positions after the first plain letter is enciphered.

In order for a pt/ct identity to occur, the disks must make a complete revolution relative to each other. The fastest this can happen is if, over nine consecutive letters, the disk advances three positions exactly eight times, and advances two positions exactly once. In this case the disk will have shifted (8x3 + 1x2) = 26 positions, and the disks will be similarly aligned, enabling a possible pt/ct identity.

It is obvious that a pt/ct identity will never occur before a minimum of ten letters, i.e., a distance of nine places.

Writing a program to simulate this simple system exhibited the expected results. Running it on the plaintext of Exhibit 1 gave the following:

Distance between pt/ct identities	Number of cases observed
Distance between pt/ct identities	Chaocipher	Random	Proposed System
1	0	25	0
2	0	18	0
3	0	38	0
4	0	22	0
5	0	23	0
6	0	29	0
7	0	18	0
8	0	31	0
9	4	30	2
10	7	30	9
11	20	26	39
12	57	24	62
13	46	19	63
14	81	44	142
15	38	24	16
16	20	31	6
17	21	35	0
18	15	43	0
19	4	30	0
20	9	30	0
21	20	33	7
22	19	20	10
23	22	26	22
24	34	23	97
25	42	24	51
26	51	28	48
27	27	15	34
28	12	17	20
29	28	35	12
30	28	32	3
. . .	. . .	. . .	. . .

I haven’t investigated why this simple system results in zero pt/ct identities for distances of 17-20. The next distance not encountered is 464, so we can assume that pt/ct identities occur for all distances greater than 20.

It is important to note the principle of this cipher -- the only disk advancements allowed are 1, 2, or 3:

An advance of zero could produce a doubled plain letter as a doubled cipher letter.
A negative advance (e.g., move the disk in the opposite direction) could also produce a pt/ct identity with a distance less than nine. This would happen if the disk advanced by +1 for the first letter, then advanced by –1 for the second letter to return to the same alignment. If the third plaintext letter were the same as the first we would get a pt/ct identity.

Exhibits 2 and 3 don’t follow Exhibit 1’s lead

When I collated pt/ct identities in Exhibits 2 and 3 there were distances less than 9:

Distance between pt/ct identities	Number of cases observed
Distance between pt/ct identities	Exhibit 2	Exhibit 3
1	0	1
2	0	0
3	0	0
4	1	0
5	0	0
6	2	1
7	0	1
8	0	0
9	0	1
10	2	0
11	1	0
12	1	0
13	2	2
14	3	0
15	1	0
16	3	2
17	4	0
18	3	1
19	2	2
20	1	2
21	1	6
. . .	. . .	. . .

At the moment I’m at a loss to explain how Exhibit 1, with 13,336 pt/ct characters, shows no pt/ct identities in under a distance of 9, while Exhibits 2 and 3 show such distances with only 1,263 and 910 characters, respectively. Keeping in mind Mellen’s feeling that the doubled plain/cipher in Exhibit 3 may have been an enciphering error, these six may just be so – enciphering errors.

For now I’m focusing solely on Exhibit 1. Regardless of the underlying system, it will have to explain why Exhibit 1 has the phenomena we observed.

Thoughts about the proposed system

The system as proposed above is a polyalphabetic whose disks advance 1, 2, or 3 positions each letter. If the shifting sequence is dependent on the plain- or ciphertext we will have a quasi-random keying sequence. Unlike a plain or cipher autokey cipher, the proposed system would be prone to repetitions and isomorphs, albeit possibly fewer. Indeed, in my simulation, every second “All good …” phrase was enciphered identically, resulting in identical ciphertext. This is because the keying sequence is too regular, being based on the plain or cipher letters (autokey style).

Indeed, enciphering Exhibit 1 using the proposed system produced massive repetitions due to the “All good …” sequences. The original Chaocipher texts have no repetitions, so the proposed system is missing something.

There’s another problem with the proposed system. Given large plaintext and ciphertext cribs, we could figure out the plain and cipher alphabets on the two disks:

For every doubled plain letter, the corresponding cipher letters c₁ and c₂ are either 1, 2, or 3 positions apart from each other in the cipher alphabet.
For the given first letter c_1, there should never have more than three alternatives for c₂.
Observing the ciphertext letters corresponding to all doubled plaintext letters should give us the cipher sequence.
Similarly we can derive the plain alphabet’s sequence
Given the plaintext and ciphertext sequences should allow a solution using an “alphabet strip” method (often used by William F. Friedman to solve slide-based polyalphabetic systems).

In practice, item (1) above does not work out correctly. Following is a portion of the output of a program I wrote to list all doubled plaintext letters and their corresponding ciphertext letters.

Plaintext	Ciphertext
OO	AB
OO	AC
OO	AG
OO	AH
LL	AI
QQ	AJ
QQ	AL
QQ	AO
QQ	AO
LL	AO
EE	AQ
LL	AQ
WW	AR
OO	AR
OO	AU
OO	AV
OO	AV
EE	AV
NN	AW
LL	AZ
QQ	BA
SS	BA
LL	BC
SS	BC
QQ	BC
OO	BD
TT	BE
FF	BH
TT	BH
QQ	BI
QQ	BI
LL	BK
FF	BL
QQ	BM
QQ	BQ
FF	BQ
LL	BS
OO	BU
LL	BV
OO	BW
LL	BW
EE	BY
LL	BZ
. . .	. . .

The ciphertext pairs in the right-hand column are sorted in ascending order.

You can see that for the ciphertext pair “A?”, the ‘?’ can be one of 14 different letters (i.e., “BCGHIJLOQRUVWZ”), not three as expected. This apparently disqualifies the cipher system proposed above.

Summarizing the findings

Let me briefly summarize where I stand at the moment and state the challenge as I see it.

We discussed the concept of pt/ct identities, i.e., two identical pt/ct pairs occuring at a certain distance.
We showed that Exhibit 1 displays the definitely non-random trait of no pt/ct identities less than nine (9) positions apart. In other words, no block of nine pt/ct pairs displays a pt/ct identity.
The only cipher system I can think of that guarantees no pt/ct identities within any nine sequential positions is two sliding alphabets that shift either one, two, or three positions every time a letter is enciphered.
Collating all ct pairs (c₁-c₂) corresponding to doubled plaintext letters (p-p) shows more than three values of c₂ for any single value of c₁.
If the cipher system were item (3) above there would be only three different values of c₂ for any single value of c₁.
Items (3) and (4) are not compatible.

Reiterating the challenge

So the challenge is: can you postulate a cipher system that guarantees item (2) above and explains item (4) at the same time?

References

[1] Byrne, John F. 1953. Silent Years. New York: Farrar, Straus & Young.

[2] Mellen, Greg. 1979. J. F. Byrne and the Chaocipher, Work in Progress. Cryptologia, 3(3): 136-154.

[3] John Byrne, Cipher A. Deavours and Louis Kruh. Chaocipher enters the computer age when its method is disclosed to Cryptologia editors. Cryptologia, 14(3): 193-197.

[4] John Savard’s excellent cryptographic site can be found at http://www.quadibloc.com/crypto/jscrypt.htm . I refer the reader to the page entitled “Polyalphabetic Substitution”.