brainwagon

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.

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 

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.

I’m not much of a soccer fan, or even a football or basketball fan anymore. If I am passionate about any sport, it would have to be baseball. But Ed Felton has a rather nice essay about not just why soccer is the way it is, but why any tweaking of the rules to more suit American audiences isn’t a very good idea. I think to a certain degree, the arguments also apply toward baseball. It’s worth noting that both soccer and baseball predate any kind of cheaply available timekeeping technology. This has probably a lot to do with why the rules are the way they are, and why soccer in particular might be enjoyed in far flung parts of the developing world.

How Not to Fix Soccer | Freedom to Tinker.

As I was driving in this morning, I entertained a train of thought that led me back to thinking about peer to peer networks. I recalled that I had seen a posting by Ed Felton some years ago about implementing a peer-to-peer networking scheme in a very few lines of Python. A few minutes of searching once I reached my desk reminded me that the name of this was TinyPTP, and that it was 15 lines of dense Python. A search of Ed’s Freedom To Tinker Website revealed nothing but dead links, but a few minutes with the Internet Wayback Machine resurrected it for our consumption:

TinyP2P

I recall that I tried to run this before, and had some difficulty, but haven’t tried again. Still, the basic idea is pretty interesting: you create a network of XMLRPC servers, whose basic functionality is to ensure that all network nodes have copies of all files. It uses the SimpleXMLRPCServer classes and some overly terse idioms to accomplish its task.

Here’s the thinking that leads me to here: I’ve been listening to a lot of stuff about the scalability of Facebook lately. Ironically, the scalability doesn’t contribute to user experience directly: no user uses very much of any of the Facebook resources. Facebook’s 60,000+ servers serve something like 200M+ users every day, so obviously each user is getting a very tiny fraction of any single server machine, a fraction so small that it could be easily subsumed by even the most tiny computing appliance. It is only the centralization which causes the need for scalability.

And, of course, a distributed architecture has the possibility of fixing a few of Facebook’s other ills, such as allowing more direct control over privacy.

So, here’s the idea: use ideas similar to the TinyPTP client to implement a distributed social network like Facebook. Implement it in a simple language like Python, and in a straightforward way (don’t be overly terse like TinyPTP). Pay attention to security, but also make it simple enough so that people can adopt it by downloading a single Python file and running it in a directory of their choosing on their machine at home.

It’s just a thought experiment at the moment. We’ll see if it gains traction in my head.

Jared Newman of PC World thinks that Apple blew it with respect to the multitasking in the iPhone:

Multitasking With iOS 4 is Horrible: Apple Blew It – PCWorld

Here’s the funny thing though: all these industry pundits keep ranting about how features of the iPhone or iPad are really terrible, and yet when polled, people who buy iPhones are overwhelmingly satisfied with their phone choice. Perhaps pundits should reconsider that they don’t understand the phone market as well as Apple does.

Newman states (correctly) that multitasking is something that has to be explicitly coded into applications. And here’s the odd thing: it would be better for the phone as a whole if most developers simply chose not to.

It’s all about battery life. If your program really doesn’t have anything to do when you aren’t staring at the screen, the iPhone will nicely not let it do anything when you shift to another process. It basically shuts down your application, perhaps storing some information so that when you re-run the program, you can go right back to where you left. Many apps are kind of lazy, and just restart the program (often displaying time wasting banners) each time, which is one of the reasons that people claim they want multitasking. For 90% of these cases, just writing the applications better would be sufficient.

But I’ll be the first to admit that there are processes which don’t fit this model, and actually do require some CPU time while the user isn’t staring at them. For instance, Google Latitude isn’t really useful on the iPhone, because it was only a web application, and therefore was really only running when you were running Safari. This kept you from informing anyone of your position if you pretty much were doing anything else. You’d like to keep your music playing. Perhaps you’d like some long downloads to complete. All good stuff.

With IOS4, Apple has given you the capability to make that happen. And yes, as a programmer you have to be explicit about that. It’s a teensy bit tedious, but frankly if you are going to make an effective app, you should really be on top of the resources that your application needs. In particular, you shouldn’t be viewing your application as necessarily so important that cutting your clients battery life unnecessarily is a virtue.

Just a quick aside about the iPhone Task Manager: in most cases, you don’t need to access it at all. Hitting the button in the task manager is just like hitting its icon on the main screen. If it is more convenient to find the application on any of your home screens, just do it that way. You will need to access it only to delete processes, and properly coded apps don’t really need to be explicitly deleted anyway: if the iPhone needs to delete an application because it runs out of memory, it will do so in a well defined way that allows you to restart the application in a consistent state.

Is iPhone multitasking amazing? No, not really. But neither is it horrible. It’s a reasonable set of design choices to ensure good user experience.

32 bit processors now cost $1. That means that you can build fairly competent video games for the price of a coffee. Check it out:

RBox: A diy 32 bit game console for the price of a latte – rossum’s posterous.

Addendum: The prototype is actually built on a small board that can be ordered from Digikey for about $30. The software is a teensy bit clever (maybe more than a teensy bit). It generates video entirely via interrupts, but the clever thing is that it uses the SPI interface on the chip in a way that allows you to generate the necessary chroma signals without overburdening the main cpu, which generates the luma part of the signal. Quite clever.

Near Space Balloon Flight, shot with HD HERO cameras from GoPro from Kevin Macko on Vimeo.

It’s good to see that 16 year old Abby Sunderland has been rescued by a French fishing vessel. She was attempting to set a world record by sailing around the world solo.

A lot of people have been commenting about how reckless, negligent, etc.. her parents were for letting someone so young attempt such a dangerous voyage. The claim is that a sixteen year old is simply incapable of comprehending the risks and the dangers involved.

I understand this concern, but I don’t share it.

Our society has become incapable of understanding risks. We tolerate the thousands who die in automobile accidents, yet when one person tries (and fails) to put a bomb in their shoes, forever after we all are forced to take off our shoes at airports. We let kids drive at 16, but they can’t vote until their are 18, and we mostly hold off drinking until age 21. And at each age, there are kids who take these new possibilities and handle then responsibly, and there are those who never become responsible at any age.

Abby comes from a family full of experienced sailors. Her brother made a similar journey at age 17. While I do not fully comprehend the compulsion that would cause someone to embark upon such an adventure, neither is it completely mystifying to me. Such a endeavor cannot help but be profoundly empowering, pushing one’s self to the limits of their endurance, resourcefulness and skill.

I’m perfectly willing to accept that Abby and her parents are better judges of what she is capable of doing than we are. By all accounts, she was well equipped, well trained, and if you take the time to read her blog, emotionally mature enough to handle a journey which would certainly cause me to question my own training and maturity at age 46.

To Abby: condolences on the loss of Wild Eyes, but it is good to hear that you are safe. Even though your record setting attempt has ended, I am sure that further adventures await you, no matter what directions you choose for yourself.

Bon voyage, and God’s speed.

French fishing boat rescues stranded Calif. teen – Yahoo! News.

Lots of amateur astronomers use Registax to do what is known as “Lucky Imaging”. The idea is that you record a bunch of video frames, and hope that you capture some moments of good seeing, which you then carefully align and average to remove noise, and then enhance. I was playing around with a sequence of 1200 frames that I found online, and in my first attempt of using this program, came up with this image of Saturn. Not bad. I keep thinking I should do some video astronomy, but never quite get around to it. Perhaps that should change.

I am always on the lookout for people who build interesting computers from scratch. Here’s another nifty one: a 4 bit CPU called the Duo 128 Elite by Jack Eisenmann. It’s a pretty obscure little architecture, but is cool enough to play pong on a 8×8 LED display.

DUO 128 Elite

As part of the “How To Make (Almost) Anything” course at MIT, David Carr designed and built a very simple 3 axis mill, that seems entirely adequate for milling PCBs and light materials. While it may not be the most precise, it’s very clever.

Nifty $90 CNC Mill, by David Carr.

I’m back again fighting the battle against my weight, cholesterol and blood pressure. As a guy who tries to be very rational and very scientific, I’m constantly looking for (and constantly frustrated) by the lack of rigorous and useful scientific data that guides me in trying to change my behavior to have a better health outcome. In doing this, I am frequently frustrated.

For instance, when I was a kid, we were warned about eating to much sugar. Sugar, it was said was the major cause of hyperactivity and tooth decay. In fact, both of those appear to be myths. Parents have been told that their kids will be more hyper when they’ve had sugar, and often apply a purely subjective standard for their children’s behavior depending upon whether they know if they’ve had sugar or not. And of course pure sugar is relatively less of a problem than starchy carbohydrates because tooth decay is primariy caused by a bacteria which feeds on sticky starch which remains stuck to teeth, which causes them to emit acids which attack tooth enamel.

By the late seventies, the blame had shifted to dietary fats. It seems logical: if you are getting fat, it’s probably, well, because you ate too much fat. So, a huge industry began which fed America based upon this wisdom: we saw the creation of larger and larger amounts of “low-fat” and “non-fat” foods, which we as Americans bought in vast quantities. And, the net result of all this was that obesity rates skyrocketed. In other words, when millions of Americans did what experts told them to do and lower their fat content, they became fatter and fatter, and dramatically so.

The Atkin “revolution” told us that much of what we learned was a lie: that in fact it wasn’t fat which made us fat, it was carbohydrates. Our new demon was bread: you could eat all the steak you wanted, as long as you didn’t eat any of that bread.

The fact of all of this is that food metabolism is very complex, and much of what people say about diet is not only incorrect, but in fact can’t possibly be correct. As a for instance, the conventional wisdom is that “a calorie is a calorie”. It doesn’t matter if you eat fats or carbs or proteins, it all doesn’t matter. If you have an excess of around 3500 calories, you will put on a pound of fat.

But this can’t possibly be true. Let’s say that it were true, and you were one of those lucky people who “hasn’t gained a pound since college” (let’s say that’s 10 years ago). That means that in the span of 3653 days (we’ll round), your total caloric intake as compared with your energy expected has to be balanced to within 3500 calories. That requires a precision of about one calorie per day. I burn a calorie in a few seconds of walking on a treadmill. Does that make any sense to anyone?

There obviously has to be more at work here.

I got on this track courtesy of Jay Parkinson’s blog. He’s an MD, and was writing about a retailer who pulled a T-shirt from their stores which carried the message “Eat Less”. He said that he thought it was a bad thing, because anorexia accounted for a mere 1% of the population, while 35% of us were obese. According to figures provided by UN FAO (and linked by Parkinson) Americans consume on average 3790 calories per day. The American Heart Association suggests that I eat between 2000 and 2400 calories as a moderately active adult male in my age group. Let’s say that my activity level burns 2200 calories per day, but that I am one of these “average” Americans. This means that I am overeating to the tune of 1590 calories per day. I should put on more than a pound every three days. If weight gain (and loss) were really as simple as Parkinson would have you believe, the real question isn’t “why can’t I seem to get thin” but rather “why aren’t we all bursting our skins?”

Someone left this link to a talk by Gary Taubes on Jay’s discussion board. I think it’s pretty interesting, and points out some of these fallacies and the likely causes. I think that if I could internalize some of the lessons, it might prove to be helpful.

Can someone (preferably somebody whose very keen on baseball, especially sabermetrics) answer me a question?

Tonight I was at the game between the Athletics and Twins in Oakland. After trailing 1-3, the A’s score twice in the bottom of the eighth inning to tie the game up going into the ninth. Danny Valencia strikes out. With nobody out, Justin Morneau replaces Brendan Harris.

Okay, here’s the question: you are in a tie game, with nobody on base. Justin Morneau is batting .376, to be followed by Nick Punto, who is batting around .200. What do you do?

The Athletics chose to intentionally walk Morneau. Sadly, they also ended up walking Punto, after they pulled Morneau for a pinch runner. Span then hits a grounder and Punto is out at second, but Span beats the throw, and we have runners at the corners with two out. Tolbert (batting about .167) pokes a shot out to center field, and the Twins score.

I can’t understand the utility of walking Morneau. Yes, he’s batting .375 or whatever, which means that over 60% of the time, he doesn’t reach base, and you then have two outs, facing Punto, Span, and Tolbert. If he singles, you are in exactly the same place you were if you intentionally walked him. So you are betting that 63% of the time making an out is less desirable than 34/191 (34 extra base hits in 191 at-bats) chance of getting an extra base hit. Sure, I haven’t quite factored in chance that you accidently walk Morneau, but I can’t help but think that the intentional walk is the wrong play.

What do others think?