Chebyshev's Revenge: Breaking a Polynomial Key Exchange

Overview

The challenge implemented a key exchange using Chebyshev polynomials over a finite field: each party publishes T_a(x) and T_b(x), and the shared secret is T_ab(x). The ciphertext was the flag XORed with a keystream derived from that secret.

Challenge brief

Given the prime p, the base value x, both public values and the ciphertext, recover the plaintext.

Analysis

The key property is composition: T_a(T_b(x)) = T_ab(x), which is exactly what makes the exchange work — and what lets it be attacked like Diffie–Hellman.

Writing x = (u + u⁻¹)/2 turns T_n(x) into (uⁿ + u⁻ⁿ)/2, so recovering a and b becomes a discrete-log problem in the multiplicative group of the quadratic extension F_{p²}, inside the subgroup of order p + 1.

Solution

p + 1 factored into small prime powers, so the group order was smooth and Pohlig–Hellman recovered the secret exponents modulo p + 1. With those, the shared exponent ab (mod p + 1) gives the shared value T_ab(x), which was converted into the challenge's keystream and XORed with the ciphertext to reveal the flag.

1# Sage sketch2F.<i> = GF(p^2)3u = lift_to_extension(x)            # x = (u + 1/u) / 24a = discrete_log(lift(A), u, ord=p+1)  # Pohlig–Hellman on a smooth order5shared = chebyshev_T(a * b % (p + 1), x)

Flag

Redacted. Format: BSides_Mumbai{…}.

Lessons learned

Exotic algebra doesn't add security if the underlying problem is a discrete log in a group with a smooth order. Parameter choice — a group order with a large prime factor — matters more than the novelty of the construction.