Some Note for UIUCTF2022 Crypto Challenges

wringing_rings

import sympy as sp
import random
import signal
from secret import FLAG

secret = random.SystemRandom().randint(1, 500_000)

_MAX = 10 ** (len(str(secret)) - 1)

# generating a polynomial
def _f(secret, minimum=3):
    coeffs = [secret] + [
        random.SystemRandom().randint(1, _MAX) for _ in range(minimum - 1)
    ]

    # print("Secret Polynomial:")
    # f_str = str(secret)
    # for i, coeff in enumerate(coeffs[1:]):
    #     f_str += " + " + str(coeff) + "*x^" + str(i + 1)
    # print(f_str)

    def f(x):
        res = 0
        for i, coeff in enumerate(coeffs):
            res += coeff * x ** (i)

        return res

    return f

def gen_shares(secret, minimum=3):
    f = _f(secret, minimum)
    shares = [(i + 1, f(i + 1)) for i in range(minimum)]
    return shares


def challenge(secret, minimum=3):
    shares = gen_shares(secret, minimum)
    points = random.sample(shares, minimum - 1)
    points.sort()
    return points


def main():
    minimum = 10
    points = challenge(secret, minimum)

    print("[SSSS] Known shares of the secret polynomial: ")
    for point in points:
        print(f"       {point}")
    print()

    signal.alarm(60)
    guess = int(input("[SSSS] Enter my secret: "))
    if guess == secret:
        print(f"[SSSS] Correct! {FLAG}")
    else:
        print("[SSSS] Incorrect...")

if __name__ == "__main__":
    main()

This is related to Shamir's Secret Sharing(SSS) scheme. But secret polynomial is integer polynomial, not over finite field.

Interpolation of Polynomial

The scheme is based on the fact that univarite polynomial

$f(x)$ whose degree

$d$ is uniquely determined as distinct

$(d+1)$ points

$(x_0,f(x_0)),\dots ,(x_d,f(x_d))$. This fact can be explained as Chinese Remainder Theorem(CRT) over univariate polynomial.

If

$f(x_i)=y_i$, then

$$f(x)=y_i\mathrm{mod}(x-x_i)$$
by polynomial remainder theorem. CRT states that we can recover polynomial

$F(x)$ such that

$$F(x)=y_i\mathrm{mod}(x-x_i)(i=0,1,\dots ,d)$$ uniquely defined over

$$\mathrm{mod}\prod _i(x-x_i).$$

$\mathrm{deg}(F)=d$ (same as

$f(x)$) and

$\mathrm{deg}(\prod _i(x-x_i))=d+1$, we have

$F(x)=f(x)$ by modulus uniqueness.

Lagrange Interpolation represents explicit formula of recovered polynomial.

$$F(x)=\sum _i{y}_i\frac{\prod _{j\ne i}(x-x_j)}{\prod _{j\ne i}(x_i-x_j)}$$

Note that the polynomial may not be over the integer ring

$\mathbb{Z}[x]$, but the rational field

$\mathbb{Q}[x]$. This causes an vulnerablility for integer version of SSS.

My First Solution of the Challenge

In the challenge, we have to find secret whose determined as

$f(0)=\mathbb{secret}$ for degree 9 polynomial

$f(x)$ by given 9 points. At first glance, we cannot recover unique polynomial

$f(x)$ by 9 points only. However, the condition that recovered polynomial is over

$\mathbb{Z}[x]$ is so restrictive.

My solution is straightforward. I recovered polynomial

$f(x)$ by adding symbolical point

$(0,t)$ (

$t$ is variable). Then, I solved the equation for all coefficient of

$f(x)$ is in

$\mathbb{Z}$, that is, the numerator modulo the denominator is

$0$. The solution is

$\mathbb{secret}$.

This leads me the folowing code.

from pwn import *
import cypari2
from Crypto.Util.number import *
from sympy.ntheory.modular import solve_congruence

proc = remote('ring.chal.uiuc.tf', 1337)
proc.recvline()
proc.recvline()

minimum = 10
points = []
for _ in range(minimum-1):
    points.append(eval(proc.recvline().strip(b'\n').split(b"       ")[1]))
print(points)

pari = cypari2.Pari()

result = None
for ele in points:
    if result == None:
        result = pari.Mod(ele[1], (pari('x') - ele[0]))
    else:
        result = pari.chinese(result, pari.Mod(ele[1], (pari('x')-ele[0])))
print(result)
result = pari.chinese(result, pari.Mod(pari('t'), pari('x')))
print(result)

tequ = []
resultpol = result.lift()
for i in range(1, minimum):
    coef = pari.polcoeff(resultpol, i, pari('x'))
    numer = pari.numerator(coef, 1)
    denom = int(pari.denominator(coef, 1))
    tequ.append((-inverse(int(pari.polcoeff(numer, 1, pari('t'))), denom)*int(pari.polcoeff(numer, 0, pari('t'))), denom))
sol = (solve_congruence(*tequ))
print(sol)
sol = sol[0]

print(proc.recvuntil(b': '))
proc.sendline(str(sol).encode())
print(proc.recvline())

(nearly) uniqueness

On CTF, I obtained flag and it works repeatedly, I think that recovered polynomial is unique. @grhkm pointed why it is, I could not explain exactly. But we can understand nearly uniqueness by using CRT construction.

Given 9 points

$(x_0^{\prime },y_0^{\prime }),\dots ,(x_8^{\prime },y_8^{\prime })$, we can recover

$F^{\prime }(x)$ such that

$F^{\prime }(x_i^{\prime })=y_i^{\prime }(i=0,\dots ,8)$.

$F^{\prime }(x)$ is uniquely defined

$\mathrm{mod}\prod _i(x-x_i^{\prime })$. So we have

$$f(x)=F^{\prime }(x)+c(x)\prod _i(x-x_i^{\prime }).$$

$\mathrm{deg}(f)=9$,

$\mathrm{deg}(\prod _i(x-x_i^{\prime }))=9$ and

$\mathrm{deg}(F^{\prime })=8$, so

$\mathrm{deg}(c)=0$, that is,

$c(x)$ is a constant. And

$\prod _i(x-x_i^{\prime })$ is monic, so

$c(x)\in \mathbb{Z}$. Then,

$F^{\prime }(x)\in \mathbb{Z}[x]$. By substituting

$x=0$, we have

$$\mathbb{secret}=F^{\prime }(0)+c\prod _i(-x_i^{\prime }).$$
This means that

$\mathbb{secret}$ is uniquely defined

$\mathrm{mod}\prod _i{x}_i^{\prime }$.

So I did not have to recover symbolic polynomial. I only have to compute

$F^{\prime }(0)\mathrm{mod}\prod _i(-x_i^{\prime })$.

On this challenge,

$\prod _i{x}_i^{\prime }$ is

$10!/a$ for some

$a\in \{1,\dots ,10\}$.
We know

$1<=\mathbb{secret}<=500000$, but

$10!/7=518400>500000$, so my solution is unique if

$a<=7$. Even if

$a=10$,

$10!/10=362880$, then my (smallest) solution is correct with the probability

$362880/500000=0.73$. The overall probability is

>>> sum([min(((10*9*8*7*6*5*4*3*2*1)/i)/500000, 1.0) for i in range(1, 10+1)])/10
0.9439359999999999

Of cource, we can compute

$c$ and check that recovered polynomial is valid (all coefficients except secret is positive and

$<=\mathbf{\_}\mathbf{MAX}$) for reliablity of solution.