Chronos in the Octet Cage

Crypto, Medium, 250 pts

Flag: FLAG{ab3l1an_n0rm_unr4v3ls_scr4mbl3d_qu4t3rn10n_t3ns0r_9f2a}

chall.py defines a 4-dimensional algebra over Z_N with a structure tensor GAMMA[k][a][b], product mix(X, Y)_k = sum GAMMA[k][a][b] X[a] Y[b] mod N, and N = p*q with 512-bit primes. The output has N, e = 65537, a partial-key-exposure hint (e_aux, hint_d), eight telemetry records {W1, W2, Z}, and C_flag = F^e in the algebra. The flag is split into four 15-byte chunks, each stored as chunk | rand << 128.

For record i (indices mod 8), with U_i = p*R_i + E_i and E_i about 60 bits:

W1 = A_i * B_i
W2 = B_i * C_i
Z  = B_{i+1} * U_i * A_i * C_{i+1} * B_i

The e_aux/hint_d data (top 230 bits of a 680-bit d_aux) is a decoy. I never used it.

Identify the algebra

Checking basis products in Sage shows it is associative, noncommutative, with identity (1,0,0,1), so it looks like M2 (2x2 matrices). Build the left-multiplication matrix L_x and factor det(L_x). It is a perfect square, q(x)^2, with

q(x) = 20x0^2 - 10x0x1 + 3x1^2 + 50x0x2 - 14x1x2 + 35x2^2 - 34x0x3 + 8x1x3 - 44x2x3 + 15x3^2

This is the reduced norm (the determinant of M2). It is multiplicative with q(1) = 1, and since it has integer coefficients it makes sense mod N and mod p.

Norm leak

Apply q to the Z equation. The unknown matrices regroup into the public W's:

q(Z_i) = q(U_i) * q(A_i)q(B_i) * q(B_{i+1})q(C_{i+1}) = q(U_i) * q(W1_i) * q(W2_{i+1})

so D_i = q(Z_i) / (q(W1_i) q(W2_{i+1})) = q(U_i) mod N. Since U_i = E_i mod p, we get D_i = q(E_i) mod p, and q(E_i) is about 127 bits against a 512-bit p. That gives eight small residues s_i = D_i mod p, |s_i| < 2^130.

Recover p (Cohn-Heninger, degree 1)

The linear polynomials x_i - D_i vanish at s_i modulo the unknown p. Build a 9x9 lattice on (1, x_1, ..., x_8):

[  N      0   ...  0 ]
[ -D_1    X   ...  0 ]
[  ...               ]
[ -D_8    0   ...  X ]     X = 2^130

The determinant is N*X^8, so short vectors have norm around 2^194, far below p (about 2^512). By Howgrave-Graham they are true integer relations satisfied by (1, s_1, ..., s_8). LLL returns 8 such vectors (the ninth jumps to about 2^511). Their kernel is one-dimensional and gives the s_i, and then p = gcd(D_0 - s_0, N).

Decrypt

Mod each prime the algebra is M2(F_r), whose unit group GL2(F_r) has exponent dividing r(r^2-1). The challenge checks gcd(e, (p^2-1)(q^2-1)) = 1, so d = e^-1 mod lcm(p(p^2-1), q(q^2-1)) and F = C_flag^d using repeated mix. Each coordinate of F is chunk | rand << 128. Take the low 128 bits of each, drop the leading zero byte, and concatenate.

The full solver, run with sage solve.sage (it is not saved as a separate file in this folder):

import json
G=[
    [[-14, 3, -19, 15],[5, -3, 9, -5],[-25, 5, -35, 25],[15, -3, 19, -15]],
    [[0, 1, 5, 0],[5, -2, 5, -4],[-5, 1, 0, 5],[0, 0, -5, 0]],
    [[0, -3, 5, 0],[3, 0, 3, -3],[1, -5, 6, 0],[0, 3, -4, 0]],
    [[-20, 0, -20, 20],[10, -3, 15, -10],[-30, -1, -35, 30],[20, 0, 20, -19]],
]
R=PolynomialRing(ZZ,'x',4); xs=R.gens()
L=matrix(R,4,4,lambda k,b: sum(G[k][a][b]*xs[a] for a in range(4)))
f=L.det().factor()
q=[fac for fac,m in f if m==2][0]
if q(1,0,0,1)==-1: q=-q

d=json.load(open('output.txt'))
N=d['N']; e=d['e']; T=d['telemetry']; m=8
nrm=lambda v: Integer(q(*v))
Dn=[]
for i in range(m):
    nx=(i+1)%m
    num=nrm(T[i]['Z'])%N
    den=(nrm(T[i]['W1'])*nrm(T[nx]['W2']))%N
    Dn.append(int(num*inverse_mod(den,N)%N))

X=2^130
M=matrix(ZZ,m+1,m+1); M[0,0]=N
for i in range(m):
    M[i+1,0]=-Dn[i]; M[i+1,i+1]=X
Lr=M.LLL()
rows=[[v[0]]+[v[i+1]//X for i in range(m)] for v in Lr.rows()[:m]]
kv=matrix(QQ,rows).right_kernel().basis()[0]
kv=kv/kv[0]
s=[Integer(x) for x in kv[1:]]
p=gcd(Dn[0]-s[0],N); qq=N//p
assert p*qq==N

Lc=lcm(p*(p^2-1), qq*(qq^2-1))
dd=inverse_mod(e,Lc)
def mix(x,y): return [sum(G[k][a][b]*x[a]*y[b] for a in range(4) for b in range(4))%N for k in range(4)]
def mp(X0,ex):
    res=list(X0)
    for bit in bin(ex)[3:]:
        res=mix(res,res)
        if bit=='1': res=mix(res,X0)
    return res
F=mp(d['C_flag'],dd)
print(b''.join(int(v%(2^128)).to_bytes(16,'big')[1:] for v in F))