# [zer0pts CTF 2020] vmlog
###### tags: `zer0pts CTF 2020`

## overview

We're given the `vm.py` and `log.txt`. `vm.py` is the VM based implementation of a brainf\*ck-like programming language. `log.txt` is program for `vm.py` VM and its execution log(challenge description tells us that `Can you guess the source code and input?`, source code was given though).

Our task is to find the input for the program, which may produce the same log as we're given.

## solution

Observating `vm.py`, there are interesting instruction `M` its dump whole memory for the debug purpose. And it is used in the program for the VM. This may be an important clue. We can search the input to follow the mem dump.

On the other hand, reversing the given program is not so hard. It caluculates the hash of input string.

# this is the rolling hash algorithm

# 0: mod, 1: r, 2: h, 3: tmp, 4: flag
program = "M"
program += "+s+>s>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[s<<l>*<s>>l-]<<l-s"  # [0] <- 2**62 - 1 (m), [1] <- 2, [2] <- 1
program += ">l*-s*-s*-s*-s*-s*-s"  # [1] <- r
program += ">l*+++++s*-----s****s"  # [2] <- h
program += ">>l+s"  # p = 4, [4] <- 1
program += "[Ml-s"  # [4] <- 0
program += "<<l"  # load [2]
program += ">"  # p = 3
program += ",["  # input
program += "<<*"  # p = 1, reg = (h + input) * r
program += ">>s"  # [3] <- reg
program += "<<<l"  # reg <- [0]
program += ">>>"  # p = 3
program += "%"  # reg = [3] % reg (<-> tmp % m)
program += "<s"  # [2] <- reg (<->h
program += ">>l<s"  # load [4] ( = 0), then [3] <- 0
program += ">l+s"  # [4] <- 1
program += "<l]"  # load [3] to break
program += ">l]"  # load [4] if end [4] == 0
program += "<<lp"  # print [2]

Luckily, intermediate state of hash is in the memory. We can search input byte by byte.

flag = ""
with open("log.txt") as f:
    prev_h = None
    for l in f:
        try:
            arr = eval(l.strip())
            if arr[4] == 1:
                if prev_h:
                    for i in range(256):
                        if (prev_h + i) * arr[1] % arr[0] == arr[2]:
                            flag += chr(i)
                            break
                prev_h = arr[2]
        except:
            pass
print(flag)

`zer0pts{3asy_t0_f0110w_th3_l0g?}
`