A Nightmare On Math Street

4 minutes to read

We are given remote server to connect to:

$ nc 138.68.163.170 32335

#####################################################################  
#                                                                   #
# I told you not to fall asleep!                                    #
#                                                                   #
# A 500 question quiz is coming up.                                 #
#                                                                   #
# Be careful; Dream math works a little differently:                #
# Addition and multiplication have the REVERSE order of operation.  #
#                                                                   #
# And remember, if you fail in your sleep, you fail in real life... #
#                                                                   #
#####################################################################


[001]: 8 + 84 * 67 * 36 * 0 + (34 + 20) * 24 = ?
>

Basically, we are challenged with 500 operations, with the difference that sums go before products. This challenge reminded me of problem 18 from Advent of Code 2020, and my solution to this problem is here (written in Go).

I adapted the solution script to this challenge and use my gopwntools module in Go to interact with the remote socket server.

Solution development

The main function is:

func main() {
        hostPort := strings.Split(os.Args[1], ":")
        io := pwn.Remote(hostPort[0], hostPort[1])
        defer io.Close()

        prog := pwn.Progress("Round")

        for round := 0; round < 500; round++ {
                prog.Status(strconv.Itoa(round+1) + " / 500")

                io.RecvUntil([]byte("]: "))
                operation := io.RecvLineS()
                operation = strings.Trim(operation, "= ?\n")

                result := evaluate(operation)
                io.SendLineAfter([]byte("> "), []byte(strconv.Itoa(result)))  
        }

        prog.Success("500 / 500")
        pwn.Success(io.RecvLineS())
}

So, the key thing is how we evaluate the operations.

Evaluating operations

We must take into account that parentheses still have priority. Hence, we must evaluate parentheses first. That’s what I do in evaluate first:

func findMostInnerParentheses(op string) (int, int) {
        opening, closing := -1, -1

        for i, t := range op {
                if t == '(' {
                        opening = i
                }

                if t == ')' {
                        closing = i
                        break
                }
        }

        return opening, closing
}

func evaluate(op string) int {
        for strings.Count(op, "(") > 0 {
                opening, closing := findMostInnerParentheses(op)

                partial := evaluateArithmetic(op[opening+1:closing])

                op = op[:opening] + strconv.Itoa(partial) + op[closing+1:]  
        }

        return evaluateArithmetic(op)
}

Once I detect opening and closing parentheses, I use evaluateArithmetic to substitute the whole parentheses block by the intermediate result:

func evaluateArithmetic(op string) int {
        op = evaluateSums(op)

        terms := strings.Split(op, " ")
        result, _ := strconv.Atoi(terms[0])

        for i := 1; i < len(terms); i += 2 {
                if terms[i] == "*" {
                        num, _ := strconv.Atoi(terms[i+1])  
                        result *= num
                }
        }

        return result
}

As can be seen, the first sentence calls evaluateSums because addition has precedence over multiplication. When all sums are evaluated, the remaining operations are products, which is what the rest of the function does.

This is evaluateSums:

func evaluateSums(op string) string {
        for strings.Count(op, "+") != 0 {
                sum := findSumSign(op)

                num1, digits1 := getLastNumber(op[:sum-1])
                num2, digits2 := getFirstNumber(op[sum+2:])

                partial := num1 + num2

                op = op[:sum-1-digits1] + strconv.Itoa(partial) + op[sum+2+digits2:]  
        }

        return op
}

The above function computes sums between two numbers until there are no more sums to evaluate. Iteratively, it substitutes the sum of such two numbers by the result. These are the involved functions:

func findSumSign(op string) int {
        for i, t := range op {
                if t == '+' {
                        return i
                }
        }

        return -1
}

func getLastNumber(op string) (int, int) {
        terms := strings.Split(op, " ")
        number, _ := strconv.Atoi(terms[len(terms)-1])  

        return number, len(terms[len(terms)-1])
}

func getFirstNumber(op string) (int, int) {
        terms := strings.Split(op, " ")
        number, _ := strconv.Atoi(terms[0])

        return number, len(terms[0])
}

Flag

In the end, we can evaluate all operations and find the flag:

$ go run solve.go 83.136.253.64:35995
[+] Opening connection to 83.136.253.64 on port 35995: Done
[+] Round: 500 / 500
[+] Well done! Here's the flag: HTB{tH0s3_4r3_s0m3_k1llEr_m4th_5k1llz}  
[*] Closed connection to 83.136.253.64 port 35995

The full script can be found in here: solve.go.

There’s a trick that can be used to calculate all operations using eval in Python. The key is to replace each * by ) * ( and add initial and final parentheses. This way, eval can use the conventional operation order in the tweaked expression but satisfies the inverse order that the challenge requires. In Python, this approach takes just a few lines:

#!/usr/bin/env python3

from pwn import log, remote, sys


def main():
    if len(sys.argv) != 2:
        log.error(f'Usage: python3 {sys.argv[0]} <ip:port>')

    host, port = sys.argv[1].split(':')
    r = remote(host, int(port))

    prog = log.progress('Round')

    for i in range(500):
        r.recvuntil(b']: ')
        operation = r.recvline()[:-5].decode()

        result = eval('(' + operation.replace(' * ', ') * (') + ')')  
        r.sendlineafter(b'> ', str(result).encode())

        prog.status(f'{i + 1} / 500')

    prog.success(f'500 / 500')
    log.success(r.recvline().decode().strip())


if __name__ == '__main__':
    main()

$ python3 solve.py 83.136.253.64:35995
[+] Opening connection to 83.136.253.64 on port 35995: Done
[+] Round: 500 / 500
[+] Well done! Here's the flag: HTB{tH0s3_4r3_s0m3_k1llEr_m4th_5k1llz}  
[*] Closed connection to 83.136.253.64 port 35995