Looking Out To Sea

We are on our way to a Burns supper in Morningside this evening, though I feel unsure about the whole proceedings. 

Last year we went straight from a Sunday night roda to the Burns supper and generally felt great. Through some freak event I was the only fellow to wear a kilt and so was “volunteered” to give the toast to the lassies.

This year I feel much worse. I am not sure if this is medical problems, the effects of being back on a full dose of medication, work stress, the weather and travel, Helen’s studies or a grand mixtur of them all, but I will not be wearing a kilt this evening.

Out of the three capoeira classes since the beginning of the year I have missed two from injury. I need to feel more alive.

I’ve recently started commuting to work by bike which is both more enjoyable than walking and gets me there quicker. There are a few downsides but they’re small enough that I’m going to continue like this until the weather really forces me off the road.

I was initially quite afraid of the ride through the centre of Glasgow. There are lots of one-way streets, really steep hills and traffic lights. I was even contemplating leaving the bike at the station overnight and commuting through town by subway. But a few more days of the inner-city commute set me at ease. It can be a bit daunting but I know the route now, and I know the tricky points and where to position myself so I’m not trapped by buses and so on.

The train is also good. There’s a bike carriage on every train with six hooks to hang bikes. The biggest problem is caused by station staff who create deliberate bottlenecks (!) on the platform ends during peak commuter times, which cause all the following trains to be late. I honestly can’t believe it’s more worth their while to start off the day behind schedule than to just employ enough conductors for the trains.

My work isn’t the most cycle-friendly environment. There’s nowhere particular to chain up a bike, so mine gets tied to the banister at the foot of a stairwell, next to the mops and Slippery Surface signs. Classy! There’s also no shower/changing facilities and the toilets are a bit of an offence to hygiene, so things could be better. But then who puts an office in an industrial estate in the middle of nowhere anyway?

My next steps are to get some panniers for the bike, to reduce the need for a rucksack (which just makes cycling hotter and sweatier) and get more familiar with maintaining my trusty steed. I would have said “I can probably pump up the tyres without assistance” but since the front inner-tube was involved in a “rapid deflation event” last time I tried to pump it up maybe that’s not true! If I suffer a puncture en route I just have to walk it to my destination as I don’t have the immediate skills or materials to patch things up.

In 1953 when Crick and Watson announced their results on the structure of DNA, the following phrase was used to conclude the results:

It has not escaped our notice that the specific pairing we have postulated immediately suggests a possible copying mechanism for the genetic material.

I recently saw Tim Berners-Lee’s message revealing the work he’d been doing at CERN on something he called WorldWideWeb:

This project is experimental and of course comes without any warranty whatsoever. However, it could start a revolution in information access. We are currently using WWW for user support at CERN. We would be very interested in comments from anyone trying WWW, and especially those making other data available, as part of a truly world-wide web.

Any other interesting but understated announcements of revolutionary discoveries or inventions?

During this period of tedious and unfruitful job applications I’ve come to the conclusion that I’m either a horrible person on paper (I refuse to believe I’m a horrible person in real life) or I need more experience in the object-oriented managed-runtime languages. To wit, Java and C#.

The Java language has failed to get its act together in the last few years and, at least on paper, I have some experience with it since all my university work used Java. (I’m also watching Nick’s updates to remind myself. An RSS feed attached to his bitbucket account makes him dead easy to stalk learn from.) So I thought I’d get myself some experience in C#. I’ve nabbed a project that Mat made a couple of years ago (a game of Thud! from the Terry Pratchett novel of the name, itself based on a Norse board game) and, with his permission, I’m going to whip it into shape.

I know for a fact that it runs fine in Mono, since I knew that two years ago when he first knocked it out, and Mono has come on a long way since then. At the moment it doesn’t do very much and Mat admits that it isn’t great code on the inside either. That’s all fine by me though. I can familiarise myself with the code base by cleaning it up before I decide where the new features need to go.

I hope to keep this and ComicBake going alongside each other, since there are a number of differences besides the subject matter:

1. Thud! doesn’t have to think much for itself. The program pits two users against each other across the network, so there’s no AI involved. The set of valid moves is very small so the game logic is not tricky. ComicBake, on the other hand, is me trying to encode a set of heuristics to simulate what an artist would do in the same situation.
2. One is old-fashioned imperative code, in the object-oriented style. It’s fairly staid C# too, not using many of the recent innovations of the language which make it differ nowadays from Java. The other is obviously purely-functional Haskell: higher-order, expressively-typed and immutable.
3. I can update and release ComicBake when I like. I haven’t checked with Mat whether he’s happy for me to publish the code/changes or whether he wants it just “between friends”. It can just be a learning experience, though obviously it’s a better one if I can point potential employers to it and say look, I can code.

The title is a reference to this Daily WTF classic.

NB: I wrote this some time ago. I didn’t get through to the next round of interview.

I just spent the last ~24 hours writing the biggest chunk of PHP I’ve ever had to work with. This isn’t much of a record, as up until now I’ve never done any PHP/web work outside of the occasional excursion into the WordPress plugins to debug problems. So I went from no PHP experience to writing a simple web app, which gave me quite a feeling of accomplishment.

This was all part of an interview for IDE Group. A fortnight ago I went for an interview, and then they sent me a problem to code the solution for. The problem involved setting up a database for users and related data, querying and updating it via web forms and so on.

Since this was the first time I’d ever done something like this (ie web programming) it was a massive learning experience. Every few steps I rediscovered things, like the need for session management, or data validation procedures, or authentication processes, and so on. There were many many things that I just had to skip over for being too cumbersome to implement quickly — a proper DB schema with validating constraints rather than a jumbled mess, salted-hashed passwords in the database, web pages that conform to any standard, never mind a recent one. The list goes on.

But I tried to get the basics done. I specifically wanted to concentrate on security of the application, since that’s something which is important for the integrity of the application. I didn’t want Little Bobby Tables to make a mess of my database. To that end I was really limiting in what counted as a valid username/password character. I didn’t know how to properly validate password data so I went the route of only accepting alphanumeric sequences. Little Bobby Tables wouldn’t be able to sign up, but at least the DB should still be standing if he tries. The web page itself looked very 1994. No CSS for you!

I handed in my solution about a day after receiving the problem. I was worried that taking this long would count against me, but there was nothing I could really do about that since I didn’t have any experience in what I was doing. I spent a lot of time researching each step and a lot of time debugging because of complete unfamiliarity with the language. The problem statement suggested a couple of frameworks for “bonus points”, though I didn’t use them. I considered that learning how to set up, integrate and use two additional systems over and above what I needed to get the job done would really have killed me.

In hindsight it seems this was the wrong choice. I have since learned from the interviewer that other candidates took much longer (about 3 days in one case). My thinking at the time was that anyone who knew what they were doing would get the whole thing finished in a working day so I wanted to give myself no more than 50% over that. I didn’t want to hand in something really slick that took me a whole week longer than everybody else, so I erred on the side of speed.

In future maybe I will be less cautious about investing extra time, though maybe there won’t be a future. These programming problems don’t seem very common in the UK. Anyone else done this kind of “interview homework” problem before? I can see why they are useful but I can also imagine they would be impossible for someone in a full-time job.

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.

The first part of the Cyber Security Challenge requires you to decode a long stream of letters, numbers and symbols into something coherent. This was by far the easiest part of the challenge. The symbols look like this:

/9j/4AAQSkZJRgABAQEAYABgAAD/4QBaRXhpZgAATU0AKgAAAAgABQMBAAUAAAABAAAASgMDAAEA
AAABAAAAAFEQAAEAAAABAQAAAFERAAQAAAABAAAOxFESAAQAAAABAAAOxAAAAAAAAYagAACxj//b
AEMACAYGBwYFCAcHBwkJCAoMFA0MCwsMGRITDxQdGh8eHRocHCAkLicgIiwjHBwoNyksMDE0NDQf

This is only the first three lines — there’s 362 lines of this. The most important bit is that the last line ends in a = sign. This symbol is used for padding out messages when they are encoded in Base 64 format, so if any string has an equals symbols on the end it’s worth seeing what happens if you decode it as if it were Base64. (The truth of the matter is that by the time my mate Rich had told me about this challenge he’d already decoded the image so I didn’t do any of this stuff!)

Thankfully there are plenty of programs that will do the decoding for you, and the resulting file is a JPEG file. Brilliant:

This is XKCD comic number 538, with a subtle difference. Round the outside of the image there is an uneven dotted border. This isn’t in the original comic, and it looks irregular which suggests that it’s not just a pretty pattern but that it encodes some further information.

For the next stage I converted the image to PNG format because it was the easiest format to load and process.

The first part we need to do is load the image file and extract all the bytes from the actual image part, ignoring any metadata. The PNG file is represents a 24 bit colour image, with each component (red, green and blue) stored as an 8 bit number from 0–255. We just return the whole thing as a long list of bytes, starting at the top left and scanning left to right, top to bottom. It’s not efficient but it’s very simple to reason about because we don’t need to think about array locations.

getimage :: IO [Word8]
getimage = do
  (Right img) <- loadPNGFile "decode.png"
  getElems (imageData img)

The long list may be conceptually simple but it’s not representative of the structure of the image. Since each pixel is represented by 3 consecutive numbers we want to gather those numbers together, so we can start dealing with them as pixels. Thus we convert [r,g,b,r,g,b,r,g …] into [[r,g,b],[r,g,b],…]

splitIntoBytes = splitEvery 3

Even though each pixel can represent many colours we’re really only dealing with black and white here so we can represent each component as fully-on or fully-off. Each pixel can really be stored as boolean values like [True, False, False]. Since it’s possible that some values are not absolutely 0 or absolutely 255 I’ve divided them up the middle — anything darker than 128 is 0, and anything lighter is white.

Once each pixel is a list of booleans we can collapse that down into a single black/white value by taking the conjunction. If all values are True then the pixel is True (ie, black) otherwise False (white).

normalise = and . map (< 128)

At this stage our image is no longer a list of integers but a list of booleans. The original list had height-times-width-times-3 elements. Since we’ve collapsed all those three elements into a single value representing each pixel we now have height-times-width elements. The image is 350x175 pixels so we can split it into rows by cutting the list every 350 elements. This gives us 175 rows.

tomatrix = splitEvery 350 . map normalise . splitIntoBytes

The next stage is, I think, the most beautiful aspect of representing the image as a list of lists. We have a full image but we only want the wavy lines of pixels which make up the border. How do we extract those pixels?

The first thing to notice is that the border is not continuous. The top and bottom edges go to the edge of the screen at both sides, but the two sides don’t meet at the top or bottom. To illustrate:

#################
 
#               #
#               #
#               #
 
#################

So the first question, “where do we start and end?” is answered for us. Each segment is discrete. It was my colleague Rich which pointed out the slight gaps in the border which makes this simplification possible. If the border were complete we’d have to determine whether the corner pieces were part of both the horizontal and the vertical (like a crossword where Across and Down share letters) or not.

The second question we ask is, “which direction does the sequence go in?”. Do we go clockwise from top left, following this alphabetical sequence?

a b c d e
n       f
m       g
l k j i h

Or do we maybe scan left-to-right, ignoring gaps?

a b c d e
f       g
h       i
j k l m n

What about anticlockwise? A mixture of the above? I took the approach which seemed obvious to me, clockwise from top left, and it turned out to be correct. But interestingly the final message is repeated in part so choosing the wrong start point would not have mattered, and it would have been obvious that the output was almost right.

Each row is a list, stored in order from top to bottom. This means the top border is just the first list:

topedge = head

The bottom border is the last list, but because we’ve chosen clockwise we need to reverse the list too.

bottomedge = reverse . last

The right edge is the last element of each list, ignoring the first 3 rows and the last three rows, because as mentioned above, the side patterns are shorter. These two look slightly complicated but it’s mostly dealing with trimming the top and bottom edges off.

rightedge = reverse . drop 3  . reverse . map last . drop 3
leftedge = drop 3 . reverse . map head . drop 3

Now we can extract each edge of the border we can join them all together into our encoded message. This converts our list of lists, which is a complete picture, into a list of bits encoded in the border.

msgstream :: [[Bool]] -> [Bool]
msgstream bits = concatMap ($ bits) [topedge, rightedge, bottomedge, leftedge]

Now we have a long list of bits. And it just so happens the number of bits we have is divisible by eight! This is a good sign because binary information is typically grouped into sets of eight. For the next stage we group our list into sets of 8 bits and turn each 8 into a single number.

One of the tricky aspects about any number is that you can’t tell in advance which end to start from. You and I know that 12 is “twelve” not “twenty-one” but that’s because we know to read numbers from left to right. Computer formats have used both in the past so I wasn’t sure which one would be important to me — is the biggest number the first digit or the last digit? The actual question is, “is the leading digit the most significant bit or the least significant bit?”. I calculated both to see what would happen, and it turned out that most-significant-bit was the way to go. Thankfully, MSB and LSB are just the reverse of each other, so by implementing one we get the other for free!

msb,lsb :: [Bool] -> Int
msb = lsb . reverse
lsb = bitsToInt . map (fromIntegral . fromEnum)

We calculate least significant bit by converting all the True values to 1 and all the False values to zero, and then multiplying element-wise by a stream of powers of two. To illustrate:

  1 2 4 8 16
* 0 1 1 0 1
= 0 2 4 0 16

Then we just add that list up, so “0 1 1 0 1” is “0+2+4+0+16” or 22.

bitsToInt = sum . zipWith (*) (iterate (2*) 1)

After all that prelude we can put this segment together, dividing the image up into its matrix, extracting the bits from the border of the image, splicing them up into sets of eight and converting each 8 bits into a single number:

msgbits = map msb . splitEvery 8 . msgstream . tomatrix

Now what do we do with our numbers? Readable characters are represented internally as numbers, so it is a simple thing to convert between number and printable characters. If we convert each number to a character we get nonsense, but consistent and tantalising nonsense:

Cyrnfr sbyybj guvf yvax: uggcf://plorefrphevglpunyyratr.bet.hx/834wgc.ugzy uggcf://plorefrphevglpunyyratr.bet.hx/834wgc.ugzy

Look at those sequences “uggcf://” repeated twice. That looks so much like a web address, “https://”. If we assume that it is a web address how has it been altered? Each letter in a pair, h/u, t/g, c/p, is 13 characters apart from its partner. But the punctuation symbols aren’t any different.

This looks like the encoding called “rot13” where each character is shifted 13 characters along in the alphabet, and if we reach the end we wrap back to the start. Also, since the first letter of the nonsense message is a capital and none of the rest are it seems like case is being preserved by this encoding.

We convert back to sensible words by rot13 encoding again, since 13+13=26 so any two applications of this transformation will undo each other.

Uppercase and lowercase are treated separately but by the same process. We’re processing some character which we call c and we want to know how many characters it is away from the start of the alphabet. The letter ‘a’ (or ‘A’) is 0 characters away from the start, ‘b’ is 1 character and so on.

If we assume an infinite stream of letters “a b c … x y z a b c…” repeating the alphabet, then the Nth letter in that stream is the one which is N away from the start. The 0th letter is ‘a’, the first letter ‘b’. But if we chop the first 13 characters off this stream, so it’s “n o p … y z a b c …” then the 0th letter is ‘n’, the 1st letter ‘o’ and so on. Each offset now directly maps one letter onto its partner letter. And because the sequences of letters is endless we don’t have to worry about falling off the end. The mapping just loops back on itself:

0 1 2 3 4 5 6 ...
a b c d e f g ...
n o p q r s t ...

Thus we can find the alternate character in our pair by checking first of all how many characters our current letter is from the start, and then looking for the equivalent character in the list which has had its head chopped off. We do the same for the upper case characters and just pass through unchanged anything which isn’t upper or lower case — all the punctuation and spaces.

rot13 :: Char -> Char
rot13 c | isLower c = lowercase!!(ord c - ord 'a')
        | isUpper c = uppercase!!(ord c - ord 'A')
        | otherwise = c
  where lowercase = drop 13 $ cycle ['a'..'z']
        uppercase = map toUpper lowercase

By now I think you’re dying to know what the message says, so let’s finish up here. We decipher a message by converting each integer to a character and performing a rot13 transformation — then we print it.

decipher = putStrLn . map (rot13 . chr)
main = getimage >>= decipher . msgbits

The whole thing is pulled together so we can run it from the command line and we receive the sensible output of:

Please follow this link:
https://cybersecuritychallenge.org.uk/834jtp.html https://cybersecuritychallenge.org.uk/834jtp.html

Next time I’ll look at what happens when we follow that link, and how we complete the next phase of the challenge.

If any of this doesn’t make sense or is confusing please ask questions in the comments. If you want to look at the code in full you can read the solutions for part 1 and part 2 online at http://www.dougalstanton.net/code/cybersecurity/.

As I mentioned in my introductory post I was incredibly impressed by the easy exploratory power of the Haskell code I wrote. Writing little segments to splice, decode, convert and transform made it simple to try out different ways of getting sensible output. I had no idea when I started which way the answer would take me, but putting them together in different combinations in the interpreter was easy and provided instant feedback. (That being said, Rich kinda floored me with his ability to wrangle Excel of all things into solving this problem, though that doesn’t mean it’s the right tool for the job!) Tune in next time for more exciting cryptographic games!

For the past three and a half years I have been working on router redundancy protocols. When your router (or its upstream connection) dies for some reason you want to minimise the loss on people using the network. Ideally users should never notice loss of connection, though in the real world there will be some time delay before things are working again. The work I’ve been doing relies on having a second router which has its own connection to the local network and to the wider world. It acts as a redundant backup so that when the first one dies the second can step into its place within some short period.

When the primary router is working normally the secondary doesn’t do much. Its only role is to monitor the liveliness of the primary machine. The redundant router can often be used for other things when the primary is operating — and many times the primary acts as a redundant router for the secondary’s clients. Each provides backup for the other.

So when I found out recently that I was being made redundant I thought “great! I’ll just sit and watch other people working and take over if they burst into flames”. But it turns out that when people are redundant it’s totally different from when routers are redundant. Instead of being relied on for backup in case of failure, it means “no longer working”. Strange but true! I can see why it wouldn’t catch on very well in networking.

My last day at Cisco is this Friday (30 July). It’s been an interesting few years and provided novel experiences, silly conversations about Star Trek and given me a bit more confidence. I’m sad to be going, and though there will always be loose ends to tie up and the promise of interesting projects on the horizon, the team I’m leaving behind seems to have a glut of these at the moment. I’m also disappointed that the study group at work will continue reading SICP without me. Obviously I can read it alone but the discussion and peer support/pressure was a useful part of it.

Meanwhile, the job hunt continues. Recruitment agencies make this process at least ten times harder by hiding the employer, the industry and the specifics of the job for their own ends. I have had a few friends pass on job details, and had some telephone discussions, but no success yet. Watch this space, or one very much like it.

A few weeks ago I mentioned the idea of a study group at work, for the purpose of reading through some programming-relevant texts and discussing them. We’ve been working on Structure and Interpretation of Computer Programs (SICP) for a few weeks now. I’m enjoying it more than I expected. The exercises are mostly within grasp and I’m happy to note that I’m not being left behind intellectually. There are a few mathematical proof exercises I’ve been skipping and some of the more boring “run this computation by hand” are not worth taking to completion once you’ve seen the basic point. But mostly we’re following the exercises as planned.

Scheme is not so interesting so far. The parentheses still bug me and we haven’t got to the stage where dynamic typing has proven useful so I’m smarting from the lack of a decent type system. From what I remember when I skimmed the book in the past most of Scheme development involves creating ad hoc type systems in the runtime. :-) Many people insist that dynamic languages are good for something so hopefully this something will become apparent.

I have enjoyed several of the exercises which require rewriting recursive algorithms in an iterative style. Seeing the contrast and thinking up different routes to the end product is fun, and I’m glad we’ve got a unit test framework (SchemeUnit) to help in that regard. I tried to track down a Scheme version of QuickCheck but while one used to exist it’s disappeared off the net.

Would it be “ludicrous to think of hiring a juggler without first seeing him perform”? Raganwald has made this point in the past, with reference to professional interviews. But if someone comes to you claiming to be a yo-yo champion it would be rude to challenge them on this point.