CSE Puzzle Challenge - Puzzle 9 - Solution

Solution

This challenge is of particular note as it coincided with the CS Games occurring in MTL. As such it became the start of CSE’s Puzzle Hero Challenge for this event.

Stage 1:

The challenge begins with a long enciphered DNA text, followed by a set of numbers.

Starting with the numbers: Though mostly numerical there is a “C” in this grouping so first assumption is that the values are base 16. A quick trip over to GCHQ’s CyberChef and the user can determine without much effort that the values here are simply hex values of ASCII characters spelling out the name “Playfair.” Referring, of course, to the famous Playfair cipher created by Charles Wheatstone in 1845.

Playfair Cipher summary:

The traditional Playfair cipher uses a secret key to build a 5x5 matrix, this matrix is then used to encipher and decipher secret messages as follows:

Building the Matrix

The key is first entered into the matrix and the leftover spaces are filled with the remaining letters of the alphabet, excepting “J”. In the Playfair cipher “J” and “I” are considered to be the same letter. No letter in the matrix can repeat, including letters in the Key.

Example:
Key = “odyssey”
Playfair Matrix =

O

D

Y

S

E

A

B

C

F

G

H

I/J

K

L

M

N

P

Q

R

T

U

V

W

X

Z

Note: The Key is marked in red in the matrix above. Note how the repeat “Y” and “S” in the key were removed and “J” and “I” share the same square.

Enciphering the Message

The message is then taken in groups of two letters; for this reason, there must be an even number of letters in the message. Moreover, the matrix does not include lower case letters or punctuation, and these values must be removed from the original message.

Example Message: “The ships sail at midnight”

  1. Remove all punctuation. -> “Theshipssailatmidnight”
  2. Convert to uppercase -> “THESHIPSSAILATMIDNIGHT”

If the secret message was not evenly divisible by 2 an “X” would be appended to the message. The letter “X” is used as a filler because its frequency of use is much lower than most other letters. This allows it to be easily recognizable as an extra letter.

The first two letters of this message to be enciphered would be “TH”. To use the matrix for enciphering the following rules must be followed:

1. The two letters being enciphered can not be the same. If the two letters are the same the latter is replaced with an “X”

2. If the two letters are in the same row, the letter to the right of each letter are taken in order as the enciphered values. If one of these letters is the last in the row, wrap back to the beginning of the row to retrieve its enciphered value:

   So, enciphering “ES” with the above matrix would work as follows:

      E->O, S->E resulting in “OE”

3. If the two letters are in the same column the letter directly below each letter will be taken as their enciphered values. If one of the letters is at the bottom of the table, the column will be wrapped to retrieve the ciphered value.

   Enciphering “GT” with the above matrix would work as follows:

      G->M, T->Z resulting in “MZ”

4. If the two letters are in different columns and different rows, form a box with the two letters being opposing corners. Then travelling horizontally, the letter is enciphered with the opposing corner of the box.

   Enciphering “BT” with the above matrix would work as follows:

      B->G, T->P resulting in “GP”

DNA Playfair summary:

Now we have two clues to how the cipher may be put together “DNA” + “Playfair.” Doing a web search on this a few papers come up for reference we worked with this one:

https://www.researchgate.net/publication/45198045_A_DNA_and_Amino_Acids-Based_Implementation_of_Playfair_Cipher

The Playfair DNA cipher allows for the users to include all ASCII values in a message and maintain the simple 5x5 matrix. In this extended cipher messages are first converted to a 2-bit DNA representation and then the DNA sequence is then converted into an extended amino acid form. Once in amino acid form the message is enciphered with Playfair and the resulting ciphered message is converted back into DNA form using the amino acid table in reverse.

1. Convert the message to ASCII, then encode the bits:

image

2-bit DNA
A  ->  00
C  ->  01
G  ->  10
T  ->  11

example:
msg:  Hi
ASCII:  0x48 0x69
bin:  0100 1000 0110 1001
DNA:  CA GA CG GC

Note: In the next step we will convert these values to amino acids. Since an amino acid is represented by 3 DNA values, we must ensure that the message once encoded into DNA is evenly divisible by 3.
  CA (length(msg)*4)%3 = 0
If this is not valid, we need to append X’s to the original message as is done in the Playfair cipher.

2. Convert the DNA to amino acids. At this stage we group the DNA values into groups of 3 and use their equivalent amino acid to identify them. The amino acid table, however, does not include all letters of the alphabet, thus some alterations need to be made.

In this format there is a maximum of four and a minimum of one possibility for each amino acid. This adds ambiguity to the cipher, specifically an ambiguity that can be represented in 2-bits. In order for the message to be decoded we will need to include this ambiguity information in the cipher itself, so a record of this must be maintained for later.

3. Encipher the amino acids using the Playfair cipher, with a secret key (see previous section).

4. Convert the Playfair ciphered amino acids back into DNA by taking the first 3 letter DNA sequence under each amino acid represented in the message, between each 3 letter DNA sequence place the 2-bit DNA representation of the original amino acid’s ambiguity.

To decipher the message the receiver simply works this process in reverse, using every 4th letter (the ambiguity) to determine the correct DNA sequence of the amino acid.

Putting It Together

When we take these two concepts into consideration, we realize that we are missing one key piece of information, the KEY. The Playfair cipher requires a secret key so that only the intended receiver can decipher the message. For this we need to take a closer look at the image that accompanied the cipher text.

The eyes of the alien have suspicious off-coloured binary (image 1). This becomes more obvious if you can remove the green from the picture (image 2)

Given that they appear to be in vertical nibbles, from left to right they would result in the following:

0100 0100

0100 0101

0101 0011

0101 0100

0101 0010

0100 1111

0101 1001

44

45

53

54

52

4F

59

If we treat this as ascii the result is: DESTROY

Looks like we found our key.

Now we just need to write up a deciphering script. For a sample decipher python script see decipherPlayfairDNA.txt.

The result of this stage is a group of URLs


 

https://getyarn.io/yarn-clip/f64e47ba-1f1d-48d1-8300-18393c5e6afe  - There was a break in
https://getyarn.io/yarn-clip/2cabccc2-e79d-4b6c-afa2-ed286b12f6cf  - The time space continuum
https://getyarn.io/yarn-clip/028ecfaf-e3a0-46e2-b45e-6bc56abb7301  - And eventually it brought us here
https://getyarn.io/yarn-clip/b8aa94c4-6d99-4e36-8297-3631c728a61f  – This world
https://getyarn.io/yarn-clip/6015a8f6-0fe0-4465-9654-60ed138272fe  – it has
https://getyarn.io/yarn-clip/77a97fd1-8650-4ecb-9bdb-466ff79b69f5  – an abundance of mineral deposits
https://getyarn.io/yarn-clip/d3af959d-d4e2-4ae1-bf5a-8f4bd78c5768  - which makes it perfect for our needs
https://getyarn.io/yarn-clip/2e4f22dd-7838-4dbe-8be7-62ebabd6e854  - We will
https://getyarn.io/yarn-clip/eea198ca-fe9b-4f82-a7de-3fc54d181c35  - take it
https://getyarn.io/yarn-clip/1490a816-ffcd-44ed-ba3e-cf20741949d1  – resistance is futile


 

Each URL takes you to a movie/TV show clip stringing together the alien dialog.

Stage 2: But wait, there’s more!

While taking a closer look at the image we were given, something else stood out. There appears to be more information in the background.

First: In the frame we can see very faintly “CS GAMERS START HERE CS GAMERS COMMENCE ICI”

Next: In the background text there are added “.” and “_” throughout the DNA at different intervals. Hummm dots and dashes? Morse Code?

The frequency at which the underscores and dots appear seems to vary between 1 and 2 alpha characters. If we assume that two alpha characters between an underscore or dot indicate a space, we can pull the underscores and dots as follows:

Line 2:

_ .... .

THE

Line 4:

._. . ... .. ... _ ._ _. _._. .

RESISTANCE

Line 5:

_. . . _.. ...

NEEDS

Line 7:

_.__ ___ .._ ._.

YOUR

Line 9:

.... . ._.. .__.

HELP

Line 14:

_...._

-

Line 17:

_.. .. ... ... . _._. _

DISSECT

Line 18:

__

ME

Line 19:

._.. ._

LA

Line 21:

._. . ... .. ... _ ._ _. _._. .

RESISTANCE

Line 23:

_... . ... ___ .. _.

BESOIN

Line 24:

_.. .

DE

Line 25:

..._ ___ _ ._. .

VOTRE

Line 27:

._ .. _.. .

AIDE

Line 28:

_...._

-

Line 30:

_.. .. ... ... __._ .._ . _...._ __ ___ ..

DISSIQUE-MOI

Well dissecting an alien may be sticky and gross, my impression here is rather to dissect the jpg. So how do we dissect a jpeg?? With a hex editor of course!!

Small fact about jpeg and jpg files, they happen to have comment section within the binary. The comment section within this jpg contains the following:

“Use the interwoven Caesar cipher to decrypt. The last thing you heard is the key.
Decode{yxlxk://pwj.ewm-uxn.zk.ne/vr/hcrslru-ivalgxa/BAotRE5IuGSwge==}Decoder
Utilisez le chiffre Caesar entrelace pour dechiffrer. La derniere chose que vous avez entendue est la cle.”

With the lack of a decent Hex editor, this can also be found by running strings on the jpg file:

$ strings < filename >.jpg | less


 

VWb<
./7t
*m;K3
Use the interwoven Caesar cipher to decrypt. The last thing you heard is the key.
Decode{yxlxk://pwj.ewm-uxn.zk.ne/vr/hcrslru-ivalgxa/BAotRE5IuGSwge==}Decoder
Utilisez le chiffre Caesar entrelace pour dechiffrer. La derniere chose que vous avez entendue est la cle.
eGBCZ
2NQ1
/)2D


 

From here we require:

1. “the interwoven Caesar cipher”
A quick search tells us another name for an interwoven Caesar cipher is a Vigenère cipher. So, we know how its enciphered.

2. A key of “The last thing you heard”
The last URL from the DNA cipher is a clip of Geordi La Forge while the Borg are heard saying “Resistance is futile”. So, the key must be “Resistance is futile”

3. To decipher “yxlxk://pwj.ewm-uxn.zk.ne/vr/hcrslru-ivalgxa/BAotRE5IuGSwge==”

Deciphering “yxlxk://pwj.ewm-uxn.zk.ne/vr/hcrslru-ivalgxa/BAotRE5IuGSwge==”
So, it turns out that the Vigenère cipher applies only to alpha characters, so the key needs ti be adjusted from “Resistance is futile” to “Resistanceisfutile”. Reversing the Vigenère cipher in CyberChef with the now known “Resistanceisfutile” key results in the following:

https://www.cse-cst.gc.ca/en/puzzles-enigmes/QWxpZW5QbGFucw==

Paste this into the browser and we are delivered to stage 3 of the challenge.

Stage 3: At the Games

When you reach the this stage the resistance gives you two files and the following message:

“Some of our agents were able to capture transmissions close to the site and transmit them back to us. Unfortunately, they were never heard from again. Below you will find the transmission we received from our allies, we have been unable to make sense of them and need your help! From what we have determined, there is a device with which they are connecting our planet to theirs as a method of bringing more of them here. We know you are going to be on site at Polytechnique Montreal; we need you to find this device, activate it, and read the location of their planet from the transmission. Once you have this information, report back immediately to one of our embedded agents with the location. Should you accomplish this mission you will have proved your loyalty and will be formally inducted into the resistance.”

We can tell from the message that the last section of this challenge may require us to be on-sight at the CS GAMES event.

File one: DRONE-79:89:D6:51:4F:28_VIS_TX.txt

Depth Map Walkthrough

The file is stored in plain-text, with each pair of numbers representing the hexadecimal value of a pixel.

Should you disable wrapping in your text editor and zoom out, an image is just visible:

Alternatively, one can create a relatively simple script to generate a proper image out of this file. Take each pair of numbers, convert from hexadecimal to decimal to get your 0-255 greyscale value and write it to the corresponding pixel of your output image. Something like this:

You may have noticed the small patch of odd numbers/colors at the bottom-left of the image. These generate a strange box if rendered:

...or this from the raw data:

323031392d30322d31315431363a34353a33302b30303a30303030
2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d2d
49443a2044524f4e455f37393a38393a44363a35313a34463a3238
44455054483a205452554520202020202020202020202020202020
434f4c4f523a2046414c5345202020202020202020202020202020
5452414e534d495353494f4e3a204c69676874426c756520202020
454e455247593a204c4f5720202020202020202020202020202020

You can throw the raw hex data into CyberChef with a "From Hex" recipe to get the following output:

2019-02-11T16:45:30+00:0000

---------------------------

ID: DRONE_79:89:D6:51:4F:28

DEPTH: TRUE

COLOR: FALSE

TRANSMISSION: LightBlue

ENERGY: LOW

 

File two: COMMS.raw

personal rule: “When in doubt, pull your hex editor out!”

Within the first 0xA0 bytes we can see “Dumpcap (Wireshark)”. So, let's look at this file through Wireshark eyes. Once you open it with wireshark it happily parses the file as a pcap. Furthermore, looking at the first packet in the file we can see immediately that we are looking a Bluetooth LE packets. More specifically eight-hundred and thirty-nine BLE packets, so let’s make our lives easier and apply a filter here:

Filter: btle.length > 0

Now it’s clear that there is one device broadcasting Raspberr_34:dd:ce and a second device attempting a connection 79:89:d6:51:4f:28. Noticing here that the connecting devices mac is the same mac presented in the DRONE-79:89:D6:51:4F:28_VIS_TX.txt we can make the assumption that in this pcap DRONE_79:89:D6:51:4F:28 connecting to a second device. Looking at the SCAN_RSP packet from the Raspberr_34:dd:ce device we can determine that the second device is something called “Planet_Gateway”. Given the previous file I think we can safely assume this second device is the portal.

The resistance would like us to find the device, activate the device, read back the location of the planet they are connecting to, and pass that information to the embedded agents at the location.

Digging through the packet capture we come across a “Characteristic User Description” received read response in packet No. 116. The slave here has returned the string “Robot Portal Interface”, indicating that this transmission medium is how the robots connect to the Portal.

The next significant action is a write request in packet No. 462, here the robot is writing - 44 49 41 4C 20 48 4f 4d 45 or “DIAL HOME” in Ascii to the portal. The following read request however seems to have the connecting location filtered out.

Activating the portal

Find the device:

   The CSE booth at CS GAMES contains a model alien and portal.

The depth map told us what the portal looked like, as well as the transmission type “LightBlue”. Searching LightBlue on the internet it is not hard to discover that LightBlue is a bluetooth discovery app for both Android and Apple.

1. Download the app and begin scanning for a device we now know to advertise as “Planet_Gateway”.

2. Connect to Planet_Gateway through the LightBlue App.

3. Write 44 49 41 4C 20 48 4f 4d 45 to Planet_Gateway.

4. Read back from Planet_Gateway.

Once the right value is written to the portal the portal will turn on. An immediate read on a correct write value will return - 50 52 4f 58 49 4d 41 2d 42 or “PROXIMA-B”, any other value will return -45 52 52 4f 52 or “ERROR”.

Now that the portal has been found, turned on, the name of the connecting location read, only one thing left to do – pass the “PROXIMA-B” information to the embedded agents.

At this point if you walked up to a CSE recruiter and said to them Proxima-B they would have handed you a Challenge card. Congratulations!!

 

Enjoy solving puzzles? Make a career out of it!