GCHQ Christmas cryptography challenge 2015 (Spoiler Alert)

3 minute read

It’s that time of the year again when the guys and girls at GCHQ do their best to try to baffle our brains with their latest cunning puzzle. This year, included inside the director’s Christmas card is a grid based puzzle which can be found at the GCHQ website

If you’re having problems knowing where to start with this puzzle, or want a few clues as to how to approach solving it then read on…. Starting with the initial grid that is presented on the webpage, and having read the accompanying instruction through, the first line of attack is to complete any of the rows or columns which contain only one possible permutation. To facilitate this, add all of the numbers in any particular row or column together to give you the number of black squares in that line. Because we know that the grid square is 25x25, then we can work out how many white spaces must be on each line by subtraction, and these numbers can the be written onto the puzzle sheet, shown below in red numbers. If the number of white spaces in a row is one less than the number of black blocks in a row, then the line must be unambiguous, leading to the first step in the solution shown in figure 1.

Complete all of the unambiguous rows and columns

Stop at this stage and think ! The result of the grid square puzzle must be a web address where the rest of this year’s puzzle questions reside, so it’s more than likely that we are looking at a QR image - those funny looking patterns that you see on products and adverts that you can scan with your phone. Do a bit of research into how QR images are formatted (there is plenty of information available on the internet) and in particular have a look at QR version 2 which is comprised of a 25 x 25 matrix. On the QR version 2 standard, there are 4 control sequences embedded into the image which must be present for the QR code to function correctly, so lets have a look to see if these control blocks are present in the data presented by GCHQ.

The QR version 2 control blocks, taken from ISO 18004

Translating the control blocks into the number system used in the puzzle would mean that the first 7 rows should start 7….. then 1,1….. then 1,3,1…. then 1,3,1…then 1,3,1… then 1,1…then 7…. This is exactly correct when compared against the puzzle data, as are the other three control blocks data and the timing data lines shown in figure 2 (thats those dotted lines that connect the top left control block to the other two corner blocks). So we can now complete a lot more of the GCHQ puzzle grid using the known QR version 2 protocol, being careful NOT to mark off the redundant 7 bits shown in white on the left side of figure 2 as blank spaces, because the nasty puzzle setter at GCHQ has sneakily included superfluous data bits in this section !

Adding the QR version 2 control blocks to the puzzle (partially completed)

In order to keep control of the solution to the puzzle, you will need to mark off in the number lists at the start of each row/column the number that represents each block of black squares that you uncover by circling it, and then also mark of in the grid itself all of the known white squares that you identify as shown in figure 3. By doing this, and using logical deductions, it is possible to complete the whole of the grid and construct a fully functioning version 2 QR code which can be decoded at a wide variety of websites. Some of them will not return an answer to you and tell you that the QR image is not correctly formatted, but those that are properly written will indeed return you a valid web address at which you can find a message from ‘the director’ congratulating you on solving the first puzzle…

Updated: