A Nightmare On Math Street
4 minutos de lectura
Se nos proporciona un servidor remoto al que conectarnos:
$ 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 = ?
>
Básicamente, nos retan a resolver 500 operaciones, con la diferencia de que las sumas tienen precedencia frente a los productos. Este reto me recordó al problema 18 de Advent of Code 2020, y mi solución a este problema está aquí (escrita en Go).
Lo que hice fue adaptar el script de solución a este reto y usar mi módulo gopwntools en Go para interactuar con el servidor remoto.
Desarrollo de la solución
La función main es:
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())
}
Entonces, lo clave es cómo evaluamos las operaciones.
Evaluando operaciones
Debemos tener en cuenta que los paréntesis aún tienen prioridad. Por lo tanto, debemos evaluar primero a los paréntesis. Eso es lo primero que hago en evaluate primero:
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)
}
Una vez que detecto los paréntesis de apertura y cierre, utilizo evaluateArithmetic para sustituir todo el paréntesis por el resultado intermedio:
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
}
Como se puede ver, la primera instrucción llama a evaluateSums porque la suma tiene precedencia sobre la multiplicación. Cuando se evalúan todas las sumas, las operaciones restantes son productos, que es lo que hace el resto de la función.
Esta es 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
}
La función anterior calcula las sumas entre dos números hasta que no hay más sumas para evaluar. Iterativamente, sustituye la suma de tales dos números por el resultado. Estas son las funciones involucradas:
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
Al final, podemos evaluar todas las operaciones y encontrar la 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
El script completo se puede encontrar aquí: solve.go.
Hay un truco que se puede usar para calcular todas las operaciones con Python y eval. La clave es reemplazar cada * por ) * ( y añadir paréntesis al principio y al final. De esta manera, eval usará el orden de operaciones convencional en la expresión modificada y obtendrá el mismo resultado que con el orden de operaciones que requiere el reto. En Python, este método se resuelve en unas pocas líneas:
#!/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