misc2.md

OliCyber.IT 2021 - Competizione nazionale

[misc-2] Il test di ammissione 2 (1 risoluzione)

La challenge richiede di settare a 5 tutti i contatori forniti nel numero minore possibile di mosse. Ogni contatore varia da 1 a 5 in maniera sequenziale (il successivo di 5 è 1). I comandi che abbiamo a disposizione possono influenzare più di un contatore alla volta; è quindi necessario scegliere la sequenza corretta per finire nella configurazione desiderata.

Soluzione

E' immediato dedurre dalle istruzioni del gioco che fare una mossa 5 volte equivale a non farla affatto. A differenza della challenge precedente (Il test di ammissione) in questo caso mosse diverse possono contenere gli stessi contatori.

Per risolvere la challenge possiamo modellare il problema come un sistema di equazioni lineari e utilizzare Sagemath per risolverlo. Gli step per la soluzione sono i seguenti:

• Step 1.1: creiamo un array che contiene l'incremento necessario per ogni contatore per arrivare a 5.
• Step 1.2: a partire dall'array creiamo un oggetto vector con Sagemath.
• Step 2.1: creiamo una "matrice" (un array di array) per rappresentare le mosse che abbiamo a disposizione: ogni riga corrisponde ad una mossa e contiene X elementi, con X = numero di contatori. Ognuno degli elementi vale 1 se il corrispondente contatore è contenuto nella mossa, 0 altrimenti.
• Step 2.2: a partire dall'array di array creiamo un oggetto matrix con Sagemath e lo trasponiamo. La matrice risultante avrà i contatori sulle righe e le mosse sulle colonne (trasporre = invertire righe e colonne).
• Step 3: risolviamo il sistema di equazioni lineari con Sagemath. In particolare vogliamo trovare C tale che MC = S ovvero quel vettore che rappresenta quante volte deve essere eseguita ciascuna delle mosse per ottenere, su ciascun contatore, l'incremento necessario per portarlo a 5 (ovvero per ottenere il vettore S).

Exploit

Il seguente script python implementa la soluzione proposta per ottenere la sequenza richiesta:

from pwn import remote
from sage.all import *
import logging
logging.disable()

def print_solution(C: list):
    sol = ""
    for i,c in enumerate(C):
        sol += f"{str(i+1)} " * c
    return sol.strip().encode()

def solve():

    # Step 1.1
    S = list(map(lambda x: 5 - x, stato))

    # Step 1.2
    S = vector(GF(5), S)

    # Step 2.1
    M = [[0] * len(S) for _ in range(len(mosse))]
    for i,mossa in enumerate(mosse):
        for index in mossa:
            M[i][index] += 1

    # Step 2.2
    M = matrix(GF(5), M).transpose()

    # Step 3
    C = list(M.solve_right(S))

    return print_solution(C)


r = remote("test2.challs.olicyber.it", 15005)
r.recvlines(20)

livello = r.recvline()
while livello.startswith(b"Livello"):
    stato = [int(_) for _ in r.recvline(False).decode().split()]
    mosse = []
    while True:
        s = r.recvline(False).decode()
        if s == "":
            break
        mosse.append(["ABCDEFGHIJKLMNOPQRSTUVWXYZ".index(_) for _ in s.split()])
    res = solve()
    r.sendline(res)
    r.recvlines(2)
    livello = r.recvline(False)

print(livello.decode())