Back

Vibrations - HackTM 2020 Finals

Reversing Golang Binaries

Analysis

Using Sibears' Golang Scripts we can resolve the function names but we cannot recover the structs used.

.text:00000000004A4037    lea     rcx, off_4EA840           ; io.Reader type
.text:00000000004A403E    mov     [rsp+1A0h+var_88], rcx
.text:00000000004A4046    mov     [rsp+1A0h+var_80], rax    ; os.Stdin
.text:00000000004A404E    lea     rax, off_4D2048           ; bufio.ScanLines
.text:00000000004A4055    mov     [rsp+1A0h+var_78], rax
.text:00000000004A405D    mov     [rsp+1A0h+var_70], 10000h
.text:00000000004A4069    lea     rax, [rsp+1A0h+var_88]
.text:00000000004A4071    mov     [rsp+1A0h+var_1A0], rax
.text:00000000004A4075    call    bufio__ptr_Scanner_Scan

bufio__ptr_Scanner_Scan from the name, we can say that Scan is called on a receiver that is a pointer.

So, rsp+1A0h+var_88 represents the bufio.Scanner struct. This code assigns some values to the struct

+00 io.Reader type
+08 os.Stdin
+10 bufio.ScanLines
+18 10000

The first two values at offsets +00 and +08 together form a interface type, since an interface in go has two values - type and pointer to value, corresponds to the first member of bufio.Scanner. The value at offset +10 represents the function used for splitting the input, this corresponds to the second member of bufio.Scanner. The third value 0x10000 defines the maxTokenSize

From the golang src, we have

type Scanner struct {
    r            io.Reader  // +0 - type, +8 - ptr to value
    split        SplitFunc  // +10
    maxTokenSize int        // +18
    token        []byte     // +20 - ptr to buffer, +28 - len, +30 - capacity
    buf          []byte     // +38 - ptr to buffer, +40 - len, +48 - capacity
    start        int        // +50
    end          int        // +58
    err          error      // +60
    // ...
}

So, this code reads a line of text

.text:00000000004A407A    mov     rax, [rsp+1A0h+var_68]    ; token.ptr
.text:00000000004A4082    mov     rcx, [rsp+1A0h+var_60]    ; token.len
.text:00000000004A408A    lea     rdx, [rsp+1A0h+var_138]   ; temporary buffer
.text:00000000004A408F    mov     [rsp+1A0h+var_1A0], rdx
.text:00000000004A4093    mov     [rsp+1A0h+var_198], rax
.text:00000000004A4098    mov     qword ptr [rsp+1A0h+var_190], rcx
.text:00000000004A409D    nop     dword ptr [rax]
.text:00000000004A40A0    call    runtime_slicebytetostring
func slicebytetostring(buf *tmpBuf, ptr *byte, n int) (str string)

runtime.slicebytetostring is called with two parameters - a pointer to a buffer, and the byte array that is to be converted to string, in this case, the token member of the bufio.Scanner is converted to string

Ohh! we didn’t cover how the values are returned right? let’s do that before resuming..

In Go, argument passing is done via stack, no registers are used. The layout is as follows:

[      ...       ]  ; high address
[  return_val 3  ]
[  return_val 2  ]
[  return_val 1  ]
[      ...       ]
[   argument 3   ]
[   argument 2   ]
[   argument 1   ]
[ return address ]  ; low address

So how do we distinguish between arguments and return values ?

  1. Arguments are initialized before the function call, return values are not
  2. In the function, the arguments that are read first are arguments passed by caller. The arguments that are written first are return values.

.text:00000000004A40A5    mov     rax, [rsp+1A0h+var_180]   ; string.len
.text:00000000004A40AA    mov     rcx, qword ptr [rsp+1A0h+var_190+8]   ; string.buf
.text:00000000004A40AF    mov     [rsp+1A0h+var_108], rcx
.text:00000000004A40B7    mov     [rsp+1A0h+var_100], rax
.text:00000000004A40BF    mov     rax, [rsp+1A0h+var_28]
.text:00000000004A40C7    mov     rcx, [rsp+1A0h+var_20]
.text:00000000004A40CF    cmp     cs:qword_56A9D0, rax

Following the above stack layout, rsp+1A0h+var_180 and rsp+1A0h+var_190+8 corresponds to the return values. Now we know that a string is defined as

type String struct {
    buf     *byte
    length  int
}

so, rsp+1A0h+var_190+8 points to buf and rsp+1A0h+var_180 points to the length of the string returned by runtime.slicebytetostring. The string is stored at rsp+1A0h+var_100. Recall that rsp+1A0h+var_88 represents bufio.Scanner and adding +0x60 to this address we get rsp+1A0h+var_28 and this corresponds to the err member of bufio.Scanner. error is an interface type, so rsp+1A0h+var_28 points to the type of the error and rsp+1A0h+var_20 points to the error instance

What is the error type being checked here ? If we go to the cross reference to qword_56A9D0 that writes to qword_56A9D0 we get this

.text:000000000046CC1D    lea     rax, aEof       ; "EOF"
.text:000000000046CC24    mov     [rsp+28h+var_28], rax
.text:000000000046CC28    mov     [rsp+28h+var_20], 3
.text:000000000046CC31    call    errors_New
.text:000000000046CC36    mov     rax, [rsp+28h+var_10]
.text:000000000046CC3B    mov     rcx, [rsp+28h+var_18]
.text:000000000046CC40    mov     cs:qword_56A9D0, rcx

So, the code checks if the Scan has succeeded by checking for EOF. If valid input has been received, the following code is executed

.text:00000000004A40ED    nop
.text:00000000004A40EE    call    runtime_makemap_small
.text:00000000004A40F3    mov     rax, [rsp+1A0h+var_1A0]
.text:00000000004A40F7    mov     [rsp+1A0h+mp1], rax
.text:00000000004A40FF    nop
.text:00000000004A4100    call    runtime_makemap_small
.text:00000000004A4105    mov     rax, [rsp+1A0h+var_1A0]
.text:00000000004A4109    lea     rdi, [rsp+1A0h+var_D8]
.text:00000000004A4111    xorps   xmm0, xmm0
.text:00000000004A4114    lea     rdi, [rdi-30h]
.text:00000000004A4118    nop     dword ptr [rax+rax+00000000h]
.text:00000000004A4120    mov     [rsp+1A0h+var_1B0], rbp
.text:00000000004A4125    lea     rbp, [rsp+1A0h+var_1B0]
.text:00000000004A412A    call    sub_464135
.text:00000000004A412F    mov     rbp, [rbp+0]
.text:00000000004A4133    mov     rcx, [rsp+1A0h+var_C8]
.text:00000000004A413B    mov     rdx, [rsp+1A0h+mp1]
.text:00000000004A4143    mov     [rsp+1A0h+var_98], rdx
.text:00000000004A414B    mov     [rsp+1A0h+var_90], rax

From this code, two map’s are created and put into a structure. How do I know it’s a structure? You will soon find out.. var_98 has second map, var_90 has the first map.

Next the code initializes a structure. From sub_464135, we can get the size of the structure. sub_464135 is called with the address of the structure - 0x30

.text:0000000000464135    movups  xmmword ptr [rdi+30h], xmm0
.text:0000000000464139    lea     rdi, [rdi+40h]
.text:000000000046413D    movups  xmmword ptr [rdi], xmm0
.text:0000000000464140    movups  xmmword ptr [rdi+10h], xmm0
.text:0000000000464144    movups  xmmword ptr [rdi+20h], xmm0
.text:0000000000464148    movups  xmmword ptr [rdi+30h], xmm0
.text:000000000046414C    lea     rdi, [rdi+40h]
.text:0000000000464150    retn

It initializes 5*16 bytes = 80 bytes. So the structure at rsp+1A0h+var_D8 is 80 bytes. Let’s define the struct for now as

type Unk struct {
    a uint64
    b uint64
    c uint64
    d uint64
    e uint64
    f uint64
    g uint64
    h uint64
    i uint64
    j uint64
}

Next we have

.text:00000000004A4154    lea     rax, uint64
.text:00000000004A415B    mov     [rsp+1A0h+var_1A0], rax
.text:00000000004A415F    mov     [rsp+1A0h+var_198], rcx
.text:00000000004A4164    movups  [rsp+1A0h+var_190], xmm0
.text:00000000004A4169    mov     [rsp+1A0h+var_180], 1
.text:00000000004A4172    call    runtime_growslice
.text:00000000004A4177    mov     rax, [rsp+1A0h+var_178]
.text:00000000004A417C    mov     rcx, [rsp+1A0h+var_170]
.text:00000000004A4181    mov     rdx, [rsp+1A0h+var_168]
.text:00000000004A4186    mov     [rsp+1A0h+var_B8], rdx
.text:00000000004A418E    mov     [rsp+1A0h+var_C8], rax
.text:00000000004A4196    lea     rdx, [rcx+1]
.text:00000000004A419A    mov     [rsp+1A0h+var_C0], rdx
.text:00000000004A41A2    mov     qword ptr [rax+rcx*8], 0

growslice accepts a type (uint64), a slice (var_198, var_190 and var_188) which is an empty slice since len and cap are 0 (xmm0 is 0) and the new capacity (var_180). Here, growslice allocates a new slice with capacity = 1 and returns the new slice. The new slice is stored in rsp+1A0h+var_C8. The first member of the slice is initialized to zero and the length of the slice is set to 1. This is same as

var_C8 = append(var_C8, 0)
.text:00000000004A41AA    lea     rax, [rsp+1A0h+var_D8]
.text:00000000004A41B2    mov     [rsp+1A0h+var_1A0], rax
.text:00000000004A41B6    mov     [rsp+1A0h+var_198], 134
.text:00000000004A41BF    nop
.text:00000000004A41C0    call    main_aa

main.aa takes two params - pointer to struct Unk and a integer (N), it returns nothing.

.text:00000000004A1E41    mov     rax, [rsp+50h+arg_8]  ; N
.text:00000000004A1E46    mov     rcx, [rsp+50h+arg_0]  ; *Unk
.text:00000000004A1E4B    mov     edx, 1
.text:00000000004A1E50    jmp     short loc_4A1E61
.text:00000000004A1E52
.text:00000000004A1E52 loc_4A1E52:
.text:00000000004A1E52    lea     rdi, [rbx+1]
.text:00000000004A1E56    mov     [rcx+18h], rdi
.text:00000000004A1E5A    mov     [rsi+rbx*8], rdx
.text:00000000004A1E5E    inc     rdx
.text:00000000004A1E61
.text:00000000004A1E61 loc_4A1E61:
.text:00000000004A1E61    cmp     rax, rdx
.text:00000000004A1E64    jle     loc_4A1EF8

Here we have a loop that runs N times where N is the second param passed to main.aa

.text:00000000004A1E6B    mov     rbx, [rcx+18h]    ; Unk.d
.text:00000000004A1E6F    mov     rsi, [rcx+10h]    ; Unk.c
.text:00000000004A1E73    mov     rdi, [rcx+20h]    ; Unk.e
.text:00000000004A1E77    lea     r8, [rbx+1]
.text:00000000004A1E7B    nop     dword ptr [rax+rax+00h]
.text:00000000004A1E80    cmp     r8, rdi
.text:00000000004A1E83    jbe     short loc_4A1E52
; ----------------------------------------------
.text:00000000004A1E85    mov     [rsp+50h+var_10], rdx
.text:00000000004A1E8A    lea     rax, uint64
.text:00000000004A1E91    mov     [rsp+50h+var_50], rax
.text:00000000004A1E95    mov     [rsp+50h+var_48], rsi
.text:00000000004A1E9A    mov     [rsp+50h+var_40], rbx
.text:00000000004A1E9F    mov     [rsp+50h+var_38], rdi
.text:00000000004A1EA4    mov     [rsp+50h+var_30], r8
.text:00000000004A1EA9    call    runtime_growslice
.text:00000000004A1EAE    mov     rax, [rsp+50h+var_28]
.text:00000000004A1EB3    mov     rcx, [rsp+50h+var_20]
.text:00000000004A1EB8    mov     rdx, [rsp+50h+var_18]
.text:00000000004A1EBD    mov     rbx, [rsp+50h+arg_0]

rcx points to the struct Unk whose layout we are going to find out. We know that growslice’s second param is a slice so, rsi, rbx and rdi make up the slice, ie., Unk.c, Unk.d and Unk.e represent []uint64 slice. growslice is called if the total size of elements we are trying to append exceeds the capacity.

.text:00000000004A1EC2    mov     [rbx+20h], rdx        ; update capacity
.text:00000000004A1EC6    cmp     cs:bUseBarrier?, 0
.text:00000000004A1ECD    jnz     short loc_4A1EED
.text:00000000004A1ECF    mov     [rbx+10h], rax        ; update slice's ptr
.text:00000000004A1ED3 loc_4A1ED3:
.text:00000000004A1ED3    mov     rdx, [rsp+50h+var_10]
.text:00000000004A1ED8    mov     rbx, rcx
.text:00000000004A1EDB    mov     rsi, rax
.text:00000000004A1EDE    mov     rax, [rsp+50h+arg_8]
.text:00000000004A1EE3    mov     rcx, [rsp+50h+arg_0]
.text:00000000004A1EE8    jmp     loc_4A1E52
.text:00000000004A1EED loc_4A1EED:
.text:00000000004A1EED    lea     rdi, [rbx+10h]
.text:00000000004A1EF1    call    runtime_gcWriteBarrier ; update slice's ptr and track
.text:00000000004A1EF6    jmp     short loc_4A1ED3

The new slice is then put into Unk.c

.text:00000000004A1E52    lea     rdi, [rbx+1]
.text:00000000004A1E56    mov     [rcx+18h], rdi    ; update length
.text:00000000004A1E5A    mov     [rsi+rbx*8], rdx  ; insert element at end
.text:00000000004A1E5E    inc     rdx
.text:00000000004A1E61
.text:00000000004A1E61 loc_4A1E61:
.text:00000000004A1E61    cmp     rax, rdx
.text:00000000004A1E64    jle     loc_4A1EF8        ; goto loop

and inserts i to the end of the slice. The structure now looks like

package main

type Unk struct {
    a   uint64
    b   uint64
    c   []uint64
    f   uint64
    g   uint64
    h   uint64
    i   uint64
    j   uint64
}

func aa(pp *Unk, n uint64) {
    for i := 1; i < n; i++ {
        pp.c = append(pp.c, i)
    }
    // ...
}

After the loop at lines 311-313 ends, we have the same pattern

.text:00000000004A1F12    lea     rsi, [rdx+1]
.text:00000000004A1F16    mov     [rcx+18h], rsi
.text:00000000004A1F1A    mov     [rbx+rdx*8], rax

this appends n to the slice Unk.c since when rax == n, the loop breaks

func aa(pp *Unk, n uint64) {
    for i := 1; i < n; i++ {
        pp.c = append(pp.c, i)
    }
    pp.c = append(pp.c, n)
    // ...
}

After this we have another call to growslice with

.text:00000000004A1F1E    mov     rdx, [rcx+30h]    ; slice's len
.text:00000000004A1F22    lea     rbx, [rdx+1]
.text:00000000004A1F26    mov     rsi, [rcx+28h]    ; slice's buffer
.text:00000000004A1F2A    mov     rdi, [rcx+38h]    ; slice's cap
.text:00000000004A1F2E    cmp     rdi, rbx
.text:00000000004A1F31    jb      short loc_4A1F49
.text:00000000004A1F33    lea     rbx, [rdx+1]
.text:00000000004A1F37    mov     [rcx+30h], rbx
.text:00000000004A1F3B    mov     [rsi+rdx*8], rax

that means Unk.f is a slice of type []uint64, and it appends n to the slice. Now we have the full code for main.aa

package main

type Unk struct {
    a   uint64
    b   uint64
    c   []uint64
    f   []uint64
    i   uint64
    j   uint64
}

func aa(pp *Unk, n uint64) {
    for i := 1; i < n; i++ {
        pp.c = append(pp.c, i)
    }
    pp.c = append(pp.c, n)
    pp.f = append(pp.f, n)
}

Next we have a call to main.bb

.text:00000000004A41C5    lea     rax, [rsp+1A0h+var_D8]
.text:00000000004A41CD    mov     [rsp+1A0h+var_1A0], rax
.text:00000000004A41D1    call    main_bb

From the call, main.bb takes the pointer to the structure as it’s parameter. It could be a receiver right? but it is not. because in receiver calls, the word _ptr is present in the function name that’s being called. We will cover this shortly.

.text:00000000004A2061    mov     rax, [rsp+38h+arg_0]
.text:00000000004A2066    mov     [rsp+38h+var_38], rax
.text:00000000004A206A    mov     [rsp+38h+var_30], 7Eh
.text:00000000004A2073    lea     rcx, unk_4C9900           ; 'C'
.text:00000000004A207A    mov     [rsp+38h+var_28], rcx
.text:00000000004A207F    mov     [rsp+38h+var_20], 1
.text:00000000004A2088    mov     [rsp+38h+var_18], 7Fh
.text:00000000004A2091    call    main__ptr_XYZ_b           ; main__ptr_XYZ_b

In the function that’s being called, ie., main__ptr_XYZ_b we have _ptr means the function name is b and its a “method that takes a receiver”. The receiver is a pointer to a type named XYZ. Also note the receiver is passed as a normal argument. What I mean to say is

func (this *XYZ) b(x int) {
    // ...
}

func c(this *XYZ, x int) {
    // ...
}

both pass this as the first param and x as the second param. Back to the assembly, we have

  1. The struct name is XYZ instead of Unk
  2. rsp+38h+var_28 and rsp+38h+var_20 together form a string

So, we can define this function as,

func (this *XYZ) b(x int, y string, z int) {
    // +00 this
    // +08 x
    // +10 y.buf
    // +18 y.len
    // +20 z
    // ...
}

Now this is my assumption.. we need to understand b to refine the parameters.

.text:00000000004A44A1    mov     rax, [rsp+50h+arg_0]
.text:00000000004A44A6    mov     rcx, [rax+10h]        ; XYZ.c.buf
.text:00000000004A44AA    mov     rdx, [rax+18h]        ; XYZ.c.len
.text:00000000004A44AE    mov     rbx, [rsp+50h+arg_8]
.text:00000000004A44B3    xor     esi, esi
.text:00000000004A44B5    jmp     short loc_4A44C0
.text:00000000004A44B7 loc_4A44B7:
.text:00000000004A44B7    inc     rsi
.text:00000000004A44BA    nop     word ptr [rax+rax+00h]
.text:00000000004A44C0
.text:00000000004A44C0 loc_4A44C0:
.text:00000000004A44C0    cmp     rsi, rdx
.text:00000000004A44C3    jge     loc_4A45AA

This loop runs for the length of the slice XYZ.c

.text:00000000004A44C9    mov     rdi, [rcx+rsi*8]
.text:00000000004A44CD    cmp     rdi, rbx              
.text:00000000004A44D0    jnz     short loc_4A44B7
.text:00000000004A44D2    mov     rcx, [rax+48h]
.text:00000000004A44D6    lea     rdx, stru_4B3D80      ; mapType
.text:00000000004A44DD    mov     [rsp+50h+var_50], rdx
.text:00000000004A44E1    mov     [rsp+50h+var_48], rcx
.text:00000000004A44E6    mov     rcx, [rsp+50h+arg_10]
.text:00000000004A44EB    mov     [rsp+50h+var_40], rcx
.text:00000000004A44F0    mov     rbx, [rsp+50h+arg_18]
.text:00000000004A44F5    mov     [rsp+50h+var_38], rbx
.text:00000000004A44FA    call    runtime_mapaccess2_faststr
.text:00000000004A44FF    cmp     [rsp+50h+var_28], 0

From the go source, we get

func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool)

So, from this snippet, we can get the map type :)

type mapType struct {
    rtype
    key    *rtype // map key type
    elem   *rtype // map element (value) type
    bucket *rtype // internal bucket structure
    // ...
}
.rodata:00000000004B3D80 stru_4B3D80     type <8, 8, 1A03D3F1h, 2, 8, 8, MAP or 20h, 0, offset unk_4E6424, 3CE4h, 0>
.rodata:00000000004B3DB0                 dq offset string_autogen_8VFFMU
.rodata:00000000004B3DB8                 dq offset bool

So, we know that the map has the key type string and values are bool and secondly rax+48h is the pointer to the map *hmap. So XYZ.j is a map[string]bool and the key to be searched for in the map is y. We are expecting two return values - a pointer to the entry (rsp+50h+var_30) and a boolean (rsp+50h+var_28) that denotes whether the entry exists.

If the entry that we are searching for exists, we assign the value to 1

.text:00000000004A4598    call    runtime_mapassign_faststr
.text:00000000004A459D    mov     rax, [rsp+50h+var_30] ; pointer to entry
.text:00000000004A45A2    mov     byte ptr [rax], 1

And then,

.text:00000000004A4524    mov     rax, [rsp+50h+arg_0]
.text:00000000004A4529    mov     rax, [rax+40h]        ; XYZ.i
.text:00000000004A452D    lea     rcx, mapmain_transitionuint64
.text:00000000004A4534    mov     [rsp+50h+var_50], rcx
.text:00000000004A4538    mov     [rsp+50h+var_48], rax
.text:00000000004A453D    lea     rax, [rsp+50h+var_20]
.text:00000000004A4542    mov     [rsp+50h+var_40], rax
.text:00000000004A4547    call    runtime_mapassign
.text:00000000004A454C    mov     rax, [rsp+50h+var_38]
.text:00000000004A4551    mov     rcx, [rsp+50h+arg_20]
.text:00000000004A4556    mov     [rax], rcx
.text:00000000004A4559    mov     [rsp+50h+arg_28], 1
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

we now know that type of Unk.i is map[transition]uint64 and it is indexed using a structure at rsp+50h+var_20 and the value is set to z (arg_20). Can we find the layout of transition ? Yes, we can. Also, the type of z is uint64 (inferred from the type of map)

.text:00000000004A4506    mov     rax, [rsp+50h+arg_8]
.text:00000000004A450B    mov     [rsp+50h+var_20], rax
.text:00000000004A4510    mov     rax, [rsp+50h+arg_10]
.text:00000000004A4515    mov     [rsp+50h+var_18], rax
.text:00000000004A451A    mov     rax, [rsp+50h+arg_18]
.text:00000000004A451F    mov     [rsp+50h+var_10], rax

Let’s recall. arg_0 is the method receiver (*XYZ), arg_8 is an integer, arg_10 and arg_18 together form a string. So we get,

type transition struct {
    srcState    uint64
    input       string
}

Now we have,

type XYZ struct {
    a   uint64                  // +00
    b   uint64                  // +08
    c   []uint64                // +10
    f   []uint64                // +28
    i   map[transition]uint64   // +40
    j   map[string]bool         // +48
}

type transition struct {
    srcState    uint64          // +00
    input       string          // +08
}

func (this *XYZ) b(t transition, z uint64) int {
    for i := 0; i < len(this.c); i++ {
        if this.c[i] == i {
            if _, ok := this.j[t.input]; !ok {
                this.j[t.input] = true
            }
            this.i[t] = z
            return 1
        }
    }
    return 0
}

Wait. How do we know it returns a int ? When the function returns, it writes to an argument which is never read, and it occurs after the input parameters, so it is the return value. The strong possibility is that the return type may be a bool instead of int

Back to main.bb, it calls XYZ.b many times with different values

.text:00000000004A41D6    lea     rax, [rsp+1A0h+var_D8]    ; *XYZ
.text:00000000004A41DE    mov     [rsp+1A0h+var_1A0], rax
.text:00000000004A41E2    lea     rax, [rsp+1A0h+var_108]   ; our input
.text:00000000004A41EA    mov     [rsp+1A0h+var_198], rax
.text:00000000004A41EF    call    main__ptr_XYZ_z ; main__ptr_XYZ_z
.text:00000000004A41F4    cmp     byte ptr [rsp+1A0h+var_190], 0
.text:00000000004A41F9    jz      loc_4A438

Similarly, z is a method of XYZ and takes one param - the input we read using bufio.Scanner.Scan. Note that the return value is read as byte byte ptr [rsp+1A0h+var_190]

func (this *XYZ) z(input string) bool {
    // ...
}

is this the correct signature?
No, it is not, since string consumes two words - ptr and len. But here we are passing the address of var_108. So, the correct signature is

func (this *XYZ) z(input *string) bool {
    // ...
}

Why did i use return type as bool? It can be any integer of size <= 8 bytes. The cmp following the function call (cmp byte ptr [rsp+1A0h+var_190], 0) reads only one byte. Now it can be a byte. Why bool, not byte? Because in XYZ.z the return value is assigned either 0 or 1. Which makes bool a stronger possibility than byte.

.text:00000000004A4641    mov     rax, [rsp+68h+pszInput]
.text:00000000004A4646    mov     rcx, [rax]
.text:00000000004A4649    mov     [rsp+68h+m_pszInp], rcx
.text:00000000004A464E    mov     rax, [rax+8]
.text:00000000004A4652    mov     [rsp+68h+m_dwLen], rax
.text:00000000004A4657    xor     edx, edx
.text:00000000004A4659    jmp     short loc_4A466A
.text:00000000004A465B loc_4A465B:
.text:00000000004A465B    mov     rax, [rsp+68h+m_dwLen]
.text:00000000004A4660    mov     rcx, [rsp+68h+m_pszInp]
.text:00000000004A4665    mov     rdx, [rsp+68h+var_38]
.text:00000000004A466A loc_4A466A:
.text:00000000004A466A    cmp     rdx, rax
.text:00000000004A466D    jge     loc_4A4737

It runs a loop for iterating through the input string. So, are we iterating through bytes or runes ?

.text:00000000004A4673    movzx   ebx, byte ptr [rcx+rdx]
.text:00000000004A4677    nop     word ptr [rax+rax+00000000h]
.text:00000000004A4680    cmp     ebx, 80h
.text:00000000004A4686    jge     loc_4A4716
; ....
.text:00000000004A4716    mov     [rsp+68h+var_68], rcx
.text:00000000004A471A    mov     [rsp+68h+var_60], rax
.text:00000000004A471F    mov     [rsp+68h+var_58], rdx
.text:00000000004A4724    call    runtime_decoderune
.text:00000000004A4729    mov     ebx, dword ptr [rsp+68h+var_50]
func decoderune(s string, k int) (r rune, pos int)

ebx points to the current byte in the loop. If the value of the byte is negative ( >= 0x80 ), that means it’s utf-8 multibyte string. runtime.decoderune decodes a multibyte utf-8 sequence as a rune and a returns the rune and the updated index, ie., pos-k is the rune length in bytes

.text:00000000004A468F    mov     [rsp+68h+var_38], rdx ; next rune index
.text:00000000004A4694    lea     rax, [rsp+68h+var_3C]
.text:00000000004A4699    mov     [rsp+68h+var_68], rax ; temporary buffer
.text:00000000004A469D    movsxd  rax, ebx
.text:00000000004A46A0    mov     [rsp+68h+var_60], rax ; rune
.text:00000000004A46A5    call    runtime_intstring

runtime.intstring takes a rune and converts into a string. The compiler uses intstring when we cast a rune to a string string(rune). The returned string is placed in rsp+68h+var_58

.text:00000000004A46AA    mov     rax, [rsp+68h+var_58] ; ptr to string
.text:00000000004A46AF    mov     rcx, [rsp+68h+var_50] ; len of string
.text:00000000004A46B4    mov     rdx, [rsp+68h+this]
.text:00000000004A46B9    mov     rbx, [rdx+8]
.text:00000000004A46BD    mov     [rsp+68h+var_20], rbx
.text:00000000004A46C2    mov     [rsp+68h+var_18], rax
.text:00000000004A46C7    mov     [rsp+68h+var_10], rcx
.text:00000000004A46CC    mov     rax, [rdx+40h]
.text:00000000004A46D0    lea     rcx, mapmain_transitionuint64
.text:00000000004A46D7    mov     [rsp+68h+var_68], rcx
.text:00000000004A46DB    mov     [rsp+68h+var_60], rax
.text:00000000004A46E0    lea     rax, [rsp+68h+var_20]
.text:00000000004A46E5    mov     [rsp+68h+var_58], rax
.text:00000000004A46EA    call    runtime_mapaccess2
.text:00000000004A46EF    mov     rax, [rsp+68h+var_50]         ; ptr to entry
.text:00000000004A46F4    mov     rax, [rax]
.text:00000000004A46F7    cmp     byte ptr [rsp+68h+var_48], 0  ; entry exists?
.text:00000000004A46FC    jz      short loc_4A470C
.text:00000000004A46FE    mov     rcx, [rsp+68h+this]
.text:00000000004A4703    mov     [rcx+8], rax
.text:00000000004A4707    jmp     loc_4A465B

A transition instance is constructed using {srcState: this.b, input: string(rune)}. This instance is used to index the map this.i. If the value exists, the value is assigned to this.b.

When the loop terminates, another method is called

.text:00000000004A4737    mov     rax, [rsp+68h+this]
.text:00000000004A473C    mov     [rsp+68h+var_68], rax
.text:00000000004A4740    call    main__ptr_XYZ_x ; main__ptr_XYZ_x
.text:00000000004A4745    movzx   eax, byte ptr [rsp+68h+var_60]
.text:00000000004A474A    mov     [rsp+68h+retVal], al

At source level, we have something like this

func (this *XYZ) z(input *string) bool {
    i := 0
    for i < len(*input) {
        b := rune((*input)[i])
        if b >= 0x80 {
            b, i = runtime.decoderune(*input, i)
        } else {
            i++
        }
        t := transition{srcState: this.b, input: string(b)}
        if v, ok := this.i[t]; ok {
            this.b = v
        }
    }
    return this.x()
}

Looks weird right? Yes, because we are too verbose. Let’s cleanup a bit, shall we?

func (this *XYZ) z(input *string) bool {
    for i, b := range *input {
        t := transition{srcState: this.b, input: string(b)}
        if v, ok := this.i[t]; ok {
            this.b = v
        }
    }
    return this.x()
}

Let’s now analyze XYZ.x

.text:00000000004A45E0    mov     rax, [rsp+arg_0]
.text:00000000004A45E5    mov     rcx, [rax+28h]    ; XYZ.f.ptr
.text:00000000004A45E9    mov     rdx, [rax+30h]    ; XYZ.f.len
.text:00000000004A45ED    xor     ebx, ebx
.text:00000000004A45EF    jmp     short loc_4A45F4
.text:00000000004A45F1 loc_4A45F1:
.text:00000000004A45F1    inc     rbx
.text:00000000004A45F4
.text:00000000004A45F4 loc_4A45F4:
.text:00000000004A45F4    cmp     rbx, rdx
.text:00000000004A45F7    jge     short loc_4A460C
.text:00000000004A45F9    mov     rsi, [rcx+rbx*8]
.text:00000000004A45FD    mov     rdi, [rax+8]      ; XYZ.b
.text:00000000004A4601    cmp     rsi, rdi
.text:00000000004A4604    jnz     short loc_4A45F1
.text:00000000004A4606    mov     [rsp+arg_8], 1
.text:00000000004A460B    retn
.text:00000000004A460C loc_4A460C:
.text:00000000004A460C    mov     [rsp+arg_8], 0
.text:00000000004A4611    retn

This function is does a linear search…

func (this *XYZ) x() bool {
    for i := 0; i < len(this.f); i++ {
        if this.f[i] == this.b {
            return true
        }
    }
    return false
}

Summarizing till now,

type XYZ struct {
    a   uint64                  // +00
    b   uint64                  // +08
    c   []uint64                // +10
    f   []uint64                // +28
    i   map[transition]uint64   // +40
    j   map[string]bool         // +48
}

type transition struct {
    srcState    uint64          // +00
    input       string          // +08
}

func aa(pp *XYZ, n uint64) {
    for i := 1; i < n; i++ {
        pp.c = append(pp.c, i)
    }
    pp.c = append(pp.c, n)
    pp.f = append(pp.f, n)
}

func (this *XYZ) b(t transition, z uint64) int {
    for i := 0; i < len(this.c); i++ {
        if this.c[i] == i {
            if _, ok := this.j[t.input]; !ok {
                this.j[t.input] = true
            }
            this.i[t] = z
            return 1
        }
    }
    return 0
}
func (this *XYZ) z(input *string) bool {
    for i, b := range *input {
        t := transition{srcState: this.b, input: string(b)}
        if v, ok := this.i[t]; ok {
            this.b = v
        }
    }
    return this.x()
}

func (this *XYZ) x() bool {
    for i := 0; i < len(this.f); i++ {
        if this.f[i] == this.b {
            return true
        }
    }
    return false
}

Looks unreadable, right? Let’s make it meaningful..

type Automata struct {
    a              uint64                  // +00
    currState      uint64                  // +08
    states         []uint64                // +10
    finalStates    []uint64                // +28
    transitions    map[transition]uint64   // +40
    visited        map[string]bool         // +48
}

type transition struct {
    srcState    uint64          // +00
    input       string          // +08
}

func InitStates(pp *Automata, n uint64) {
    for i := 1; i < n; i++ {
        pp.states = append(pp.states, i)
    }
    pp.states = append(pp.states, n)
    pp.finalStates = append(pp.finalStates, n)
}

func (this *Automata) AddTransition(t transition, nextState uint64) int {
    for i := 0; i < len(this.states); i++ {
        if this.states[i] == i {
            if _, ok := this.visited[t.input]; !ok {
                this.visited[t.input] = true
            }
            this.transitions[t] = nextState
            return 1
        }
    }
    return 0
}
func (this *Automata) IsAccepted(input *string) bool {
    for i, b := range *input {
        t := transition{
            srcState: this.currState,
            input: string(b),
        }
        if v, ok := this.transitions[t]; ok {
            this.currState = v
        }
    }
    return this.IsFinalState()
}

func (this *Automata) IsFinalState() bool {
    for i := 0; i < len(this.finalStates); i++ {
        if this.finalStates[i] == this.state {
            return true
        }
    }
    return false
}

Now the code looks logical…

Back to main.main, if the currState is not in one of the finalStates the main__ptr_XYZ_z which is IsFinalState, returns false. And it prints "Maybe next year?"

It then iterates over every rune in the input and printing each character with a delay of 1sec and then calls main.c() with the pointer to the input string as the argument.

func c(input *string) {
    bb := []byte("very big hex string")
    n, _ := hex.Decode(bb, bb)
    key := md5.Sum([]byte(*input))
    block, _ := aes.NewCipher(key[:0x10])
    sl := []byte(*input)
    stream := cipher.NewCTR(block, sl[0x14:0x24])
    dst := make([]uint8, 0x400, 0x400)
    stream.XORKeyStream(dst, bb[:n])
    fmt.Println(string(dst))
}

Solution

I quickly wrote an IDAPy script to extract the transition table

state = 0
start = 0x4A206A
end = 0x4A3C4A
auto = []

for i in Heads(start, end):
    d = GetDisasm(i).strip()
    if d.startswith('mov'):
        if GetOpType(i, 1) == 5:
            if state == 0:
                from_state = int(GetOperandValue(i, 1))
                state = 1
            elif state == 2:
                # skip len
                state = 3
            elif state == 3:
                next_state = int(GetOperandValue(i, 1))
                auto.append((from_state, chr(on), next_state))
                state = 0
    elif d.startswith('lea'):
        if state == 1:
            on = Byte(GetOperandValue(i, 1))
            state = 2

fsm = {}
for i, ch, j in fsm:
    fsm[i] = (ch, j)

Now it’s easy to solve. We just have to follow the transition table to the final state which is the end of the input

s = ''
state = 0
final_state = 134
while state != final_state:
    ch, state = fsm[state]
    s += ch

print(s)

this prints CFFGFEDDDGGAGFECCAABAGFDCCDGEFCFFGFEDDDGGAGFECCAABAGFDCCDGEFCFFFEEFEDCGAGFCCCCDGEFCFFGFEDDDGGAGFECCAABAGFDCCDGEFCFFFEEFEDCGAGFCCCCDGEF

running the decryptor,

package main

import (
    "fmt"
    "encoding/hex"
    "crypto/aes"
    "crypto/md5"
    "crypto/cipher"
)

func main() {
    input := "CFFGFEDDDGGAGFECCAABAGFDCCDGEFCFFGFEDDDGGAGFECCAABAGFDCCDGEFCFFFEEFEDCGAGFCCCCDGEFCFFGFEDDDGGAGFECCAABAGFDCCDGEFCFFFEEFEDCGAGFCCCCDGEF"
    bb := []byte("blob at 0x4D1C13")
    n, _ := hex.Decode(bb, bb)
    key := md5.Sum([]byte(input))
    block, _ := aes.NewCipher(key[:0x10])
    sl := []byte(input)
    stream := cipher.NewCTR(block, sl[0x14:0x24])
    dst := make([]uint8, 0x400, 0x400)
    stream.XORKeyStream(dst, bb[:n])
    fmt.Println(string(dst))
}

we get

----------------------------------------------------------------------------------------
| (Hopefully) You just played a (baby) version of Merry Christmas on your keyboard!    |
| Congrats and HackTM{m3rry_xm4s_and_4_b3tt3r_2021}                                    |
|                                                                                      |
| https://www.youtube.com/watch?v=xm4qSgLVDcs                                          |
----------------------------------------------------------------------------------------
Built with Hugo
Theme Stack designed by Jimmy