Haymarket – Boston Key Party 2015

I took part in this year’s BkP CTF. In contrast to lots of other CTFs, it wasn’t massively DoSed and was responsive for most of the time. It also had *lots* of challenges, and they were mostly tricky.

The Challenge

So, onto the problem. You were given 32 images that looked like this:

The first image in the series for the puzzle
The first image in the series for the puzzle

and an accompanying description that read:

Monty Hall wrote a script of how he was supposed to run one of his game shows for his trusty accounting computer some time ago, but he’s not really sure what the punch-cards mean any more. I mean, that was a while ago. Only, he’s sure his key is hidden somewhere in these punch-cards, if he could figure out how to run them…

 

By this description, you may loosely infer that what you’re looking at is : a) machine generated, b) old, c) probably called a punch-card and d) it contains the key, in some form. I didn’t know who Monty Hall was, but it turns out he was famous. More importantly he’s also got a really interesting and counter-intuitive problem named after himself!

The young among you will probably not know what this is or what purpose it served, while others might have a vague notion of it. I did not know the exact model, but after some digging it turns out that this is a DEC-029, made by IBM. The Columbia University Computing History has a really interesting page for those who can’t imagine what it was to program old computers (a bit painful from what I hear) that didn’t even do floppy drives.

So it is a DEC-029 punch-card. It is straightforward to read, but if you don’t have a machine to read all 32 of them then it will be inefficient and *really* irritating. Keeping true to being lazy, I obviously went for a coding solution. I tried doing half the first punch-card and it took me about 30 minutes, so no.

The plan

I thought to myself “Punch-cards were the status quo, there must be a punch-card to text OCR-ish website somewhere. After all people do like their retro geek stuff”, but I couldn’t find one (actually I did, but it only translated punch-cards that it had generated). I kind of feel like the person who set the challenge knew about this.

I came up with a cunning plan. I would code a program that read the punch-cards, extract each character and then spit out the result into a file. After thinking about this (obvious) solution for a while, it became evident that it would involve too much effort, as I would have needed to read each column, extract the “punched” positions and look those up against a mapping that I would have somehow managed to create. Or would I?

I came across this website, Kloth.net, which generated DEC-029 punch-cards for any given string and it also had a list of valid characters for the DEC-029. After having generated a punch-card for all the valid characters, I couldn’t help but notice that the generated punch-card and the challenge cards looked alarmingly similar:

DEC-029 punch-card, with the complete supported character set.
DEC-029 punch-card, with the complete supported character set.

Running both images through pnginfo also indicated similarities between the two. This mapping is probably the one to go with, and probably one step closer to the solution.

The implementation

To avoid doing all the heavy lifting concerned with image processing in my program, I thought I’d be better off using existing code. I figured out that it would be enough to extract each column from each image, take its MD5 hash and compare it with known values in order to translate that into a letter.

Step 1: Transform the images

For this task I used pngcrush, gimp and convert. I figured out that this would be easier if I cropped the areas around the centre, as the margins on the side contain no meaningful information. I identified the borders with gimp and then extracted the centre with convert. This is not the most elegant code, but the code below basically cuts the inner (target) area, removes excess information and takes the hash of every column, storing it in a file.

#!/bin/bash
#this script crops the punch-cards into strips 

if [ ! -e processed ]; then
    mkdir -f processed;
fi
for i in *.png; do
    # make images grayscale to remove all color information
    # and crop to target area
    convert $i -colorspace Gray -crop 560x230+15+20 +repage processed/auto.$i;
done
cd processed/ # cleanup old
: > sums.txt #  data here
rm -rf L*/
i=0;
for j in {1..32};
    do mkdir L$j/;
    i=0;
    while [ $i -lt 79 ];do
        # extract each column
        convert auto.L$j.png -crop 7x230+$(($i*7)) +repage L$j/auto.L$j.let$i.full.png
        # remove unnecessary information
        pngcrush L$j/auto.L$j.let$i.full.png L$j/auto.L$j.let$i.png 1>&/dev/null
        # get its hash
        md5sum L$j/auto.L$j.let$i.png >> sums.txt
        i=$[$i+1]
    done
done
find ./ -type f -name '*.full.png' -exec rm {} \;  #cleanup the old images

After this script was run, it would take the first punch-card through the following transformation changes:

Cropped image, ready for extracting each column.
Cropped image, ready for extracting each column.

and subsequently would extract each column, as shown below:

Stripped columns from the punch-card.
Stripped columns from the punch-card.

The hashes would then be extracted from each of the above images, for a total of 2,497 characters.

Step 2: Create a mapping

This, sadly, I didn’t manage do automatically. I processed the image of the dictionary I generated exactly as the original images, but I couldn’t get the hashes of identical letters to match. The script below was used to extract a collection of unique hashes along with the filenames of the files they belong to, in order to create the hash-to-character mapping.

#!/bin/bash
#get unique sums
cat sums.txt | cut -d' ' -f1 | sort -u > uniq_sums.txt
for i in $(cat uniq_sums.txt);do
    # save hash to file-name, to extract the letter manually.
    grep $i sums.txt | head -n 1
done
#generate a python-style dictionary, after having done the mapping manually.
cat mappings_letter.txt | awk '{print $1":"$3}' | sed -e "s/^/'/g" -e "s/:/':'/" -e "s/$/',/g" -e 's/SPACE/ /' | grep -v -e ":''," | tr -d '\n'

And now, I was ready to read the punch-cards, after some python! The script below translated the hashes in sums.txt to letters:

#!/usr/bin/python
mapping = {
// big dictionary here
}
fp = open('sums.txt','r')
ans = ''
for line in fp.readlines():
    md5sum = line.split('  ')[0]
    if md5sum in mapping:
        ans += mapping[md5sum]
    else:
        print 'UKNWN : '+md5sum
print ans

The resulting text was a COBOL program. Yes, you did read COBOL; I have never touched COBOL, I was only aware that it was an old language with quirky syntax. After fixing the program up (using this handy reference), I still failed to make it compile. However, it did reveal an interesting part of the program!

#sorry, wordpress has no COBOL syntax highlighting
DISPLAY 'MH: CONGRATULATIONS! YOU FOUND A KEY.'
DISPLAY   'MH: THE KEY IS:'
DISPLAY 'KEY SETALEXTREBEKISASOCIALENGINEER)'

Success

I was pretty tired by this point, so I needed some help. Thankfully, Skybound and Luxx came to the rescue. I tried submitting SETALEXTREBEKISASOCIALENGINEER, SETALEXTREBEKISASOCIALENGINEER) and even ALEXTREBEKISASOCIALENGINEER), but none worked. Skybound and I managed to get the COBOL to compile, but Luxx submitted ALEXTREBEKISASOCIALENGINEER and we got the 150 points.

I think that this was a fun, somewhat cryptic challenge. I can’t say I got all the references to Alex Trebek or Monty Hall, but at least we got the points and some interesting time.

Advertisements
Haymarket – Boston Key Party 2015

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s