Square CTF 2018 C1: dots-n-dash

01

Analysis

Inside the file ‘dot-n-dash.jar’ we have 2 files: dot-n-dash.html and instructions.txt.

The file instructions.txt is encrypted with dots and dashes and in the file dot-n-dash.html:

01b

In the source code of dot-n-dash.html we have the algorithm used to encode it, but not the decoding one.

Let’s analyze the page’s code. It’s Javascript based. The function to encode is:

function _encode(input) {
  var a=[];
  for (var i=0; i<input.length; i++) {
    var t = input.charCodeAt(i);
    for (var j=0; j<8; j++) {
      if ((t >> j) & 1) {
        a.push(1 + j + (input.length - 1 - i) * 8);
      }
    }
  }

  var b = [];
  while (a.length) {
    var t = (Math.random() * a.length)|0;
    b.push(a[t]);
    a = a.slice(0, t).concat(a.slice(t+1));
  }

  var r = '';
  while (b.length) {
    var t = b.pop();
    r = r + "-".repeat(t) + ".";
  }
  return r;
}

The encoding algorithm is divided into three steps.

Step 1 : Encode charCode to binary bits

  var a=[];
  for (var i=0; i<input.length; i++) {
    var t = input.charCodeAt(i);
    for (var j=0; j<8; j++) {
      if ((t >> j) & 1) {
        a.push(1 + j + (input.length - 1 - i) * 8);
      }
    }
  }

The first for loop iterates over all input characters. The second one iterates on the bits of the current character. For each bit, if its value is 1, 1 + j + (input.length - 1 - i) * 8 (where i is the character index and j the bit index) is added to the output.

In other words, this step is taking the bit representation of the input string and building a list with the indexes of all bits with value 1

An example would be clearer. With ‘a’ with ASCII value 97 in decimal, we can generate a list of bitwise shifts from 0 to 7:

01

In essence, this encodes the binary digits of 97 (the ‘a’ symbol) where if t >> j, then the bit is 1:

02

You can find more about the JavaScript (Sign Preserving) Bitwise Right Shift (>>) and Bitwise AND (&) here.

03

This encoding is always reversible, since we are encoding both the value of the character, as well as its position with:

04

The ‘a Array’ contains the values of the position of the ‘1’ in the calculated binary (note that the calculated binary value is the mirrored real binary value!), and for:

05

Step 2: Shuffle positions

  var b = [];
  while (a.length) {
    var t = (Math.random() * a.length)|0;
    b.push(a[t]);
    a = a.slice(0, t).concat(a.slice(t+1));
  }

This section essentially just randomizes the position of the resultant encoded “bits”. Since we have previously encoded the positions as well, we will have no problem restoring them to the correct positions later.

The b Array stores the shuffled values, for example:

06

Step 3: Convert values to dashes

  var r = '';
  while (b.length) {
    var t = b.pop();
    r = r + "-".repeat(t) + ".";
  }
  return r;

This section performs the conversion. The number of dashes corresponds to the encoded value, and is delimited by dots. It picks the values from b array (shuffled a Array).

07

An example:

08

Let’s see an example with a more complicated word: “flag-

09

The output is:

---------------------------.-----------.--------------------------------------.---.-----------------.------------------------------.----------------------------------.----------.---------.----------------------------.------.-------------------------------.---------------.--------------.-----------------------------------.----.---------------------------------------.-.-----------------------.----------------------.

Solution

In order to decode the provided instructions file, all I need is to reconstruct the ‘a array’, sort it, and convert each bit value back to a character. This was done with some simple Python code below.

We named it dot-n-dash-solve.py

data = open('dot-n-dash/instructions.txt').read()

lens = [len(x) for x in data.strip().split('.')]
lens.sort()

st = []
for i in range(0,max(lens),8):
	ch = 0
	for j in range(8):
		if i+j+1 in lens:
			ch = ch | (1<<j)
	st.append(chr(ch))

st.reverse()
print(''.join(st))

And the result is:

06

The flag we were searching for is:

flag-bd38908e375c643d03c6

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.