CSE Puzzle Challenge - Puzzle 4 - Solution

Claude parked his unicycle in front of his office at the Bell Laboratory building. Arriving at his desk, he saw that Richard had left him a note. Was he trying to convince Claude that the answer to the universe was 74 again?

No... it was some kind of riddle attached to a transmission printout:

Claude!
I've left you an "error message" that can be retrieved using some of my latest research.
Don't be fooled! What appears right might be wrong! What appears wrong... might be something you can make right!
Think you can decipher it?
-RH

 

"ppdpddd! of course I can!" thought Claude.

He was already off to a brilliant start.

Printout:

00000000  90 58 8f 61 e5 d7 20 dd  8f f8 71 3b 91 62 1e 9c  |.X.a.. ...q;.b..|
00000010  70 a5 f0 67 84 c9 87 b4  10 19 da e6 5d 0d e8 ae  |p..g........]...|
00000020  02 21 ee 3d d9 e7 d5 79  81 62 bf 0f 71 4e c8 51  |.!.=...y.b..qN.Q|
00000030  66 81 9e 5e 64 da 13 69  32 5d 12 04 d6 b8 a6 49  |f..^d..i2].....I|
00000040  89 4c f5 c2 a0 3c cd c1  79 dd db cf a7 44 0a 7c  |.L...<..y....D.||
00000050  24 c0 e7 a8 c5 97 82 6d  b9 fa ab 0c b8 16 c9 33  |$......m.......3|
00000060  f3 e4 00 f3 36 fc e6 12  aa 4d 35 71 03 f1 c7 40  |....6....M5q...@|
00000070  4d ef 27 ec 46 51 cf 30  b8 44 f0 71 a3 e2 db 9e  |M.'.FQ.0.D.q....|
00000080  28 d0 6b a1 b6                                    |(.k..|
00000085

 

 

Solution

This puzzle can be a little tricky if you don't pay close attention to some of the subtle hints provided. The names and laboratory in this refer to Claude Shannon and Richard Hamming, two mathematicians who shared an office at Bell Telephone Laboratories in the 1940s and 1950s, during which time Hamming devised what are now referred to as Hamming codes, which is how this message is encoded.

This Wikipedia article on how Hamming codes work will be instrumental in solving this puzzle: https://en.wikipedia.org/wiki/Hamming(7,4)

  1. To get started, let's take a look at the hints provided in the first few paragraphs.
    1. "Was he trying to convince Claude that the answer to the universe was 74 again"
      1. This subtle hint tells us that the Hamming encoding in this puzzle is Hamming(7,4), where every 4 bits of data has three parity bits associated with it.
    2. "What appears right might be wrong! What appears wrong... might be something you can make right!"
      1. This suggests that codes that have no parity errors are, in fact, useless to us, but the ones with errors, when corrected, may provide some indispensible information
    3. "'ppdpddd'"
      1. At first glance, this appears to be a gibberish statement which makes no logical sense, however, is how the message bits, and the parity bits are mixed together, and provide a vital clue as to what our parity-check matrix should look like:

      2. ppdpddd represents the following in a 7-bit binary number:
        parity_1, parity_2, data_1, parity_3, data_2, data_3, data_4
        So, for example, if our number was 0010111, the actual message wuld be 1111.
      3. Bearing this in mind, we can create a parity-check matrix (or H) for this message. The above Wikipedia article provides details on how to devise this matrix.
      With these hints in mind, you can create a script that will check the message at a binary level for parity errors. We will go over this in step 3.

 

2. In order for a script to accurately decipher the riddle, the encoded hexadecimal values must be extracted into their own file, and saved in UTF-7 format. A good tool that can, among other things, convert Hex to UTF-7 and then save it as a file is CyberChef, a free utility provided by the Government Communications Headquarters in the United Kingdom.: https://gchq.github.io/CyberChef

 

3. You can now create a script that groups that reads the message from this file into 7-bit words, and collect and correct all words with errors, then outputs the recovered data. A script that already processes the Hamming codes can be found here:

#!/usr/bin/python3

import sys
import numpy
import binascii
import bitstring


def decode(path):
    '''
    Converts the binary file at the path to a string of 1's and 0's representing the binary code.
    Words are parsed, checked, and the data is extracted 7 'bits' at a time.
    '''
    encoded = bitstring.Bits(filename=path).bin
    output = bitstring.BitArray()
    for i in range(0, len(encoded), 7):
        word = encoded[i:i + 7]
        syndrome = get_syndrome(word)
        if syndrome != 0:
            corrected = error_correct(word, syndrome)
            output.append(bitstring.Bits(bin=extract_data_from_word(corrected)))

    return binascii.unhexlify(output.hex).decode('utf-8', 'replace')


def string_of_binary_to_numpyarray(string_of_binary):
    '''Converts string of characters representing binary digits to numpy array of unsigned 1-byte integers'''
    return numpy.fromstring(string_of_binary, 'u1') - ord('0')


def get_syndrome(word):
    '''Calculates the syndrome of the word using the parity-check matrix h'''
    h = numpy.array([
        [0, 0, 0, 1, 1, 1, 1],
        [0, 1, 1, 0, 0, 1, 1],
        [1, 0, 1, 0, 1, 0, 1]
    ])
    numpyword = string_of_binary_to_numpyarray(word)        # the word must be converted to numpy array first
    syndrome = numpy.dot(h, numpyword) % 2                  # produces a vector of 3 digits
    syndrome_str = "".join([str(x) for x in syndrome])
    return int(syndrome_str, 2)


def error_correct(word, syndrome):
    '''In order to correct the single bit error detected by the syndrome, the bit at index syndrome - 1 is flipped'''
    word_list = list(word)
    word_list[syndrome - 1] = '0' if word_list[syndrome - 1] == '1' else '1'

    return "".join(word_list)


def extract_data_from_word(word):
    '''The encoding scheme for hamming[7,4] is ppdpddd or indices 2,4,5, and 6'''
    return "%s%s%s%s" % (word[2], word[4], word[5], word[6])


'''
Decodes from binary file passed as commandline argument
'''
if len(sys.argv) < 2:
    print("Usage: solution.py ")
else:
    print(decode(sys.argv[1]))

 

4. Now that you have your script, try running it on both the English and French versions of the riddle, and you should see the secret message that Richard left for Claude to decipher:

 

Enjoy solving puzzles? Make a career out of it!