brainwagon "There is much pleasure in useless knowledge." — Bertrand Russell

20Nov/133

Visual Cryptography

I read an interesting article the other day. I'll skip to the end to show you the result. Check out this pair of binary images:

img1

img2

Not too fascinating, huh? If you print both images out on transparency though, and stack them together, you'll get this...

both

Hopefully that worked (with my limited CSS skills, I don't think I got it exactly right). I couldn't get the CSS exactly right, so the above image is really just the pairwise minimum of both images above. But how I accomplish this miracle? My own simple python implementation of the ideas cribbed from this page. Script to come later.

13Sep/111

Can we go beyond WSPR? An idea for beacon operations on amateur radio.

I was interested in WSPR and visual MEPT oeprations for quite some time. I operated both a beacon and a QRSS aggregator on 30m for a while, but I grew a bit tired of it, and it's been silent for a year or so. But I haven't stopped thinking about them. In fact, I've had an idea percolating in the back of my head since last year, when I became aware of the work of Leemon Baird and William Bahn on Jam Resistant codes.

But I'm getting ahead of myself. Here are some of what I think could be improved with WSPR:

  1. WSPR requires accurate clocks both for receiving and transmitting. To be successfully decoded, transmissions must start within a window just a few seconds long surrounding even numbered minutes. This makes both sending and receiving systems complicated: they probably need to access an external reference (NTP, GPS or WWV) to operate reliably over an extended period.
  2. Fixed frequency operation can cause collisions. Each transmitter selects a fixed transmit frequency, and relies on multiplexing over time to avoid collisions. WSPR software itself provides no real help in selection of an appropriate free frequency.
  3. The choice of a convolutional code is somewhat odd. The payload is only 50 bits long, but we pad the results with 31 zeros to flush out the convolutional coder. Thus, we are actually getting the error correction of a rate 1/2 code, but we are only sending as much data as if we were sending a rate 1/3 code.

I had been pondering some of these issues, when I became aware of the work of Baird and Bahn. They are researchers for the Air Force Academy, and were particularly studying the problem of providing jam proof communications without the need for shared secrets. Briefly, you can imagine using spread spectrum to provide a measure of jam proofing: because the data is spread out among many frequencies over time, the spread spectrum signal has a good measure of jam proofing: the jammer needs to put energy over most of the frequency most of the time, where as the transmitter can put his full power on just one frequency at a time (other variants of spread spectrum are a bit different, but the principle holds). The only way a jammer can work efficiently is by knowing the sequence, which is usually a cryptographic secret.

This is where Baird, Bahn, and Collins' work comes in: In their paper:

Baird, Leemon C. III, Bahn, William L. & Collins, Michael D. (2007) Jam-Resistant Communication Without Shared Secrets Through the Use of Concurrent Codes, Technical Report, U. S. Air Force Academy, USAFA-TR-2007-01, Feb 14.

they show a simple technique that can be used to transmit signals with high reliability and a high degree of jam resistance, without requiring any kind of shared secret or cryptography.

The idea is somewhat subtle, but reasonably straightforward. The idea is to create take the binary message (say, the same 50 bits that we use for WSPR). This message gets padded by a series of zeros (maybe lots of them, perhaps a multiple of the original message length). You then need a hash function (some details matter, but you can think of using a standard one like MD5 or one of the SHA variants if you like). Now, for each prefix of the message (bit streams of length one, then two, then three, and so on), you compute the hash of that prefix. Let's say that you are going to transmit the message by sending short, powerful bursts of energy at particular times in particular window. (You can imagine this being the two minute window used to transmit WSPR to make it more practical). If we divide that into (say) 8192 slots, then we could take each hash, take the lower 13 bits, and use that to specify a particular time when that bit would get turned on. If we send 500 bits total (9 zero checksum bits) for every real one, we are sending about 500/8192 slots, or about 6% of the total. To mark the start and stop, let's turn on the first and last bit. That's pretty much the entire transmit side.

What's cool is that you can decode the message on the remote side, and if you ignore efficiency, it isn't even that hard. Let's say that you located a stretch of bits 8190 long, between two on bits. That might be a message. So, how do you decode it? Well, the first bit might be a zero or a one. You basically pretend that you are transmitting, and encode both messages. That will return a location, which you check to see is on. If it isn't, then you know that guess was wrong. If it is, then that hypothesis is good. It's possible that none could be right. That means there is probably not a message in that span. It's possible that one could be right, in which case you then add a zero, and then try adding an one, and seeing if the hypothesis still holds. There are times when both results will check out, but statistically it is unlikely. When you hit the "checksum bits", you know that there is only one possibility: a zero. If the specified hash doesn't yield a location that is turned on, you know that you are on the wrong track. (The overall algorithm reminds me somewhat of a Viterbi style decoder, although it is actually considerably simpler).

There are lots of details to make this efficient (you want a hash function which allows incremental updates as you add individual bits to the message) but it's pretty straightforward.

Anyway, I think this could be the basis for a new highly-collision resistant beaconing protocol for amateur radio. It would enable very simple transmitters (a simple microcontroller could hold the sequence in internal EEPROM, no need for highly accurate clocks) and the system would be more highly jam resistant than the current system. We could use simple CW transmissions, or adapt to slower rates with more diverse frequency usage. And, the technology has been paid for by your tax dollars, so no pesky patent/IP issues would seem to apply.

What do people think? I'm interested in hearing some feedback from digitally minded radio amateurs.

Addendum: if my descriptionw as insufficient, try reading the papers (especially Visually Understanding Jam Resistant Communication) and/or posting some questions in the comments.

28Aug/115

Donald Michie, Alan Turing, Martin Gardner, and Tic Tac Toe

As anyone who reads my blog with any regularity will tell you, I like to read and learn new things. The problem with being self taught and also easily distracted means that you often learn a great deal, but don't always perceive the connections and scope of what you are learning. I found another example today while surfing.

Years ago, I remember reading one of Martin Gardner's Mathematical Games columns (from March, 1962, in case you want to look it up) where he described an interesting machine for playing tic-tac-toe. It was made entirely out of matchboxes, each one of which had a tic tac toe position on the top. Inside was a collection of colored beads. Each color specified a possible legal move for the position on top. The idea was that you'd play a game by drawing these beads from the appropriate box, and making the appropriate move. At the end of the game, you'd remove the bead from the last box that sent you along the losing path. Eventually, all the losing moves get removed, and the machine plays perfect tic-tac-toe. Gardner showed how this same idea could be used to create a matchbox computer to play hexapawn, a simple game played with six pawns on a 3x3 board.

I really haven't given it much thought since then. Many of you have probably read this article in one of the collections of Gardner's columns.

But today, I was surfing through links and reread some of the details. I found that the machine was called MENACE (Matchbox Educable Naughts and Crosses Engine) and was invented in 1960 by a gentleman named Donald Michie. And it turns out that he's a pretty interesting guy.

He was a colleague and friend of Alan Turing, and worked with him at Bletchley Park. Apparently Michie, Turing and Jack Good were all involved in the British code breaking efforts, and in the creation of Collosus, the first digital programmable computer which was used to crack the German "Tunny" teleprinter code. (Good and Michie were apparently two of the authors of the General Report on Tunny, a report on the cracking of the code which has only in recent years become declassified). None of this work could have been known by Martin Gardner at the time of this publication. Of course, this was also true of Turing's work as well.

Turing made a huge impact in several related disciplines: in mathematical logic and computation, in his wartime efforts in code breaking, and in his role in creating some of the first digital computers. Turing also became interested in mathematics in biology, writing about the chemical foundations of morphogenesis and predicting oscillatory chemical reactions. Michie received a doctorate in biology from Oxford, but returned to have a profound and lasting influence on artificial intelligence. Oh, and that modest little paper on Tic Tac Toe? One of the first instances of reinforcement learning.

Very cool, to discover that the little bit of reading you did as a teen, which seemed like an insignificant game at the time, actually has profound threads which stretch out into lots of different areas.

Donald Michie's Home Page
Trial and Error, the paper describing MENACE

28Mar/111

Neat article on William Friedman and Steganography

William F. Friedman is a name that might not be familiar to you unless you are a bit of a cryptography nut. Of course, I am a bit of one: I have a couple of long technical notes that were authored by Friedman on the cracking of some complex WWI era ciphers. But I must admit that I've barely scratched the surface of a very fascinating man and his career. The following article talks about Friedman's work on steganography (the hiding of information in plain sight) and its relationship with Bacon's cipher. Pretty neat stuff, and includes some material I had never seen before.

CABINET // How to Make Anything Signify Anything.

Filed under: Cryptography 1 Comment
15Mar/110

Demo of Enigma and the Turing Bombe at Bletchley Park

Carmen and I just got back from a trip to London, and we had a blast. One of the geekiest things we did while there was to take a day trip by train out to Bletchley Park to see the site of the codebreaking efforts by the British during WWII. As any long time reader of this blog must know, I'm pretty interested in codes and cryptography, and this was a bit of a personal thrill for me.

While we were there, we managed to get demonstrations of a real Enigma machine (very cool) and the modern reconstruction they completed of the Turing Bombe. I shot some video of it using a Canon G11, which isn't all that great (the sound in particular is pretty terrible) but I thought I'd archive it on YouTube in case anyone else found it of interest. If you get the chance to go to Bletchley, I heartily recommend it: we spent four hours there, and it really wasn't enough. Besides the Enigma and the Bombe, they have a reconstruction of Colossus, the first electronic digital computer that was used to break the German teleprinter code that the British called "Tunney". They also have huts filled with many artifacts of the period, including one containing a bunch of radio equipment, dating all the way back to the crystal sets of the 1910s and 1920s to the Piccolo secure modem transceivers that were used in British embassies well past the war. Nifty stuff.

I have some pictures that I'll get onto Picasa sometime soon of related nifty topics.

15Jan/112

Colossus: The secrets of Bletchley Park’s code-breaking computers

As long time readers of my blog might remember, I've been fascinated by old cryptographic machines. I spent quite a bit of time tinkering around with them back when I was working on Simon Singh's cipher challenge in his book. In particular, I spent a considerable amount of time reading up on the German Enigma machine, and eventually managed to break Stage 8 of that challenge using an Enigma machine simulator that I coded up. I also have a fair number of books on Enigma.

For all that, I didn't actually know much about the other great code breaking effort at Bletchley Park: the break of the German "Tunny" code using Colossus, an even more impressive machine than the "Bombe" which allowed the breaking of Enigma. My lovely wife scanned my Amazon wishlist at Christmas, and picked up this book for me for my Kindle.

Colossus: The secrets of Bletchley Park's code-breaking computers

If your tastes in reading are sufficiently refined to the point where reading about sixty year old code machines is interesting, I think you'll enjoy the book. It isn't too technical/nuts-n-bolts, but it does give a good basic idea of how the Tunny operated, and how the British developed an advanced code-breaking bureau that saved thousands of British lives and allowed the preservation of important supply lines in the face of German U-boats. If you are more interested in the history, you might do well to also pick up a copy of Codebreakers: The Inside Story of Bletchley Park, but Colossus includes more technical details on the Tunny.

After the war, the British destroyed Colossus, and most of the records of its function were lost or classified. But in 2000, the British released the "General Report on Tunny with Emphasis on Statistical Methods" which was written in 1945, and details much of the techniques they used to attack the Tunny. It's online at alanturing.net and also makes for some interesting (and free!) reading.

27Jul/1015

10,000 Monkeys Typing…with a Unix/sh challenge…

I was testing some code that I wrote for analyzing cryptograms, and decided that the easiest way to do so would be to get some random text, drawn from the letters A-Z. A moments thought yielded this method, without even programming anything:

tr -d -c A-Z < /dev/urandom | dd ibs=10000 count=1

The tr generates the required data, and the dd truncates it to the desired number of characters. But for tidiness, I'd like to have the output broken up so that each line consists of 50 characters, with spaces inserted between every 5 characters (I won't begrudge you if you leave a dangling space at the end of each line). I couldn't figure out a simple way to get that to happen all in one command line and using standard utilities. I can of course write a little Python utility, or even perl, but can anyone think of a clever short way to do this?

Addendum: Tom pointed out something interesting about the command that I listed above: it doesn't work the way I think it does. Apparently the ibs is the input block size, which dd dutifully allocates, and the count is the number of read system calls that the system issues. For reasons which escape me, it does not try to make sure that it actually received a full input block: it will nicely return short blocks if it finds them, and doesn't bother retrying to get more. Hence, it works rather erratically when using a pipe as input, particularly when the writes from the upstream process may flush in odd intervals.

15Jul/103

Crazy Optimization of Chaocipher…

Okay, this is a minor hack, but I thought it was fun, so I thought I'd write it up here.

My original code for simulating the Chaocipher machine proceeded as follows: it found the character in the plaintext wheel (by linear search), then rotated each wheel to get the plain and cipher text entry to the zenith minus one and zenith positions respectively, then did the short cycle rotates. It used a temporary array to perform the first rotate, and then used memcpy to copy the results back. The short rotates were done in position. Hey, it was easy to write, but kind of ugly. In particular, it did twice as many read/write operations as necessary, and I hypothesized that it was a bottleneck.

So, I wrote a little code generator that instead generated "compiled" code for each of the 26 possible paths through the encoding code. Each entry in the cipher and plaintext wheels is read and written only once, and I use only an additional char of storage to hold temp values. Here's the fragment of the code that executes if the cipher text is found in position number zero:

	case 0:
		tmp = m->cw[1]; 
		m->cw[1] = m->cw[2]; 
		m->cw[2] = m->cw[3]; 
		m->cw[3] = m->cw[4]; 
		m->cw[4] = m->cw[5]; 
		m->cw[5] = m->cw[6]; 
		m->cw[6] = m->cw[7]; 
		m->cw[7] = m->cw[8]; 
		m->cw[8] = m->cw[9]; 
		m->cw[9] = m->cw[10]; 
		m->cw[10] = m->cw[11]; 
		m->cw[11] = m->cw[12]; 
		m->cw[12] = m->cw[13]; 
		m->cw[13] = tmp; 
		tmp = m->pw[0]; 
		m->pw[0] = m->pw[1]; 
		m->pw[1] = m->pw[2]; 
		m->pw[2] = m->pw[4]; 
		m->pw[4] = m->pw[6]; 
		m->pw[6] = m->pw[8]; 
		m->pw[8] = m->pw[10]; 
		m->pw[10] = m->pw[12]; 
		m->pw[12] = m->pw[14]; 
		m->pw[14] = m->pw[15]; 
		m->pw[15] = m->pw[16]; 
		m->pw[16] = m->pw[17]; 
		m->pw[17] = m->pw[18]; 
		m->pw[18] = m->pw[19]; 
		m->pw[19] = m->pw[20]; 
		m->pw[20] = m->pw[21]; 
		m->pw[21] = m->pw[22]; 
		m->pw[22] = m->pw[23]; 
		m->pw[23] = m->pw[24]; 
		m->pw[24] = m->pw[25]; 
		m->pw[25] = tmp; 
		tmp = m->pw[3]; 
		m->pw[3] = m->pw[5]; 
		m->pw[5] = m->pw[7]; 
		m->pw[7] = m->pw[9]; 
		m->pw[9] = m->pw[11]; 
		m->pw[11] = m->pw[13]; 
		m->pw[13] = tmp; 
		break;

You should notice that the cipher wheel doesn't bother to move element zero at all (it doesn't move if the plaintext letter is found at index 0). It also doesn't touch the upper half of the cipher wheel, since those letters are left in place by this particular path. It then uses each element as the source and destination precisely once. Since there are two cycles, uses the temporary variable twice.

The resulting code is about 1450 lines long, but the resulting program runs almost 2.5x faster overall, searching about 10.8M nodes per second in my backtracking search. Worth the 20 minutes or so it took me to write the code generator.

Addendum: In theory at least, you could safely issue reads and writes which occur in different cycles in parallel, since you know they don't target the same addresses. But I don't know how to hint to the C compiler to perform that optimization. I also suspect that SSE instructions might allow you to load and swizzle faster.

Filed under: Cryptography 3 Comments
12Jul/103

Typos in Exhibit 1?

WARNING: if you are working on this code, this article contains spoilers which may blunt your own intellectual satisfaction in working on it yourself, including some recovered keys.

Okay, I'm home, and feeling pretty jet-lagged, so this might be wrong in some way that additional sleep will reveal, but I wanted to get this out of my head before work today.

First of all, I downloaded Exhibit 1's plaintext from this page, specifically this link for the plaintext and this link for the ciphertext. These files contain no spaces or carriage returns, so are relatively unfriendly for human consumption, so the first thing I did was to reformat them into 11 groups of 5 characters per line to match the format that Exhibit 1 is presented in the scanned chapter of Silent Years.

Then, I set my constraint solver working. It loads both the cipher and plaintext, and does an exhaustive search to find the consistent wheel settings that consumes the most input. It then dumps the settings as a command line that should decode the ciphertext, or at least as much of it as it has discovered.

The first 100 lines of Exhibit 1 consist of 100 copies of the 55 character sentence:

ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW

So, the first 100 lines of the decryption of the cipher text should be just 99 copies. But my cipher program pointed at a problem after 603 characters. Here are

./chaocipher -d -c 'CPEDQRSTIXYLMOZABFVGUHWJKN' -p 'AYZNBQDSEFGHLWIKCMOPRTUVJX'

When I run this on the original text, I get the following (numbered for convenience):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTYW
ALLGO ODQQU ICKBR OWNFO XESJU MPOVE RLAZY DOGTO SAVET HEIRP ARTGW
ADLGO OSLLI VFCRB YMHAW QGNMS NDNCK GZYPM LAYNZ LFNDO WGBJU IXZLD
TNOJM TUSZG IKMLC WNCKK OUICA YKSJJ SSKFR GLLPU XAOXS BXAPQ ECJSU
SFLFT ZLNQS SWNZN TKSDG JUUQC GQCDD WPDIN FZODL MJEXV WIFFW TEFPS
ZKUAT XVTKL FZLHM VICVD PMEZP YCULX VAXNE AYRSL BBMIT UJGII TSPIQ
UMUMC FWFPO SYYAW EYCKY ZQUVJ BOIIU FBHXT QFHKS EMWDB TSNJY GNIKJ
QHJRR DCGCX MINUQ ZGITG HTINW UZWFX HJEWM QDCXN BXKGY QDDNG IAXNY
RCRAM KCOAI VLKLF SNVGW SQYOA OYUUW YOQAC SUDFF KYXPJ GTBPS ZTONZ
CZPDM MOORN EVZZV AHBUP VOCUJ AHCGZ SLVUY ILIDG YAOOX TYDDA LJDLO
ULRNQ ASEZW BXPSV LEMYZ THMVA BHCII YVHIU JQBAU RGZEI ARUIL NZEDY
BJIOG TRFMH HDJFR ROBKH SMUHY PBYUQ MNNRW YBPRZ KCUQK LGNAI EXRAX
KDJVP JHMRN IFINI ZYGSZ ITDWZ NKGQV QUXVJ YZUIJ FQECB RWSDK QZUHM
XZBFK XGICH IMHHR NKSMF VXTCG IQOJK TCCJO BWQJC ATUBZ ILHRE ULVHQ
WUMDQ SERWK AYNOW PGKZF CWMOG SOLYO YVUSW AIEIO FPJDS SCMEC LTWBA
KNGQE KZFCC RKKXL ZXNTH UQXQD DGJPU EZEVE IPVZC XNRZV OGGVV JBCYP
WMJQG BYMKX NNGAA YDGRA XKVAV LVLFK WIQDE DBZHF YSVEN WOGJK USZPZ
QPEKM UHTDT HTOJU FQIMZ KHPWT AJGDE CEUKS RSLNU GIUAM XUWLN CSJVC
NXOBT AVQTY HLBUL VYYBX CLFEV LKVVE JGYAP SDSIS RZPJQ ISDKS JNEDW
HMSMF DXVZY LVVJF USVXN ZGKFQ NYMZO QQGQJ SCUVS LJRAL NOYIY HRWVD
JMEFF ZRNCU PRUFT NFETI WESRY NOVKQ UVCKY QNWQU OQMHA MATEE QBRWE
YBSQR HLMRH OCLOP PWIOE AGTHF KTMLE TYILX UZSNX JWHIG LJXRB KUCNW
RZMFC OBKBL FGEVF THGHE MYHMA LLWBV SMUDF XGHPM IWDVC ODXYR LGLTU
SGPKX WQBIR IPVJV LNNWR LYSQK OQPOD BBZQL WSSJB IUHVU IXTVW RAUJJ
BLGMT CIVOQ KQXXZ FCXQN GWCWI SQWMY OCZBY PHCEH ULDTT FETNI ESUVQ
CUWCL LSQVL BRYZW BRGIC QFHDU MUJQQ SXCVK SPYRM BYFFI NQZPZ PURFS
RWNWH WOKUZ GSNPM LJQDB XOZEG YTYHH PAGFR NQILO QCTNP RNFMY PHSEH
MXUDW AUDMB MLZBW SIGDP EOAVG BXWWH EREWH DBPSC WFAFS AHATC HAYAL
UVYMP KGPMD NBIWC NQTXT FYVYW KNKQU VJZIH WZCLF HTTBY SRRWW APVAQ
PCZYV PTMLJ BYQRQ IHIHZ ZXIWX CEOVG FYZUN PQFTW NNHYX CQKUN GWVNF
NYGDI ZKOUR VTQYI MNFVX JHJYN TWOKP DMOYF RJOED GLGKL JZYVE EKLZU
JEMXF VWVYZ ROISI CQKRZ XUFWX RFWVS VPPLH MUEOF YUBPW BBOUG BAUMD
GIWET YNTKV DSESI ZLWSL VKHIZ NZKCO JTRGH SWVVZ RUNDD LHEFP XTLHD
LFEFB UHDDH ZORCZ NLKQZ QJZQB ZBQFT CDMOS UGHCE YYUSY EPCID PMZYY
ZHWWL TZNLX HEEMQ JCEYS EAOWO JXBGK BHCAT QTHAB CPXXT BMSLW BBLQR
CSHCH MHURA WOQRG LWMLT WGFDG AOEJF GSFXR DMRHR FCBPY JLFGP UXQHW
NPUQP BKMIC EQZDM YIMXU FWASM CXJAR PSVEK ZMIZV PQNRP YGBLK IXJFF
ASHHB BWRDJ ZXFSG STINW TGJHY TQSRQ ENFIX JMSZZ FYKKC IEOIR ERJYK
JLPCU NXTAP XTCBL HIGZT SEPTW SBMFE WLKZX WIZDG RBAEJ LIIRW UFRKI
NLJTR UTFWF KFSVJ KZQEC VCYNI RIBQM BJHEG FZYAT UQOAS UCLBG GCYBD
PSTDV TKEBN IGUFH XTKTL INLVG KDPGG IEPJG BHASL CBWNS BOVYA GKCRZ
WUQXV JZMNG NANAD BMGFN QUZCM QAHQH VAXWK SRFCY OJGKC RIGHL HGTAH
WCFRZ MHXWK TWJPM YQWJH FNCPU BLBXD YXMSK BDDIY ZQABQ HZMEO WPNOE
RHFVE QHIBY FPDCW EXRZG GJNZO MLEYY WZJHH YVRRM LUHXI YJDDQ TJOOM
EVWYG IQUFD LPPMD QADBK CTBIJ HELST EOXZZ SUUWI XZHIS OXPVY FMNOP
WKOIF JHBOZ CITZQ VTGEM NOJGB KQMVG URNWU GFEBB IDWXB KQEOD FOPIV
XLNJA LPUKH NXQTI YBIEV YIJYT ZHSQW LISZT YPZHQ VOYTF CMRFM QAPSP
YZGZT SHGIW VFZDZ YMVEF YZYJI KHQMG WVQOG YACHG MELVP MNMOE PASDH
WIWLH KAEQX QBEWW IMPVC PZISZ SWZBR SETHW LXHQO DADLT UVUXC JSNKB
EDYMV KNXGM DLOOB KUUFA DRPHO GLBNA WXVCG YZKVY BQMKF NFWGR JPAHA
DGDIO OQCTC SQBKT JVHDE KFKQF KOKYW RPEBF HBKCK ZNQYH MZBWD VAHFF
QVIAZ QUWKA IEVXP KLDWJ ATRTB LYPWI AWPAO TYDOM YFQZR ZTMAS DMCOS
ALHRW QRSPC KIHJV JXSJB UQVOG EWQON BKNLO VPIGF TNGUP BVBTU WHGTJ
XZJAV NCACR UNPZW DQWOT SYOAS YPBQZ TVIYF VZKIW SFETG XUCYI QSBPY
IHYRV YSIII IUGHL FNUUH ARMJL BIAUT WNLOP ZXECP SEBYG SSUGS LNNJR
GMPDT ZQIIE RHKSO UEZBO XEAFB DYKRK ARYYX XQUJG DTWLB WJZCB LHVIQ
RKQAF VVKEW MSVDR ZVQAN JNCBA MJJRR EJKZK ZLILN KKXVR UTXIQ ZRQDG
OKHRZ KWVHH MOHNP JVXLB XVCVV YVYYO CKKZH VRXKQ PWAJY ZIKAS QVFET
CPJHD OOZBT JIULN OSVTG DJBPP ZMALD ZCUJW HNWTL AZNIV VFVQC NMAMC
DXUGM ZUHOX YDEYR NYNIA NRWQY UIRPD UTUZF JLUJL GYIOQ GYGZG DWDIM
GMGJT TPOOK DTBFJ YUAAN OPEGH TSMPT VDUOV ZRANZ MUFDB ECZQV NWCBV
NKLVO ELKJI LKOAI PPRHR AOXIA YNYEY DFSAN JCCTR GDLWE MLOLP SQRXF
NMWLV KXALI PHSHL CHQKI CQZNK VGHBZ YXPBS CQSUB JEUYH RHAXU TJIGJ
EEMUT RSLMQ OJVLO XHXZQ GGNZM CBCZS OAWTR TTZDK YJPIQ FUVMV FCHIC
KLIRL XNRHK QKLKD JZKGJ OTCUQ ISBBH QFQOL VHAWG HWTPB BYDBB PVJKE
HQDFQ OBHXD YLZVV UXHSJ RYNXU MQENC ZHKUN MIZZB NNHRS ZVETO PCQOR
THGUI LBPFB CDJHW ARUBH FEIYL KRTXP FQEKX TFGND WQPVO NTESV WYQFU
OZMVC BMSAF ARKMX LQCWD JEAOZ WVFKM SSQND FVZNH EWCRP TKBBY ZCYCB
OWGTB IIBQX EUSAH VYJVM YHFYQ JFZIS AIKBX YIROC DEAJY PZKXG NQCZI
CCVFP PEDOC DUIES JDHAC THZCD VVSAG AWLIG XATOG ODAPS HWPWL MAUPP
AYXHP QGPKT LBERJ UKYXL JQSJG UKVMM IVWFS CMXER OKYIS QPQUS LOVHM
QIVLW GVEDN SORUC AHVTJ UNEYH VOYEE TSTSW KNGVO PZVCK BNMNC ITPNN
BVAZI JHIKG ULJOY RYYTB MLJZR PUOUZ NZQZI GTOIL CMMXY EUUSQ MJUBT
SFAGH JOKBU ODASI ILJHS QYVVD ZRZOC KZEZW XFVFS OMYZA YRXGC ONOQO
DRUGY MDFVL PRAOH SKVRX YKHRB DJVLA HNDKQ JJWMO VAOND VXZHC WEEXK
ZQQLH AOWLO TNKXI LHEJX ZHTSQ DFFJJ DPAUH TFXDI ZOWUK BOLMY ASRGP
XXNDA DIOCT BJJLK PUOUM LBHFE JBUBS FFYTK PZWNA FUJMA NVKNF JNXRH
HMROR KPBRB AJPUE IBUAI CWEMA SMTED JOAMB KFLPH BPYFT EZQZX JKHIF
VQRTJ ECWYC BQYTO CREGC TPFRT LGSHD YSULB HUVCW YFNYB BRRGH FGWAR
SBZXO LSUYP FJCPC TEZSM ICAZJ ACVIA MXMHC QHHUH HWBFF YSDII FUPYN
NHEWK YWBWH BJBTY GWPYR HSVKH DYHLZ JWCXH SYCFS SYEMJ DVIAA XNQNH
SAVVH ZCHBS LXYEO PIWHC OLQKW CSQXH JLNGE IYGDN XYCZK LTGPR YXMDQ
BXWVC XAJLI SKXIH TJHRB BONEZ ZJDPU YETBL EOVZZ LYMSG XTAEX HAGHS
CVTNS LZSMY ZWFHL ARUVN JMGLB PNZGJ ZFNWT JDYDH HBUAI GKQMG FNXON
FXQRH NNYMB ILCXR SPNZJ KCIVK OMXZN XWVGA KVHSE RVGTM UBCSC PUABB
IOBXN DATDL LTJUZ LMEXE EAHNR PIIHZ WHHEM XMFSM JDRIQ JHPRS CBGRW
CIGED BTPIU HLCTQ KOMDD KBHCV ICRWI CJBSJ IWIVB WYOHK ECODH NBSZH
HUPNL FXJEX SZVMM TLYPQ WYQDJ IIRTN YNIHG UZJFS VQPST RSKNP WMHYT
SEEYI YCKNF NYGEI XLJGF HSFGM NDXEI UUGJF RVBWV CDLDE SFCNW LZXUB
AKWBI KATXO OALDE SHAHB RTXTI FMSEW WKDEB GBWMM RPBXO VRQIR MTQFH
VMPVA BMMTM MPBAI ZTKTS XAZJU NRHUK RCKMI ILHBK VVMSS VWLAE GWXAV

You can see that in line 11, goes awry, and becomes desynchronized. It could have been a bug in my program, but I also suspected the possibility of a typo. So, I created my own version of the cipher text by taking 100 copies of the original line, using the key settings that I recovered, and creating my own version of the cipher text.

They match, except for three places. Here are the context diffs:

*** original.1	2010-07-11 17:37:09.000000000 -0700
--- fixed.1	2010-07-12 07:02:11.000000000 -0700
***************
*** 8,14 ****
  BUZLA GDBCU AMFQL ACRWW TUGSM PPZBR FASRO YIRCA GVEYN SRTOQ TDLFJ
  RUTKF KASGV LVYYF VRAIY NIVJK IUWPF ZBVRU EOTEJ GLCGY SSNHH QTIQW
  UKQAS XKGSP WHRYM TQSOQ BAMAP FQRLI IUGTI VBEBY XFBIU SEYHM LKGOE
! CSWUH TBIZZ HLBND IWTQA MAZBM YMBEK CYKCA BLYQY MELPJ OWNRV FZVBR
  EBVUJ EQIAE MOHTG FHFFI DIQQJ UAWDH LUYRE UGSKT IMDWR RNONJ KDPTC
  JDCJN BVEOU TWXOF GRXND KITNL OXSLZ WQRDE RERHL XWAMY LRVPR JFHRA
  SDJWW OIWEV AVMRR NLRJM IFDHH ADDQC BZWYK DVPAY NPIAX BYUKI JGVUC
--- 8,14 ----
  BUZLA GDBCU AMFQL ACRWW TUGSM PPZBR FASRO YIRCA GVEYN SRTOQ TDLFJ
  RUTKF KASGV LVYYF VRAIY NIVJK IUWPF ZBVRU EOTEJ GLCGY SSNHH QTIQW
  UKQAS XKGSP WHRYM TQSOQ BAMAP FQRLI IUGTI VBEBY XFBIU SEYHM LKGOE
! CSWUH TBIZZ HLBND IWTQA MAZBM YMBEK CYKCA BLYQY MELPJ OWNRV FZVKR
  EBVUJ EQIAE MOHTG FHFFI DIQQJ UAWDH LUYRE UGSKT IMDWR RNONJ KDPTC
  JDCJN BVEOU TWXOF GRXND KITNL OXSLZ WQRDE RERHL XWAMY LRVPR JFHRA
  SDJWW OIWEV AVMRR NLRJM IFDHH ADDQC BZWYK DVPAY NPIAX BYUKI JGVUC
***************
*** 47,53 ****
  AEXFA UPOKM SBMNZ YUHEM ZLBQM ROIUH KECCE IXDAR VFAEV WDHPS GYTTA
  ZRNTO WRSTD YOKCW NQUIS WEFIF LFFZQ BSDCS CBNRQ SZLXB BRICQ CLSCB
  INRYO RGNZE GCYAW PMCQL CGBMX BBUBO NQOZZ OFNQR YMZWA CDMGX NAIRA
! ABKCI OWTGT OTOOK MFRPG XADLN AAJSU BMTIQ VHOUZ TBCZA LEOPO YVEWO
  USDUN TZTJT YXUIG OZQFS VDDSR JWUFH FGIZS ORJTB IVSKB BHMPQ NXMWK
  AGSNT KJWOX HALOV WEXTS VKIYF ADOMO NPZCZ FZROC BIRWP UNTAX WXSER
  PGPPU RINGD CGFDG ZALDT NXPUQ EPQSU ZVKDO TXTBN MUQAS ZKIGH WQRQI
--- 47,53 ----
  AEXFA UPOKM SBMNZ YUHEM ZLBQM ROIUH KECCE IXDAR VFAEV WDHPS GYTTA
  ZRNTO WRSTD YOKCW NQUIS WEFIF LFFZQ BSDCS CBNRQ SZLXB BRICQ CLSCB
  INRYO RGNZE GCYAW PMCQL CGBMX BBUBO NQOZZ OFNQR YMZWA CDMGX NAIRA
! ABKCI OWTGT CTOOK MFRPG XADLN AAJSU BMTIQ VHOUZ TBCZA LEOPO YVEWO
  USDUN TZTJT YXUIG OZQFS VDDSR JWUFH FGIZS ORJTB IVSKB BHMPQ NXMWK
  AGSNT KJWOX HALOV WEXTS VKIYF ADOMO NPZCZ FZROC BIRWP UNTAX WXSER
  PGPPU RINGD CGFDG ZALDT NXPUQ EPQSU ZVKDO TXTBN MUQAS ZKIGH WQRQI
***************
*** 84,90 ****
  FCNLQ NWAOG NTOIV JZRVS IACOO KEYIN OZBNP KEGHF JFASY SDIFB NXNXF
  JPSAM RVBQG XNIZB MVGVU VNFMU FJXEL BZLTP IFIWB LBXPB QDXAW FRHBF
  QPDCM OXOSU MMERK QNMYF YKDOC BOXIY SPLGV PBLNG NKTAK YNGBX MIPOM
! RIDCL TCIBZ HFLDV RXBKP LRKMU CQHEY RAAVH XAYDH NNNUN JCINA RAEXP
  UAQRP RUDMO OHOOM EMGUP IEEIX AQTLU PETXI BQEPN IWBRE BNSEQ RDUGG
  TGWUR QRJRL XGRDP MJPDX TSDBG YYQDR DQYSZ GLXDR IDLYX FIVSQ WZVQG
  QRXLN LBLGT EGHVN ZXRFN HFQOW XIXBE ULILO MRXQO GJXRC JOUZH OTJAK
--- 84,90 ----
  FCNLQ NWAOG NTOIV JZRVS IACOO KEYIN OZBNP KEGHF JFASY SDIFB NXNXF
  JPSAM RVBQG XNIZB MVGVU VNFMU FJXEL BZLTP IFIWB LBXPB QDXAW FRHBF
  QPDCM OXOSU MMERK QNMYF YKDOC BOXIY SPLGV PBLNG NKTAK YNGBX MIPOM
! RIDCL TCIBZ HFLDV RXBKF LRKMU CQHEY RAAVH XAYDH NNNUN JCINA RAEXP
  UAQRP RUDMO OHOOM EMGUP IEEIX AQTLU PETXI BQEPN IWBRE BNSEQ RDUGG
  TGWUR QRJRL XGRDP MJPDX TSDBG YYQDR DQYSZ GLXDR IDLYX FIVSQ WZVQG
  QRXLN LBLGT EGHVN ZXRFN HFQOW XIXBE ULILO MRXQO GJXRC JOUZH OTJAK

The first is clearly a transcription error: if you look at the original, the last five characters should be FZVKR. The next is seemingly a printers error, it does appear to say OTOOK instead of CTOOK. And frankly, I don't remember what I found out about the last one.

If you fix these three typos, the first 117 lines of Exhibit 1 decode properly, then go astray again. I haven't worked on figuring out what the next typo is.

Eventually we should make a verified copy of the Exhibit 1 plain and cipher texts available, so that others won't need to toil through this.

Filed under: Cryptography 3 Comments
10Jul/101

Progress on Exhibit 1

Okay, I think I've figured out the problem with my code that back propagates cipher wheels to the beginning of the code, and ran it on Exhibit 1 again. It actually matches 603 characters of input, then stalls, after searching 1.8 billion cipher encoding possibilities. I am now trying to figure out if it is a typo in the original, or some slim bug that causes it to go awry.

Because others might be pursuing their own solution of this issue, I'll hold off on publishing the key that I've recovered for a bit longer. If anyone needs it, let me know, and I'll send you the spoiler.

Addendum: There is a typo in the version of the cipher text that I downloaded from the Chaoscipher clearing house. I'll write up more when I've learned more.

Addendum2: More than one transcription error. More later.

Filed under: Cryptography 1 Comment
9Jul/100

More on Chaocipher…

Well, I didn't have much time left to work on Chaocipher last night, so I left it running on Exhibit 1. It claimed to recover a key that allowed it to match 601 characters of input, but found no better match. But it also uncovered an error in my code. It doesn't appear that the code that I wrote to rewind the machine to find the initial settings are quite right. For instance, if I use the cipher wheel and plain wheel both set to ABCDEFGHIJKLMNOPQRSTUVWXYZ, and then encode a test message (like the first paragraph of Moshe's announcement of the publication of the algorithm of the Chaocipher) then I get the following cipher text:

NHLBP ULNFR XRNDL IZRDO IWZSY HQCUQ XFSDE QGMPG RFUIR FQETN
ZTTXI YQJJN FHFYN WWQTO SXEKX DKCXP OKOAH FPCKI XQFYF UQVMA
JFKSN LGOTY KTNQJ ZNFXV ULYNO YRZQY ORVJV RUWUH HMAZA LVSIS
IGLJB QAZPK NJZXO YZHPK EMBCS XGKGY YTUET VSJWK WPXKC OCYRH
CNGVU RUPYZ AAFQE 

which decodes to:

NINET YTWOY EARSA FTERI TSINV ENTIO NFIFT YSEVE NYEAR SAFTE
RCHAL LENGE MESSA GESWE REPUB LISHE DANDA FTERM ANYCR YPTAN
ALYTI CRESE ARCHE RSUNS UCCES SFULL YTRIE DTOSO LVETH ESECH
ALLEN GEMES SAGES JOHNF BYRNE SCHAO CIPHE RALGO RITHM CANFI
NALLY BEREV EALED 

When I run my solver though, it recovers:

found a solution that exhausted the input.
NPQRSTUVWXYZAOBCDEFGHIJKLM OPRSTUVW?Y?AB?CDEFGHIJ?LMN

Which is close, but no cigar. I'm not awake enough to spot my mistake yet, and it seems unlikely that I'll get a chance to fix my error for the next few days, but I'll try to get an hour to track down my mistake. I do think I'm 90% of the way there to recovering the key for Exhibit 1. I'm pretty confident that the solver gets the right answer, but that it is rewinding very slightly incorrectly.

Addendum: Ah, it appears I'm not quite rewinding the very last character properly. The key that I recovered is actually good for decoding, as long as you start from the second character. I've written this in an overly clever way. If I use my recovered key from Exhibit 1, but start at the second letter, I get something pretty reasonable:

LLGOO DQQUI CKBRO WNFOX ESJUM POVER LAZYD OGTOS AVETH EIRPA
RTYWA LLGOO DQQUI CKBRO WNFOX ESJUM POVER LAZYD OGTOS AVETH
EIRPA RTYWA LLGOO DQQUI CKBRO WNFOX ESJUM POVER LAZYD OGTOS
AVETH EIRPA RTYWA LLGOO DQQUI CKBRO WNFOX ESJUM POVER LAZYD
OGTOS AVETH EIRPA RTYWA LLGOO DQQUI CKBRO WNFOX ESJUM POVER
LAZYD OGTOS AVETH EIRPA RTYWA LLGOO DQQUI CKBRO WNFOX ESJUM
POVER LAZYD OGTOS AVETH EIRPA RTYWA LLGOO DQQUI CKBRO WNFOX
ESJUM POVER LAZYD OGTOS AVETH EIRPA RTYWA LLGOO DQQUI CKBRO
WNFOX ESJUM POVER LAZYD OGTOS AVETH EIRPA RTYWA LLGOO DQQUI
CKBRO WNFOX ESJUM POVER LAZYD OGTOS AVETH EIRPA RTYWA LLGOO
DQQUI CKBRO WNFOX ESJUM POVER LAZYD OGTOS AVETH EIRPA RTYWA
LLGOO DQQUI CKBRO WNFOX ESJUM POVER LAZYD OGTOS AVETH EIRPA
RTGWA DLGOO SLLIV FCRBY MHAWQ GNMSN DNCKG ZYPML AYNZL FNDOW
GBJUI XZLDT NOJMT USZGI KMLCW NCKKO UICAY KSJJS SKFRG LLPUX
AOXSB XAPQE CJSUS FLFTZ LNQSS WNZNT KSDGJ UUQCG QCDDW PDINF
ZODLM JEXVW IFFWT EFPSZ KUATX VTKLF ZLHMV ICVDP MEZPY CULXV
AXNEA YRSLB BMITU JGIIT SPIQU MUMCF WFPOS YYAWE YCKYZ QUVJB
OIIUF BHXTQ FHKSE MWDBT SNJYG NIKJQ HJRRD CGCXM INUQZ GITGH
TINWU ZWFXH JEWMQ DCXNB XKGYQ DDNGI AXNYR CRAMK COAIV LKLFS
NVGWS QYOAO YUUWY OQACS UDFFK YXPJG TBPSZ TONZC ZPDMM OORNE
VZZVA HBUPV OCUJA HCGZS LVUYI LIDGY AOOXT YDDAL JDLOU LRNQA
SEZWB XPSVL EMYZT HMVAB HCIIY VHIUJ QBAUR GZEIA RUILN ZEDYB

But that predictably goes astray after (presumably) 601 characters. Not sure if the remaining issue is mine or not.

Oh well, enough for today.

Filed under: Cryptography No Comments
8Jul/102

Progress on the Chaocipher…

My brain has got a bug now. It's called Chaocipher.

Despite the fact that I'm spending my days off with my family, I find that in my odd moments my brain keeps leaping back to Byrne's cipher. The other night I implemented the basics of key recovery using a chosen plaintext attack (if you have both plain and cipher text, recover the key). It proceeds according to the following idea: initialize a Chaocipher machine with all '?' in every entry. Then, for every cipher/plaintext pair, check to see if the cipher or the plain text letter has already been placed in the wheel. If it has, then they better be in the same slot in each of the respective wheels. If they aren't, then the placement is bad, and you need to backtrack. If only one has been placed opposite a '?', then you fill in the '?' and proceed to the next pair. If neither has been placed, then you have to try all places where two '?' are opposite one another. If you manage to exhaust the input, then you probably have the right wheel, so I then run the machine in reverse back to the beginning to recover the initial key settings.

I've had some success on this with some of my own test cases, but have not managed to crack Exhibit 1 or Exhibit 2 on the Chaocipher Clearing House website. I'm not sure if this is due to problems in my own implementation or a more general problem. I haven't worked on trying to generalize this into a cipher-text only cracking program, but I suspect that it's possible. The techniques that I remember from cracking the Enigma don't really apply here, since the permutations are dependent on the plaintext. I have a couple of ideas that I'll be pondering during the three plus hours of driving that I am going to do today.

I left the solver working on Exhibit 2. It's searched about a billion keys in the five minutes or so I've had it running: we'll see if it can solve the cipher by the time I get back tonight.

Addendum: it searched about 20 billion nodes, before returning a partial key that properly recovers the first 51 characters of the plaintext. Not sure if there is a problem in my implementation or in the transcript of Exhibit 2. I'll think about it more over the next few days.

Filed under: Cryptography 2 Comments
6Jul/103

Visual Inspection of Chaocipher Output Implies Weakness

So, first thing this morning, before I had even had coffee or blinked the sleep from my eyes, I decided to try a chosen plaintext attack against Chaocipher. I created a file consisting entirely of 2000 A's, and passed it through Chaocipher.
Here is my output:

PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV
ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK
LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC
UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS
DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX
HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM
AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE
PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV
ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK
LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC
UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS
DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX
HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM
AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE
PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV
ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK
LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC
UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS
DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX
HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM
AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE
PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV
ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK
LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC
UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS
DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX
HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM
AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE
PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV
ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK
LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC
UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS
DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX
HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM
AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE
PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV
ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK
LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS DMAVZ CUXHE PKLSD MAVZC
UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX HEPKL SDMAV ZCUXH EPKLS
DMAVZ CUXHE PKLSD MAVZC UXHEP KLSDM AVZCU XHEPK LSDMA VZCUX

If you stare at it a second, you see that it's periodic with a very short period (13 14 (thanks Moshe, for pointing this out, I was doing this before coffee) characters). That can't be good, and is in fact much weaker than Enigma, whose periodicity is at least around 26^3 (a bit less, because of the odd way in which the rotors increment), and even longer with the Stecker in place that isn't modified by the Stecker, which is entirely a static table (don't know what I was thinking when I wrote that). Enigma is sensitive (and was in fact routinely cracked using the Bombe) using cribs, which are merely short versions of the chosen plaintext attack. I'll ponder this some more.

Filed under: Cryptography 3 Comments
5Jul/102

An Implementation of Byrnes’ Chaocipher

Okay, insomnia got me, so I went ahead and implemented it in Python. It appears to work reasonably well, at least it successfully deciphers their test message. You can specify the key by specifying the -c and -p options, which are the settings for the cipher and plain wheels. You should pass a permutation of the uppercase letters as arguments to those if you want to use other than the default key, which matches Rubin's example.

#!/usr/bin/env python
#
#       _                      _       _               
#   ___| |__   __ _  ___   ___(_)_ __ | |__   ___ _ __ 
#  / __| '_ \ / _` |/ _ \ / __| | '_ \| '_ \ / _ \ '__|
# | (__| | | | (_| | (_) | (__| | |_) | | | |  __/ |   
#  \___|_| |_|\__,_|\___/ \___|_| .__/|_| |_|\___|_|   
#                               |_|                    
# An implementation of John Byrnes' Chaocipher as described in papers
# by Moshe Rubin.
# 
# Written by Mark VandeWettering <mvandewettering@gmail.com>
# No rights are reserved.  No warranties are implied.
#

import sys
import random
import string
import optparse

p = optparse.OptionParser()
p.add_option("-d", "--decrypt", action="store_true", dest="decrypt",
	default=False, help="decrypt instead of encrypt")
p.add_option("-p", "--pwheel", dest="pw",
	default="PTLNBQDEOYSFAVZKGJRIHWXUMC",
	help="plaintext wheel setting")
p.add_option("-c", "--cwheel", dest="cw",
	default="HXUCZVAMDSLKPEFJRIGTWOBNYQ",
	help="cipher wheel setting")

opts, args = p.parse_args()

# initialize the code machine...

cnt = 0 

def output(c):
    global cnt
    sys.stdout.write(c)
    cnt = cnt + 1 
    if cnt % 50 == 0:
	sys.stdout.write('\n')
	cnt = 0
    elif cnt % 5 == 0:
	sys.stdout.write(' ')

	
class Machine:
    def __init__(self, cw, pw):
	self.cw = cw 		# cipher wheel
 	self.pw = pw 		# plaintext wheel
	pass
    def twizzle(self, idx):
	self.cw = self.cw[idx:] + self.cw[0:idx]
	self.cw = list(self.cw[0]) + \
		  self.cw[2:14] + \
		  list(self.cw[1]) + \
		  self.cw[14:]
	# and the plaintext wheel
	self.pw = self.pw[idx:] + self.pw[0:idx]
	self.pw = self.pw[1:] + list(self.pw[0])
	self.pw = self.pw[0:2] + \
		  self.pw[3:14] + \
		  list(self.pw[2]) + \
		  self.pw[14:]
    def encrypt(self, d):
	# find where it is in the plain text wheel...
        idx = self.pw.index(d)
	r = self.cw[idx]
	self.twizzle(idx)
	return r
    def decrypt(self, d):
	idx = self.cw.index(d)
	r = self.pw[idx]
	self.twizzle(idx)
	return r 

random.seed(0)
machine = Machine(list(opts.cw), list(opts.pw))

for arg in args:
    try:
	data = open(arg).read()
    except IOError, msg:
	print >> sys.stderr, "%s: %s" % (arg, msg)
	print >> sys.stderr, "continuing..."
    data = data.upper()
    # filter out all the non alpha characters...
    data = filter(lambda x : x in string.uppercase, data)
    if opts.decrypt:
	for d in data:
	    output(machine.decrypt(d))
    else:
	for d in data:
	    output(machine.encrypt(d))
    print

Addendum: Here is some cipher text that you can decode with the above program (or your own implementation):

TLMAG OONSK JBJYB QVGDQ CDUNW NMZPL OYCWP CWKWQ RBOYA DSLQB
KYCDG XJOLO NKTTL RUZZJ QGJBQ NRQHQ RREUI YIDHZ OMVWZ MVYUF
QOGSN NUVYT JGQPS QTBRW FHLTC LVVBP MYYQV 
Filed under: Cryptography 2 Comments
5Jul/100

The Chaocipher revealed! from Cipher Mysteries

Stumbling back through articles in Slashdot, I found a pretty nifty article on one of my favorite subjects: historical cryptography. The story goes that back in 1918, a cipher system/machine was invented by John F. Byrne. Rumor says that it was very strong, and yet could be implemented using a mechanism that would fit in a cigar box. The details of this invention were never publicly released. However, recently the widow of Bryne's son, John Byrnes Jr., has decided to donate his notes to the National Cryptological Museum, and the first publications are beginning to trickle out. Moshe Rubin has a new paper that details the working of the algorithm in sufficient detail that it should be possible to write an implementation in whatever language you like for experimentation. It's too late for me to start today, but expect a Python reference implementation in the next few days:

The Chaocipher revealed! | Cipher Mysteries.

A cursory glance over the implementation suggests that the key space is basically 26! * 26! or about:

162,644,002,617,632,464,507,038,883,409,628,607,021,056,000,000,000,000

By comparison, the German Army Enigma (three rotors) had a keyspace of only 562,064,881,159,999,426,560, and the Navy Enigma a keyspace which was only 1000x larger. So if all things were equal, we might expect that the Chaocipher was a lot harder to crack. But all things are probably not equal. I'll be pondering this over the next few days.

Filed under: Cryptography No Comments