Ghost in the Shellcode Teaser CTF 2015: Lost to Time

Created:2014.12.16, last modified: 2014.12.16 by xorpse
Status: Complete

The challenge, after unpacking the given xz compressed data is in the form of an assembly listing. Following a search for some of the mnemonics, the dialect is revealed to be COMPASS. The Wikipedia page for COMPASS [0] as well as many additional references ([1], [2], [3], [4], [5]) were used to produce the following annotated assembly listing:

         IDENT     CTF
         ABS
         SST
         ENTRY     CTF
         SYSCOM    B1
         SPACE  4,10
         ORG    110B
FWA      BSS    0
 
BUFL     EQU    401B
 
F        BSS    0
ZZZZZG0  FILEB  FBUF,BUFL,DTY=2RTT

CTF      BSS       0
         SB1       1          ; B1 = 1
         SA1       CTFB       ; A1 = CTFB
         BX6       X1         ; X6 = X1
         SB7       27         ; B7 = 27
         SA6       A1         ; A6 = A1
         SA2       CTFA       ; A2 = CTFA  (load into X2 first 60 bits of CTFA)
         MX0       30         ; X0 = 0b111111111111111111111111111111000000000000000000000000000000
         SA1       A2+B1      ; A1 = A2 + B1 (load A2 + B1 into X1)

CTF2     BX6       X0*X1      ; X6 = X0 & X1
         ZR        X6,CTF4    ; if X6 == 0 then goto CTF4
         JR        FCT        ; Jump + Return: FCT
         SA6       A6+B1      ; A6 += B1  (store X6 into A6 + B1)
         BX6       -X0*X1     ; X6 = ~X0 & X1
         ZR        X6,CTF4    ; if X6 == 0 then goto CTF4
         JR        FCT        ; Jump + Return: FCT
         SA6       A6+B1      ; A6 += B1  (store X6 into A6 + B1)
         SA1       A1+B1      ; A1 += B1  (load A1 + B1 into X1)
         NZ        X1,CTF2    ; if X1 != 0 then goto CTF2

CTF4     WRITES    F,CTFB,CTFBL
         ENDRUN 

FCT      SUBR
         CX6       X6          ; X6 = #of 1s in X6
         SB6       X6          ; B6 = X6
         LT        B6,B7,FCT2  ; if B6 < B7 then goto FC2 (B7 is always 27)
         SB6       B6-B7       ; B6 = B6 - B7
         SB6       B6+B6       ; B6 = B6 + B6
         SB5       B6+B6       ; B5 = B6 + B6
         SB5       B5+B5       ; B5 = B5 + B5
         SB6       B5+B6       ; B6 = B5 + B6 (B6 now equals (B6 - 27) * 10)
         AX6       X2,B6       ; X6 = X2 >> B6
         MX7       -10         ; X7 = 0b111111111111111111111111111111111111111111111111110000000000
         BX6       -X7*X6      ; X6 = ~X7 & X6
FCT2     JP        FCTX        ; return


CTFA     BSS       0
         VFD       6/00B,9/000B,9/000B,9/520B,9/244B,9/120B,9/057B   ; Each line = 60 bits
         VFD       6/40B,9/210B,9/003B,9/100B,9/774B,9/415B,9/040B
         VFD       6/00B,9/000B,9/400B,9/000B,9/442B,9/211B,9/001B
         VFD       6/77B,9/776B,9/777B,9/770B,9/010B,9/002B,9/004B
         VFD       6/77B,9/377B,9/577B,9/610B,9/040B,9/000B,9/400B
         VFD       6/00B,9/100B,9/200B,9/343B,9/556B,9/115B,9/671B
         VFD       6/00B,9/000B,9/004B,9/441B,9/625B,9/031B,9/752B
         VFD       6/63B,9/015B,9/236B,9/227B,9/165B,9/273B,9/762B
         VFD       6/27B,9/167B,9/713B,9/057B,9/111B,9/504B,9/353B
         VFD       6/14B,9/205B,9/324B,9/130B,9/006B,9/000B,9/100B
         VFD       6/67B,9/775B,9/673B,9/736B,9/000B,9/000B,9/000B
         VFD       6/10B,9/007B,9/000B,9/204B,9/666B,9/666B,9/661B
         VFD       6/10B,9/010B,9/010B,9/010B,9/002B,9/000B,9/000B
         VFD       6/35B,9/671B,9/077B,9/650B,9/001B,9/000B,9/000B
         VFD       6/70B,9/000B,9/000B,9/007B,9/677B,9/737B,9/566B
         VFD       6/40B,9/000B,9/000B,9/044B,9/000B,9/700B,9/004B
         VFD       6/57B,9/135B,9/427B,9/072B,9/000B,9/400B,9/010B
         VFD       6/54B,9/710B,9/650B,9/722B,9/667B,9/170B,9/671B
         VFD       6/37B,9/503B,9/354B,9/061B,9/653B,9/521B,9/704B
         VFD       6/67B,9/531B,9/564B,9/700B,9/000B,9/000B,9/004B
         VFD       6/12B,9/345B,9/677B,9/674B,9/127B,9/002B,9/011B
         VFD       6/27B,9/315B,9/340B,9/647B,9/003B,9/653B,9/700B
         VFD       6/77B,9/777B,9/777B,9/770B,9/000B,9/000B,9/000B
         VFD       6/00B,9/000B,9/000B,9/000B,9/000B,9/000B,9/055B
CTFB     BSS       0
         DUP       64,1  ; Result buffer
         DATA      1R 
CTFBL    EQU       *-CTFB

COMCPL   XTEXT     COMCCDD
COMCPL   XTEXT     COMCCIO
COMCPL   XTEXT     COMCCPM
COMCPL   XTEXT     COMCDXB
COMCPL   XTEXT     COMCLFM
COMCPL   XTEXT     COMCSYS
COMCPL   XTEXT     COMCWTS
COMCPL   XTEXT     COMCWTW
BUFFERS  SPACE     4,10 
         USE       BUFFERS
FBUF     EQU       *
RFL=     EQU       FBUF+BUFL+10

         END

Which decompiles (roughly) to the following psuedo-C:

main()
{
  i = 1;

  while (i < number_of_words(CTFA)) {
    w = CTFA[i];
    hi = 0b111111111111111111111111111111000000000000000000000000000000 & w;
    lo = 0b000000000000000000000000000000111111111111111111111111111111 & w;

    if (hi == 0)
      break;

    value = compute_value(hi);
    CTFB[i] = value;

    if (lo == 0)
      break;

    value = compute_value(lo);
    CTFB[i + 1] = value;

    i += 2;
  }

  write(flag);
}

compute_value(value)
{
  n = count_1s(value);

  if (n < 27)
    return n;

  n = (n - 27) * 10;
  n = CTFA[0] >> n;

  mask = 0b111111111111111111111111111111111111111111111111110000000000;
  return ~mask & n;
}

With the aforementioned pseudo-code, it was relatively straight-forward to produce the following simulator (in OCaml), which outputs the flag, as required:

open Core_kernel.Std
open Option.Monad_infix

let lookup =
"          VFD       6/00B,9/000B,9/000B,9/520B,9/244B,9/120B,9/057B"

let lines = [
"          VFD       6/40B,9/210B,9/003B,9/100B,9/774B,9/415B,9/040B";
"          VFD       6/00B,9/000B,9/400B,9/000B,9/442B,9/211B,9/001B";
"          VFD       6/77B,9/776B,9/777B,9/770B,9/010B,9/002B,9/004B";
"          VFD       6/77B,9/377B,9/577B,9/610B,9/040B,9/000B,9/400B";
"          VFD       6/00B,9/100B,9/200B,9/343B,9/556B,9/115B,9/671B";
"          VFD       6/00B,9/000B,9/004B,9/441B,9/625B,9/031B,9/752B";
"          VFD       6/63B,9/015B,9/236B,9/227B,9/165B,9/273B,9/762B";
"          VFD       6/27B,9/167B,9/713B,9/057B,9/111B,9/504B,9/353B";
"          VFD       6/14B,9/205B,9/324B,9/130B,9/006B,9/000B,9/100B";
"          VFD       6/67B,9/775B,9/673B,9/736B,9/000B,9/000B,9/000B";
"          VFD       6/10B,9/007B,9/000B,9/204B,9/666B,9/666B,9/661B";
"          VFD       6/10B,9/010B,9/010B,9/010B,9/002B,9/000B,9/000B";
"          VFD       6/35B,9/671B,9/077B,9/650B,9/001B,9/000B,9/000B";
"          VFD       6/70B,9/000B,9/000B,9/007B,9/677B,9/737B,9/566B";
"          VFD       6/40B,9/000B,9/000B,9/044B,9/000B,9/700B,9/004B";
"          VFD       6/57B,9/135B,9/427B,9/072B,9/000B,9/400B,9/010B";
"          VFD       6/54B,9/710B,9/650B,9/722B,9/667B,9/170B,9/671B";
"          VFD       6/37B,9/503B,9/354B,9/061B,9/653B,9/521B,9/704B";
"          VFD       6/67B,9/531B,9/564B,9/700B,9/000B,9/000B,9/004B";
"          VFD       6/12B,9/345B,9/677B,9/674B,9/127B,9/002B,9/011B";
"          VFD       6/27B,9/315B,9/340B,9/647B,9/003B,9/653B,9/700B";
"          VFD       6/77B,9/777B,9/777B,9/770B,9/000B,9/000B,9/000B";
"          VFD       6/00B,9/000B,9/000B,9/000B,9/000B,9/000B,9/055B"]

let binary_fmt_oct width n =
  let i = int_of_string ("0o" ^ n) in
  let s = String.make width '0' in
  for j = width - 1 downto 0 do
    if i lsr (width - j - 1) land 1 = 1 then
      s.[j] <- '1'
  done;
  s

let count_1s_in =
  String.fold ~init:0 ~f:(fun n v -> if v = '1' then succ n else n)

let get_bits line =
  Re_pcre.split ~rex:(Re_pcre.regexp ",") line
  |> List.map ~f:(fun v ->
      match Re_pcre.extract ~rex:(Re_pcre.regexp "([0-9]+)/([0-7]+)B") v with
        | [| _; width; value |] -> (width, value)
        | _ -> assert false)
  |> List.map ~f:(fun (width, value) -> binary_fmt_oct (int_of_string width) value)
  |> String.concat

(* http://en.wikipedia.org/wiki/CDC_display_code *)
let get_letter =
  let table = ":ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+-*/()$= ,.#[]%\"_!&'?<>@\\^;" in
  let lookup_table = get_bits lookup in
  fun n ->
    if n = 0 then
      None
    else if n < 27 then
      Some table.[n]
    else
      let shift = (n - 27) * 10 in
      let value = String.sub ~pos:0 ~len:(60 - shift) lookup_table in
      let len = String.length value in
      let wmask = int_of_string ("0b" ^ String.sub ~pos:(len - 10) ~len:10 value) in
      Some table.[wmask]

let rec decode_lines = function
  | [] -> Option.return ()
  | x :: xs ->
      let values = get_bits x in
      let first = String.sub ~pos:0 ~len:30 values in
      let second = String.sub ~pos:30 ~len:30 values in

      get_letter (count_1s_in first) >>= fun c1 ->
      print_char c1;
      get_letter (count_1s_in second) >>= fun c2 ->
      print_char c2;
      decode_lines xs

let () =
  decode_lines lines |> ignore;
  print_newline ()

Running gives:

$ ./lost_to_time
FLAG(CYBERCONTROLCYBERDATACYBERCORPORATION)