Énoncé
C’est l’anniversaire de votre ami Adi. Vous vouliez lui faire une blague à sa fête d’anniversaire en dissimulant un message caché dans chacune des 17 saucisses préparées pour les invités. Malheureusement, le barbecue a pris feu et Adi n’a pu sauver que 16 des 17 saucisses. Peut-il malgré tout s’en sortir ?
Le code source présente le partage de clé secrète de Shamir. Ce partage de clé permet de sécuriser un secret de sorte qu’il faille au minimum $k$ pièces afin de retrouver le secret, sans quoi il est impossible d’obtenir la moindre information le concernant.
Dans le challenge, nous disposons de 16 pièces d’un secret qui devrait nécessiter 17 pièces pour le déchiffrer.
Partage de clé secrète de Shamir À l’initialisation d’une instance de la classe \verb|SSS|, un polynôme secret $f(x)$ sur $F_p$ est généré comme suit :
$$ f(x) \equiv a_0 + a_1x + a_2x^2 + a_3x^3 + \dots + a_kx^k \mod p, $$
où $p$ est un nombre premier sur 140 bits, et $a_0$ représente le secret dont nous cherchons à nous emparer. Les coefficients $a_i$ sont générés au hasard entre 0 et $2^{128}$.
class SSS:
def __init__(self, secret, k):
self.p = 931620319462745440509259849070939082848977
self.k = k
self.polynomial = [ int.from_bytes(secret) ]
for _ in range(k):
self.polynomial.append(int.from_bytes(os.urandom(16)))
La fonction eval_poly permet de calculer la valeur de $f(x)$ pour
n’importe quel $x$ donné en paramètre
class SSS:
def eval_poly(self,x):
return sum(self.polynomial[j] * (x ** j) for j in range(self.k + 1)) % self.p
Et finalement, la fonction generate_share permet de générer une pièce
de la clé en évaluant le polynôme en un point différent à chaque appel.
Le premier appel évaluera le polynôme en $x = 5,062,981,954,164,503,093$,
et les appels suivants utiliseront les entiers consécutifs.
class SSS:
def __init__(self, secret, k):
# ...
self.index = int.from_bytes(b"FCSC2024")
def generate_share(self):
self.index = self.index + 1
return self.index, self.eval_poly(self.index)
Modèle d’attaque
Le challenge consiste à retrouver le secret depuis 16 pièces d’un polynôme qui devrait en nécessiter 17 pour être retrouvé :
if __name__ == "__main__":
key = os.urandom(16)
iv = os.urandom(16)
flag = pad(open("flag.txt", "rb").read().strip(), AES.block_size)
E = AES.new(key, mode = AES.MODE_CBC, iv = iv)
flag_enc = E.encrypt(flag)
k = 16
s = SSS(key, k)
shares = [ s.generate_share() for _ in range(k) ]
data = {
"iv": iv.hex(),
"flag_enc": flag_enc.hex(),
"shares": shares,
}
print(json.dumps(data, indent = 4))
En temps normal, cela devrait être impossible, car, correctement implémenté, le partage de clé secrète de Shamir garantit une confidentialité parfaite tant que l’adversaire connaît moins de $k$ clés.
Vulnérabilité
L’erreur se situe ici au niveau de la génération du polynôme secret. Afin de garantir la sécurité du polynôme, il est nécessaire que les coefficients soient générés de manière aléatoire et uniforme entre 0 et $p - 1$. Ici, les coefficients sont générés au hasard entre $0$ et $2^{128}$, ce qui ne couvre qu’un nombre sur 2,737.
Soit $X = (x_0, x_1, \dots, x_{15}) \in F_p^{15}$ la famille des 16 antécédents utilisés pour la génération des pièces, et $Y = (y_0, y_1, \dots, y_{15}) \in F_p^{15}$ leur image respective.
Énumérons les contraintes sur nos paramètres. Étant donné la nature de $Y$, on a pour tout $i$ allant de $0$ à $15$ :
$$ a_0 + a_1 x_i + a_2 x_i^2 + \dots + a_{16}x_i^{16} + \lambda_ip= y_i $$
Concernant les coefficients $a_i$, on sait qu’ils se situent entre 0 et $2^{128}$. Dit autrement, on a pour tout $i$ allant de $0$ à $16$ :
$$ a_i = 2^{127} \pm 2^{127} $$
On peut alors représenter le problème de retrouver les coefficients $a_i$ comme une instance du problème du plus proche vecteur d’un réseau Euclidien
De manière plus explicite, on cherche à retrouver le vecteur
$$ V = (y_0, y_1, \dots, y_{15}, a_0, a_1, \dots, a_{16}) $$
qui appartient au réseau Euclidien
$$ \begin{alignat*}{7} 1 & \cdot a_0 + x_0 && \cdot a_1 + x_0^2 && \cdot a_2 + \dots + x_0^{16} && \cdot a_{16} + p && \cdot \lambda_0 + 0 && \cdot \lambda_1 + \dots + 0 && \cdot \lambda_{15} = y_0 \\ 1 & \cdot a_0 + x_1 && \cdot a_1 + x_1^2 && \cdot a_2 + \dots + x_1^{16} && \cdot a_{16} + 0 && \cdot \lambda_0 + p && \cdot \lambda_1 + \dots + 0 && \cdot \lambda_{15} = y_1 \\ & \vdots && \vdots && && \vdots && \vdots && \vdots && \vdots \\ 1 & \cdot a_0 + x_{15} && \cdot a_1 + x_{15}^2 && \cdot a_2 + \dots + x_{15}^{16} && \cdot a_{16} + 0 && \cdot \lambda_0 + 0 && \cdot \lambda_1 + \dots + p && \cdot \lambda_{15} = y_{15} \\ 1 & \cdot a_0 + 0 && \cdot a_1 + 0 && \cdot a_2 + \dots + 0 && \cdot a_{16} + 0 && \cdot \lambda_0 + 0 && \cdot \lambda_1 + \dots + 0 && \cdot \lambda_{15} = a_0 \\ 0 & \cdot a_0 + 1 && \cdot a_1 + 0 && \cdot a_2 + \dots + 0 && \cdot a_{16} + 0 && \cdot \lambda_0 + 0 && \cdot \lambda_1 + \dots + 0 && \cdot \lambda_{15} = a_1 \\ 0 & \cdot a_0 + 0 && \cdot a_1 + 1 && \cdot a_2 + \dots + 0 && \cdot a_{16} + 0 && \cdot \lambda_0 + 0 && \cdot \lambda_1 + \dots + 0 && \cdot \lambda_{15} = a_2 \\ & \vdots && \vdots && && \vdots && \vdots && \vdots && \vdots \\ 0 & \cdot a_0 + 0 && \cdot a_1 + 0 && \cdot a_2 + \dots + 1 && \cdot a_{16} + 0 && \cdot \lambda_0 + 0 && \cdot \lambda_1 + \dots + 0 && \cdot \lambda_{15} = a_{16} \end{alignat*} $$
Pour être une solution valide, $V$ doit respecter ces contraintes :
$$ \begin{align*} V_0 &= y_0 \\ V_1 &= y_1 \\ \dots\\ V_{15} &= y_{15} \\ V_{16} &= a_0 = 2^{127} \pm 2^{127} \\ V_{17} &= a_1 = 2^{127} \pm 2^{127} \\ \dots\\ V_{32} &= a_{16} = 2^{127} \pm 2^{127} \end{align*} $$
Afin de pouvoir traduire notre problème en problème du plus proche vecteur, on peut multiplier les contraintes strictes par une grande constante $C \gg 2^{127}$.
En multipliant les 16 premières lignes par $C$, on obtient un réseau généré par la base suivante :
$$ \left( \begin{pmatrix} C \\ C \\ \dots \\ C \\ 1 \\ 0 \\ 0 \\ \dots \\ 0 \end{pmatrix}, \begin{pmatrix} Cx_0 \\ Cx_1 \\ \dots \\ Cx_{15} \\ 0 \\ 1 \\ 0 \\ \dots \\ 0 \end{pmatrix}, \begin{pmatrix} Cx_0^2 \\ Cx_1^2 \\ \dots \\ Cx_{15}^2 \\ 0 \\ 0 \\ 1 \ \dots \\ 0 \end{pmatrix}, \dots, \begin{pmatrix} Cx_0^{16} \\ Cx_1^{16} \\ \dots \\ Cx_{15}^{16} \\ 0 \\ 0 \\ 0 \\ \dots \\ 1 \end{pmatrix}, \begin{pmatrix} Cp \\ 0 \\ \dots \\ 0 \\ 0 \\ 0 \\ 0 \\ \dots \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ Cp \\ \dots \\ 0 \\ 0 \\ 0 \\ 0 \\ \dots \\ 0 \end{pmatrix}, \dots, \begin{pmatrix} 0 \\ 0 \\ \dots \\ Cp \\ 0 \\ 0 \\ 0 \\ \dots \\ 0 \end{pmatrix} \right), $$
dont l’objectif est de trouver un vecteur appartenant à ce réseau étant égal à
$$ \begin{pmatrix} Cy_0 \\ Cy_1 \\ \dots \\ Cy_{15} \\ a_0 \\ a_1 \\ \dots \\ a_{16} \end{pmatrix} = \begin{pmatrix} Cy_0 \\ Cy_1 \\ \dots \\ Cy_{15} \\ 2^{127} \pm 2^{127} \\ 2^{127} \pm 2^{127} \\ \dots \\ 2^{127} \pm 2^{127} \end{pmatrix}. $$
Un tel vecteur peut être découvert à l’aide de l’algorithme de Babai.
Mise en œuvre
from sage.modules.free_module_integer import IntegerLattice
from fpylll import IntegerMatrix, CVP
from json import load
data = load(open('output.txt', 'r'))
p = 931620319462745440509259849070939082848977
G = GF(p)
pieces = [(G(x), G(y)) for x, y in data['pieces']]
C = 2^256
base = [
[C * Integer(pieces[x][0] ^ y) for x in range(16)]
+ [1 if x == y else 0 for x in range(17)]
for y in range(17)
] + [
[C*p if x == y else 0 for x in range(33)]
for y in range(16)
]
reseau = IntegerLattice(Matrix(base), lll_reduce=True)
# vecteur cible
cible = vector([C * Integer(pieces[x][1]) for x in range(16)] + [2^127] * 17)
# résolution du CVP par Babai
resultat = reseau(CVP.babai(IntegerMatrix.from_matrix(reseau.reduced_basis), cible))
# sanity check
assert resultat[:16] == cible[:16]
coefficients = resultat[-17:]
secret = coefficients[0]
print(secret) # On récupère la clé secrète
# 235565870110229829737652217435172810038