Aller au contenu
skifo/ BA26 CTF
Tous les challenges
Crypto Résolu

autoencrypt

Un chiffrement « post-quantique » à base d'autoencodeur, cassé avec 65 requêtes.

Scripts
1 fichier

Énoncé (résumé)

« AE » se présente comme un chiffrement asymétrique post-quantique construit sur un autoencodeur :

  • chaque bloc de 8 octets (64 bits) est encodé par répétition ×3, ce qui donne x ∈ {0,1}^192 ;
  • x passe par une couche affine c = W·x + b (192 entrées, 96 sorties), arrondie à 6 décimales ;
  • le décodeur entraîné fait office de clé privée.

L’encodeur (W, b) est secret et l’API de chiffrement est payante. On dispose de :

  • ae.py, l’implémentation ;
  • output.txt, qui contient les paramètres, le flag chiffré en 6 blocs (flag_0 … flag_5) et un journal de 70 requêtes (log_00 … log_69) : bloc clair en hex → chiffré.

Indice : « Don’t learn the encoder. Count what it would take to determine it. »

Analyse

Dans ae.py, ecc_encode répète chaque bit 3 fois : x = (m₀,m₀,m₀, m₁,m₁,m₁, …). La couche affine donne donc :

c = W·x + b = Σ_i (W[:,3i] + W[:,3i+1] + W[:,3i+2]) · m_i + b = W'·m + b

avec W’ (96×64) la somme des colonnes répétées. Le système ne dépend pas des 18432 poids de W, seulement de W’ et b, soit 65 inconnues par ligne de sortie (64 + biais).

Vulnérabilité

  1. Récupération de la clé publique : chaque couple (m, c) du journal donne une équation linéaire par sortie. Avec 70 couples, on a plus que les 65 inconnues nécessaires (la matrice [m | 1] est de rang 65), donc W’ et b se déterminent exactement par moindres carrés. Seul l’arrondi à 1e-6 introduit du bruit.
  2. Le « goulot » n’en est pas un : l’argument de non-inversibilité vaut pour 192 → 96. Mais l’espace effectif des messages n’a que 64 dimensions, et W’ (96×64) est de rang plein. L’application m ↦ W’·m + b est donc injective et s’inverse directement par moindres carrés, puis arrondi à {0,1}. Aucun décodeur n’est nécessaire.

Exploitation

  1. Parser output.txt.
  2. Construire A = [bits(m) | 1] (70×65) et C (70×96), puis résoudre A·X = C par lstsq. On obtient W’ = X[:64]ᵀ et b = X[64]. Le résidu maximal est d’environ 3.5e-7, cohérent avec l’arrondi.
  3. Pour chaque bloc du flag : résoudre W’·m = c − b par lstsq, arrondir à 0/1, puis convertir les bits en octets.
  4. Concaténer les blocs et retirer le padding nul.
cd .
python3 -m venv .venv && .venv/bin/pip install numpy
.venv/bin/python -I solve.py files/output.txt

Sortie :

70 queries, design rank 65 / 65
fit residual max: 3.545410279803818e-07
BA26{sixty_five_queries_and_not_one_more}

Script

Voir solve.py : parsing, moindres carrés pour (W’, b), puis inversion bloc par bloc.

Code

"""autoencrypt (BlackAlps 2026) -- solve.

Flaw: the repetition code makes the encoder input x = ecc(m) live in a 64-dim
space.  W·x + b = W'·m + b where W' (96x64) sums each triple of columns of W.
So the "18432-weight" encoder is really an affine map 64 -> 96 with 65 unknowns
per output row.  70 known (plaintext, ciphertext) pairs >= 65 unknowns, so
least squares recovers W' and b exactly (up to 1e-6 rounding).  Then W' is a
tall full-rank 96x64 matrix: c - b = W'·m is injective on bits, so the
"bottleneck" loses nothing -- solve by least squares and round to {0,1}.

Usage: .venv/bin/python -I solve.py files/output.txt
"""
import ast
import sys

import numpy as np


def bits(data):
    return [(byte >> (7 - i)) & 1 for byte in data for i in range(8)]


def unbits(b):
    return bytes(sum(bit << (7 - i) for i, bit in enumerate(b[j:j + 8]))
                 for j in range(0, len(b), 8))


def parse(path):
    vals = {}
    for line in open(path):
        line = line.strip()
        if not line or line.startswith("#") or "=" not in line:
            continue
        name, rhs = line.split("=", 1)
        vals[name.strip()] = ast.literal_eval(rhs.strip())
    return vals


def main(path):
    v = parse(path)
    logs = sorted(k for k in v if k.startswith("log_"))
    flags = sorted(k for k in v if k.startswith("flag_"))

    # design matrix: [m bits | 1]
    A = np.array([bits(bytes.fromhex(v[k][0])) + [1] for k in logs], float)
    C = np.array([v[k][1] for k in logs], float)
    print(f"{len(logs)} queries, design rank {np.linalg.matrix_rank(A)} / {A.shape[1]}")

    X, *_ = np.linalg.lstsq(A, C, rcond=None)  # (65, 96)
    Wp, b = X[:64].T, X[64]
    print("fit residual max:", np.abs(A @ X - C).max())

    out = b""
    for k in flags:
        c = np.array(v[k], float)
        m, *_ = np.linalg.lstsq(Wp, c - b, rcond=None)
        mb = [int(round(t)) for t in m]
        assert all(t in (0, 1) for t in mb) and np.abs(m - mb).max() < 0.1, m
        out += unbits(mb)
    print(out.rstrip(b"\0").decode())


if __name__ == "__main__":
    main(sys.argv[1] if len(sys.argv) > 1 else "files/output.txt")

Aussi en Crypto