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).
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:
The bottom border is the last list, but because we’ve chosen clockwise we need to reverse the list too.
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.
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!
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.
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!
