real-but-hidden

Énoncé (résumé)

Un service cloud détient une clé CKKS. Il calcule sur des données chiffrées et publie un log de transparence : pour chaque job, le ciphertext (b, a) à côté du résultat déchiffré. Chaque résultat est « smudgé » par un bruit frais (borné par smudge = 65536). Le service ne publie que la partie réelle des 32 slots. Le flag est chiffré sous la même clé, et le service refuse de le déchiffrer.

Fichiers : lib.py (implémentation CKKS) et output.txt. output.txt contient n=64, q≈2^40 (premier), delta=2^20, le ciphertext du flag et 3 jobs (jobN_b, jobN_a, jobN_re).

Indice de l’énoncé : « Half the numbers is not half the information: it is all of the information about half the polynomial. » La clé est ternaire, et 3^64 clés, c’est trop pour une recherche exhaustive.

Analyse

lib.py est un CKKS standard sur Z_q[X]/(X^64+1) :

clé secrète s ternaire, ciphertext b = -a·s + m + e, avec un bruit e uniforme dans [-3, 3] ;
déchiffrement : m + e = b + a·s mod q (centré), puis decode ;
decode : slot j = m(ζ_j) / delta, avec ζ_j = exp(iπ(2j+1)/64) pour j = 0..31.

On connaît (b, a), et le résultat publié est Re(slots) de b + a·s + smudge. Si on sait ce qu’apporte exactement la partie réelle, on obtient des équations linéaires en s.

Le point clé : quelle « moitié » du polynôme est révélée

Pour une racine 128-ième primitive ζ :

ζ^64 = -1, donc ζ^(64-k) = -ζ^(-k) = -conj(ζ^k) ;
ζ^32 = ±i, donc sa partie réelle est nulle.

Il vient :

Re m(ζ_j) = m_0 + Σ_{k=1}^{31} cos(π(2j+1)k/64) · (m_k − m_{64−k})

Les 32 parties réelles sont donc l’image, par une matrice 32×32 inversible de type DCT, du vecteur entier

d(m) = (m_0, m_1 − m_63, m_2 − m_62, …, m_31 − m_33)

c’est-à-dire la partie anti-palindromique de m, que l’on connaît exactement. En inversant la matrice sur les données, on tombe sur des entiers à 1e-7 près. Cela confirme que le smudge est ajouté aux coefficients entiers, pas aux slots.

Pour chaque job, comme d est linéaire :

d(a·s) ≡ d_pub − d(b) + err   (mod q),   |err| ≲ 2^17  (smudge + e)

a·s s’écrit M_a · s, avec M_a la matrice négacyclique de a. Chaque job donne donc 32 équations linéaires mod q en s, avec une erreur d’environ 2^17 très petite devant q ≈ 2^40. Les 3 jobs en donnent 96 pour 64 inconnues ternaires : c’est une instance LWE à petit bruit, que l’on résout par réseau.

Exploitation

Parser output.txt avec ast.literal_eval, ligne par ligne.
Pour chaque job, calculer d_pub = round(R^{-1} · (re · delta)), avec R[j][k] = cos(π(2j+1)k/64).
Construire A = d(M_a) (lignes M_0 et M_k − M_{64−k} mod q) et c = d_pub − d(b) mod q.
Plongement de Kannan, en dimension 64 + 96 + 1 = 161 :
- lignes [W·e_j | A[:,j] | 0] pour chaque coordonnée de s, avec W = 2^16 ;
- lignes [0 | q·e_i | 0] ;
- ligne [0 | −c | K], avec K = 2^17.
Le vecteur court recherché est (W·s, err, K), de norme ≈ 2^20. L’heuristique gaussienne donne ≈ 2^32 pour ce réseau.
Réduire avec BKZ-20 via le binaire fplll, en ~14 s.
Prendre la ligne dont la dernière coordonnée vaut ±K et dont les 64 premières sont dans {−W, 0, W}. On en tire s, puis on vérifie que les résidus sur les 96 équations restent < 2^19.
Calculer b + a·s sur le ciphertext du flag, décoder, et lire les slots comme des codes ASCII : 66, 65, 50, 54, 123, … → BA26{the_real_part_was_enough}.

Script

solve.py. Dépendances : numpy (dans .venv) et le binaire fplll (brew install fplll ; fpylll ne compile pas ici).

cd . && .venv/bin/python -I solve.py files/output.txt

Morale

Ne publier que la partie réelle ne cache pas la moitié de l’information « au hasard » : on obtient exactement la composante anti-symétrique du polynôme, qui reste linéaire en la clé. Smudger avec un bruit de 2^16 ne suffit pas quand q ≈ 2^40 et que la clé est ternaire. Il faudrait un bruit de smudging statistiquement proche de q, ou ne jamais publier un déchiffrement à côté de son ciphertext.

Code

#!/usr/bin/env python3
"""real-but-hidden (BlackAlps 2026) -- recover the CKKS ternary key from real-part-only logs.

Re m(zeta_j) = m_0 + sum_{k=1}^{31} cos(pi(2j+1)k/n) * (m_k - m_{n-k})   (zeta^(n-k) = -conj(zeta^k), zeta^32 = +-i)
=> the 32 published reals give *exactly* the integers d_0 = m_0, d_k = m_k - m_{n-k}.
Each job: d(b + a*s) = d_published - d(smudge + e) mod q  -> 32 linear equations in s with ~2^17 error.
q ~ 2^40: Kannan embedding + LLL (fplll CLI) recovers s.  Usage: .venv/bin/python -I solve.py files/output.txt
"""
import ast, sys, subprocess, numpy as np

def load(p):
    d = {}
    for line in open(p):
        if '=' in line and not line.lstrip().startswith('#'):
            k, v = line.split('=', 1)
            d[k.strip()] = ast.literal_eval(v.strip())
    return d

D = load(sys.argv[1] if len(sys.argv) > 1 else 'files/output.txt')
n, q, delta = D['n'], D['q'], D['delta']
h = n // 2

def negacyclic_matrix(a):
    """M with (a*s) = M s in Z_q[X]/(X^n+1)."""
    M = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            k = i + j
            if k < n: M[k][j] = (M[k][j] + a[i]) % q
            else:     M[k - n][j] = (M[k - n][j] - a[i]) % q
    return M

def dmap(v):  # v: length-n integer vector -> d (length h)
    return [v[0]] + [v[k] - v[n - k] for k in range(1, h)]

jj = np.arange(h)
R = np.cos(np.pi * np.outer(2 * jj + 1, jj) / n)

rows_A, rhs = [], []
t = 0
while f'job{t}_re' in D:
    b, a, re = D[f'job{t}_b'], D[f'job{t}_a'], D[f'job{t}_re']
    dpub = [int(round(x)) for x in np.linalg.solve(R, np.array(re) * delta)]
    M = negacyclic_matrix(a)
    # d(b + M s) ≡ dpub + err   ->  d(M) s ≡ dpub - d(b) + err
    dM = [M[0]] + [[(M[k][c] - M[n - k][c]) % q for c in range(n)] for k in range(1, h)]
    db = dmap(b)
    for i in range(h):
        rows_A.append(dM[i]); rhs.append((dpub[i] - db[i]) % q)
    t += 1

m = len(rows_A)
W, K = 1 << 16, 1 << 17  # weight s (ternary) to match error size ~2^17
B = []
for c in range(n):
    B.append([W if r == c else 0 for r in range(n)] + [rows_A[i][c] for i in range(m)] + [0])
for i in range(m):
    B.append([0] * n + [q if r == i else 0 for r in range(m)] + [0])
B.append([0] * n + [(-rhs[i]) % q for i in range(m)] + [K])

inp = '[' + '\n'.join('[' + ' '.join(map(str, r)) + ']' for r in B) + ']'
out = subprocess.run(['fplll', '-a', 'bkz', '-b', '20'], input=inp, capture_output=True, text=True, check=True).stdout
red = [list(map(int, l.strip(' []').split())) for l in out.strip().strip('[]').split('\n') if l.strip(' []')]

s = None
for r in red:
    if abs(r[-1]) == K and all(x % W == 0 and abs(x // W) <= 1 for x in r[:n]):
        sg = r[-1] // K
        s = [sg * x // W for x in r[:n]]
        break
assert s is not None, "key not found"
print("s =", s)

def mul(f, g):
    hh = [0] * n
    for i, fi in enumerate(f):
        for j, gj in enumerate(g):
            k = i + j
            if k < n: hh[k] += fi * gj
            else:     hh[k - n] -= fi * gj
    return [c % q for c in hh]

def center(v): return [c - q if c > q // 2 else c for c in v]

# sanity: residuals on jobs are small
for i in range(m):
    e = (sum(rows_A[i][c] * s[c] for c in range(n)) - rhs[i]) % q
    assert min(e, q - e) < 1 << 19

V = [[np.exp(1j * np.pi * (2 * k + 1) / n) ** p for p in range(n)] for k in range(h)]
flag = ''
t = 0
while f'flag{t}_b' in D:
    b, a = D[f'flag{t}_b'], D[f'flag{t}_a']
    mpoly = center([(x + y) % q for x, y in zip(b, mul(a, s))])
    z = [sum(V[j][k] * mpoly[k] for k in range(n)) / delta for j in range(h)]
    print('slots:', [round(c.real, 3) for c in z][:8], '...')
    flag += ''.join(chr(int(round(c.real))) for c in z if 0 < round(c.real) < 256)
    t += 1
print(flag)

Télécharger solve.py

Énoncé (résumé)

Analyse

Le point clé : quelle « moitié » du polynôme est révélée

Exploitation

Script

Morale

Code

Aussi en Crypto

ecrsa

Too Much Crypto

autoencrypt