Looking Out To Sea

We’re not quite finished the festival run yet (still got something to see next Saturday) but I can’t be bothered waiting until then. Despite taking me by surprise we tackled the festival hard and got to a number of good shows, including some stuff in the — whisper it — EIF.

• Duke Special. Stuff from his new album, The Stage, A Book and the Silver Screen, with songs about the films of Hector Mann (is this a real person or just a character in a book?), a Kurt Weill musical about Huckleberry Finn (unfinished) and an anti-war Brecht play. There were a few fan favourites as well, including the terminally catchy Salvation Tambourine.

• The Penny Dreadfuls. I have no idea if this show had a name, but it was a comedy sketch show with no particular theme. In previous years they have mined the comic depths of Victoriana with sketch shows and comic plays. Last year’s show was a stand-out amongst several shining examples. This year wasn’t bad though I felt I didn’t get the same weeping pain and fear-for-my-underwear that I’ve felt in previous years.

• Miles Jupp: Fibber in the Heat (A Cricket Tale). Brilliant tale of one cricket fan’s bid to blag his way into the press box for an tour in India. I know nothing about cricket but it was still a marvellously-told and hilarious story.

• Gutted: A Revenger’s Musical. A late-night comedy musical with the Dreadfuls in supporting roles. It was fun in a slapstick farcical way. Definite Fringe material, though I don’t mean that in the worst possible way. I laughed a good deal more than at some of the stuff I’ve seen…

• Henry Rollins: Frequent Flyer Tour. I had heard a great deal said about Henry Rollins and seen one or two clips on YouTube but had no real measure of what the show would contain. It was an hour and a bit of white-knuckle anecdote and comedy. Totally recommended if you can catch his show anywhere, and from the way he talks he does about a million shows every week.

• Opera de Lyon: Porgy and Bess. A free “orchestra rehearsal” at the Festival Theatre. Sadly the singers were a bit mumbled and even the songs which I knew didn’t come across very well. The interval provided some nice insight as the conductor made some members of the cast re-do certain lines and phrases. I’m just sorry he didn’t get them to sing a bit more clearly at the same time. The dancers were amazing.

• Axis of Awesome: Songs in the Key of Awesome. Comedy musical trio with parodies and hilarious ditties, including the ever-flexible four chords…

• Caledonia. Another free preview, at the King’s Theatre this time, of the latest NTS production. This is a dark and satirical comedy about the Darien venture, Scotland’s ill-fated attempt at empire-building which led to its bankruptcy and eventual merging of parliaments with England. And what better time than now to look at the past of financial speculation and ruin, and claims that “trade begets trade, money begets money”? While enjoyable it was, I think, under-rehearsed: some slightly stumbled lines and one or two on-stage collisions between actors betrayed some lack of familiarity. Mostly this didn’t detract from the show though. Not as completely riveting as Black Watch, but then what is?

• Nofit State Circus: Tabu. Gritty, energetic circus fun with moody live band providing klezmer jollity, rock and cinematic soundscapes. I nearly laughed at the very beginning because the speaker said “it’s been raining for four years, eleven months and two days…” and behind me I could hear the popcorn machine making rain-like pop-pop-pop noises. Funny, alarming, wildly athletic and terrifyingly immediate. Catch them wherever you can. Now when are Archaos going to come back to Edinburgh…?

I’ve probably forgotten something in this list, and we’re going to an Aussie opera on Saturday, so there’ll be more to come.

When we moved to the flat we bought a biiiig television because biiiig televisions are what all the cool people have. We mostly watch DVDs on it but occasionally we use it as a useful backdrop while we watch iPlayer on Helen’s laptop, and feel slightly silly about the whole scenario.

Anyway, the telly is plugged into the hi-fi so we can turn up the audio as loud as we need without the television vibrating its minuscule speakers out of their fixings. At the time I didn’t have an adequate cable so the I had a lead plugged into the headphone socket on the television, which went to a 2-phono lead at the amplifier end. Very silly but it did the job.

I was in B&Q today and spotted the right lead for the job on my way out. When I got it home and plugged it in I discovered that all along I had been using the correct lead because the “proper” way of doing it results in stupidity.

Picture this. You’re watching telly and the adverts come on so you press “mute”. If it’s just a straightforward telly the sound goes off; if the audio is coming out the headphone socket, the sound goes off; but if the sound is going out the Audio Out socket on the back of the television the sound stays on. Yes, I know. The mute button doesn’t affect the proper audio output, only the speakers or the headphone bypass.

So, having done things properly I’ve now lost the mute function on the telly and I think I’ll reinstate the headphone-socket-kludge. Thanks Samsung, great design.

Earlier today our little SICP study group agreed to start on Chapter 3 for our next meeting. There are five chapters in total so we are past the halfway mark and it’s been pretty interesting so far. To recap the recent stuff:

• Representing data structures as functions, and data as functions. Specifically, calculating with Church numerals and simulating cons, car and cdr without built-in operations.
• Manipulation of code as data, including symbolic differentiation of simple algebraic formulae. Converting “3x²” into “6x” with relevant simplification and grouping of symbols.
• Some straight-up data structure work — ordered lists, trees, sets — and using them to implement Huffman encoding.
• Organising multiple interacting systems, in this case a generic arithmetic package which works (almost) seamlessly on integers, rationals, reals, complex numbers and finally polynomial terms. Using this as a way of discussing functional and object-oriented design and introducing the expression problem.

I can definitely say that this last section, building a multi-module (for some definition of module) system made me really miss static types. Not being able to tell where functions were defined and called with different arities, or were using different symbols, until the problem manifested at runtime, was infuriating. The book is very interesting but the language is not to my taste. :-)

For comparison, here’s Yaron Minsky talking about using Ocaml for large scale programming:

Effective ML from Yaron Minsky on Vimeo.

In case you didn’t see his comment, I just wanted to promote Andrew’s answer to my question to the front page. I had wondered why my dividing-by-two techniques had worked to find the answer to the second part of the Cyber Security Challenge. The explanation is quite obvious when written in full.

The input sequence was a series of 8 bits which had been permuted in some way. According to the published solution they had been rearranged so that the right-most bits had been looped around and pushed onto the left side:

6 7 8 1 2 3 4 5

The recommended solution was of course to take those three and move them back round to the right hand side:

1 2 3 4 5 6 7 8

My accidental solution relied on two features of the problem. First, as I said previously, the hexadecimal encoding could be reordered before decoding. Since each hex number represents 4 bits, we’re going to reorder around the middle:

6 7 8 1 : 2 3 4 5

If we swap these 4-bit sequences first, we get something which is very close to the desired sequence:

2 3 4 5 : 6 7 8 1

The next step I performed was division-by-two. In binary this is represented by shifting all the numbers one place to the right. (Think of dividing by ten normally — you just shift the decimal point one place to the left.) When we do this right-shift the right-most digit disappears, and a left-most digit is created which is always zero in our case. I’ll mark this place with a # symbol.

# 2 3 4 5 6 7 8

We’ve almost got a full understanding of the solution here, but one problem remains. My method and the official method are nearly identical, except for the left-most bit:

1 2 3 4 5 6 7 8 <-- official solution
# 2 3 4 5 6 7 8 <-- my solution

We don’t know what any of the bits 1–8 represents, but we know that # is always a zero. So my solution “works” when bit number 1 is zero. And it just so happens that ASCII, the standard way of encoding simple characters in binary, only uses the 7 bits on the right. The left bit, number 1, is always 0 for simple text encoding.

If the message had been encoded in some extended ASCII format that uses all 8 bits my method would have failed. For the general case, bit 1 is only zero half the time!

This second part of the problem was more difficult, though the solution is much shorter to present. The input message looks like this, in part:

68edcdec4e2c8eae8d2c8e2dedcd6e04d2042fedae52ceac
04ccedaecd8c042ccd8c046cedad0e8dac8eac8c048e0dac

Under the assumption that each pair of characters represents a byte, we split the stream into pairs.

splitStream = splitEvery 2

Of course each pair isn’t actually a hexadecimal number, though it looks like one. It’s a string of characters, so we need to turn it into something the computer will recognise as a number.

Now, there’s a robust, I’m-a-serious-engineer way of doing this and then there’s the way I chose, which is to prefix all the strings with “0x” and use the read routine. The Read typeclass is not meant to represent a robust parsing mechanism but since this is a one-shot thing I think we’ll both just ignore it, yeah?

hexToInt :: String -> Int
hexToInt = read . ("0x" ++) -- ouch!

Having read in our number I tried to do what I did in the previous exercise and print it out, which produced complete nonsense. Then I decided that reversing the string before converting it to numbers would be helpful. I did that, but the result was still nonsense, just of a different shade.

Then I decided that my resulting numbers were a bit large. The number which represent capital A is 65, and I was getting numbers in the 200 range. Then I realised, “all these numbers are even, aren’t they?” So I divided the whole lot by two.

Outputting that message gave me a backwards English message. Aha! It’s close but there’s something wrong. I threw in another “reverse” statement and got an answer. At this point I noticed I had two reverse statements — one at the beginning and one at the end. This seemed like it would be the cause of my problems so I removed them both and, Robert’s your father’s brother, I was back to gibberish again.

What happened? What I had failed to realise was that when I had reverse my original message I had done so before splitting into pairs of characters. So ABCD becomes DCBA. After splitting this is [DC,BA]. If each pair is converted into a printable character, represented by f(XY), then the result is [f(DC),f(BA)]. I then reversed the message to get [f(BA),f(DC)].

If I didn’t do any reversing but went through the same splitting and conversion process, I got [f(AB),f(CD)]. Look — f(AB) is not the same as f(BA)! By reversing the list before splitting and again after conversion, I was implicitly reversing the order of the characters in each pair.

Obviously I had to reverse only the pairs after they’d been split, rather than the whole list at the beginning and end. If I do this then print the result I get an answer which is close to right.

byteToChar = chr . flip div 2 . hexToInt . reverse
message = map byteToChar . splitStream
 
loadfile = (head . lines) `fmap` readFile "hexstring.txt"
main = loadfile >>= putStrLn . message

The resulting message is:

Congratulations youve found and completed the REAL challenge. Your win code is cyb3r=s3cur1ty*ch@ll3nge+26-07-2010.

Please email this code to our team at media@cybersecuritychallenge.org.uk. If youre the first person to do so, and can prove you meet the eligibility criteria (British citizen currently resident in the UK) we will be in touch to advise how to claim your prize. Well done and good luck in the Cyber Security Challenge competitions taking place throughout the rest of the year.

There are a few infelicities which are explained by the official solution. My divide-by-two technique is not the proper approach so I think some of the characters get lost in the decryption process. But as the saying goes, close enough for government work!

The solution states:

The challenge was based on a bitshift operation applied to a string, here each byte’s “3 least significant bits” have been added to the left side of the byte (making them the most significant bits respectively)

Assuming we have bits one to eight:

1 2 3 4 5 6 7 8

what I did was divide everything by two, which we do in binary by shifting everything to one side so the least significant bit disappears. We fill the opposite edge with a zero here:

0 1 2 3 4 5 6 7

What the solution demands is to rotate the bits like so:

6 7 8 1 2 3 4 5

I am still not sure how it is that my solution matches so neatly with their own. Answers on a postcard.

If I hadn’t stumbled on a solution like this, the sensible approach might have been to produce a histogram of common characters. In this case, the most commonly used character encoded the space, followed closely by “e”, the most common letter in standard English texts. From there it would have been a bit of a slog to produce the result but it could be done.

The two other solutions I have found both use the official method without problems. I suspect it’s got something to do with default word lengths (8 bit versus 32 bit) and signed integers, though I’ve not thought deeply on the issue.