Tremendous 2 - BreizhCTF 2026

Contexte

Le flavour text du challenge continue la saga des personnages mégalomanes. Bref, j'ai ouvert le code Flask et j'ai cherché la route intéressante. En une minute, j'avais trouvé /api/verify qui déchiffre n'importe quel ciphertext soumis et répond juste avec la parité du résultat. C'est un RSA parity oracle - j'avais déjà vu ce pattern, j'ai su immédiatement comment y répondre.

L'objectif était clair : le cookie de session admin est le ciphertext RSA du mot de passe. Sans clé privée, j'allais l'inverser bit par bit en exploitant la malléabilité multiplicative de RSA.

Flag

••••••••••••••••••••••••••••••••Cliquer pour afficher

1. La vulnérabilité

L'application expose trois routes. Les deux qui m'intéressent :

app.py (routes clés)

# GET /  -> renvoie la clé publique (N, E)
# POST /api/verify -> oracle de parité
# POST /login -> compare le password avec le cookie admin

@app.route('/api/verify', methods=['POST'])
def verify():
    ticket = int(request.json['ticket'], 16)
    m = pow(ticket, D, N)   # déchiffrement RSA
    if m % 2 == 0:
        return jsonify({"side": "Bâbord"})   # pair
    else:
        return jsonify({"side": "Tribord"})  # impair

Et dans intercepted_data.json, j'ai la clé publique (N, E) et le cookie de session admin, qui est exactement C_ADMIN = password_admin^E mod N.

La faille est double : RSA textbook (pas de padding) + oracle qui déchiffre des ciphertexts arbitraires. Les deux conditions réunies permettent la malléabilité multiplicative : si je multiplie un ciphertext par 2^E mod N, son déchiffré est multiplié par 2.

2. L'attaque : dichotomie par parité

Le principe est simple. Je veux retrouver m = C_ADMIN^D mod N sans connaître D.

Je précalcule f = 2^E mod N, le chiffrement de 2. En multipliant le ciphertext par f, son déchiffré est doublé :

Propriété de malléabilité

c' = c * f mod N
   = c * 2^E mod N

=> dec(c') = 2m mod N

La parité de 2m mod N me dit exactement si une réduction modulo N a eu lieu :

La clé de l'attaque

2m mod N est pair   <=>  2m < N  <=>  m < N/2
2m mod N est impair <=>  2m >= N <=>  m >= N/2

Un seul appel à l'oracle localise m dans la première ou la seconde moitié de [0, N). En itérant - multiplier par f, interroger, bissecter l'intervalle - je divise l'incertitude par 2 à chaque étape. Après 1024 itérations (taille de N en bits), l'intervalle se réduit à un seul entier.

Dichotomie (pseudo-code)

lo, hi, c = 0, N, C_ADMIN
f = pow(2, E, N)

for i in range(N.bit_length()):
    c = c * f % N          # plaintext sous-jacent devient 2^i * m mod N
    mid = (lo + hi) // 2
    if oracle(c) == "Tribord":  # impair -> réduction -> m dans moitié haute
        lo = mid
    else:                        # pair -> pas de réduction -> moitié basse
        hi = mid

# hi ~= m, à quelques unités près (erreur d'arrondi)

La division entière accumule une petite erreur. Je la corrige en cherchant le delta dans [-20, 20] tel que (hi + delta)^E mod N == C_ADMIN.

3. Le script

solve.py

import requests

N = int("101646000634959031725154661405870010409950962209123707678659882164972350237169"
        "157460692866950983884429112344771015131810052770764800456306492306639149157441"
        "470846099674367755641503480298049066020742710941063942126524254881782107742673"
        "295652252565294818485128043958428858647298411408258740535747623355015124347")
E = 65537
C_ADMIN = int(
    "5e6caa0607af838358f9bb85f60c3caad6fd16733332dfa536860d026d3177e2d"
    "2093d464bae448d297bf70361709c2626a051b62f57af79375ac25ae4e7c18fb1"
    "46445ad53e2ed5eee155cc56f098c9442a1576cdcc592dbd03013031ad4d27a97"
    "9f307266852066e1d7faf760988a6c70c1eb3442ed918ae5379176c7e7b01",
    16,
)
URL = "https://tremendous2-babord-tribord-requins-140.chall.ctf.bzh"

def oracle(c: int) -> int:
    resp = requests.post(f"{URL}/api/verify", json={"ticket": hex(c)}, timeout=15)
    return 0 if resp.json()["side"] == "Bâbord" else 1

f = pow(2, E, N)
lo, hi, c = 0, N, C_ADMIN

for _ in range(N.bit_length()):
    c = c * f % N
    mid = (lo + hi) // 2
    if oracle(c) == 1:
        lo = mid
    else:
        hi = mid

# Correction de l'arrondi
m = hi
for delta in range(-20, 21):
    if pow(m + delta, E, N) == C_ADMIN:
        m = m + delta
        break

password = m.to_bytes((m.bit_length() + 7) // 8, "big").decode()
print(f"Mot de passe : {password}")

resp = requests.post(f"{URL}/login", data={"password": password})
print(resp.text)

Résultat

Mot de passe : auF2kxrHYK5VYYKe

BZHCTF{they_stole_my_beautiful_cookie_very_sad}

Ce que j'en retiens

RSA textbook = malléabilité. Sans padding OAEP, la relation multiplicative enc(a) * enc(b) = enc(a*b) tient. C'est ça qui rend toute la dichotomie possible.
Un seul bit suffit. La parité du déchiffré semble une information minime, mais répété 1024 fois avec les bonnes multiplications, c'est suffisant pour retrouver n'importe quel plaintext dans [0, N).
La correction du delta est nécessaire. Les divisions entières dans la dichotomie accumulent une erreur. Sans la vérification finale, on tombe à quelques unités près de la bonne valeur.