Bespoke Padding

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: franklin_reiter_related_message, polynomial_gcd_mod_n, related_message_recovery

Summary

Task: an interactive RSA service encrypts the same flag m under the same modulus N with e=11, each time applying a known linear padding am+b (a,b disclosed) so c=(am+b)^11 mod N. Solution: Franklin–Reiter related-message attack — for two queries form g_i(x)=(a_i*x+b_i)^11 - c_i over Z_N[x]; their polynomial GCD modulo N collapses to the linear factor (x - m), revealing the flag directly. Affine padding provides no protection against related-message attacks.

Bespoke Padding — cryptohack (Padding)

Description

"Come back as much as you want! You'll never get my flag."

File: 13386_42e6fb9bddd96dc87c9b79435e226329.py, solver solve_bespoke.py. Live service: socket.cryptohack.org:13386.

 python read-only • copy allowed Copy
class Challenge():
    def __init__(self):
        self.p = getPrime(1024); self.q = getPrime(1024)
        self.N = self.p * self.q
        self.e = 11

    def pad(self, flag):
        m = bytes_to_long(flag)
        a = random.randint(2, self.N)
        b = random.randint(2, self.N)
        return (a, b), a*m + b               # known a, b returned to client
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    def encrypt(self, flag):
        (a, b), pad_msg = self.pad(flag)
        return (a, b), (pow(pad_msg, self.e, self.N), self.N)

    # get_flag -> {"encrypted_flag": c, "modulus": N, "padding": (a, b)}

Every get_flag call returns c = (a·m + b)^11 mod N together with the known padding (a, b) and the fixed modulus N. The plaintext m (the flag) never changes.

Analysis

This is a textbook Franklin–Reiter related-message attack. Take two queries:

c1 = (a1·m + b1)^e  (mod N)
c2 = (a2·m + b2)^e  (mod N)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Both share the same unknown m. Define over Z_N[x]:

g1(x) = (a1·x + b1)^e − c1
g2(x) = (a2·x + b2)^e − c2

Both polynomials vanish at x = m, so (x − m) divides each. With overwhelming probability the polynomial GCD of g1, g2 over Z_N[x] is exactly the linear polynomial (x − m):

gcd(g1, g2)  =  x − m   (monic)   ⇒   m = −(constant term)

The "linear padding" a·m + b is an affine transform and therefore adds no security against related-message attacks — hence the flag. The only subtlety is doing polynomial arithmetic modulo a composite N: a non-invertible leading coefficient during division would itself factor N (also a win), but here every inversion succeeds and the GCD bottoms out at degree 1. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

Implement polynomial GCD over Z_N[x] (coefficients low→high). Square-and-multiply to build (a·x + b)^11, then Euclidean GCD with monic normalization:

 python read-only • copy allowed Copy
from math import gcd
from Crypto.Util.number import long_to_bytes

def poly_trim(p):
    while len(p) > 1 and p[-1] == 0: p.pop()
    return p
def poly_sub(a, b, N):
    n = max(len(a), len(b))
    return poly_trim([((a[i] if i<len(a) else 0) - (b[i] if i<len(b) else 0)) % N for i in range(n)])
def poly_mul(a, b, N):
    if a==[0] or b==[0]: return [0]
    r=[0]*(len(a)+len(b)-1)
    for i,ai in enumerate(a):
        if ai:
            for j,bj in enumerate(b):
                if bj: r[i+j]=(r[i+j]+ai*bj)%N
    return poly_trim(r)
def inv_modN(x, N):
    x%=N
    if gcd(x,N)!=1: raise ValueError(gcd(x,N))   # a factor of N -> also a win
    return pow(x,-1,N)
def poly_divmod(a, b, N):
    a=poly_trim(list(a)); b=poly_trim(list(b)); db=len(b)-1
    li=inv_modN(b[-1],N); q=[0]
    while len(a)-1>=db and a!=[0]:
        coef=(a[-1]*li)%N; shift=len(a)-1-db
        if shift>=len(q): q+=[0]*(shift-len(q)+1)
        q[shift]=coef
        a=poly_sub(a,[0]*shift+[(coef*bc)%N for bc in b],N)
    return poly_trim(q), poly_trim(a)
def poly_gcd(a, b, N):
    a=poly_trim([c%N for c in a]); b=poly_trim([c%N for c in b])
    while b!=[0]:
        _, r = poly_divmod(a, b, N); a, b = b, r
    li=inv_modN(a[-1],N); return [(c*li)%N for c in a]
def poly_pow_linear(a, b, e, N):       # (a*x + b)^e, low->high
    base=[b%N, a%N]; result=[1]
    while e>0:
        if e&1: result=poly_mul(result, base, N)
        base=poly_mul(base, base, N); e>>=1
    return result
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# two responses (a_i, b_i, c_i) under the same N, e=11
g1 = poly_sub(poly_pow_linear(a1, b1, e, N), [c1], N)
g2 = poly_sub(poly_pow_linear(a2, b2, e, N), [c2], N)
g  = poly_gcd(g1, g2, N)               # -> [ -m, 1 ] (monic x - m)
m  = (-g[0]) % N
print(long_to_bytes(m))

Running it against two get_flag responses recovers m directly.

Takeaways

• Same modulus + same plaintext + small e + known relation between messages ⇒ Franklin–Reiter. Build g_i(x) = (relation_i(x))^e − c_i and take gcd_{Z_N[x]}(g1, g2) = (x − m).
• Affine padding a·m + b is not padding: it's a polynomial relation the attacker fully knows, so it provides zero protection. Only randomized, non-algebraic padding (OAEP) defeats this.
• Polynomial GCD mod a composite N is safe to run blindly: if a leading coefficient is non-invertible, the failed inverse hands you a non-trivial factor of N — another path to the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍