Revers(ibl)e Engineering [0/2]

Divers - Difficile

Énoncé

"My game is a lot about footwork. If I move well - I play well." - Joueur de tennis peu connu

Au tennis, des déplacements optimaux font gagner des matchs - même chose ici, mais avec des circuits logiques. Recevez un circuit logique réversible effectuant une opération sur 3 bits. Renvoyez un circuit optimal équivalent. Plusieurs solutions sont possibles.

Précisions :

Les seules portes logiques réversibles utilisées seront :
- La porte NOT
- La porte CNOT (controlled NOT)
- La porte TOFFOLI
La convention de notation sera de noter les bits de contrôle en premier.
Deux circuits seront dit équivalents s'ils effectuent la même opération.
Un circuit sera dit optimal s'il n'existe aucun circuit équivalent comportant un nombre de portes logiques strictement plus petit.
Si la connexion se coupe sans message, c'est que vous avez timeout ! Pas plus de 60 secondes par circuit !

Analyse

Exemple de fonctionnement

Chargement...
Voici un circuit réversible aléatoire sur 3 bits. Donnez un circuit équivalent optimal dans le même format. Les bits de contrôle seront notés en premier.

{"gates": [["NOT", [2]], ["CNOT", [1, 0]], ["NOT", [1]], ["NOT", [1]], ["NOT", [1]], ["TOFFOLI", [1, 0, 2]], ["CNOT", [2, 0]], ["NOT", [2]]], "bits": 3}

Chargement...
Voici un circuit réversible aléatoire sur 3 bits. Donnez un circuit équivalent optimal dans le même format. Les bits de contrôle seront notés en premier.

{"gates": [["NOT", [2]], ["CNOT", [1, 0]], ["NOT", [1]], ["NOT", [1]], ["NOT", [1]], ["TOFFOLI", [1, 0, 2]], ["CNOT", [2, 0]], ["NOT", [2]]], "bits": 3}

On recoit donc un circuit reversible et on doit le simplifier. On pourrait mettre en place une logique, utiliser par exemple qiskit qui nous permettrait, dans une transposition algorithmique quantique de résoudre cette exercice mais ca prendrait du temps... Donc... Brute force ? Oui !

Logique

On veut simplifier le circuit, donc garder la même table de vérité ? Créons un script permettant d'émuler ça

python

import itertools

class Circuit:
    def __init__(self, gates):
        self.gates = gates

    def op_not(self, data, p):
        data[p] = not data[p]
        return data

    def op_cnot(self, data, p):
        co, op = p
        if data[co]:
            data[op] = not data[op]
        return data

    def op_ccnot(self, data, p):
        co1, co2, op = p
        if data[co1] and data[co2]:
            data[op] = not data[op]
        return data

    def run(self, input):
        data = input
        for gate, conf in self.gates:
            if gate == "NOT":
                data = self.op_not(data, conf[0])
            if gate == "CNOT":
                data = self.op_cnot(data, conf)
            if gate == "TOFFOLI":
                data = self.op_ccnot(data, conf)
        return data
    
    
    def truth_table(self, n_bits):
        truthtable = ""
        for inputs in itertools.product([False, True], repeat=n_bits):
            truthtable += str(list(inputs))+str(self.run(list(inputs)))
        return str(hash(truthtable))

import itertools

class Circuit:
    def __init__(self, gates):
        self.gates = gates

    def op_not(self, data, p):
        data[p] = not data[p]
        return data

    def op_cnot(self, data, p):
        co, op = p
        if data[co]:
            data[op] = not data[op]
        return data

    def op_ccnot(self, data, p):
        co1, co2, op = p
        if data[co1] and data[co2]:
            data[op] = not data[op]
        return data

    def run(self, input):
        data = input
        for gate, conf in self.gates:
            if gate == "NOT":
                data = self.op_not(data, conf[0])
            if gate == "CNOT":
                data = self.op_cnot(data, conf)
            if gate == "TOFFOLI":
                data = self.op_ccnot(data, conf)
        return data
    
    
    def truth_table(self, n_bits):
        truthtable = ""
        for inputs in itertools.product([False, True], repeat=n_bits):
            truthtable += str(list(inputs))+str(self.run(list(inputs)))
        return str(hash(truthtable))

Vous remarquerez un hash de la table de vérité, car en soit l'information ne m'interesse pas, je souhaite juste facilement comparer la table de vérité de deux circuits afin d'en déduire s'ils ont le même comportement (un equal en quelque sorte).

Préparation de notre bruteforce

python

cc_not_iter = itertools.product([0, 1, 2], repeat=3)
c_not_iter = itertools.product([0, 1, 2], repeat=2)
not_iter = itertools.product([0, 1, 2], repeat=1)

p_for_layer = []
for c in itertools.product([["NOT", not_iter], ["CNOT", c_not_iter], ["TOFFOLI", cc_not_iter]]):
    for l in c[0][1]:
        p_for_layer.append([ c[0][0], list(l)])

cc_not_iter = itertools.product([0, 1, 2], repeat=3)
c_not_iter = itertools.product([0, 1, 2], repeat=2)
not_iter = itertools.product([0, 1, 2], repeat=1)

p_for_layer = []
for c in itertools.product([["NOT", not_iter], ["CNOT", c_not_iter], ["TOFFOLI", cc_not_iter]]):
    for l in c[0][1]:
        p_for_layer.append([ c[0][0], list(l)])

L'idée est que pour chaque type de porte on détermine l'ensemble combinatoire possible en entrée et pour chaque composant de notre circuit (appelé layer ici), chercher l'ensemble combinatoire.

Solution

Il nous suffit une fois notre ensemble combinatoire donné, de tester pour chaque complexité de circuit, aka nombre de layers (ici je m'arrete à 5 pour une raison de durée de bruteforce), l'ensemble de circuit possible et vérifier la correspondance entre le circuit résultant et le circuit donné.

python

from pwn import *
import json

r = remote("challenges.404ctf.fr", 32274)

layer_max = 5

r.recvline()
r.recvline()
r.recvline()
for kjih in range(5):
    circuit = json.loads(r.recvline().decode())
    print(f"Given circuit {circuit}")

    n_bits = circuit['bits']
    gates = circuit['gates']
    c = Circuit(gates)
    c.truth_table(n_bits)
    expected = c.truth_table(n_bits)

    resolved = False

    for n_layer in range(1, layer_max+1):
        for gates in itertools.product(p_for_layer, repeat=n_layer):
            circuit = {}
            circuit["gates"] = list(gates)
            circuit["bits"] = 3
            c = Circuit(circuit["gates"])
            if c.truth_table(circuit["bits"]) == expected:
                resolved = True
                break
        if resolved:
            break

    optimized_circuit = str(circuit).replace('\'', '"')
    print(f"Optimized circuit {optimized_circuit}")

    r.sendline(optimized_circuit.encode())
    print(r.recvline())
    print(r.recvline())
r.close()

from pwn import *
import json

r = remote("challenges.404ctf.fr", 32274)

layer_max = 5

r.recvline()
r.recvline()
r.recvline()
for kjih in range(5):
    circuit = json.loads(r.recvline().decode())
    print(f"Given circuit {circuit}")

    n_bits = circuit['bits']
    gates = circuit['gates']
    c = Circuit(gates)
    c.truth_table(n_bits)
    expected = c.truth_table(n_bits)

    resolved = False

    for n_layer in range(1, layer_max+1):
        for gates in itertools.product(p_for_layer, repeat=n_layer):
            circuit = {}
            circuit["gates"] = list(gates)
            circuit["bits"] = 3
            c = Circuit(circuit["gates"])
            if c.truth_table(circuit["bits"]) == expected:
                resolved = True
                break
        if resolved:
            break

    optimized_circuit = str(circuit).replace('\'', '"')
    print(f"Optimized circuit {optimized_circuit}")

    r.sendline(optimized_circuit.encode())
    print(r.recvline())
    print(r.recvline())
r.close()

On obtient la réponse suivante :

[x] Opening connection to challenges.404ctf.fr on port 32274
[x] Opening connection to challenges.404ctf.fr on port 32274: Trying 162.19.101.153
[+] Opening connection to challenges.404ctf.fr on port 32274: Done
Given circuit {'gates': [['NOT', [2]], ['TOFFOLI', [0, 1, 2]], ['CNOT', [2, 1]], ['CNOT', [1, 0]], ['CNOT', [1, 0]], ['NOT', [2]], ['TOFFOLI', [2, 0, 1]], ['NOT', [0]]], 'bits': 3}
Optimized circuit {"gates": [["TOFFOLI", [0, 1, 2]], ["NOT", [0]], ["NOT", [1]], ["TOFFOLI", [0, 2, 1]]], "bits": 3}
b'Encore un !\r\n'
b'\r\n'
Given circuit {'gates': [['NOT', [0]], ['NOT', [1]], ['NOT', [0]], ['TOFFOLI', [0, 2, 1]], ['CNOT', [2, 1]], ['NOT', [1]], ['CNOT', [1, 0]], ['CNOT', [2, 0]]], 'bits': 3}
Optimized circuit {"gates": [["CNOT", [2, 0]], ["TOFFOLI", [0, 2, 1]], ["CNOT", [1, 0]]], "bits": 3}
b'Un autre !\r\n'
b'\r\n'
Given circuit {'gates': [['CNOT', [2, 1]], ['TOFFOLI', [1, 2, 0]], ['NOT', [2]], ['TOFFOLI', [1, 0, 2]], ['TOFFOLI', [1, 0, 2]], ['CNOT', [2, 1]], ['TOFFOLI', [0, 1, 2]], ['CNOT', [2, 1]]], 'bits': 3}
Optimized circuit {"gates": [["NOT", [1]], ["TOFFOLI", [1, 2, 0]], ["NOT", [2]], ["TOFFOLI", [0, 1, 2]], ["CNOT", [2, 1]]], "bits": 3}
b'Un dernier !\r\n'
b'\r\n'
Given circuit {'gates': [['TOFFOLI', [2, 1, 0]], ['TOFFOLI', [0, 2, 1]], ['CNOT', [0, 1]], ['TOFFOLI', [2, 0, 1]], ['TOFFOLI', [0, 1, 2]], ['CNOT', [2, 0]], ['NOT', [0]], ['CNOT', [2, 1]]], 'bits': 3}
Optimized circuit {"gates": [["NOT", [1]], ["TOFFOLI", [0, 1, 2]], ["NOT", [0]], ["TOFFOLI", [1, 2, 0]], ["CNOT", [0, 1]]], "bits": 3}
b'Bravo ! Voici le flag : 404CTF{.....................}\r\n'

[x] Opening connection to challenges.404ctf.fr on port 32274
[x] Opening connection to challenges.404ctf.fr on port 32274: Trying 162.19.101.153
[+] Opening connection to challenges.404ctf.fr on port 32274: Done
Given circuit {'gates': [['NOT', [2]], ['TOFFOLI', [0, 1, 2]], ['CNOT', [2, 1]], ['CNOT', [1, 0]], ['CNOT', [1, 0]], ['NOT', [2]], ['TOFFOLI', [2, 0, 1]], ['NOT', [0]]], 'bits': 3}
Optimized circuit {"gates": [["TOFFOLI", [0, 1, 2]], ["NOT", [0]], ["NOT", [1]], ["TOFFOLI", [0, 2, 1]]], "bits": 3}
b'Encore un !\r\n'
b'\r\n'
Given circuit {'gates': [['NOT', [0]], ['NOT', [1]], ['NOT', [0]], ['TOFFOLI', [0, 2, 1]], ['CNOT', [2, 1]], ['NOT', [1]], ['CNOT', [1, 0]], ['CNOT', [2, 0]]], 'bits': 3}
Optimized circuit {"gates": [["CNOT", [2, 0]], ["TOFFOLI", [0, 2, 1]], ["CNOT", [1, 0]]], "bits": 3}
b'Un autre !\r\n'
b'\r\n'
Given circuit {'gates': [['CNOT', [2, 1]], ['TOFFOLI', [1, 2, 0]], ['NOT', [2]], ['TOFFOLI', [1, 0, 2]], ['TOFFOLI', [1, 0, 2]], ['CNOT', [2, 1]], ['TOFFOLI', [0, 1, 2]], ['CNOT', [2, 1]]], 'bits': 3}
Optimized circuit {"gates": [["NOT", [1]], ["TOFFOLI", [1, 2, 0]], ["NOT", [2]], ["TOFFOLI", [0, 1, 2]], ["CNOT", [2, 1]]], "bits": 3}
b'Un dernier !\r\n'
b'\r\n'
Given circuit {'gates': [['TOFFOLI', [2, 1, 0]], ['TOFFOLI', [0, 2, 1]], ['CNOT', [0, 1]], ['TOFFOLI', [2, 0, 1]], ['TOFFOLI', [0, 1, 2]], ['CNOT', [2, 0]], ['NOT', [0]], ['CNOT', [2, 1]]], 'bits': 3}
Optimized circuit {"gates": [["NOT", [1]], ["TOFFOLI", [0, 1, 2]], ["NOT", [0]], ["TOFFOLI", [1, 2, 0]], ["CNOT", [0, 1]]], "bits": 3}
b'Bravo ! Voici le flag : 404CTF{.....................}\r\n'

Revers(ibl)e Engineering [0/2] ​

Énoncé ​

Analyse ​

Exemple de fonctionnement ​

Logique ​

Préparation de notre bruteforce ​

Solution ​

Revers(ibl)e Engineering [0/2]

Énoncé

Analyse

Exemple de fonctionnement

Logique

Préparation de notre bruteforce

Solution