/den/face0xff/writeups
HomeMy blog
Search…
/den/face0xff/writeups
Introduction
2019
2020
FCSC Prequals 2020
Keykoolol (reverse, 500)
Macaron (crypto, 200)
Merry (crypto, 500)
SSEcret (reverse, 500)
Why not a sandbox? (pwn, 500)
European Cyber Week CTF Qualifiers 2020
DefCamp CTF 2020
ångstromCTF 2020
2021
Powered By GitBook
Merry (crypto, 500)

Description du challenge

1
Un serveur a été conçu pour utiliser un algorithme d'échange de clés avec ses clients. Cet algorithme génère et garde le même bi-clé pour plusieurs requêtes. Il notifie aussi ses clients quand l'échange a échoué et que la clé partagée n'est pas la même. Votre but est de retrouver la clé secrète du bi-clé généré par le serveur.
2
​
3
Service : nc challenges1.france-cybersecurity-challenge.fr 2001
4
​
5
Note : La version de Python utilisée par le serveur est 3.5.3 (default, Sep 27 2018, 17:25:39) [GCC 6.3.0 20170516]
Copied!

Solution

Le challenge a pour tag post-quantum mais il ne faut pas se laisser impressionner, aucune connaissance en crytographie quantique n'est nécessaire pour résoudre ce challenge. Il faut juste savoir faire du calcul matriciel de base 😃
Voici le code du serveur :
1
import sys
2
import numpy as np
3
from flag import flag
4
from zlib import compress, decompress
5
from base64 import b64encode as b64e, b64decode as b64d
6
​
7
class Server:
8
def __init__(self, q, n, n_bar, m_bar):
9
self.q = q
10
self.n = n
11
self.n_bar = n_bar
12
self.m_bar = m_bar
13
self.__S_a = np.matrix(np.random.randint(-1, 2, size = (self.n, self.n_bar)))
14
self.__E_a = np.matrix(np.random.randint(-1, 2, size = (self.n, self.n_bar)))
15
self.A = np.matrix(np.random.randint( 0, q, size = (self.n, self.n)))
16
self.B = np.mod(self.A * self.__S_a + self.__E_a, self.q)
17
​
18
### Private methods
19
def __decode(self, mat):
20
def recenter(x):
21
if x > self.q // 2:
22
return x - self.q
23
else:
24
return x
25
​
26
def mult_and_round(x):
27
return round((x / (self.q / 4)))
28
​
29
out = np.vectorize(recenter)(mat)
30
out = np.vectorize(mult_and_round)(out)
31
return out
32
​
33
def __decaps(self, U, C):
34
key_a = self.__decode(np.mod(C - np.dot(U, self.__S_a), self.q))
35
return key_a
36
​
37
### Public methods
38
def pk(self):
39
return self.A, self.B
40
​
41
def check_exchange(self, U, C, key_b):
42
key_a = self.__decaps(U, C)
43
return (key_a == key_b).all()
44
​
45
def check_sk(self, S_a, E_a):
46
return (S_a == self.__S_a).all() and (E_a == self.__E_a).all()
47
​
48
def menu():
49
print("Possible actions:")
50
print(" [1] Key exchange")
51
print(" [2] Get flag")
52
print(" [3] Exit")
53
return int(input(">>> "))
54
​
55
if __name__ == "__main__":
56
​
57
q = 2 ** 11
58
n = 280
59
n_bar = 4
60
m_bar = 4
61
​
62
server = Server(q, n, n_bar, m_bar)
63
​
64
A, B = server.pk()
65
print("Here are the server public parameters:")
66
print("A = {}".format(b64e(compress(A.tobytes())).decode()))
67
print("B = {}".format(b64e(compress(B.tobytes())).decode()))
68
​
69
nbQueries = 0
70
while True:
71
try:
72
choice = menu()
73
if choice == 1:
74
nbQueries += 1
75
print("Key exchange #{}".format(nbQueries), file = sys.stderr)
76
U = np.reshape(np.frombuffer(decompress(b64d(input("U = "))), dtype = np.int64), (m_bar, n))
77
C = np.reshape(np.frombuffer(decompress(b64d(input("C = "))), dtype = np.int64), (m_bar, n_bar))
78
key_b = np.reshape(np.frombuffer(decompress(b64d(input("key_b = "))), dtype = np.int64), (m_bar, n_bar))
79
​
80
if server.check_exchange(U, C, key_b):
81
print("Success, the server and the client share the same key!")
82
else:
83
print("Failure.")
84
​
85
elif choice == 2:
86
S_a = np.reshape(np.frombuffer(decompress(b64d(input("S_a = "))), dtype = np.int64), (n, n_bar))
87
E_a = np.reshape(np.frombuffer(decompress(b64d(input("E_a = "))), dtype = np.int64), (n, n_bar))
88
​
89
if server.check_sk(S_a, E_a):
90
print("Correct key, congratulations! Here is the flag: {}".format(flag))
91
else:
92
print("Sorry, this is not the correct key.")
93
print("Bye bye.")
94
exit(1)
95
​
96
elif choice == 3:
97
print("Bye bye.")
98
break
99
​
100
except:
101
pass
Copied!
L'idée est que l'on peut demander autant de fois que l'on veut au serveur un "key exchange", qui est un oracle à réponse binaire. Le but du challenge est de déterminer deux paramètres privés
SaS_a
 et
EaE_a
.
A l'initialisation, le serveur pose
q=211q = 2^{11}
,
n=280n = 280
,
nbar=mbar=4n_{bar} = m_{bar} = 4
 et génère deux clés privées
SaS_a
 et
EaE_a
 à valeurs dans
{−1,0,1}\{-1,0,1\}
 (oui, 2 est exclu, le randint de numpy n'agit pas comme le randint vanilla... !!).
SaS_a
 et
EaE_a
 sont de dimensions
(n,nbar)(n, n_{bar})
.
Enfin,
AA
 et
BB
 sont deux matrices publiques.
AA
 est générée aléatoirement à valeurs dans
{0, ..., q}\{0, \:..., \: q\}
 et est de taille
(n,n)(n, n)
 ;
BB
 satisfait la relation suivante :
​
B:=(ASa+Ea) mod  qB := (A S_a + E_a) \: \mod{q}
​
Étudions maintenant check_exchange. Le serveur nous demande
UU
, une matrice
(mbar,n)(m_{bar}, n)
,
CC
, une matrice
(mbar,nbar)(m_{bar}, n_{bar})
, et
keyb\text{key}_b
, une matrice aussi
(mbar,nbar)(m_{bar}, n_{bar})
.
Il vérifie alors si :
​
decode((C−USa)mod  q)=keyb\text{decode}((C - U S_a) \mod{q}) = \text{key}_b
​
decode est une fonction qui recentre les valeurs de la matrice autour de 0 (pour qu'elles passent entre
−q/2-q/2
 et
q/2q/2
 environ) puis les divise par
q/4q/4
 et les arrondit, ce qui donne une matrice à valeurs dans
{−2,−1,0,1,2}\{-2, -1, 0, 1, 2\}
.
Si l'on arrive à retrouver
SaS_a
, il sera aisé de calculer
EaE_a
. Alors comment choisir les paramètres pour faire fuiter de l'information sur
SaS_a
 ?
Ma solution (il y a certainement plusieurs techniques) est de poser
C=0C = 0
 et de choisir
U=λE1,jU = \lambda E_{1, j}
, où
λ\lambda
 est un coefficient entier à paramétrer et
Ei,jE_{i,j}
 sont les matrices de la base canonique (des zéros partout, sauf un 1 en
(i,j)(i, j)
).
Ainsi, on aura :
​
C−USa=−USa=−λE1,jSa=[−λSa,j000]∈M4,4({0, ..., q−1}) mod  qC - U S_a = -U S_a = -\lambda E_{1, j} S_a = \begin{bmatrix} & -\lambda S_{a, j} & \\ & 0 & \\ & 0 & \\ & 0 & \end{bmatrix} \in \mathcal{M}_{4, 4}(\{ 0, \:..., \: q - 1\}) \: \mod{q}
​
où
Sa,jS_{a, j}
 est la j-ème ligne de
SaS_a
 (qui contient 4 valeurs entre -1 et 1).
Les valeurs subissant dans decode la division par
q/4q/4
, on voit l'importance du facteur
λ\lambda
. En effet, sans, les coefficients
00
 et
11
 de la matrice obtenue se feraient arrondir à 0 et on ne pourrait plus les distinguer.
Je pose maintenant
λ=q/4=512\lambda = q/4 = 512
 qui donne des résultats intéressants. En effet, en raisonnant coefficient par coefficient dans la matrice, on a, en partant d'un coefficient de
Sa,jS_{a,j}
 :
    ​
    00
     reste
    00
    , est recentré en
    00
     et est arrondi à
    00
    ​
    ​
    11
     devient
    −512≡1536 mod  q-512 \equiv 1536\:\mod{q}
    , est recentré en
    −512-512
     et est arrondi à
    −1-1
    ​
    ​
    −1-1
     devient
    512512
    , est recentré en
    512512
     et est arrondi à
    11
    ​
Il suffit donc de prendre l'opposé du résultat pour obtenir la valeur d'origine. Il ne reste plus qu'à challenger l'oracle en brute-forçant toutes les matrices
4×44 \times 4
 dont la première ligne est à valeurs dans
{−1,0,1}\{-1, 0, 1\}
 (donc
34=813^4 = 81
 requêtes dans le pire cas) jusqu'à ce qu'on nous réponde succès, ce qui nous permet d'identifier une ligne de
SaS_a
.
On répète cela
n=280n = 280
 fois (soit
2268022680
 requêtes dans le pire cas) et on a réussi à déterminer
SaS_a
. Il ne reste plus qu'à utiliser :
​
Ea≡B−ASa mod  qE_a \equiv B - A S_a \: \mod{q}
​
et à soumettre la réponse
(Sa, Ea)(S_a, \:E_a)
 au serveur.
Voici l'exploit :
1
from pwn import *
2
import numpy as np
3
from zlib import compress, decompress
4
from base64 import b64encode as b64e, b64decode as b64d
5
from itertools import product
6
​
7
q = 2 ** 11
8
n = 280
9
n_bar = 4
10
​
11
LAMBDA = 512
12
​
13
s = remote('challenges1.france-cybersecurity-challenge.fr', 2001)
14
​
15
msg = s.recvuntil(b'Possible actions')
16
s.recv(1024)
17
​
18
A = msg.split(b'A = ')[1].split(b'\n')[0]
19
B = msg.split(b'B = ')[1].split(b'\n')[0]
20
​
21
A = np.reshape(np.frombuffer(decompress(b64d(A)), dtype = np.int64), (n, n))
22
B = np.reshape(np.frombuffer(decompress(b64d(B)), dtype = np.int64), (n, n_bar))
23
​
24
__S_a = np.zeros((n, n_bar), dtype = np.int64)
25
​
26
s.send(b'1\n')
27
​
28
for k in range(n):
29
U = np.zeros((n_bar, n), dtype = np.int64)
30
C = np.zeros((n_bar, n_bar), dtype = np.int64)
31
​
32
U[0][k] = LAMBDA
33
​
34
U = b64e(compress(U.tobytes()))
35
C = b64e(compress(C.tobytes()))
36
​
37
for c in product([-1, 0, 1], repeat=n_bar):
38
CMP = np.zeros((n_bar, n_bar), dtype = np.int64)
39
for i in range(n_bar):
40
CMP[0][i] = c[i]
41
CMP = b64e(compress(CMP.tobytes()))
42
​
43
s.recv(1024)
44
s.send(U + b'\n')
45
​
46
s.recv(1024)
47
s.send(C + b'\n')
48
​
49
s.recv(1024)
50
s.send(CMP + b'\n')
51
​
52
msg = s.recv(1024)
53
s.send(b'1\n')
54
​
55
if b'Success' in msg:
56
break
57
​
58
for i in range(n_bar):
59
__S_a[k][i] = -c[i]
60
​
61
print("[+] Ligne %s: %s" % (k, repr(__S_a[k])))
62
​
63
__E_a = np.mod(B - np.dot(A, __S_a), q)
64
​
65
def t(x):
66
if x == q - 1:
67
return -1
68
return x
69
​
70
__S_a = b64e(compress(np.vectorize(t)(__S_a).tobytes()))
71
__E_a = b64e(compress(np.vectorize(t)(__E_a).tobytes()))
72
​
73
print(__S_a)
74
print(__E_a)
75
​
76
s.interactive()
77
s.close()
Copied!
L'exploit est un peu long, il y a peut-être moyen de faire plus court en répartissant un peu plus l'information à travers les requêtes mais cette méthode est suffisante donc je n'ai pas cherché.
La séquelle de cette épreuve, Pippin, se résolvait de façon exactement similaire, mais il fallait remarquer que
SaS_a
 avait sur chaque ligne exactement 2 "0", 1 "1" et 1 "-1", ce qui réduit les possibilités et permet de passer en dessous de 3000 requêtes.
Enjoy !
Previous
Macaron (crypto, 200)
Next
SSEcret (reverse, 500)
Last modified 1yr ago
Copy link
Contents
Description du challenge
Solution