Objective #3: de Bruijn Sequences

Problem

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.

Hints

Tangle Coalbox provides the following hint:

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!

Tangle also provides a link to a webpage on how you can open a Ford vehicle with a robot and the de Bruign Sequence https://hackaday.com/2018/06/18/opening-a-ford-with-a-robot-and-the-de-bruijn-sequence/

Tangle also provides a link to a de Bruijn Sequence generator: http://www.hakank.org/comb/debruijn.cgi

Solution

The challenge is to come up with the correct combination to unlock the door to the Speaker Unpreparedness Room.

Visit the sequence generator page that Tangle provided, and enter a value of 4 for both k (alphabet size) and n (word length). This produces 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)

Now, assign a digit to each of the buttons on the door lock (triangle=0, square=1, circle=2, star=3). The first door password attempt is the first four digits of the sequence (0 0 0 0), the next attempt starts with the second digit (0 0 0 1), then the third digit (0 0 1 0), and so on until we find a combination that works.

The winning combination turns out to be 0 1 2 0 (triangle, square, circle, triangle). Inside the Speaker Unpreparedness Room, Morcel Nougat says Welcome unprepared speaker!

Alternatives

There are 256 different combinations possible, but fortunately the door unlocks after on the 19th attempt. If the problem were more complicated, manual attempts would not be feasible, so we could try automating the tries.

A look at the terminal through the OWASP ZAP proxy reveals that each guess is submitted as a parameter in a HTTP GET request. We could send this request to the fuzzer and try each combination automatically until a successful response is returned.

Here we define parameter i as our fuzzing target.

This Python program generates the payload list, which we can paste into ZAP as a list of strings.

#!/usr/bin/python

seq='0000100020003001100120013002100220023003100320033010102010301110112011301210122012301310132013302020302110212021302210222022302310232023303031103120313032103220323033103320333111121113112211231132113312121312221223123212331313221323133213332222322332323333000'

for x in range (1,256):
   print seq[x:x+4]

Now start the fuzzer and look at the results. We know from our first request that failed attempts result in a 46 byte response from the server; a result of a different length may indicate success.

Here we see that the response to request #18 is 142 bytes, unlike the others, and the JSON returned from the server says "Correct guess!"