Holiday Hack 2018: de Bruijn Sequences

Objective

Terminal - Lethal ForensicELFication

Challenge

When I head up the strairs, and turn right, past the speakers rooms, I’ll find Tangle Coalbox in the hallway:

Hi, I’m Tangle Coalbox.

Any chance you can help me with an investigation?

Elf Resources assigned me to look into a case, but it seems to require digital forensic skills.

Do you know anything about Linux terminal editors and digital traces they leave behind? Apparently editors can leave traces of data behind, but where and how escapes me!

                       ............'''',,,;;;::ccclloooddxxkkOO00KKXXNNWWMMMMMM
                       ............'''',,,;;;::ccclloooddxxkkOO00KKXXNNWWMMMMMM
   .,.   ,. .......,.  .',..'',,..:::::,,;:c:::ccooooodxkkOOkOO0KKXXXNNWMMMMMMM
   ldd: .d' ';... .o:  .d;.;:....'dl,;do,:lloc:codddodOOxxk0KOOKKKKXNNNWMMMMMMM
   lo.ol.d' ';'..  ,d'.lc..;:,,,.'docod:,:l:locldlddokOxdxxOK0OKKKXXXNNWMMMMMMM
   lo  lod' ';      co:o...;:....'dl':dl,:l::oodlcddoxOkxxk0KOOKKKKXNNNWMMMMMMM
   ,,   ,;. ......  .;:....',,,,''c:'':l;;c:;:llccoooodkkOOOkOO0KKKXNNNWMMMMMMM
                       ............'''',,,;;;::ccclloooddxxkkOO00KKXXNNWWMMMMMM
                       ............'''',,,;;;::ccclloooddxxkkOO00KKXXNNWWMMMMMM
Christmas is coming, and so it would seem,
ER (Elf Resources) crushes elves' dreams.
One tells me she was disturbed by a bloke.
He tells me this must be some kind of joke.
Please do your best to determine what's real.
Has this jamoke, for this elf, got some feels?
Lethal forensics ain't my cup of tea;
If YOU can fake it, my hero you'll be.
One more quick note that might help you complete,
Clearing this mess up that's now at your feet.
Certain text editors can leave some clue.
Did our young Romeo leave one for you?
- Tangle Coalbox, ER Investigator
  Find the first name of the elf of whom a love poem 
  was written.  Complete this challenge by submitting 
  that name to runtoanswer.
elf@9fb7f3b1c79c:~$

Solution

First, I will take a look at what’s in the current directory. ls only shows runtoanswer, but looking also at hidden files with -a shows a couple more interesting things:

elf@9fb7f3b1c79c:~$ ls
runtoanswer

elf@9fb7f3b1c79c:~$ ls -la
total 5460
drwxr-xr-x 1 elf  elf     4096 Dec 14 16:28 .
drwxr-xr-x 1 root root    4096 Dec 14 16:28 ..
-rw-r--r-- 1 elf  elf      419 Dec 14 16:13 .bash_history
-rw-r--r-- 1 elf  elf      220 May 15  2017 .bash_logout
-rw-r--r-- 1 elf  elf     3540 Dec 14 16:28 .bashrc
-rw-r--r-- 1 elf  elf      675 May 15  2017 .profile
drwxr-xr-x 1 elf  elf     4096 Dec 14 16:28 .secrets
-rw-r--r-- 1 elf  elf     5063 Dec 14 16:13 .viminfo
-rwxr-xr-x 1 elf  elf  5551072 Dec 14 16:13 runtoanswer

The .secrets folder is interesting, but first I’m going to check out the .bash_history file. The bash history records commands run, and grows down, adding new commands to the end of the file. Here’s what I found (notes added by me):

elf@9fb7f3b1c79c:~$ cat .bash_history 
set -o history                   <-- turn on history
whoami
echo "No, really...  /-:"
mkdir -p .secrets/her/           <-- make the .secrets directory
firefox https://www.google.com/search?q=love+poetry
vim                              <-- vim editor
ls -lAR
exit
set -o history
df -h
who
firefox https://www.google.com/search?q=replacing+strings+in+vim
time vim
ls -lAR
exit
set -o history
vim
exit
                                 <-- line that got appended by echo below
ls -lA
cat .bash_history
echo "" >> .bash_history         <-- tried to clear history, but only appends a line
firefox https://www.google.com/search?q=turn+off+bash+history
set +o history                   <-- turns off history
set +o history

Next, I’ll list files in the .secret directory (-type f limiting results to just files):

elf@0909624c3731:~$ find .secrets/ -type f
.secrets/her/poem.txt

So only the one file, poem.txt:

elf@1034dc916f18:~$ cat .secrets/her/poem.txt 
Once upon a sleigh so weary, Morcel scrubbed the grime so dreary,
Shining many a beautiful sleighbell bearing cheer and sound so pure--
  There he cleaned them, nearly napping, suddenly there came a tapping,
As of someone gently rapping, rapping at the sleigh house door.
"'Tis some caroler," he muttered, "tapping at my sleigh house door--
  Only this and nothing more."

Then, continued with more vigor, came the sound he didn't figure,
Could belong to one so lovely, walking 'bout the North Pole grounds.
  But the truth is, she WAS knocking, 'cause with him she would be talking,
Off with fingers interlocking, strolling out with love newfound?
Gazing into eyes so deeply, caring not who sees their rounds.
  Oh, 'twould make his heart resound!

Hurried, he, to greet the maiden, dropping rag and brush - unlaiden.
Floating over, more than walking, moving toward the sound still knocking,
  Pausing at the elf-length mirror, checked himself to study clearer,
Fixing hair and looking nearer, what a hunky elf - not shocking!
Peering through the peephole smiling, reaching forward and unlocking:
  NEVERMORE in tinsel stocking!

Greeting her with smile dashing, pearly-white incisors flashing,
Telling jokes to keep her laughing, soaring high upon the tidings,
  Of good fortune fates had borne him.  Offered her his dexter forelimb,
Never was his future less dim!  Should he now consider gliding--
No - they shouldn't but consider taking flight in sleigh and riding
  Up above the Pole abiding?

Smile, she did, when he suggested that their future surely rested,
Up in flight above their cohort flying high like ne'er before!
  So he harnessed two young reindeer, bold and fresh and bearing no fear.
In they jumped and seated so near, off they flew - broke through the door!
Up and up climbed team and humor, Morcel being so adored,
  By his lovely NEVERMORE!

-Morcel Nougat

So the name of the person in the poem is NEVERMORE. Time to look at the vim history to see what I can find. There are many different things in this file, but I’ll be looking at the history:

# Command Line History (newest to oldest):
:wq                                          <-- save and exit
|2,0,1536607231,,"wq"
:%s/Elinore/NEVERMORE/g                      <-- replace Elinore with NEVERMORE! That's the answer
|2,0,1536607217,,"%s/Elinore/NEVERMORE/g"
:r .secrets/her/poem.txt                     <-- open poem.txt
|2,0,1536607201,,"r .secrets/her/poem.txt"
:q
|2,0,1536606844,,"q"
:w
|2,0,1536606841,,"w"
:s/God/fates/gc
|2,0,1536606833,,"s/God/fates/gc"
:%s/studied/looking/g
|2,0,1536602549,,"%s/studied/looking/g"
:%s/sound/tenor/g
|2,0,1536600579,,"%s/sound/tenor/g"
:r .secrets/her/poem.txt
|2,0,1536600314,,"r .secrets/her/poem.txt"

With the answer in hand, now runtoanswer:

elf@142305b3d529:~$ ./runtoanswer 
Loading, please wait......
Who was the poem written about? Elinore
WWNXXK00OOkkxddoolllcc::;;;,,,'''.............                                 
WWNXXK00OOkkxddoolllcc::;;;,,,'''.............                                 
WWNXXK00OOkkxddoolllcc::;;;,,,'''.............                                 
WWNXXKK00OOOxddddollcccll:;,;:;,'...,,.....'',,''.    .......    .''''''       
WWNXXXKK0OOkxdxxxollcccoo:;,ccc:;...:;...,:;'...,:;.  ,,....,,.  ::'....       
WWNXXXKK0OOkxdxxxollcccoo:;,cc;::;..:;..,::...   ;:,  ,,.  .,,.  ::'...        
WWNXXXKK0OOkxdxxxollcccoo:;,cc,';:;':;..,::...   ,:;  ,,,',,'    ::,'''.       
WWNXXXK0OOkkxdxxxollcccoo:;,cc,'';:;:;..'::'..  .;:.  ,,.  ','   ::.           
WWNXXXKK00OOkdxxxddooccoo:;,cc,''.,::;....;:;,,;:,.   ,,.   ','  ::;;;;;       
WWNXXKK0OOkkxdddoollcc:::;;,,,'''...............                               
WWNXXK00OOkkxddoolllcc::;;;,,,'''.............                                 
WWNXXK00OOkkxddoolllcc::;;;,,,'''.............                                 
Thank you for solving this mystery, Slick.
Reading the .viminfo sure did the trick.
Leave it to me; I will handle the rest.
Thank you for giving this challenge your best.
-Tangle Coalbox
-ER Investigator
Congratulations!

On running, another achievement:

Hints

On solving, Tangle tells me the following, and unlocks two hints, with some really interesting information on de Bruijn Sequences:

Hey, thanks for the help with the investigation, gumshoe.

Have you been able to solve the lock with the funny shapes?

It reminds me of something called “de Bruijn Sequences.”

You can optimize the guesses because there is no start and stop – each new value is added to the end and the first is removed.

I’ve even seen de Bruijn sequence generators online.

Here the length of the alphabet is 4 (only 4 buttons) and the length of the PIN is 4 as well.

Mathematically this is k=4, n=4 to generate the de Bruijn sequence.

Math is like your notepad and pencil - can’t leave home without it!

I heard Alabaster lost his badge! That’s pretty bad. What do you think someone could do with that?

de Bruijn Sequences

Prep

Just to the right of the speaker tracks, I find the room:

After wondering for a moment about if this lock is meant to be opened with your feet, I lay down on the floor and start working on the lock:

I found four ways to solve this challenge.

de Bruijn Brute Force It

The hints reference de Bruijn sequences, which are a sequence of input that is optimized to require the minimum input in cases where only the last x entries are examined to validate the code. Therefore you can walk the entire code space much faster than an un-ordered brute force. If I look at the javascript on the page, I’ll see that each time a button is pressed, it’s added to the queue of input and the last four values are checked, so a de Bruijn sequence could be useful here.

Following the de Bruijn Sequence doesn’t reduce the number of passcodes guessed to get to a solution. However, in a case where you can’t automate input, it does significantly reduce the number of buttons I’d have to push. In fact, it makes this challenge solvable just by manually clicking until I get in.

I’ll use this generator to make a sequence with k =4 and n = 4 to get the following sequence:

0 0 0 0 1 0 0 0 2 0 0 0 3 0 0 1 1 0 0 1 2 0 0 1 3 0 0 2 1 0 0 2 2 0 0 2 3 0 0 3 1 0 0 3 2 0 0 3 3 0 1 0 1 0 2 0 1 0 3 0 1 1 1 0 1 1 2 0 1 1 3 0 1 2 1 0 1 2 2 0 1 2 3 0 1 3 1 0 1 3 2 0 1 3 3 0 2 0 2 0 3 0 2 1 1 0 2 1 2 0 2 1 3 0 2 2 1 0 2 2 2 0 2 2 3 0 2 3 1 0 2 3 2 0 2 3 3 0 3 0 3 1 1 0 3 1 2 0 3 1 3 0 3 2 1 0 3 2 2 0 3 2 3 0 3 3 1 0 3 3 2 0 3 3 3 1 1 1 1 2 1 1 1 3 1 1 2 2 1 1 2 3 1 1 3 2 1 1 3 3 1 2 1 2 1 3 1 2 2 2 1 2 2 3 1 2 3 2 1 2 3 3 1 3 1 3 2 2 1 3 2 3 1 3 3 2 1 3 3 3 2 2 2 2 3 2 2 3 3 2 3 2 3 3 3 3 (0 0 0)

It actually doesn’t take that long to just enter it by hand and find the right solution (I’ll demonstrate in the story instance since it shows the nice pop-up on success):

Brute Force It

With four options and four characters, there’s only 4⁴ = 256 possible codes. de Bruijn makes that easier to input by hand, but I could also just script it to try all those combinations.

I’ll watch network traffic in the Firefox dev console to see how the input passcode is submitted. The request looks like this (if I work through the story interface, the resourceId is undefined instead of that guid value):

GET /checkpass.php?i=0123&resourceId=dfde3e1c-6097-4d1b-9ff9-e91fa9002226 HTTP/1.1
Host: doorpasscoden.kringlecastle.com
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Firefox/60.0
Accept: */*
Accept-Language: en-US,en;q=0.5
Accept-Encoding: gzip, deflate
Referer: https://doorpasscoden.kringlecastle.com/
Connection: close

The response looks like:

HTTP/1.1 200 OK
Server: nginx/1.14.1
Date: Fri, 21 Dec 2018 13:43:54 GMT
Content-Type: text/html; charset=UTF-8
Connection: close
X-Powered-By: PHP/7.2.10
Content-Length: 46

{"success":false,"message":"Incorrect guess."}

Since the check is done with a simple HTTP GET request, I can just write a script to brute force the code:

#!/usr/bin/env python3

import requests
import sys
from itertools import product

# Loop over all possible codes
for code in [''.join(x) for x in product('0123', repeat=4)]:
    resp = requests.get(f'https://doorpasscoden.kringlecastle.com/checkpass.php?i={code}&resourceId=undefined')
    
    # Use \r and sys.stdout.write to update status on one line
    sys.stdout.write(f"{code}: {resp.text}   \r")
    sys.stdout.flush()
    
    # If success, print result and break
    if ":true" in resp.text:
        print(f"\nFound passcode: {code}       ")
        break

Here it is in action:

Enter that code into the game, and enter the room:

Modify HTTP Response

Brute forcing the door worked, but it’s loud, and could raise the attention of the castle SOC. A better solution is to catch the response from the server and modify it so that I succeed. I’ll look at the javascript source for the page:

To open Firefox dev tools, right-click then “Inspect Item”
Go to “Debugger”
Select the “doorpasscode.kringlecastle.com”

If response.success, then the __POST_RESULTS__ variable is set. After a bit more exploring through the code, I found this in conduit.js:

/* 
  expects `data` to be a plain object
  with the following attributes (at least):
  - resourceId (same as the one initially passed)
  - hash (hmac)

  this object will be passed to the client if the
  challenge is loaded in an iframe, and will be 
  dumped in the console.
  
*/
const __POST_RESULTS__ = data => {
  const payload = {
    type: 'challengeResult',
    ...data,
  };

So setting the __POST_RESULTS_ object will return success from the iframe with the challenge. Awesome. So all I need to do to solve is intercept the response, and change success to true.

I’ll set a breakpoint at line 105 in the Firefox debugger. Line 105 will set the message response. Then line 106 will check for success. I’ll use the console to change the value of parsedResponse.message to true.

In the gif below, I’ll show hitting the break point two times. The first time, I don’t change anything, and it doesn’t set __POST_RESULT__. In the second, I modify the response, __POST_RESULT__ is set, and the door is open once I exit:

[

](https://0xdfimages.gitlab.io/img/sans2018-interceptdoor.gif) Click on the above image for full size version

Go Directly to the Image

In the story instance of this challenge, there was another way to get the answer - Go right to the image.

In the source for this page, there’s a couple additions. First, if success is returned, there’s this:

document.getElementById('banner').style.visibility='visible';

And at the bottom of the page, the banner:

<img id="banner" src="db-victory-banner.png" style="position:absolute; left:50%; top:50%; transform: translate(-50%, -50%); max-width:60%; width: 60%; visibility: hidden;" onMouseDown='this.style.visibility="hidden"'>

Visiting https://doorpasscoden.kringlecastle.com/db-victory-banner.png gives the phrase: