Contexte
J'avais déjà fait Kybeurre doux un peu avant dans le CTF, donc j'étais dans le bain LWE. Mais celui-là c'était différent : pas de service TCP, pas d'oracle à interroger. On avait deux fichiers - un firmware IoT et un dump réseau de 1000 paquets. Le nom du challenge (demi-sel) était déjà un gros indice sur ce qui allait craquer.
En lisant iot_scanner.py, j'ai immédiatement repéré les deux erreurs fatales : un secret dans {0,1} et un bruit dans [-10, 10]. Avec un module de 100 bits, le ratio bruit/modulus est tellement ridicule que LWE n'offre plus aucune résistance. La réduction de réseau allait s'en charger.
Flag
••••••••••••••••••••••••••••••••Cliquer pour afficher1. Lecture du code source
Le firmware génère un secret aléatoire toutes les 5000 itérations et broadcaste des échantillons LWE. La structure est classique :
iot_scanner.py (extrait)
PARAM_N = 50
PARAM_Q = 1017194805530087781866367482651 # ~100 bits
def _refresh_secret():
sys_ctx['secret_vector'] = [rng.randint(0, 1) for _ in range(PARAM_N)]
def generate_beacon():
vec_a = [random.randint(0, Q-1) for _ in range(PARAM_N)]
dot_prod = sum(a * s for a, s in zip(vec_a, sys_ctx['secret_vector']))
val_b = (dot_prod + _get_noise()) % Q # bruit dans [-10, 10]Chaque paquet broadcaste un échantillon de la forme :
Équation LWE
b_i = <a_i, s> + e_i (mod Q)
avec :
s in {0,1}^50 -- secret BINAIRE
e_i in [-10, 10] -- bruit entier très faible
Q ~= 10^30 -- module 100 bitsToutes les 500 itérations, le device envoie aussi un sovereign_pulse : le flag chiffré en AES-ECB avec comme clé sha256(str(s)). Retrouver s = déchiffrer le flag.
2. Les deux failles
GPT-Erwann se vante d'une architecture Frictionless Security. En pratique, deux erreurs cumulées rendent le système trivial à casser.
Secret binaire
Le secret est dans {0,1}^50, soit 50 bits d'entropie maximum. Dans Kyber, les secrets sont tirés d'une distribution binomiale centrée sur plusieurs valeurs - jamais du binaire pur. Ça change tout pour les attaques par réseau.
Bruit négligeable
Le bruit e_i vaut au plus 10. Le module Q fait ~10^30. Le ratio est de l'ordre de 10^-28 - c'est quasi-zéro. Dans LWE, le bruit est ce qui rend le problème difficile. Sans bruit significatif, on est ramené à un système linéaire presque exact.
3. L'attaque - Kannan embedding + LLL
L'idée est de transformer le problème LWE en un problème de vecteur court dans un réseau (SVP), puis de laisser LLL faire le travail. Je prends 50 échantillons (A, b) du dump et je construis une matrice de dimension 101 x 101 :
Construction de la matrice de Kannan
dim = N + m + 1 (= 50 + 50 + 1 = 101)
B =
[ I_50 | A^T | 0 ] <- lignes 0..49
[ 0 | Q*I_50| 0 ] <- lignes 50..99
[ 0 | b^T | 1 ] <- ligne 100
avec A = matrice 50x50 des vecteurs a_i
b = vecteur des b_iLe vecteur cible (s, -e, -1) est dans ce réseau. Sa norme vaut au plus sqrt(50 + 50*100 + 1) ~= 72. La norme minimale typique d'un vecteur aléatoire dans ce réseau est de l'ordre de 10^15. Le vecteur cible est donc 10 milliards de fois plus court que les vecteurs génériques - LLL va le trouver immédiatement.
Après réduction, je cherche une ligne dont le dernier élément est +/-1 et dont les 50 premiers éléments sont dans {0,1} :
Extraction du secret
for i in range(dim):
row = [int(mat[i][j]) for j in range(dim)]
if abs(row[-1]) != 1:
continue
sign = row[-1]
s_cand = [-sign * x for x in row[:N]]
if all(x in (0, 1) for x in s_cand):
# Trouvé !4. Le script complet
J'ai utilisé fpylll pour la réduction LLL avec précision arbitraire (mpfr) pour éviter les erreurs d'arrondi sur les grands entiers :
solve.py
import json, hashlib
from fpylll import IntegerMatrix, LLL
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
N, Q, m = 50, 1017194805530087781866367482651, 50
with open("sniffed.json") as f:
packets = json.load(f)
# Récupérer m échantillons LWE + le flag chiffré
As, bs, encrypted_flag = [], [], None
for pkt in packets:
if pkt["type"] == "beacon" and len(As) < m:
As.append(pkt["A"])
bs.append(pkt["b"])
elif pkt["type"] == "sovereign_pulse":
encrypted_flag = pkt["encrypted_token"]
dim = N + m + 1
B = [[0] * dim for _ in range(dim)]
for j in range(N):
B[j][j] = 1
for i in range(m):
B[j][N + i] = As[i][j]
for i in range(m):
B[N + i][N + i] = Q
for i in range(m):
B[N + m][N + i] = bs[i]
B[N + m][dim - 1] = 1
mat = IntegerMatrix.from_matrix(B)
LLL.reduction(mat, method='proved', float_type='mpfr', precision=200)
s_cand = None
for i in range(dim):
row = [int(mat[i][j]) for j in range(dim)]
if abs(row[-1]) != 1:
continue
sign = row[-1]
cand = [-sign * x for x in row[:N]]
if all(x in (0, 1) for x in cand):
s_cand = cand
break
key = hashlib.sha256("".join(str(x) for x in s_cand).encode()).digest()
flag = unpad(AES.new(key, AES.MODE_ECB).decrypt(bytes.fromhex(encrypted_flag)), 16)
print(flag.decode())Résultat
Secret : [1,1,1,0,1,0,1,0,1,1,0,0,1,0,0,0,0,0,0,0,1,0,1,1,1,0,1,1,0,0,0,1,0,1,1,0,0,0,0,0,0,0,1,1,0,1,0,1,1,0]
BZHCTF{adding_too_much_salt_in_the_modulus_cracks_the_algorithm}Ce que j'en retiens
- Secret binaire + bruit négligeable : les deux conditions suffisent pour que l'embedding de Kannan soit trivial. Chaque condition seule rendrait déjà le système fragile.
- LLL avec mpfr : sur des entiers de 100 bits, la précision flottante par défaut de fpylll est insuffisante. Le paramètre
float_type='mpfr', precision=200est nécessaire pour que la réduction converge correctement. - Le nom du challenge dit tout : "demi-sel" = trop peu de sel (bruit) dans le module. GPT-Erwann a littéralement enlevé le bruit pour "optimiser les KPIs", et c'est littéralement ce qui casse tout.