Hello guys! In this post I’ll be covering three cryptography challenges I made for BSides Mumbai CTF.

The challenges are:

  1. Chebyshev’s Revenge
  2. GCD, but it’s ACD
  3. Heat Death of RSA

Let’s start without any further ado.

1. Chebyshev’s Revenge

This challenge gives us the following basic construction:

alice = randbits(768)
bob = randbits(768)

A = T(alice, x)
B = T(bob, x)

shared_alice = T(alice, B)
shared_bob = T(bob, A)

assert shared_alice == shared_bob

and then the shared value is converted into a SHAKE256 stream and XORed with the flag.

At first glance it basically looks like some weird Diffie-Hellman replacement using Chebyshev polynomials.

The important identity is:

T_m(T_n(x)) = T_(mn)(x)

which explains why:

T_alice(B) = T_bob(A)

works.

The obvious problem is that alice and bob are both random 768-bit values.

We aren’t brute forcing those.

My laptop heard ‘768-bit brute force’ and asked for early retirement.

Chebyshev polynomials are hiding a group

The important identity for the attack is:

T_n(x) = (α^n + α^-n) / 2

where:

α = x + sqrt(x² - 1)

Let:

D = x² - 1

In this particular challenge, D is intentionally a quadratic non-residue modulo p.

So:

sqrt(D)

doesn’t exist inside Fp.

But it does exist in the extension field:

Fp²

We can represent one element as:

a + b*s

where:

s² = D

and multiplication becomes:

(a + bs)(c + ds)
=
(ac + bdD) + (ad + bc)s

Now define:

alpha = x + s

The norm of this value is:

(x+s)(x-s)
= x² - s²
= x² - (x²-1)
= 1

So alpha lives inside the norm-one subgroup of Fp².

And:

T_n(x)

is exactly the first coordinate of:

alpha^n

This converts our weird Chebyshev problem into a normal discrete logarithm problem.

Recovering the missing Fp² coordinate

Suppose:

alpha^n = y + k*s

We only know:

y = T_n(x)

but because the norm is one:

y² - k²D = 1

therefore:

k² = (y² - 1) / D

So given the public value A:

k2 = (A*A - 1) * inverse(D, p) % p
k = sqrt_mod(k2, p)
AA = Fp2(A, k)

and we now have either:

alpha^alice

or:

alpha^-alice

because modular square roots give two possible signs.

This ambiguity doesn’t actually matter for us.

We repeat the same process for B.

The actual vulnerability

Now we seem to have turned the challenge into:

Solve a discrete logarithm in a ~514-bit group.

which doesn’t sound much better.

Except we factor the group order.

Because alpha has norm one, its order divides:

p + 1

Factoring p+1 gives a beautiful sight:

2^14
11
4933
10067
26321
31151
32801
39239
...
297991

The largest prime factor is only:

297991

Oops.

So the entire 514-bit group order is smooth.

And therefore Pohlig-Hellman absolutely destroys this.

Pohlig-Hellman

For every prime power:

q^e | p+1

we project the problem into that subgroup:

gg = alpha ** ((p + 1) // (q**e))
hh = AA    ** ((p + 1) // (q**e))

and solve:

hh = gg^r

Because every subgroup is tiny, Baby-Step Giant-Step works perfectly fine.

A simple implementation looks like:

def bsgs(g, h, n):
    m = isqrt(n) + 1

    table = {}
    cur = ONE

    for j in range(m):
        table.setdefault(cur, j)
        cur *= g

    factor = g ** (-m)
    gamma = h

    for i in range(m + 1):
        if gamma in table:
            x = i*m + table[gamma]
            if x < n and g**x == h:
                return x

        gamma *= factor

We repeat this for every factor and obtain:

alice mod q1^e1
alice mod q2^e2
alice mod q3^e3
...

Then use CRT:

alice, modulus = crt(moduli, residues)

and do the same for Bob.

Recovering the shared value

Once we have a and b:

shared = (
    alpha ** ((a*b) % (p+1))
).a

Remember that .a is the first coordinate in Fp².

Then the challenge’s original stream encryption was:

stream = shake_256(
    b"chebyshevs-revenge-final|" +
    shared.to_bytes(width, "big")
).digest(len(ct))

so we just XOR again.

Running the solver gives:

BSides_Mumbai{ch3by5h3v_l0gs_l1v3_1n_th3_tw1st}

So the flag is:

BSides_Mumbai{ch3by5h3v_l0gs_l1v3_1n_th3_tw1st}

Huge exponent != secure discrete log if you very kindly choose a completely smooth group order :)

2. GCD, but it’s ACD

This challenge is based around the Approximate Common Divisor problem, hence:

GCD
but it's
ACD

The public model literally tells us what’s happening:

sample[0] = p*q[0]

sample[i] = p*q[i] + error[i]

where:

abs(error[i]) < 2^52

If there was no error we could simply do:

gcd(sample[0], sample[1], sample[2], ...)

and recover p.

Unfortunately:

gcd(p*q1 + r1, p*q2 + r2)

doesn’t magically remove r1 and r2.

So direct GCD gives us nothing useful.

The samples themselves are roughly 600 bits while the hidden divisor is 288 bits, so brute forcing a 52-bit signed error for each sample is also not exactly the world’s greatest plan.

We get one exact sample

The first value is special:

x0 = p*q0

and all the others are:

xi = p*qi + ri

where:

|ri| < X
X = 2^52

If we can recover the errors ri, the problem is instantly over because:

gcd(x0, xi - ri)

contains the exact hidden p.

So really our goal is:

recover the small errors.

Constructing the lattice

Take t noisy samples and create the following basis:

[x0, 0,  0,  ..., 0]
[x1, X,  0,  ..., 0]
[x2, 0,  X,  ..., 0]
...
[xt, 0,  0,  ..., X]

Any lattice vector is of the form:

[
  a0*x0 + a1*x1 + ... + at*xt,
  X*a1,
  X*a2,
  ...
  X*at
]

Substitute:

x0 = p*q0
xi = p*qi + ri

and the first coordinate becomes:

p(a0*q0 + a1*q1 + ... + at*qt)
+
a1*r1 + ... + at*rt

Now imagine coefficients where:

a0*q0 + a1*q1 + ... + at*qt = 0

The gigantic multiple of p vanishes.

And suddenly the first coordinate is only:

a1*r1 + ... + at*rt

which is very small compared to the original ~600-bit samples.

That is exactly the kind of structure LLL likes finding.

Running LLL

So we run lattice reduction on the basis.

After reduction, promising rows satisfy:

row[i] % X == 0

for the coefficient columns.

We obtain:

coeff_i = row[i] // X

and every genuine short relation gives an equation:

a1*r1 + a2*r2 + ... + at*rt
=
row[0]

The solver also applies a basic sanity filter:

abs(row[0]) <= 2 * sum(abs(c) for c in coeff) * X

because a real quotient-cancelling relation should leave a value bounded by the small errors.

Solve for the errors

Once we have enough independent relations we basically have:

A * r = b

where:

r = [r1, r2, ..., rt]

Solve this exactly over the rationals/integers and we recover every signed error.

Then:

p = x0

for xi, ri in zip(noisy_samples, errors):
    p = gcd(p, xi - ri)

and eventually p becomes the hidden 288-bit divisor.

Decryption

The challenge generates the encryption stream from p:

pb = p.to_bytes((p.bit_length() + 7) // 8, "big")

stream = shake_256(
    b"acd-revenge/key|" + pb
).digest(len(ciphertext))

XORing gives:

BSides_Mumbai{n01sy_gcD_n33ds_l4tt1c3s}

So our flag is:

BSides_Mumbai{n01sy_gcD_n33ds_l4tt1c3s}

The funny part is that adding noise absolutely does stop the normal GCD attack.

It just changes the challenge from:

math.gcd()

to:

lattice time

3. Heat Death of RSA

And finally we have Heat Death of RSA.

This challenge is what happens when you take RSA, a noisy physical-ish mathematical model, matrix exponentials and lattices and throw all of them inside the same file.

The final challenge parameters are:

NM  = 16
NS  = 48
RAW = 48

There are 32 hidden coefficients:

2 * NM = 32

Each coefficient is around:

2^190 <= coefficient < 2^192

These coefficients eventually determine the RSA primes.

In other words:

recover coefficients
      ↓
regenerate p and q
      ↓
decrypt RSA

That’s the entire attack.

Unfortunately recovering those coefficients is the slightly annoying part.

Public observations

The challenge gives 48 public observations.

They aren’t direct sensor readings though.

Every observation is passed through:

obs[i] = spin(reading_i, power(i))

The first thing we therefore have to do is undo spin.

Undoing spin()

The operation behaves like exponentiation in a finite abelian group where exponent arithmetic is modulo:

Q + 1

Luckily every public exponent:

power(i)

is invertible modulo Q+1.

Therefore:

e = model.power(i)
e_inv = pow(e, -1, model.Q + 1)

reading = model.spin(obs[i], e_inv)

After converting values larger than Q/2 back into signed integers we obtain a vector:

y

satisfying approximately:

y = B*s + error

where:

s = 32 secret coefficients
B = public transfer matrix
error = bounded noise

Now this starts looking much friendlier.

Except B isn’t directly given to us.

Reconstructing B

The public model gives enough individual functions to reconstruct it.

For every sensor site we get:

xn, xd, tn, td, kind, w = model.site(i)

which gives us a position:

x = pi * xn/xd

and time:

t = tn/td

For every mode:

j = 1..16

we also obtain a 2×2 linear ODE block:

A = model.block(j)

For each of the two basis states we need:

z(t) = exp(A*t) * basis

and also:

h(t) = integral from 0 to t exp(A*s) ds * basis

The integral can be calculated as:

A^-1 (exp(A*t) - I)

So for each mode/basis pair we calculate:

E = exp(A*t)
H = A^-1 * (E-I)

and feed everything through:

model.sense(...)

The result is scaled by the challenge’s fixed-point constant:

entry = round(model.FP * value)

Doing this for all 32 hidden basis coefficients produces one row of the transfer matrix.

Do it for every raw sensor and we get the raw matrix.

Finally the public:

model.wiring(i)

function mixes those rows into the actual 48 observations.

The result is:

B = 48 × 32 integer matrix

and:

y = B*s + e

where e is small.

And now LLL returns

The columns of B generate a 32-dimensional lattice inside Z^48.

The real observation vector is extremely close to one lattice point:

B*s

because:

y = B*s + error

This means we have a Bounded Distance Decoding problem.

The error is too annoying for direct linear algebra, but small enough for lattice reduction.

First reduce a row basis for the column lattice:

reduced = Matrix(B).T.lll(delta=0.75)

Then use Babai nearest-plane with target:

y

The nearest lattice vector should be:

B*s

and therefore the residual is:

error

Conceptually:

error = babai(reduced, y)

exact = [
    y[i] - error[i]
    for i in range(48)
]

Now:

exact = B*s

with absolutely no noise left.

Solve the exact system

At this point the scary crypto challenge has become a linear algebra problem.

secret, params = Matrix(B).gauss_jordan_solve(
    Matrix(exact)
)

This recovers all 32 secret coefficients.

We also know their expected range so we can easily verify the result:

assert all(
    model.LO <= x < model.HI
    for x in coeffs
)

RSA falls apart

The public model contains:

p, q = model.finalize(coeffs)

So once we recover the hidden vector we simply regenerate the exact RSA primes:

p, q = model.finalize(coeffs)

assert p*q == N

Then normal RSA:

phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(c, d, N)

Converting m back to bytes gives:

BSides_Mumbai{Y0u_kn0w_about_LLL!?!?}

So the final flag becomes:

BSides_Mumbai{Y0u_kn0w_about_LLL!?!?}

And that’s it for the three crypto challenges.

The basic ideas behind them were:

Chebyshev's Revenge
    -> disguised DLP + smooth group order

GCD, but it's ACD
    -> approximate multiples + LLL

Heat Death of RSA
    -> noisy linear leakage + LLL/Babai + RSA key regeneration

I definitely used more lattices than a normal person should while making these.

Anyways, hope you enjoyed the challenges/writeups and maybe learnt something new from them :D