Paramètres
Le code source propose une implémentation du cryptosystème
Kyber.
Les meta-paramètres du système sont définis dans l’initialisation de la
classe Kzber :
class Kzber:
def __init__(self, q = 3329, d = 256, k = 2, B = 2):
self.q = q
self.d = d
self.k = k
self.B = B
Zq, Y = PolynomialRing(GF(q), 'Y').objgen()
R, X = Zq.quotient_ring(Y**d - 1, 'X').objgen()
self.R = R
self.X = X
self._keygen()
Le système travaille en particulier sur l’anneau $R = \mathbb{Z}_q[X]/\langle X^d-1 \rangle$, c’est-à-dire l’anneau des polynômes de degré $d=256$ ayant des coefficients dans $\mathbb{Z}_q$ (les entiers modulo $3329$), où les polynômes eux-mêmes sont considérés modulo $X^d-1$.
Génération des clés
Kyber repose sur le problème de l’apprentissage avec erreurs. Le code source propose plusieurs méthodes afin de générer des polynômes à coefficients faibles, et ainsi des vecteurs à coefficients faibles :
def _sample_short_poly(self):
coeffs = [randint(-self.B, self.B) for i in range(self.d)]
return self.R(coeffs)
def _sample_short_vector(self):
return vector(self.R, [self._sample_short_poly(), self._sample_short_poly()]).column()
La fonction _sample_short_poly génère un polynôme court dans $R$
ayant tous ses coefficients entre $-2$ et $2$.
La fonction _sample_short_vector génère
un vecteur de deux polynômes courts.
Vient ensuite la fonction responsable de la génération des clés :
def _keygen(self):
A = random_matrix(self.R, 2, 2)
s = self._sample_short_vector()
e1 = self._sample_short_vector()
t = A * s + e1
self.sk = s
self.pk = (A, t)
La fonction génère $A$ une matrice aléatoire dans $\mathcal M_2(R)$. On génère également $s$, la clé privée, un vecteur court dans $R$.
Comme dans le problème de l’apprentissage avec erreurs, on enregistre dans $t$ une approximation de $A \cdot s$, avec une petite erreur $e_1$ rajoutée ($e_1$ étant un vecteur court).
$A$ et $t$ forment la clé publique, et $s$ forme la clé privée.
Chiffrement
def encrypt(self, m):
A, t = self.pk
r = self._sample_short_vector()
e2 = self._sample_short_vector()
e3 = self._sample_short_poly()
u = r.transpose() * A + e2.transpose()
v = r.transpose() * t + e3 + (int(round(self.q/2)) * self.R(m))
return u, v
Afin de chiffrer un bit $m$, on choisit notre propre vecteur court secret $r$, et on considère le produit $r \cdot t$.
Comme $t \approx A \cdot s$, et que seul le détenteur de la clé privée peut connaître $s$, on profite de ce fait pour permettre à cette personne uniquement d’approximer elle-même $r \cdot t$ sans révéler $r$ : Si on donne une approximation $u \approx r \cdot A$, le détenteur de la clé privée peut simplement multiplier $u$ par $s$ et obtenir $u\cdot s \approx r \cdot A \cdot s \approx r \cdot t$.
En envoyant une approximation de $r \cdot A$, alors seul l’expéditeur du message et le détenteur de la clé privée $s$ sont en mesure de calculer une approximation de $r \cdot t$. Vu qu’on possède alors tous les deux une vague idée d’un polynôme secret, on en profite pour s’en servir afin de faire passer notre bit secret $m$ en l’ajoutant au coefficient constant de ce polynôme secret commun, en envoyant $v \approx r \cdot t + \left\lfloor \frac q2 \right\rfloor \cdot m$.
Pour déchiffrer, le destinataire utilise $u$ pour avoir sa propre approximation de $r \cdot t$, et en enlevant $r \cdot t$ à $v$, il obtient une approximation de $\left\lfloor \frac q2 \right\rfloor \cdot m$. Si cette valeur se rapproche plutôt de $0$, alors $m$ était vraisemblablement $0$, et si cette valeur se rapproche plutôt de $\frac q2$, alors $m$ était vraisemblablement $1$.
Kyber permet normalement de chiffrer jusqu’à $d$ bits en même temps, en rajoutant $0$ ou $\left\lfloor \frac q2 \right\rfloor$ à chacun des $d$ coefficients de $r \cdot t$. La fonction de déchiffrement donné dans l’énoncé permet de déchiffrer les $d$ bits chiffrés, même si la fonction de chiffrement donnée ne permet d’en chiffrer qu’un.
def decrypt(self, c):
u, v = c
w = (v - u * self.sk)[0, 0]
coeffs = list(w)
coeffs = [int(wi) if int(wi) < self.q//2 else int(wi) - self.q for wi in coeffs]
return [0 if abs(wi) <= self.q//4 else 1 for wi in coeffs]
Modèle
Le serveur effectue 128 chiffrements Kyber pour chacun des 128 bits de la clé AES chiffrant le flag. L’objectif est de récupérer depuis ces 128 chiffrés les 128 bits de la clé, pour ainsi déchiffrer le flag :
PKE = Kzber()
A, t = PKE.pk
sk = randint(0, 2 ** 128)
C = [ PKE.encrypt(int(m)) for m in f"{sk:0128b}" ]
flag = open("flag.txt", "rb").read()
iv = os.urandom(16)
E = AES.new(int.to_bytes(sk, 16), AES.MODE_CBC, iv = iv)
enc = E.encrypt(pad(flag, 16))
print(base64.b64encode(zlib.compress(pickle.dumps({
"A": A,
"t": t,
"C": C,
"flag" : {
"iv": iv,
"enc": enc,
}
}))).decode())
Vulnérabilité
La principale erreur dans le code réside dans l’anneau utilisé. Dans un chiffrement Kyber traditionnel, on utilise plutôt $R = \mathbb Z_q / \langle X^d + 1 \rangle$, car $X^d + 1$ est un polynôme irréductible. Dans notre cas, on trouve $R = \mathbb Z_q / \langle X^d - 1 \rangle$, et $X^d - 1$ se factorise très bien en $(X-1)(X+1)\dots$. (Pour être plus précis, $X^d - 1$ est le produit de tous les k-polynômes cyclotomiques, où $k$ divise $d$).
Vu que $d$ est pair, on trouve notamment le fait que $1$ et $-1$ sont des racines de $X^d - 1$. Prenons un cas concret. Soit $m$ un bit secret (0 ou 1), chiffré avec Kzber. On a alors
- $u = r\cdot A + e_2$, et
- $v = r \cdot t + e_3 + \left\lfloor \frac q2 \right\rfloor \cdot m$.
Dans $R = \mathbb Z_q / \langle X^d - 1 \rangle$, comme $1$ et $-1$ sont des racines de $X^d - 1$, l’évaluation d’un polynôme en $1$ ou $-1$ forme un morphisme d’anneaux vers $\mathbb Z_q$. On note alors $A(1) = A(X)|_{X=1}$ la matrice que l’on obtient en évaluant tous les polynômes de $A$ en $X = 1$. De manière similaire, on notera $A(-1) = A(X)|_{X=-1}$, et également $r(1)$, $r(-1)$, $t(1)$, $t(-1)$, $e_2(1)$, $e_2(-1)$, $\dots$, pour représenter l’évaluation d’un polynôme, vecteur de polynômes ou matrice de polynômes en un point donné.
En Sage, voila un code un peu moche qui effectue ces évaluations :
def lift_eval_poly(P, v):
# Évalue un polynôme dans R en v, ce qui donne un entier dans Zq
return P.lift()(v)
def lift_eval_matrix(M, v):
# Évalue chaque polynôme de la matrice M
R = M.base_ring()
K = R.base_ring()
return Matrix(K, [[lift_eval_poly(e, v) for e in line] for line in M])
def lift_eval_vector(V, v):
# Évalue chaque polynôme du vecteur colonne V
R = V.base_ring()
K = R.base_ring()
return vector(K, [lift_eval_poly(e[0], v) for e in V]).column()
Comme l’évaluation en $1$ ou $-1$ forme un morphisme d’anneaux, on retrouve alors quatre équations dans $\mathbb Z_q$ :
- $u(1) = r(1)\cdot A(1) + e_2(1)$,
- $v(1) = r(1) \cdot t(1) + e_3(1) + \left\lfloor \frac q2 \right\rfloor \cdot m$,
- $u(-1) = r(-1)\cdot A(-1) + e_2(-1)$, et
- $v(-1) = r(-1) \cdot t(-1) + e_3(-1) + \left\lfloor \frac q2 \right\rfloor \cdot m$.
Comme $r$, $e_2$ et $e_3$ sont des vecteurs/polynômes courts, leurs polynômes évalués en $1$ ou $-1$ donneront une valeur entre $-2d$ et $2d$. Comme $r$, $e_2$ et $e_3$ ont été choisi au hasard, on peut déterminer la probabilité que n’importe quel polynôme dans $r$, $e_2$ ou $e_3$ donne une valeur $k$ spécifique une fois évalué en $1$ ou $-1$.
Chacun des coefficients du polynôme vaut une valeur aléatoire entre $-2$ et $2$ de manière uniforme. Évaluer ce polynôme en $1$ ou $-1$ revient à faire la somme de $d$ variables aléatoires uniformes entre $-2$ et $2$. On peut approximer cette loi en construisant une loi d’espérance $0$ et de variance $B \cdot d = 512$, où même trouver les valeurs exactes avec un peu de programmation dynamique :
proba = [0] * q
proba[0] = 1
for k in range(d):
# Invariant : proba[x] indique la probabilité que la somme de
# k variables aléatoires uniformes entre -B et B
# donne x.
proba2 = [0] * q
for x in range(q):
for i in range(-B, B+1):
proba2[x] += (proba[(x + i) % q]) / (2 * B + 1)
proba = proba2
Maintenant, considérons le vecteur secret $r$ du chiffrement. $r(1)$ (qui est un vecteur de deux entiers entre $-512$ et $512$) peut prendre seulement 262,144[^1] valeurs différentes. [^1]: En pratique, la probabilité qu’une valeur de $r$ donnée soit inférieure à $-96$ ou supérieure à $96$ est inférieure à 0.0019%, donc on peut se limiter à moins de 10,000 valeurs différentes de $r(1)$ sans trop de craintes
Pour une valeur de $r(1)$ donnée, on retrouve la valeur correspondante de $e_2(1)$ : $$e_2(1) = u(1) - r(1) \cdot A(1)$$
Puis on retrouve également ce qui est censé être une estimation de la valeur de $\left\lfloor \frac q2 \right\rfloor \cdot m$ : $$\left\lfloor \frac q2 \right\rfloor \cdot m + e_3(1) = v(1) - r(1) \cdot t(1)$$
Si la valeur de $v(1) - r(1) \cdot t(1)$ est plus proche de $0$, on considère $m=0$, et si $v(1) - r(1) \cdot t(1)$ est plus proche de $\left\lfloor \frac q2 \right\rfloor$, on considère $m=1$, et on en déduit la valeur correspondante de $e_3(1)$.
On se retrouve alors avec une hypothèse pour $r(1), e_2(1), e_3(1)$ et $m$. On peut calculer la probabilité qu’un chiffrement produise précisément ces valeurs de $r(1), e_2(1), e_3(1)$ en tirant des polynômes courts aléatoires en effectuant simplement un produit des probabilités correspondantes dans le tableau des probabilités que l’on a calculé auparavant, et on rajoute cette probabilité à la probabilité que $m$ soit égal à $0$ ou $1$.
En sachant que l’une de nos hypothèses est forcément la bonne (car on itère sur toutes les valeurs possibles de $r(1)$ ), on multiplie simplement par le facteur de Bayes correspondant nos probabilités obtenues pour $m = 0$ et $m = 1$, et on obtient la probabilité exacte que $m$ soit égal à $0$ ou $1$ avec les informations obtenues de l’évaluation en $1$ de nos équations.
On peut effectuer exactement la même stratégie en évaluant les polynômes en $-1$ pour encore plus de précision :
def recover_m(m):
# retourne 0 ou 1 selon si m se rapproche plus de 0 ou de q/2
return int(m + q // 4)*2 // q
def distinguish(A, t, u, v, high_d = 96):
# high_d représente l'intervalle des valeurs qui seront considérées.
# high_d = 512 donnera des probabilités exactes, mais sera considérablement
# plus long.
# high_d = 96 correspond à un taux d'erreur de 0.0019% par évaluation.
R = A.base_ring()
K = R.base_ring()
mp = [0, 0] # mp[i] représente P(m = i)
for eval_point in (-1, 1):
A_ = lift_eval_matrix(A, eval_point)
t_ = lift_eval_vector(t, eval_point)
u_ = lift_eval_vector(vector(u).column(), eval_point).transpose()
v_ = lift_eval_poly(v[0][0], eval_point)
for r0 in range(-high_d, high_d+1):
for r1 in range(-high_d, high_d+1):
r_ = vector(K, [r0, r1]).column().transpose() # r(X)
e2_ = (u_ - r_ * A_).transpose() # e2(X) = u(X) - r(X)A(X)
me3_ = (v_ - r_ * t_)[0][0] # M+e3(X) = v(X) - r(X)t(X)
m = recover_m(me3_)
e3_ = (me3_ - (int(round(q/2)) * R(m)))[0]
p = 1 # probabilité que ce tirage ait lieu
for value in (e2_[0][0], e2_[1][0], e3_, r0, r1):
p *= proba[value]
mp[m] += p
s = 1 / (mp[0] + mp[1]) # facteur de Bayes
mp[0] *= s
mp[1] *= s
return mp
Quelques expériences aléatoires pour évaluer l’efficacité de notre distingueur :
for i in range(100):
A = random_matrix(R, 2, 2)
s = sample_short_vector()
e1 = sample_short_vector()
t = A * s + e1
m = randint(0, 1)
u, v = encrypt(m, A, t)
m0, m1 = distinguish(A, t, u, v)
print("P(m = 0):", round(m0 * 100, 2), '%')
print("P(m = 1):", round(m1 * 100, 2), '%')
print("Vraie valeur de m:", m)
print()
P(m = 0): 0.19 %
P(m = 1): 99.81 %
Vraie valeur de m: 1
P(m = 0): 0.33 %
P(m = 1): 99.67 %
Vraie valeur de m: 1
P(m = 0): 99.93 %
P(m = 1): 0.07 %
Vraie valeur de m: 0
P(m = 0): 43.76 %
P(m = 1): 56.24 %
Vraie valeur de m: 0
P(m = 0): 78.51 %
P(m = 1): 21.49 %
Vraie valeur de m: 0
P(m = 0): 1.88 %
P(m = 1): 98.12 %
Vraie valeur de m: 1
On se rend compte que bien souvent, notre distingueur nous permet de retrouver la valeur de $m$ avec quasi-certitude ($> 99%$). Cependant, quelques fois, on retrouve des probabilités moins certaines, qui se rapprochent quasiment de une chance sur deux. Notre objectif est de récupérer les 128 bits d’une clé AES, alors on peut se permettre d’avoir maximum 2-3 erreurs sur 128 bits (que l’on pourrait corriger par force brute), mais au-delà, cela rend le message complètement introuvable.
Heureusement pour nous, il semble que la probabilité de succès de notre distingueur dépend grandement de la clé publique $(A, t)$, qui reste constante pour les 128 bits chiffrés. Certaines clés publiques offrent une probabilité quasi-certaine de retrouver $m$ de manière consistante, et certaines clés publiques beaucoup moins. On peut estimer la qualité de notre distingueur par le conditionnement de $A(1)$ et $A(-1)$. En effet, si le conditionnement de $A(1)$ est faible, alors un vecteur proche de $r(1)$ aura tendance à décrire une solution proche de la solution réelle, qui pourrait même être plus probable que la vraie solution. Avec un conditionnement élevé, n’importe quel vecteur, même très proche de $r(1)$, donnera des valeurs complètement différentes pour $e_2(1)$ et $e_3(1)$, qui auront de grandes chances d’être des tirages de probabilité $0$.
Notre stratégie va donc être la suivante~:
- Se connecter au serveur de multiples fois, jusqu’à tomber sur une instance où la valeur de $A(1)$ ou $A(-1)$ tirée de la clé publique $A$ donnée possède un conditionnement suffisant. (Typiquement, avoir l’un des deux conditionnement supérieur à 100 est excellent).
- Lancer notre distingueur pour tous les chiffrés données, et estimer au passage la probabilité que notre solution aie moins de 3 erreurs.
- Si cette probabilité est suffisante, on tente de corriger les erreurs à la main par force brute, jusqu’à trouver la bonne clé qui nous indiquera le flag.
cond = lift_eval_matrix(A, 1).change_ring(RDF).condition()
print("Conditionnement en 1 :", cond)
cond = lift_eval_matrix(A, -1).change_ring(RDF).condition()
print("Conditionnement en -1 :", cond)
# On pourra corriger jusqu'à deux erreurs, donc je garde
# en mémoire la probabilité d'avoir effectué <= 2 erreurs.
# Si cette probabilité devient trop faible, on peut directement
# arrêter le code et recommencer avec un meilleur A.
proba_0_erreur = 1
proba_1_erreur = 0
proba_2_erreurs = 0
cle = 0
for i, (u, v) in enumerate(C):
m0, m1 = distinguish(A, t, u, v)
p = max(m0, m1)
m = [m0, m1].index(p)
proba_2_erreurs = p * proba_2_erreurs + (1 - p) * proba_1_erreur
proba_1_erreur = p * proba_1_erreur + (1 - p) * proba_0_erreur
proba_0_erreur = p * proba_0_erreur
cle <<= 1
cle |= m
print(f"Clé récupérée: {cle:0{i+1}b}")
print("P(E = 0):", round(proba_0_erreur * 100, 2), '%')
print("P(E = 1):", round(proba_1_erreur * 100, 2), '%')
print("P(E = 2):", round(proba_2_erreurs * 100, 2), '%')
print()
print(f'{hex(cle) = }')