MazeOfPower

Catégorie: Reverse Difficulté: insane Flag: HTB{by_th3_p0w3r_0f_th3_m4z3!!1}

Challenge

1MB

rev_mazeofpower.zip

archive

Ouvrir

Description

---

MazeOfPower is an Insane reversing challenge. Players will first reverse engineer a Golang binary containing a maze game. They must identify a backdoor built into the game, and abuse it to win on the server.

Ce challenge tourne sur un docker, disponible sur Github

Analyse du binaire

Dans un logiciel de décompilation, direction main.main car c’est du Go.

Challenge Proof of Work

On trouve un appel à la fonction GenerateChallenge du module github.com/redpwn/pow

Si l’on se rend sur le github, on y trouve l’objectif du module et son fonctionement. On ne va pas réinventer la roue et regarder comment le challenge se résout.

// Solve solves the challenge and returns a solution proof that can be checked by Check.
func (c *Challenge) Solve() string {
	x := gmp.NewInt(0).Set(c.x) // dont mutate c.x
	for i := uint32(0); i < c.d; i++ {
		x.Exp(x, exp, mod)
		x.Xor(x, one)
	}
	return fmt.Sprintf("%s.%s", version, base64.StdEncoding.EncodeToString(x.Bytes()))
}

Le module utilise gmp, comme je suis sur Windows et que c’est une galère à installer, j’ai recoder la fonction rapidemment en Python. (Sans module pour optimiser le traitement, mon ordi prend environ 20s à le résoudre)

from base64 import b64encode, b64decode
from Crypto.Util.number import bytes_to_long, long_to_bytes

class Challenge:
    VERSION = "s"
    MOD = (1 << 1279) - 1
    EXP = 1 << 1277

    @staticmethod
    def decode(challenge: str):
        version, raw_d, raw_x = challenge.split('.')
        if version != Challenge.VERSION:
            raise ValueError('Version not supported')
        d = bytes_to_long(b64decode(raw_d))
        x = bytes_to_long(b64decode(raw_x))
        if d.bit_length() > 16:
            raise ValueError('Difficulty too long')
        return d, x

    @staticmethod
    def solve(challenge: str):
        d, x = Challenge.decode(challenge)
        for i in range(d):
            x = pow(x, Challenge.EXP, Challenge.MOD)
            x ^= 1
        return f"{Challenge.VERSION}.{b64encode(long_to_bytes(x)).decode()}"

---

Calculer la seed de l’aléatoire

Si l’on fait bien attention, quelques lignes après, un appel à math/rand.Seed est effectué, et cet appel est précédé étrangement de :

• ReadString pour récupérer notre solution au challenge PoW

• stringtoslicebyte pour transformer une string en bytes

• hash/crc32.ChecksumIEEE pour calculer un checksum de bytes et qui retourne un entier

Effectivement, quel hasard.

Un petit tour dans GDB avec des breakpoint juste avant ces fonctions nous confirme les paramètres qui leur sont passés.

1. On commence avec un break sur stringtoslicebyte qui confirme que c’est bien la solution au challenge PoW qui est passée en paramètre :

1. Ensuite on passe bien le résultat de stringtoslicebyte à la fonction de checksumIEEE, à noter le ajouté à la fin :

1. Enfin, rand.Seed qui est appelé. La fonction utilise RAX et dans RAX on a bien le résultat du checksumIEEE

On en conclu donc que la seed est le résultat du checksumIEEE sur la solution de notre challenge (avec \n un à la fin)

En python ça nous donne :

import zlib

def calculate_checksum(input_string: str) -> int:
    input_bytes = input_string.encode('utf-8')
    return zlib.crc32(input_bytes)

---

Résoudre le labyrinthe

Une fois le PoW passé et la seed de l’aléatoire cassée, on termine dans un labyrinthe sans voir les murs. Heureusement, on voit que celui-ci est généré grâce au module github.com/itchyny/maze

On peut alors explorer le github et voir que le créateur implément également une fonction de résolution. On va simplement la copier coller et la modifier un peu pour récupérer le chemin à faire en texte.

On en profite aussi pour prendre en argument la seed de l’aléatoire et générer le même labyrinthe.

package main

import (
	"fmt"
	"math/rand"
	"os"
	"strconv"
	"strings"
	"github.com/itchyny/maze"
)

func Solve(maze_in *maze.Maze) {
	if maze_in.Solved {
		return
	}
	point := maze_in.Start
	stack := []*maze.Point{point}
	solution := []*maze.Point{point}
	visited := 1 << 12
	// Repeat until we reach the goal
	for !point.Equal(maze_in.Goal) {
		maze_in.Directions[point.X][point.Y] |= visited
		for _, direction := range maze.Directions {
			// Push the nearest points to the stack if not been visited yet
			if maze_in.Directions[point.X][point.Y]&direction == direction {
				next := point.Advance(direction)
				if maze_in.Directions[next.X][next.Y]&visited == 0 {
					stack = append(stack, next)
				}
			}
		}
		// Pop the stack
		point = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		// We have reached to a dead end so we pop the solution
		for last := solution[len(solution)-1]; !maze_in.Connected(point, last); {
			solution = solution[:len(solution)-1]
			last = solution[len(solution)-1]
		}
		solution = append(solution, point)
	}
	// [MODIFICATION] c'est là dedans qu'on récupèrera le chemin à faire
	path := []int{}
	for i, point := range solution {
		if i < len(solution)-1 {
			next := solution[i+1]
			for _, direction := range maze.Directions {
				if maze_in.Directions[point.X][point.Y]&direction == direction {
					temp := point.Advance(direction)
					if next.X == temp.X && next.Y == temp.Y {
						// [MODIFICATION] et ici que l'on ajoute dedans
						path = append(path, direction)
						maze_in.Directions[point.X][point.Y] |= direction << maze.SolutionOffset
						maze_in.Directions[next.X][next.Y] |= maze.Opposite[direction] << maze.SolutionOffset
						break
					}
				}
			}
		}
	}
	maze_in.Solved = true
	// [MODIFICATION] on le print pour le récupérer avec notre Python
	println(strings.Trim(strings.Join(strings.Fields(fmt.Sprint(path)), ", "), "[]"))
}

func main() {
	seed, err := strconv.Atoi(os.Args[1])
	if err != nil {
		panic(err)
	}

	rand.Seed(int64(seed))

	m := maze.NewMaze(0x19, 0x32)
	m.Generate()
	Solve(m)
}

Concernant la taille du labyrinthe, soit on le calcul à la main avec ce que le binaire affiche, soit on le trouve dans le code, c’est 0x19 et 0x32 , autrement dit 25 de hauteur par 50 de largeur

---

Script de résolution

Pour résoudre le challenge, je suis parti sur du python qui appelle le Go pour récupérer la solution au labyrinthe

from challenge import Challenge
from utils import calculate_checksum
import subprocess
from pwnlib.tubes.remote import remote

DIRECTIONS = {1: 'k', 2: 'j', 4: 'h', 8: 'l'}

def parse_maze_solution(raw: str) -> str:
    return ''.join([DIRECTIONS[int(n)] for n in raw.split(', ')])

def solve(host, port):
    client = remote(host, port)

    data = client.recvuntil(b'solution: ').decode()
    challenge = data.split('sh -s ')[1].split('\n')[0]
    print(f"Challenge: {challenge}")

    solution = Challenge.solve(challenge)
    print(f"Solution: {solution}")
    checksum = calculate_checksum(solution + '\n')
    print(f"Checksum: {checksum}")

    cmd = ["go", "run", "./solve.go", str(checksum)]
    output = subprocess.check_output(cmd, stderr=subprocess.STDOUT, universal_newlines=True)
    maze_solution = parse_maze_solution(output)
    print(f"Maze: {maze_solution}")

    client.sendline(solution.encode())
    client.recvuntil(b'\n\n\n')
    client.sendline(maze_solution.encode())
    data = client.recvall(timeout=1)
    flag = data.splitlines()[-2].split(': ')[1]
    print(f"Flag: {flag}")

if __name__ == "__main__":
    solve('83.136.254.221', 36588)