Home › Capture The Flag Write-ups › SANS Holiday Hack 2018: Objective 3: de Bruijin Sequences

SANS Holiday Hack 2018: Objective 3: de Bruijin Sequences

Posted on Posted in Capture The Flag Write-ups, SANS Holiday Hack 2018

Objective: When you break into the speaker unpreparedness room, what does Morcel Nougat say? For hints on achieving this objective, please visit Tangle Coalbox and help him with Lethal ForensicELFication Cranberry Pi terminal challenge.

Answer: Welcome unprepared speaker!

Speaker UNpreparedness Room
At the “Speaker UNpreparedness Room” we find a “Door Entry Passcode”, which appears to be a combination lock of 4 symbols, with symbols allowed to be entered multiple times. Also each time a new character is pressed, a new guess is made.


This is a permutation problem with repetition allowed, so in total there are 4^4 = 256 possible guesses. But due to the guess being made on each character change we can use a De Bruijin Series (as suggested by the title) to do this manually. The series provides the optimal shortest number of guesses.

Using the online resource we can generate a De Bruijin Series for an alphabet of size 4 and a sub-string of size 4:

http://www.hakank.org/comb/debruijn.cgi?k=4&n=4&submit=Ok

Which provides us with 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)

Where we can map the following ids to our symbols:

  • 0 = Triangle
  • 1 = Square
  • 2 = Circle
  • 3 = Star

So it is possible to manually follow the sequence entering the 259 symbols as specified in the series, instead of having to press 1024 buttons (4 presses per 256 guesses). If this is done the result is found after 19 key presses, which is nice:

Cracking Via Automation
Though I solved this manually initially there is another option. When the input code in the image is entered this API call is seen below (note: parameter ‘i’ is the numeric representation of the code, the numbers map as presented above to):


And the response of the API is as follows:

{“success”:false,”message”:”Incorrect guess.”}

So the following Python code was created to use the API, and we still used the De Bruijn Sequence just for fun:

import requests
import json

resourceId = "***SENSITIVE***" #Copy this from an example request
deBruijin = "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"
array = deBruijin.split(" ")

req_str = "https://doorpasscode.kringlecastle.com/checkpass.php?i={}&resourceId=" + resourceId

for x in range(len(array)-3):
    guess = array[x:x+4]
    resp = requests.get(req_str.format("".join(guess)))
    success = json.loads(resp.text)['success']
    print("%i\tGuess: %s Success: %s" % (x, guess, success))
    if success:
        break

This produced the same result as expected, but the breakdown of the output:

 0    Guess: ['0', '0', '0', '0'] Success: False
 1    Guess: ['0', '0', '0', '1'] Success: False
 2    Guess: ['0', '0', '1', '0'] Success: False
 3    Guess: ['0', '1', '0', '0'] Success: False
 4    Guess: ['1', '0', '0', '0'] Success: False
 5    Guess: ['0', '0', '0', '2'] Success: False
 6    Guess: ['0', '0', '2', '0'] Success: False
 7    Guess: ['0', '2', '0', '0'] Success: False
 8    Guess: ['2', '0', '0', '0'] Success: False
 9    Guess: ['0', '0', '0', '3'] Success: False
 10    Guess: ['0', '0', '3', '0'] Success: False
 11    Guess: ['0', '3', '0', '0'] Success: False
 12    Guess: ['3', '0', '0', '1'] Success: False
 13    Guess: ['0', '0', '1', '1'] Success: False
 14    Guess: ['0', '1', '1', '0'] Success: False
 15    Guess: ['1', '1', '0', '0'] Success: False
 16    Guess: ['1', '0', '0', '1'] Success: False
 17    Guess: ['0', '0', '1', '2'] Success: False
 18    Guess: ['0', '1', '2', '0'] Success: True
 Process finished with exit code 0

So the answer is once again:

Triangle, Square, Circle, Star

Which allows us access to the “Speaker UNpreparedness Room”:

Here we can speak to “Morcel Nougat”:

Who says: “Welcome unprepared speaker!”