2018::0CTF-Quals::g0g0g0

Published: May 2, 2018 (Taiwan Time) | Category: CTF

Hadding a headache, I did not spent so much time on 0CTF, which always has some fun problem to solve.

This problem give you a trace.log ( download file )

It looks like:

Entering main.init.
.0:
   t0 = *init$guard
   if t0 goto 2 else 1
.1:
   *init$guard = true:bool
   t1 = fmt.init()
Entering fmt.init.
.0:
   t0 = *init$guard
   if t0 goto 2 else 1
.1:
   *init$guard = true:bool
   t1 = strconv.init()
Entering strconv.init.
.0:
   t0 = *init$guard
   if t0 goto 2 else 1
.1:
   *init$guard = true:bool
   t1 = math.init()
Entering math.init.
.0:
   t0 = *init$guard

This is a trace log of a program, which should be written in Golang.But the trace.log looks like some LLVM IR, rather than trace generated by go tool trace. It seems like trace.log is too large to analyze, but actually this is a simple program. You can slim the trace.log by deleting some library function.

//delete init
Entering main.init.
    ...15584 lines
Leaving main.init.
//and some input and ouput function
Entering fmt.Println at /usr/local/Cellar/go/1.9.2/libexec/src/fmt/print.go:256:6.
Leaving fmt.Println, resuming main.main at /tmp/gogo.go:192:16.

Now, we can start to analyze the trace of program. The trace is easy to read, but there are some weird IR :

t15 = phi [1: t8, 6: t8, 4: t14]

This is actually call the Phi node, since LLVM uses SSA (Static Single Assignment),which means that every variable can only be assigned once.Then,what if I wrote this program:

a = 1;
if (v < 10)
    a = 2;
b = a;

We assign a value to a twice! So, it actually has more than one a.

a1 = 1;     //block 0
if (v < 10)
    a2 = 2; //block 1
b = PHI(a1, a2);    //block 3

The IR of line 4 is :

b = phi [0:a1, 1:a2]

You can understand the trace.log now. The program implement big number by array, and also some function for multipling, adding big num, finally we can derive a equation from it:

$$(x+y)(x+z)x−10(x+y)(x+z)(y+z)+(x+y)(y+z)y+(x+z)(y+z)z=0$$

It seems to be simple, but it actually is a elliptic curve…

PS. The trace.log is actually generated by ssadump