Nous savons que l’opération xor (noté $\oplus$ ici) est linéaire (c’est l’addition modulo 2). Ici, notre cher ami nous construit un circuit qui prend 128 bits en entrées et 256 bits de sortie.
Donc appelons $f$ la fonction qui prend notre entrée de 128 bits et la transforme en sortie de 256 bits. Chaque bit de sortie est une combinaison de xor sur les bits d’entrées. Si on appelle $f_i$ la fonction qui donne l’i-ème bit de sortie, nous avons:
$f_i(e)= \oplus_{j=1}^{128} \alpha_j e_j $ avec $\alpha_j= 0$ ou 1, $\alpha_j$ ne peut pas valoir plus car xor 2 fois le même élément l’annule. Par linéarité du xor, on a bien $f_i(e_1\oplus e_2)=f_i(e_1)\oplus f_i(e_2)$ pour tout i. Donc tous les $f_i$ sont linéaires, donc $f$ est bien une application linéaire.
Mon but va être donc d’obtenir la représentation matricielle A de cette application linéaire (qui va de l’espace vectoriel $Z_2^{128}$ à l’espace vectoriel $Z_2^{256}$) puis une fois que je l’ai obtenu, je peux obtenir la sortie avec n’importe quelle entrée.
Pour l’obtenir, je vais profiter des questions que j’ai le droit de poser pour lui demander les sorties sur des entrées qui forment la base canonique (les vecteurs $(1,0,\dots,0), (0,1,\dots,0)$ etc.). Je dois donc poser au minimum 128 questions pour avoir la représentation matricielle de A. Heureusement, on a le droit à 130 questions après quelques tests avec le programme de notre ami.
Voici le programme que je propose:
#!/usr/bin/env python3
import pwn
import numpy as np
A=np.zeros((256,128),dtype=int)
def solution(x):
x_numeric = np.array(list(map(int, x)))
y = A.dot(x_numeric) % 2
stringy = ''.join(map(str, y))
return stringy
def construct(colonne,string):
for i in range(256):
A[i][colonne]=int(string[i])
def payload(i):
string = "0"*128
string=string[:i]+"1"+string[i+1:]
return string
def main():
conn = pwn.remote(IP,PORT)
for i in range(128):
conn.sendlineafter(">>> ",payload(i))
line=conn.recvline().decode("utf-8")
reponse=line[15:-1]
construct(i,reponse)
for i in range(2):
line=conn.recvline().decode("utf-8")
conn.sendlineafter(">>> ",payload(1))
print(line)
print(A)
conn.recvline()
conn.recvline()
x=conn.recvline().decode("utf-8")[:-1]
conn.sendlineafter(">>> ",solution(x).encode("utf-8"))
conn.interactive()
if __name__=='__main__':
main()
On sait que chaque fois que l’on donne un vecteur de la base canonique de l’espace d’entrée, on obtient une colonne de A. La fonction construct sert juste à construire colonne après colonne la matrice A, tandis que la fonction payload construit les vecteurs de la base canonique.
Ensuite, il suffit de faire une multiplication entre la matrice A et l’entrée “challenge” pour obtenir la sortie à deviner, c’est le principe de la fonction solution.
Une fois la sortie à deviner envoyée, l’application nous renvoie le flag !