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

Regev over Rings

Ring-LWE avec seulement 13 échantillons publics : 8192 essais suffisent.

Scripts
1 fichier

Énoncé

Une variante du cryptosystème de Regev (le premier basé sur LWE) utilisant Ring-LWE. On dispose du chiffré du flag en base64 (ct_b64.txt), de la clé publique en base64 (pk_b64.txt) et de l’implémentation regev.sage.

Reconnaissance

Paramètres lus dans regev.sage : q = 12289, n = 256, et surtout le nombre d’échantillons publics m = floor(log2 q) = 13.

Chiffrement d’un message msg (vecteur de bits) :

  • c0 = Σ r_i · a_i
  • c1 = Σ r_i · b_i + floor(q/2) · msg

où chaque r_i est un bit aléatoire et (a_i, b_i) sont les 13 échantillons publics.

La faille

Le vecteur r ne fait que 13 bits → seulement 2^13 = 8192 possibilités. C’est trivialement brute-forçable (le flag le dit : bruteforce 4 ever).

  1. Retrouver r : on essaie les 8192 vecteurs r jusqu’à ce que Σ r_i · a_i == c0. Les a_i étant uniformément aléatoires, la correspondance est unique.
  2. Lire le message : on calcule c1 − Σ r_i · b_i. Chaque coefficient vaut exactement 0 ou 6144 (= floor(q/2)) — il ne reste aucun bruit — donc les bits se lisent directement.
  3. La clé secrète s n’est jamais utilisée.

Le r trouvé est (0,1,1,1,1,0,0,0,0,0,0,0,0).

Reproduire

python3 -I regev/solve.py

Pur Python, sans Sage ni dépendance, s’exécute en moins d’une seconde. Il retrouve r par force brute, soustrait la contribution des b_i, puis décode les bits en octets → le flag.

Script : solve.py.

Code

import base64, itertools, sys
q, n, m = 12289, 256, 13
d = sys.argv[1] if len(sys.argv) > 1 else './files'
def polys(b):
    return [[int.from_bytes(b[2*(k*n+i):2*(k*n+i)+2], 'little') for i in range(n)] for k in range(len(b)//(2*n))]
pk = polys(base64.b64decode(open(d+'/pk_b64.txt').read().strip()))
ct = polys(base64.b64decode(open(d+'/ct_b64.txt').read().strip()))
A = [(pk[2*i], pk[2*i+1]) for i in range(m)]
c0, c1 = ct
for r in itertools.product([0,1], repeat=m):
    s = [0]*n
    for ri,(a,_) in zip(r,A):
        if ri: s = [(x+y) % q for x,y in zip(s,a)]
    if s == c0:
        v = c1[:]
        for ri,(_,b) in zip(r,A):
            if ri: v = [(x-y) % q for x,y in zip(v,b)]
        bits = ''.join('1' if x == q//2 else '0' for x in v)
        assert all(x in (0, q//2) for x in v)
        print(r, bytes(int(bits[i:i+8],2) for i in range(0,n,8)).rstrip(b'\0'))
        break

Aussi en Crypto