# constellations (reversing, 17 teams solved)

###### tags: `SECCON CTF 2021`

## Overview

As stated in the problem description, the given binary is a x64 ELF file written in Go(lang).
The program starts printing the flag and slows down.

$ ./constellations
SECCON{N33d_m0r3_sp33d_vo6Rg

The task is to speed it up.

## Solution

Go's compiler outputs x64 native code, not VM's one.
You can reverse it just like a ordinal ELF file, though it will be a bit more difficult.
Try hard.

~~This is my intended solution. However..., when writing this writeup, I noticed that the binary contains the original source code as debugging information :face_with_rolling_eyes:~~

UPDATE: The binary contains no source code.
My gdb just showed the original source code.
@harrier told me that in Discord.
Thanks!

$ gdb ./constellations
GNU gdb (Ubuntu 9.2-0ubuntu1~20.04) 9.2
Copyright (C) 2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
 :
(gdb) set listsize 1000
(gdb) list main.main
1       //      go build constellations.go
2
3       package main
4
5       import (
6               "fmt"
7               "math/big"
8               "strings"
9       )
10
11      func main() {
12              a := []string{
13                      "Sagittarius_Taurus",
14                      "Virgo_Virgo",
15                      "Aquarius_Aquarius_Taurus",
16                      "Aquarius_Aquarius_Taurus",
17                      "Virgo_Gemini",
18                      "Sagittarius_Libra",
19                      "Libra_Gemini",
20                      "Sagittarius_Libra",
21                      "Aries_Aries_Aries",
22                      "Aries_Aries_Aries",
23                      "Gemini_Aries_Cancer",
24                      "Aquarius_Gemini",
25                      "Aquarius_Leo_Capricorn_Aquarius",
26                      "Pisces_Gemini_Cancer_Cancer",
27                      "Capricorn_Capricorn_Scorpio_Libra",
 :
187                     "Pisces_Capricorn_Taurus_Sagittarius_Aquarius_Scorpio_Capricorn_Libra_Aries_Taurus_Taurus_Aries_Gemini_Scorpio_Gemini_Taurus_Capricorn_Gemini_Cancer_Gemini_Leo_Virgo_Aries_Pisces_Aries_Libra_Capricorn_Gemini_Scorpio_Virgo_Aquarius_Sagittarius_Leo_Leo_Scorpio_Virgo_Pisces_Pisces_Cancer_Virgo_Aries_Cancer_Scorpio_Capricorn_Gemini_Aquarius_Pisces_Leo_Capricorn",
188                     "Aries_Aquarius_Leo_Leo_Virgo_Scorpio_Sagittarius_Capricorn_Libra_Aquarius_Pisces_Gemini_Aries_Pisces_Capricorn_Taurus_Aries_Leo_Aries_Gemini_Aquarius_Sagittarius_Cancer_Libra_Libra_Virgo_Capricorn_Virgo_Leo_Aries_Virgo_Cancer_Aquarius_Aries_Pisces_Virgo_Taurus_Pisces_Libra_Virgo_Gemini_Leo_Taurus_Virgo_Gemini_Virgo_Leo_Sagittarius_Gemini",
189                     "Capricorn_Gemini_Taurus_Libra_Cancer_Capricorn_Aquarius_Sagittarius_Pisces_Aquarius_Leo_Taurus_Aries_Leo_Leo_Sagittarius_Taurus_Gemini_Libra_Capricorn_Sagittarius_Pisces_Aquarius_Taurus_Sagittarius_Cancer_Aries_Aquarius_Capricorn_Taurus_Cancer_Aries_Virgo_Taurus_Pisces_Libra_Sagittarius_Virgo_Leo_Virgo_Aquarius_Libra_Scorpio_Libra_Capricorn_Aquarius_Taurus_Aries_Virgo",
190             }
191             b := []string{
192                     "Cancer",
193                     "Aquarius",
194                     "Pisces",
195                     "Aries",
196                     "Leo",
197                     "Virgo",
198                     "Capricorn",
199                     "Gemini",
200                     "Scorpio",
201                     "Sagittarius",
202                     "Libra",
203                     "Taurus",
204             }
205             for c := 0; c < len(a); c++ {
206                     d := strings.Split(a[c], "_")
207                     e := big.NewInt(0)
208                     for f := 0; f < len(d); f++ {
209                             for g := 0; g < 12; g++ {
210                                     if d[f] == b[g] {
211                                             e.Mul(e, big.NewInt(12))
212                                             e.Add(e, big.NewInt(int64(g)))
213                                     }
214                             }
215                     }
216                     h := big.NewInt(0)
217                     for i := big.NewInt(0); i.Cmp(e) < 0; i = i.Add(i, big.NewInt(1)) {
218                             h = h.Add(h, big.NewInt(5))
219                     }
220                     h = h.Mod(h, big.NewInt(256))
221                     fmt.Printf("%c", h.Int64())
222             }
223             fmt.Println()
224     }

The program

1. Parse names of constellations as base 12 number $n$,
2. Add $5$ up $n$ times and
3. Print a character of ASCII code of it mod 256.

We can easily speed it up by changing $5+5+5+...+5$ to $5\times n$.

import sys
import struct

data = open("constellations", "rb").read()

enc = []
for i in range(0xb1):
  t = 0xc95e8+i*0x10
  p, l = struct.unpack("<QQ", data[t:t+0x10])
  p -= 0x400000
  enc += [data[p:p+l].decode()]

C = [
  "Cancer",
  "Aquarius",
  "Pisces",
  "Aries",
  "Leo",
  "Virgo",
  "Capricorn",
  "Gemini",
  "Scorpio",
  "Sagittarius",
  "Libra",
  "Taurus",
]

flag = ""
for e in enc:
  e = e.split("_")
  x = 0
  for c in e:
    x = x*12+C.index(c)
  flag += chr(5*x%256)
print(flag)

This script reads the names of constellations from the binary.

$ python3 solve.py
SECCON{N33d_m0r3_sp33d_vo6RgykRuK8rY9r07kLO3Aj9xsfffimRWK7ferM8MU4q5qoP32yKOaPyWcmCKyJ6yIgWJOBP5eTA8lgRl7u3JinsZPqlItrjnbsTIZ5uhnLCd5KsLcsena9wmdclyV7H_Wh47_1s_y0ur_b1r7h_51gn?}

`SECCON{N33d_m0r3_sp33d_vo6RgykRuK8rY9r07kLO3Aj9xsfffimRWK7ferM8MU4q5qoP32yKOaPyWcmCKyJ6yIgWJOBP5eTA8lgRl7u3JinsZPqlItrjnbsTIZ5uhnLCd5KsLcsena9wmdclyV7H_Wh47_1s_y0ur_b1r7h_51gn?}`